最近正好复习一下操作系统，总结一下，以后看也方便一点。

Operating System（一段英文介绍，还没写好，先空着）

chapter 1 导论

计算机系统大致分为4个部分：计算机硬件、操作系统、系统程序与应用程序、用户。（硬件为系统提供基本的计算资源，应用程序规定了用户按何种方式使用这些资源，操作系统控制和协调用户的应用程序对硬件的使用）

从用户视角：使用方便 -> 性能 ->资源利用率 ease of use/ performance/ resource utilization

从系统视角：a resource allocator 、a control program

定义：资源管理、程序控制、方便用户

计算机启动过程

中断：硬件可随时通过系统总线向CPU发出信号触发中断，软件通过执行特别操作（系统调用）触发中断。当CPU中断时，它暂停正在做的事转到中断服务程序开始位置的地址，中断服务程序开始执行，执行完后，CPU重新执行被中断的计算。

存储结构：寄存器 -> 高速缓存 -> 主存 -> 电子磁盘 -> 磁盘 -> 光盘 -> 磁带

I/O结构：查询，中断，DMA

单处理器系统：仅用一个处理器来完成系统操作和目标仿真 。

多处理器系统：增加吞吐量，规模经济，增加可靠性 。非对称多处理（asymmetric multiprocessing）：每个处理器都有各自特定的任务（主从）。对称多处理：每个处理器都要完成操作系统中的所有任务。

集群系统：将多个CPU集中起来完成计算任务。与多处理器系统不同，由两个或多个独立的系统耦合起来。非对称集群/对称集群

集群：多个计算机耦合成单一系统，耦合度较低，消息通信。

多道程序：由多个CPU组成的单一物理试题，共享存储间通信。

多道程序系统：提供了一个可以充分使用各种系统资源的环境。目的是无论何时都有进程在运行，从而使CPU利用率达到最大化。

分时操作系统：允许许多用户同时共享计算机。目的是在进程之间快速切换CPU以便用户在程序运行时能与其进行交互。

双重模式：用户模式，监督程序模式/系统模式/特权模式。提供了保护操作系统和用户程序不受错误用户程序影响的手段。将能引起损害的机器指令作为特权指令。

定时器（timer）：确保操作系统能维持对CPU的控制，也必须防止用户程序陷入死循环或不调用系统服务，并且不将控制权返回到操作系统。

进程管理：进程是系统工作的单元。系统由多个进程组成，操作系统进程/用户进程。

内存管理：内存通常是CPU所能直接寻址和访问的唯一大容量存储器。

存储管理：文件系统管理，大容量存储器管理，高速缓存，I/O系统。

保护和安全：保护是一种控制进程或用户对计算机系统资源的访问的机制。安全主要是防止系统不受外部或内部攻击。

分布式系统：将一组物理上分开来的、各种可能异构的计算机系统通过网络连接在一起，为用户提供系统所维护的各种资源的计算机的集合。

专用系统：实时嵌入系统，多媒体系统，手持系统

计算环境：传统计算，客户机-服务器计算，对等计算，基于Web的计算。

chapter2 操作系统结构

操作系统服务：

用户有用（1）用户界面：命令行界面，批界面。最常用的是图形用户界面。（2）程序执行：系统必须能将程序装入内存并运行程序。（3）I/O操作：为了提高效率和进行保护，用户通常不能直接进行控制I/O设备，因此OS必须提供进行I/O操作的方法。（4）文件系统操作。（5）通信：发生在同一台计算机运行的两个进程之间，运行在由网络连接起来的不同的计算机上的进程之间。实现：共享内存，消息交换。（6）错误检测：OS需要知道可能出现的错误。

系统高效运行（1）资源分配：多个用户/多个作业运行时。（2）统计：记录哪些用户使用了多少和什么资源。（3）保护和安全。

用户界面：（1）命令解释程序：shell，获取并执行用户指定的下一条指令。执行方法：命令解释程序本身包含代码以执行这些命令，由系统程序实现绝大多数命令。（2）图形用户界面：GUI，提供基于鼠标的窗口和菜单系统作为接口。

系统调用：system call，提供了OS提供的有效服务界面。一般使用API。传递参数的三种方法：（1）寄存器，简单。（2）寄存器传递参数块的首地址，参数通常存在内存的块和表中，并将块的地址通过寄存器来传递。（3）参数可通过程序放在或压入堆栈中，并通过OS弹出。

系统调用类型：（1）进程控制。（2）文件管理。（3）设备管理。（4）信息维护。（5）通信，消息传递模型（通信进程通过彼此之间交换消息来交换信息，直接或间接地通过一个共同的邮箱，在通信前必须先打开连接，必须知道另一个通信试题的名称）和共享内存模型（进程使用shared memory create和shared memory attach系统调用来获得其他进程所拥有的内存区域的访问权）。

系统程序：文件管理，状态信息，文件修改，程序语言支持，程序装入和执行，通信。

OS设计目标：首要问题是定义系统的目标和规格，用户目标和系统目标。

机制和策略：机制决定如何做（方法），策略决定做什么（目的）。

OS结构：简单结构，分层（自定向下，每层只能利用较低层的功能和服务），微内核（将所有非基本部分从内核中移走，使客户程序和运行在用户空间的各种服务之间进行通信，利于扩充OS），模块（比分层更灵活，任一模块能调用任何其他模块，不需要调用消息传递来通信）。

虚拟机：在并行运行几个不同的执行环境时能够共享相同的硬件。每个虚拟机完全独立于其他虚拟机，因此没有安全问题，但同时也没有直接资源共享。优点：可通过共享小型磁盘来共享文件，可通过定义一个虚拟机的网络来传递消息。

系统启动：之前1中有个链接。引导程序存储在固件总，OS保存在磁盘上。

并行：多个CPU多个程序；并发：一个CPU多个程序。

chapter3 进程

作业：用户在一次解题或一个事物处理过程中要求计算机系统所做工作的集合。它包括用户程序、所需要的数据及控制命令等。作业是由一系列有序的步骤组成的。

进程：一个程序在一个数据集合上的一次运行过程。

线程：线程是进程中的一个实体，是被系统独立调度和执行的基本单位。

管程：管程实际上是定义了一个数据结构和在该数据结构上的能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。

进程间的通信：信号、信号量、消息队列、共享内存。

进程：包括程序代码/文本段、当前活动，堆栈段、数据段、堆..。程序本身不是进程。程序是被动实体，进程是活动实体。有一个程序计数器用来表示一个要执行的命令和相关资源集合。两个进程可与同一程序相关，但被当做两个独立的执行序列。

进程状态：（1）新的，进程正在被创建。（2）运行，指令正在被执行。（3）等待，进程等待某个时间的发生。（4）就绪，进程等待分配处理器。（5）终止，进程完成执行。一次只有一个进程可在一个处理器上运行，但是多个进程可处于就绪或等待状态。

进程控制块：PCB。进程状态，程序计数器（下个指令的地址），CPU寄存器，CPU调度信息，内存管理信息，记账信息，I/O状态信息。

调度程序：（1）长期调度程序/作业调度程序：从缓冲池中选择进程，并装入内存以准备执行。（2）短期调度程序/CPU调度程序：从准备执行的进程中选择进程，并并为之分配CPU。主要差别为执行的频率，（1）低。

中期调度程序：将进程从内存中移出，从而降低多道程序设计的程度。之后，进程能被重新调入内存，并从中断处继续执行。（交换）

上下文切换：将CPU切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态。PCB

进程创建：进程在其执行过程中，能通过创建进程系统调用创建多个新进程，创建进程称为父进程，而新进程称为子进程。进程标识符PID。

创建新进程时：①父进程与子进程并发执行 ②父进程等待，直到某个或全部子进程执行完。新进程的地址空间：①子进程是父进程的复制品 ②子进程装入另一个新程序。

fork()：子进程返回0，父进程返回子进程PID。exec()。wait()。进程终止：exit()。

进程间通信：（1）共享内存：建立起一块供协作进程共享的内存区域，进程通过向此共享区域读或写入数据来交换信息。速度快。（2）消息传递：通过协作进程间交换消息来实现通信。交换较少数量的数据。易于实现。（直接通信/间接通信，同步(阻塞)/异步(非阻塞)，0缓冲/有限缓冲/无线缓冲）

客户机-服务系统通信：（1）socket：通信的端点。（2）远程过程调用RPC。（3）Java的远程方法调用RMI。

chapter4 线程

线程：CPU使用的基本单元，由线程ID，程序计数器，寄存器集合和栈组成。共享代码段、数据段、其他资源，寄存器和栈不共享。

多线程编程优点：响应度高，资源共享，经济，多处理器体系结构的利用。

多线程模型：（1）多对一，许多用户级线程映射到一个内核线程，一个线程阻塞则整个阻塞，任一时刻只有一个线程能访问内核。（2）一对一，每个用户线程映射到一个内核线程，允许多个线程并行运行在多处理器系统上，一个用户线程就需要创建一个相应的内核线程从而限制了系统所支持的线程数量。（3）多对多，多路复用了许多用户线程到同样数量或更小数据量的内核线程上，可以创建任意多的用户线程，并且相应内核线程能在多处理器系统上并发执行，当一个线程阻塞内核能调度另一个线程来执行。

线程库：为程序员提供创建和管理线程的API。（1）在用户空间提供一个没有内核支持的库，本地函数调用。（2）执行一个由OS直接支持的内核级的库。

（1）fork()之后立即调用exec()，没必要复制所有线程。（2）fork()之后另一进程不调用exec()，另一进程应复制所有线程。

线程取消：在线程完成之前来终止线程的任务。（1）异步取消：一个线程立即终止目标线程。（2）目标线程不断地检查它是否应终止，这允许目标线程有机会以有序方式来终止自己。

信号：用来通知进程某个特定事件已经发生了。（1）信号是由特定事件的发生所产生的。（2）产生的信号要发送到进程。（3）一旦发送，信号必须加以处理。

线程池：在进程开始时创建一定数量的线程，并放入到池中以等待工作。当服务器收到请求时，它会唤醒池中的一个线程，并将要处理的请求传递给它。一旦线程完成了服务，它会返回到池中再等待工作。如果池中没有可用的线程，那么服务器会一直等待知道有空线程为止。优点：①通常用现有线程处理请求要比等待创建新的线程要快。②线程池限制了在任何时候可用线程的数量。

chapter5 CPU调度

进程执行由CPU执行和I/O等待周期组成。进程在这两个状态之间切换。

CPU调度程序：4种环境：①当一个进程从运行状态切换到等待状态。非抢占。②当一个进程从运行状态切换到就绪状态。③当一个进程从等待状态切换到就绪状态。④当一个进程终止时。非抢占。采用非抢占调度，一旦CPU分配给一个进程，那么该进程会一直使用CPU直到进程终止或切换到等待状态。

分派程序：一个模块，用来将CPU的控制交给由短期调度程序选择的进程。功能：切换上下文，切换到用户模式，跳转到用户程序合适位置以重新启动程序。

调度准则：CPU使用率（使CPU尽可能忙），吞吐量（测量工作量），周转时间（从进程提交到进程完成的时间段），等待时间（在就绪队列中等待所花费时间之和），响应时间（从提交请求到产生第一响应的时间）。需要使CPU使用率和吞吐量最大化，而使周转时间、等待时间和响应时间最小化。

调度算法：（1）先到先服务 FCFS，先请求CPU的进程先分配到CPU。FIFO队列。非抢占。（2）最短作业有限调度 SJF，当CPU空闲时，会赋给具有最短CPU区间的进程，同样长度FCFS。平均等待时间最小。用于长期调度。抢占/非抢占。抢占SJF/最短剩余时间优先调度。（3）优先级调度，每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU，具有相同优先级FCFS。抢占/非抢占。无穷阻塞/饥饿，老化（逐渐增加在系统中等待很长时间的进程的优先级）。（4）轮转法调度，专门为分时系统设计，类似FCFS，增加了抢占。时间片（一个较小时间单元），循环队列，FIFO，可抢占。（5）多级队列调度，将就绪队列分成多个独立队列，根据进程的属性，一个进程被永久地分配到一个队列，每个队列有自己的调度算法。队列之间通常采用固定优先级抢占调度/划分时间片。（6）多级反馈队列调度，根据不同CPU区间的特点以区分进程，如果进程使用过多CPU时间，那么它会被转移到更低优先级队列。将I/O约束和交互进程留在更高优先级队列，在较低优先级队列中等待时间过长的进程会被转移到更高优先级队列。（队列0中的1个时间片，未完成放到队列1尾部）。

线程调度：进程竞争范围 PCS，系统竞争范围 SCS。

算法评估：（1）分析评估法。使用给定算法和系统负荷，产生一个公式或数字，以评估对于该负荷算法的性能。（2）确定模型法。采用特殊预先确定的负荷，计算在给定负荷下每个算法的性能。

chapter6 进程同步

临界区问题：critical-section problem，设计一个以便进程协作的协议。进入区：entry section，实现进程请求允许进入临界区的代码。退出区：exit section。剩余区：remainder sction。

解答的三个要求：（1）互斥：mutual exclusion，如果进程Pi在其临界区内执行，那么其他进程都不能在其临界区内执行。（2）前进：progress，如果没有进程在其临界区内执行且有进程需进入临界区，那么只有那些不在剩余区内执行的进程可参加选择，以确定谁能下一个进入临界区，且这种选择不能无限推迟。（3）有限等待：bounded waiting，从一个进程作出进入临界区的请求，直到该请求允许为止，其他进程允许进入其临界区的次数有上限。

典型进程Pi的通用结构：do{进入区 临界区 退出区 剩余区}while(TRUE);

两种方法：（1）抢占内核：preemptive kernel。适合实时编程，响应快。（2）非抢占内湖：nonpreemptive kernel。

Peterson算法：一个经典的基于软件的临界区问题的解答。适用于两个进程在临界区与剩余区间交替执行。（Pi，Pj，j=1-i）共享两个数据项：int turn;表示哪个进程可以进入临界区。boolean flag[2];表示哪个进程想要进入临界区。

锁：通过要求临界区用锁来防护，就可以避免竞争条件。

单处理器：修改共享变量时禁止中断。

多处理器：原子。TestAndSet() & Swap()。

信号量：semaphore，信号量S，整数变量，两个标准原子操作 wait() & signal()。

1
2
3
4
5
6

do{
    waiting(mutex);
    //critical section
    signal(mutex);
    //remainder section
}while(TRUE);

计数信号量：可用来控制访问具有若干个实例的某种资源。

二进制信号量：互斥锁，值为0或1。

忙等待，自旋锁：当一个进程位于其临界区内时，任何其他试图进入其临界区的进程都必须在其进入代码中连续地循环。（解决就是block() & wakeup()，S<0加入队列里阻塞，signal()唤醒）

死锁：deadlocked，两个或多个进程无限地等待一个时间，而该事件只能由这些等待进程之一来产生。

饥饿/无限期阻塞：starvation/indefinite blocing，进程在信号量内无限期等待。

有限缓冲问题：n个缓冲项；信号量mutex互斥，初始化为1；信号量empty，初始化为n；信号量full，初始化为0。

读者-写者问题：要求写者对共享数据库有排他的访问。

哲学家进餐问题：思考和吃饭，一边一只筷子。

管程：monitor，管程结构确保一次只有一个进程能在管程内活动。

原子事务：要么完全执行，要么什么也不做。

事务：transaction，执行单个逻辑功能的一组指令或操作。

提交：committed，已成功完成执行的终止事务。否则，称为撤销aborted。回退 rolled back。

调度：执行顺序。串行调度：每个事务原子地执行的调度。非串行调度：允许两个事务重叠执行。冲突可串行化：如果调度S通过一系列非冲突操作的交换而转换成串行调度S’，则调度S为冲突可串行化的。冲突操作：读写，写读，写写？

加锁协议：（1）共享，可读，不能修改。（2）排他，可读可写。

两端加锁协议：（1）增长阶段，事务可获取锁，但不能释放锁。（2）收缩阶段，事务科释放锁，但不能获取新锁。

时间戳：对于系统内的每个事务Ti，都为之关联一个唯一固定的时间戳，并记为TS(Ti)。

（具体的是在数据库里学的）

chapter7 死锁

死锁：deadlocked，两个或多个进程无限地等待一个时间，而该事件只能由这些等待进程之一来产生。/ 某个进程申请资源，如果这时资源不可用，那么该进程进入等待状态，如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变其状态。

正常操作模式：①申请，如果申请不能立即被允许，那么申请进程必须等待，直到它获得资源为止。②使用，进程对资源进行操作。③释放，进程释放资源。

死锁的必要条件：①互斥。至少有一个资源必须处于非共享模式，即一次只有一个进程使用。如果另一个进程申请该资源，那么申请进程必须等到该原被释放为止。②占有并等待。一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程所占有。③非抢占。资源不能被抢占，即资源只能在进程完成任务后自动释放。④循环等待。有一组等待进程{P0,P1,..,Pn}，P0等待的资源为P1所占有，..，Pn等待的资源为P1所占有。所有4个条件同时满足才会出现死锁。条件并不完全独立。

资源分配图：如果分配图没有环，那么系统就没有进程死锁。如果分配图有环，那么可能存在死锁。如果每个资源类型刚好有一个实例，那么有环就以为这已经出现死锁。如果环涉及一组资源类型，而每个类型只有一个实例，那么就出现死锁。

处理死锁：（1）可使用协议以预防或避免死锁，确保系统不会进入死锁状态。（2）可允许系统进入死锁状态，然后检测它，并加以恢复。（3）可忽视这个问题，认为死锁不可能在系统内发生。

死锁预防：deadlock revention，是一组方法，以确保至少一个必要条件不成立。

死锁避免：deadlock avoidance，要求操作系统事先得到有关进程申请资源和使用资源的额外信息。有了额外信息，系统可确定，对于一个申请，进程是否应等待。

如果不采用死锁预防和避免，系统可提供一个算法来检查系统状态以确定死锁是否发生，并提供另一个算法来从死锁恢复。

死锁预防：（1）互斥。非共享资源要有互斥条件。通常不能通过否定互斥条件来预防死锁，有的资源本身就是非共享的。（2）占有并等待。当一个进程申请一个资源时，它不能占有其他资源。①每个进程在执行前申请并获得所有资源。②允许进程在没有资源时才可申请资源。两种方法资源利用率低，可能发生饥饿。（3）非抢占。如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都可被抢占。（4）循环等待。对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源。（低设备使用率，低系统吞吐率）

死锁避免：获得以后如何申请资源的附加信息。（1）安全状态。如果存在一个安全序列，那么系统处于安全状态。进程顺序<P1,P2,..,Pn>，如果对于每个Pi，Pi仍然可以申请的资源数小于当前可用资源加上所有进程Pj(j<i)所占有的资源，则为安全序列。安全状态不是死锁状态，死锁状态是不安全状态。（2）资源分配图算法。引入需求边，虚线表示。检测环。（3）银行家算法。系统进程个数n，资源类型的种类m，Available[j]=k资源类型Rj现有k个实例，Max ij=k进程Pi最多可申请k个资源类型Rj的实例，Allocation ij=k进程Pi现在已分配了k个资源类型Rj的实例，Need ij=k进程Pi还可能申请k个资源类型Rj的实例。

死锁检测：（1）每种资源类型只有单个实例。等待图，从资源分配图中，删除所有资源类型节点，合并适当边，就可以得到等待图。当且仅当等大图中有一个环，系统中存在死锁。（2）每种资源类型可有多个实例。与银行家算法类似。Available，Allocation，Request。

死锁恢复：（1）进程终止。终止所有死锁进程，一次只终止一个进程直到取消死锁循环为止。（2）资源抢占。（选择一个牺牲品，回滚，饥饿）

chapter8 内存管理

CPU能直接访问的存储器：内存，处理器内的寄存器。

地址绑定：（1）编译时，绝对代码。（2）加载时，可重定位代码。（3）执行时。

逻辑地址：CPU所生成的地址。物理地址：内存单元所看到的地址。

运行时从虚拟地址到物理地址的映射是由被称为内存管理单元MMU的硬件设备来完成的。

进程可以暂时从内存中交换到备份存储上，当需要再次执行时再调回到内存中。一个交换出的进程需要交换回它原来所占有的内存空间。（1）如果绑定是在汇编时或加载时所定的，那么就不可以移动到不同的位置。（2）如果绑定在运行时才确定，由于物理地址是在运行时才确定的，那么进程可以移到不同的地址空间。交换需要备份存储，通常是快速磁盘。

内存映射：重定位寄存器含有最小的物理地址值，界限地址寄存器含有逻辑地址的范围值。

内存分配：分区，最简单，将内存分为多个固定大小的分区，每个分区只能容纳一个进程。

可变分区。操作系统有一个表，用于记录哪些内存可用和哪些内存已被占用。孔hole，一大块可用内存。找足够大的孔，孔内未分配的内存可以下次使用。新进程需要内存时，查找足够大的孔，如果孔太大则分为两块，一块给新进程，另一块还给孔。进程终止时释放内存还给孔集合。如果新孔和其他孔相邻，则合并。选孔：①首次适应，分配第一个足够大的孔。②最佳适应，分配最小的足够大的孔。③最差适应，分配最大的孔。

外部碎片问题，首次适应和最佳适应都有。50%规则，假定有N个可分配块，那么可能有0.5N个块为外部碎片。

内部碎片问题，内存按固定大小分配，在分区内，但不能使用。

解决外部碎片的问题：（1）紧缩，移动内存内容，以便使所有空闲空间合并成一整块。如果重定位是静态的，并且在汇编时或装入时进行的，那么就不能紧缩。（2）允许物理地址空间为非连续。

分页：允许进程的物理地址空间可以是非连续的。基本方法：将物理内存分为固定大小的块（帧）。将逻辑内存分为同样大小的块（页）。由CPU生成的每个地址分为两个部分：页号p和页偏移d。页表包含每页所在物理内存的基地址。采用分页技术不会产生外部碎片，会有内部碎片。

页表的硬件实现：一组专用寄存器，转换表缓冲区TLB。TLB只包括页表的一小部分条目，当CPU产生逻辑地址后，其页号交给TLB，如果找到…，如果不在TLB中，就需要访问页表…。

分页下的内存保护：通过与每个帧相关联的保护胃来实现。一个位定义可读写还是只读。

如果代码是可重入代码，则可以共享。不能自我修改的代码。

层次页表：外页表->页表->内存

哈希页表：以虚拟页码作为哈希值，每个元素三个域，虚拟页码、所映射的帧号、指向链表中下一个元素的指针。虚拟地址中的虚拟页号转换到哈希表中，用虚拟页号与链表中的下一个元素的第一个域相比，如果皮诶，那么相应的帧号就用来形成物理地址，如果不匹配，就对下一个节点进行比较。

反向页表：△

分段：支持用户视角的内存管理方案。逻辑地址空间是由一组段组成的，每个段都有名称和长度，地址指定了段名称和段内偏移。段表：段基地址，段界限。逻辑地址：段号，段内偏移。

chapter9 虚拟内存

虚拟内存：将用户逻辑内存与物理内存分开。

按需调页：在需要时才调入相应的页。懒惰交换：只有在需要页时，才将它调入内存。交换程序对整个进程进行操作，调页程序只对进程的单个页进行操作。

写时复制：如果任何一个进程需要对页进行写操作，那么就创建一个共享页的副本。

基本页置换：如果没有空闲帧，就查找当前没有使用的帧，并将其释放（将其内容写到交换空间，并改变页表以表示该页不在内存中）。①查找所需页在磁盘上的位置。②查找一个空闲帧。a.如果有空闲帧，就使用它。b.如果没有空闲帧，就使用页置换算法以选择一个牺牲帧。c.将牺牲帧的内容写到磁盘上，改变页表和帧表。③将所需页读入空闲帧，改变页表和帧表。④重启用户进程。

可以通过修改位或脏位以降低额外开销。如果修改位没有设置，那么就知道自从磁盘读入后该页没有发生修改，磁盘上页的副本的内容没有必要重写。

FIFO置换：为每个页记录着该页调入内存的时间。当必须置换一页时，将选择最旧的页。

Belady异常：对有的页置换算法，页错误率可能会随着所分配的帧数的增加而增加，而原期望为进程增加内存会改善其性能。

最优置换：置换最长时间不会使用的页。无Belady异常。

LRU算法：最近最少使用，选择最长时间没有使用的页。（计数器，栈）无Belady异常。

近似LRU页置换：引用位，（1）附加引用位，（2）二次机会算法，FIFO，检查引用位，0直接置换，1给第二次机会。（3）增强型二次机会算法，引用位和修改位，(0,0)最近没有使用且没有修改，(0,1)最近没有使用但修改过，(1,0)最近使用过但没被修改，(1,1)最近使用过且被修改过。

基于计数的：最不经常使用，最常使用。

页缓冲：维护一个已修改页的列表，每当调页设备空闲时，就选择一个修改页并写到磁盘上，接着重新设置其修改位；保留一个空闲帧池，但要记住哪些页在哪些帧中。

帧分配：全局置换，允许一个进程从所有帧集合中选择一个置换帧；局部置换，每个进程仅从其自己的分配帧中进行选择。

系统颠簸：thrashing，频繁的页调度。

预调页：同时将所需要的所有页一起调入到内存中。

chapter10 文件系统接口

文件：记录在外存上的相关信息的具有名称的集合。是逻辑外村的最小分配单元。

顺序访问：

直接访问/相对访问：文件由固定长度的逻辑记录组成，以允许程序按任意顺序进行快速读和写。

存储结构：分区（目录，文件）

单层结构目录：所有文件包含在同一目录中，便于理解和支持。必须具有唯一名名称。

双层结构目录：主文件目录，用户文件目录。

树状结构目录：绝对路径名：从根开始并给出路径上目录名直到所指定的文件；相对路径名：从当前目录开始定义路径。禁止共享文件和目录。

无环图目录：允许目录含有共享子目录和文件，同一文件或子目录可出现在两个不同目录中，无环图是树状结构目录方案的扩展。

通用图目录：

chapter11 文件系统实现

应用程序-> 逻辑文件系统-> 文件组织系统-> 基本文件系统-> I/O控制-> 设备

文件组织模块知道文件及其逻辑块和物理块。可以将逻辑块地址转换成基本文件系统所用的物理块地址。

文件系统实现包括三个主要层次：（1）文件系统接口，open() read() write() close()调用以及文件描述符。（2）虚拟文件系统层，VFS：定义一个清晰的VFS接口，以将文件系统的通用操作和具体实现分开。提供了在网络上唯一标识一个文件的机制。（3）实现文件系统类型或远程文件系统协议。

目录实现：（1）线性列表：使用存储文件名和数据块指针的线性列表。（2）哈希表：根据文件名得到一个值，并返回一个纸箱线性列表中元素的指针。

主要磁盘空间分配方法：（1）连续，要求每个文件在磁盘上占有一组连续的块，用于访问连续分配文件所需要的寻道数最小，在确实需要寻道时所需要的寻道时间最小；支持顺序访问和直接访问。（2）链接。解决了连续分配的所有问题，采用链接分配，每个文件是磁盘块的链表，磁盘块分布在磁盘的任何地方。目录包括文件第一块的指针和最后一块的指针。只要有空闲块，文件就可以增大，无需合并磁盘空间。缺点：只能有效地用于文件的顺序访问，指针需要空间（将多个块组成簇，增加内部碎片），可靠性低。文件分配表FAT，每个卷开始部分用于存储FAT。（3）索引。通过把所有指针放在一起，通过索引块解决了这个问题。没有外部碎片问题。

空闲空间管理：（1）位向量（2）链表（3）组（4）计数

效率：取决于所使用的磁盘分配和目录管理算法。

恢复：一致性检查程序，备份和恢复

chapter12 大容量存储器的结构

磁盘：磁头，磁臂，磁道，扇区，柱面。

磁盘速度：传输速率（在驱动器和计算机之间的数据传输速率）+定位时间/随机访问时间（寻道时间(移动磁臂到所要的柱面所需时间)+旋转等待时间(等待所要的扇区旋转到磁臂下所需时间)）

磁头碰撞：虽然磁盘片上涂了一层薄的保护层，但是磁头还是可能损坏磁盘表面。

磁带：主要用于备份，速度慢，存储长久。

现代磁盘驱动器：一个一维的逻辑块的数组，逻辑块是最小的传输单位。按顺序映射到磁盘的扇区，先按磁道内扇区顺序，再按柱面内磁道顺序，最后按从外到内的柱面顺序来排序。

磁盘存储：（1）I/O端口或主机附属存储。（2）分布式文件系统的远程主机/网络附属存储。缺点：存储I/O操作需要使用数据网络的带宽，因此增加了网络通信延迟。

磁盘调度：（1）FCFS，先来先服务。（2）SSTF，最短寻道时间优先，在将磁头一道远处以处理其他请求之前，先处理靠近当前磁头位置的请求。（3）SCAN，电梯算法，磁臂从磁盘的一端向另一端移动，同时当磁头移过每个柱面时，处理位于该柱面上的服务请求。当到达另一端时，磁头改变移动方向，处理继续。（4）C-SCAN，提供一个更为均匀的等待时间，将磁头从磁盘一端移到磁盘的另一端，随着移动不断地处理请求。不过当磁头移到另一端时，它会马上返回到磁盘的开始，返回时不处理请求。（5）LOOK，磁头只移动到一个方向上最远的请求为止。C-LOOK

RAID：

chapter13 I/O输入系统

总线：一组线和一组严格定义的可以描述在线上传输信息的协议。

控制器：用于操作端口、总线或设备的一组电子器件。

轮询，中断，直接内存访问，

缓冲区：用来保存两个设备之间或在设备和应用程序之间所传输数据的内存区域。（速度差异，协调传输数据大小不一致，支持应用程序I/O的复制语义）

假脱机：Spooling，用来保存设备输出的缓冲区。

chapter14 保护

最小特权原则。

访问矩阵