（红色知识点有简答或综合题） :::info 第一章 绪论
1. 操作系统的定义、作用、功能
2. 操作系统的分类
3. 操作系统的基本特征
3. 操作系统的主要功能（处理机，存储器，设备，文件的功能及其主要任务）

第二章 进程 第四章 进程同步
1. 进程的三基本状态及其转换原因
2. 进程的定义与特征及并发时的特点
3. 信号量的定义，值的含义，wait、signal操作，应用（前驱图的伪码描述、生产者-消费者问题的引申问题的解决）
4. 进程同步时的进程间的制约关系
5. 临界资源和临界区，进程同步机制应遵循的准则

第三章 处理机调度
1. 处理机调度的层次（高、中、低，概念）
2. 调度算法（FCFS，SJF）
3. 死锁的定义、产生的原因、必要条件、处理死锁的方法
4. 死锁的避免（银行家算法）

第五、六章 存储器管理
1. 动态分区分配算法（FF,NF,BF,WF,QF,BUDDY）
2. 分页存储中逻辑地址的结构，页表，地址变换
3. 页面置换算法（FIFO,LRU）
4. 抖动的预防

第七章 设备管理
1. I/O控制方式
2. 中断处理程序
3. 与设备无关软件
4. 假脱机系统及缓冲
5. 磁盘调度算法（FCFS,SSTF,SCAN,CSCAN）

第七、八章 文件
1. 文件的打开
2. 目录、文件共享，文件存储空间管理
3. 提高文件访问速度的途径、磁盘高速缓存
3. 索引结构（直接索引和混合索引）的原理 :::

第一章 绪论

1. 操作系统的定义、作用、功能

操作系统的定义
操作系统(Operating System，OS)是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，它是现代计算机系统中最基本和最重要的系统软件，而其它的诸如编译程序、数据库管理系统等系统软件，以及大量的应用软件，都直接依赖于操作系统的支持，取得它所提供的服务。

操作系统的作用
用户与硬件之间的接口

OS 的第一个作用是作为用户与计算机硬件系统之间的接口，从层次上看 OS 处于用户与计算机硬件系统之间，用户在OS帮助下能够方便、快捷、可靠地操纵计算机硬件和运行自己的程序。用户可以通过命令方式、系统调用方式和图标一窗口方式来实现与 OS 的通信，由于应用程序也是基于 OS 运行的，因此用户使用软件也离不开 OS。

资源的管理者

OS 第二个作用是作为计算机系统资源的管理者，因为在一个计算机系统中通常都含有多种硬件和软件资源。归纳起来可将这些资源分为四类：处理机、存储器、I/O设备以及文件(数据和程序)，OS 的主要功能也正是对这四类资源进行有效的管理。

对资源的抽象

一台完全无软件的计算机系统(即裸机)向用户提供的仅是硬件接口(物理接口)，用户想要使用该系统就必须对物理接口的实现细节有充分的了解，这就致使该物理机器难于广泛使用。

为了方便用户使用 I/O设备，人们在裸机上覆盖上一层 I/O 设备管理软件，这样的软件隐藏了 I/O 设备的具体细节，向上提供了一组抽象的 I/O 设备。通常把覆盖了上述软件的机器称为扩充机器或虚机器，它向用户提供了一个对硬件操作的抽象模型。

操作系统的功能
处理器管理
存储管理
文件管理
设备管理
用户接口
网络与通信管理

2. 操作系统的分类

3. 操作系统的基本特征

操作系统具有并发、共享、虚拟和异步四个基本特征。

3.1. 并发

并发执行这一特征使得 OS 能有效地提高系统中的资源利用率，增加系统的吞吐量。并行性是指两个或多个事件在同一时刻发生，而并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。倘若在计算机系统中有多个处理机，这些可以并发执行的程序便可被分配到多个处理机上，从而实现并行执行。
实现并发的关键在于引入了进程，进程是指在系统中能独立运行并作为资源分配的基本单位，它是由一组机器指令、数据和堆栈等组成的，是一个能独立运行的活动实体。若对内存中的多个程序都分别建立一个进程，它们就可以并发执行。

3.2. 共享

OS 环境下的资源共享(资源复用)是指：系统中的资源可供内存中多个并发执行的进程共同使用，这里在宏观上既限定了时间(进程在内存期间)，也限定了地点(内存)。因为系统中的资源远少于多道程序需求的总和，会形成它们对共享资源的争夺，系统必须对资源共享进行妥善管理。由于资源属性的不同，进程对资源复用的方式也不同，目前主要实现资源共享的方式有如下两种：

并发和共享是多用户（多任务）OS 的两个最基本的特征，它们又是互为存在的条件。若系统不允许并发执行也就不存在资源共享问题，若系统不能对资源共享实施有效管理也必然会影响到诸进程间并发执行的程度。

3.3. 虚拟

在 OS 中把通过某种技术将一个物理实体变为若干个逻辑上的对应物的功能称为虚拟，这是通过时分复用和空分复用实现的。时分复用技术能实现虚拟处理机、虚拟设备等，使资源的利用率得以提高。这是因为它利用某设备为一用户服务的空闲时间，又转去为其他用户服务，使设备得到最充分的利用。主要包括：

空分复用技术则是利用存储器的空闲空间分区域存放和运行其它的多道程序，以此来提高内存的利用率。单纯的空分复用存储器只能提高内存的利用率，并不能实现在逻辑上扩大存储器容量的功能，还必须引入虚拟存储技术才能达到此目的。

3.4. 异步

在单处理机环境下，一台处理机每次只允许一个进程执行，其余进程只能等待。由于资源等因素的限制，使进程的执行通常都不可能“一气呵成”，而是以“停停走走”的方式运行。只有系统具有并发性，才有可能导致异步性。

3. 操作系统的主要功能（处理机，存储器，设备，文件的功能及其主要任务）

3.1. 处理机管理功能

在传统的多道程序系统中，处理机的分配和运行都是以进程为基本单位的，因而对处理机的管理可归结为对进程的管理。处理机管理的主要任务是对处理机的分配和运行进行管理，它的主要功能有：

3.2. 存储器管理功能

存储器管理的主要任务是为多道程序的运行提供良好的环境，提高存储器的利用率，方便用户使用并能从逻辑上扩充内存。

实现内存分配主要有两种方式，它们分别是：

对于扩充内存来说，系统具体需要实现：

1. 请求调入功能：若发现要继续运行时所需的程序和数据尚未装入内存，OS 可以从磁盘中将所需部分调入内存；
2. 置换功能：若发现在内存中已无足够的空间来装入需要调入的程序和数据时，系统应能将内存中的一部分暂时不用的程序和数据调至硬盘上。

   3.3. 设备管理功能

   设备管理需要完成用户进程提出的 I/O 请求，为用户进程分配所需的 I/O 设备，同时要提高 CPU 和 I/O 设备的利用率。

3.4. 文件管理

文件管理的主要任务是对用户文件和系统文件进行管理以方便用户使用，并保证文件的安全性。

其中文件保护需要实现以下 3 个目标：

1. 防止未经核准的用户存取文件；
2. 防止冒名顶替存取文件；
3. 防止以不正确的方式使用文件。

第二章 进程 第四章 进程同步

1. 进程的三基本状态及其转换原因

由于多个进程在并发执行时呈现间断性的运行规律，所以进程在其生命周期内可能具有多种状态。

其中对于进程的创建，首先要申请一个空白 PCB 并填写用于控制和管理进程的信息，然后为该进程分配运行时所必须的资源，最后把该进程转入就绪状态并插入就绪队列之中。如果进程创建工作尚未完成，进程不能被调度运行时，该进程就属于创建状态。进程各状态的转换关系如下：

2. 进程的定义与特征及并发时的特点

为了使参与并发执行的每个程序(含数据)都能独立地运行，操作系统中为之配置一个专门的数据结构——进程控制块(Process Control Block，PCB)用来描述进程的基本情况和活动过程。由程序段、相关的数据段和 PCB 三部分便构成了进程实体（又称进程映像)，一般情况下把进程实体就简称为进程。
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。引入了“进程”的概念能使程序并发执行，并且可以对并发执行的程序加以描述和控制。进程具有的一些特性如下：

1. 动态性：进程的实质是进程实体的执行过程；
2. 并发性：多个进程实体同存于内存中，且能在一段时间内同时运行；
3. 独立性：进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位；
4. 异步性：进程是按各自独立的、不可预知的速度向前推进；
5. 结构性：每个进程都需要配置一个名为 PCB 的数据结构。

并发执行
观察上面的图，执行一次计算操作需要借助 3 类资源：输入设备、CPU 和输出设备，注意当 C1 被执行的时候输入设备是空闲的。如果在执行 C1 时让输入设备执行 I2，这样当 C1 执行完毕后就可以继续执行 C2。以此类推可以发现这么做可以有效利用资源，提高系统的运行效率，这就是程序的并发执行。

程序并发执行虽然提高了系统的吞吐量和资源利用率，但由于它们共享系统资源，致使在这些并发执行的程序之间必将形成相互制约的关系。例如当计算程序完成 C1 的计算后，如果输入程序 I1 尚未完成，则计算程序 C2 就无法进行计算。同时程序在并发执行时失去了封闭性，也将导致其又失去可再现性。
（1）间断性
（2）失去封闭性
（3）不可再现性

3. 信号量的定义，值的含义，wait、signal操作，应用（前驱图的伪码描述、生产者-消费者问题的引申问题的解决）

信号量就是用一个变量来表示系统中某种资源的数量，可以利用这种机制来实现同步。

整型信号量

整型信号量定义为一个用于表示资源数目的整型量 S，S 除了初始化外仅能通过两个标准的原子操作 wait(S) 和 signal(S)来访问，这两个操作也可以被称为 P、V 操作。wait 操作的伪代码如下：

wait(S){
    while(S<=0);
    S--;
}

signal 操作的伪代码如下：

signal(S){
    S++;
}

当一个进程在修改某信号量时，由于 P、v 操作是原子操作，因此没有其它进程可同时对该信号量进行修改。

记录型信号量

当整型信号量 s≤0 时就会不断地测试直到它大于 0，因此该机制并未遵循“让权等待”的准则。但是采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。因此除了需要一个用于代表资源数目的整型变量 value，还应增加一个进程链表指针 list 用于链接的所有等待进程，这类信号量称之为记录型信号量。

typedef struct{
    int value;
    struct process_control_block *list;
}semaphore;

将原本的整型变量修改为上述结构体定义的变量后，wait(S) 操作使系统中可供分配的该类资源数减少一个，表示进程请求一个单位的资源，伪代码如下：

wait(semaphore *S){
    S->value--;
    if(S->value < 0)
        block(S->list)；
}

signal(S) 操作使可分配的资源增加一个，表示进程释放一个单位的资源，伪代码如下：

signal(semaphore *S) {
    S->value++;
    if(S->value <= 0)
        wakeup(S->list)；
}

AND 型信号量

如果一个进程需要多个临界资源才能进行工作，在只获得部分资源时会导致工作无法展开且占用着资源无法释放的情况。AND 型信号量的基本思想是一次性分配进程在整个运行过程中需要的所有资源，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。
wait 操作就需要加入 AND 的条件对多个资源进行判断，伪代码如下：

wait(S1,S2,...,Sn){
    while(TRUE)
        if(Si >= 1 &&...&& Sn >= 1){
            for(int i = 1; i <= n; i++)
                Si--;
            break;
        }
        else {
            进程加入等待队列
        }
    }
}

相应的 signal 操作需要释放进程占用的所有资源，伪代码如下：

Ssignal(S1,S2,..., Sn) {
    while(TRUE){
        for(int i = 1; i <= n; i++){
            Si++;
            将等待该资源的进程移入就绪队列
        }
    }
}

信号量集

前面的记录型信号量机制中，wait(S) 或 signal(S) 操作仅能对某类临界资源进行一个单位的申请或释放。当一次需要 N 个单位时要进行 N 次操作，不仅效率低，还可能出现获得部分资源导致工作无法展开且占用着资源无法释放的情况。在有些情况下，当所申请的资源数量低于某一下限值时要进行管制，不分配该类资源来保证安全性。因此在分配临界之前，都必须测试资源的数量，判断是否大于可分配的下限值。
因此可以提出信号量集，也就是进程对信号量 S 的测试值可以从 1 改成资源的分配下限值 t，当 S ≥ t 时才能进行资源分配。进程对该资源的需求值为 d，分配资源时进行 S = S - d 一次分配多个资源。对应的 Swait 和 Ssignal 格式为：

Swait(S1, t1, d1,..., Sn, tn, dn);
Ssignal(S1, d1,..., Sn, dn);

信号量的应用

实现进程互斥

为该临界资源设置一个初始值为 1 的互斥信号量 mutex，然后将各进程访问该资源的临界区置于 wait(mutex) 和 signal(mutex)。这样每个欲访问该临界资源的进程在进入临界区之前，都要先执行 wait 操作判断资源是否可用，临界区运行完毕后需要用 signal 操作释放资源。

semaphore mutex=1;
PA(){
    其他代码
    wait(mutex);
    临界区
    signal(mutex);
    剩余区
}
PB(){
    其他代码
    wait(mutex);
    临界区
    signal(mutex);
    剩余区
}

实现前趋关系

设有两个并发执行的进程 P1 和 P2 分别有语句 S1 和 S2，希望在 S1 执行后再执行 S2。如果进程之间必须保证执行的顺序是一前一后的，可以设置一个初始值为 0 的同步信号量 S，然后在前操作之后执行 signal(s)，在后操作之前执行 wait(s)。前操作执行完之后 s 的会加一，此时后操作调用 wait 满足了条件即可开始执行。

semaphore s = 0;
PA(){
    S1
    signal(s);
}
PB(){
    wait(s);
    S2
}

应用（前驱图的伪码描述、生产者-消费者问题的引申问题的解决）

生产者-消费者问题

问题描述

生产者-消费者(producer-consumer)问题是有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。在两者之间设置了一个具有 n 个缓冲区的缓冲池，生产者进程将其所生产的产品放入一个缓冲区中，消费者进程可从一个缓冲区中取走产品去消费。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。缓冲区是临界资源，各进程必须互斥地访问。

可以利用一个数组 buffer 来表示具有 n 个缓冲区的缓冲池，每投入或取出一个产品时，缓冲池 buffer 中暂存产品或或被取走产品的数组单元指针 in 或 out 需要移动，这些用代码描述如下。

int in  = 0;    //输入指针
int out = 0;    //输出指针
item buffer[n];    //缓冲区

由于 buffer 描述的缓冲池是循环队列结构，因此输入指针 in 或输出指针 out 表示成“in = (in + 1) % n” 和 “out = (out + 1) % n”，当 (in + 1) % n = out 时表示缓冲池满，in = out 则表示缓冲池空。

记录型信号量解法

可利用互斥信号 mutex 实现诸进程对缓冲池的互斥使用，利用信号量 empty 和 full 分别表示缓冲池中空缓区和满缓冲区的数量。

semaphore mutex = 1;    //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;    //同步信号量，表示空闲缓冲区的数量
semaphore full  = 0;    //同步信号量，表示非空缓冲区的数量

又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者可将消息送入缓冲池。只要缓冲池未空，消费者便可从缓冲池中取走一个消息。应注意每个程序中用于实现互斥的 wait(mutex) 和 signal(mutex) 必须成对地出现，其次对资源信号量 empty 和 full 的 wait 和 signal 操作。
对生产者而言，可以用代码描述如下：

void proceducer(){
    do{
        producer an item nextp;    //生产一个产品
        wait(empty);    //消耗一个空闲缓冲区
        /*实现互斥*/
        wait(mutex);
        buffer[in] = nextp;    //产品放入缓冲区
        in = (in + 1) % n;    //移动输入指针
        signal(mutex);
        /*实现互斥*/
        signal(full);
    }while(TRUE)；
}

对消费者而言，可以用代码描述如下：

void consumer(){
    do{
        wait(full);    //消耗一个产品
        /*实现互斥*/
        wait(mutex);
        nextc = buffer[out];    //产品拿出缓冲区
        out = (out + 1) % n;    //移动输出指针
        signal(mutex);
        /*实现互斥*/
        signal(empty);    //增加一个空闲缓冲区
        consumer the item in nextc;    //使用产品
    }while(TRUE)；
}

整个生产消费者问题的流程，用代码描述如下：

void main() {
    cobegin
        proceducer(); 
        consumer();
    coend
}

AND 信号量解法

利用 AND 信号量来解决时，用 Swait(empty，mutex) 来代替 wait(empty) 和 wait(mutex)，用 Ssignal(mutex, full) 来代替 signal(mutex) 和 signal(full)。用 Swait(full，mutex) 代替 wait(full) 和 wait(mutex)，以及用 Ssignal(mutex，empty) 代替 Signal(mutex) 和 Signal(empty)。利用 AND 信号量来解决生产者-消费者问题的代码描述如下：

int in  = 0;    //输入指针
int out = 0;    //输出指针
item buffer[n];    //缓冲区
semaphore mutex = 1;    //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;    //同步信号量，表示空闲缓冲区的数量
semaphore full  = 0;    //同步信号量，表示非空缓冲区的数量
void proceducer(){
    do{
        producer an item nextp;
        Swait(empty, mutex);
        buffer[in] = nextp;
        in = (in + 1) % n;
        Ssignal(mutex, full);
    }while(TRUE)；
}
void consumer(){
    do{
        Swait(full, mutex);
        nextc= buffer[out];
        out = (out + 1) % n;
        Ssignal(mutex, empty);
        consumer the item in nextc;
    }while(TRUE);
}
void main() {
    cobegin
        proceducer(); 
        consumer();
    coend
}

管程解法

利用管程来解决生产者-消费者问题时，首先便是为它们建立一个管程，并命名为 procducerconsumer(PC)。用整型变量 count 来表示在缓冲池中已有的产品数目，其中包括两个过程：

对于条件变量 notfull 和 notempty，分别有两个过程 cwait 和 csignal 对它们进行操作：

PC 管程可描述如下：

Monitor procducerconsumer {
    int in  = 0;    //输入指针
    int out = 0;    //输出指针
    item buffer[n];    //缓冲区
    condition notfull, notempty;    //条件变量
    int count = 0;    //缓冲池中已有的产品数目
    public void put(item x){
        if(count >= N)    //缓冲池已满
        {
            cwait(notfull)；    //生产者等待
        }
        buffer[in] = x;
        in = (in + 1) % N;
        count++;
        csignal(notempty);
    }
    public void get(item x){
        if (count<= 0)    //缓冲池没有可用的产品
        {
            cwait(notempty)；    //消费者等待
        }
        x = buffer[out];
        out =(out+1) % N;
        count--;
        csignal(notfull);
   }
}PC;

在利用管程解决生产者-消费者问题时，可用代码描述为：

void producer(){
    item x;
    while(TRUE){
        produce an item in nextp;
        PC.put(x)；
    }
}
void consumer(){
    item x;
    while(TRUE){
        PC.get(x);
        consume the item in nextc;
    }
}
void main() {
    cobegin
        proceducer(); 
        consumer();
    coend
}

哲学家进餐问题

问题描述

一张圆桌上坐着 5 名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家只做思考和进餐两件事情，哲学家在思考时不影响他人，只有当哲学家饥饿时才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上则需等待，饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

解法

经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。

semaphore chopstick[5] = {1,1,1,1,1};

所有信号量均被初始化为 1，当哲学家饥饿时总是先去拿他左边的筷子，成功后再去拿他右边的筷子便可进餐。进餐完毕时先放下他左边的筷子，然后再放他右边的筷子。

do{
    wait(chopstick[i]);              //拿起左边的筷子
    wait(chopstick[(i + 1) % 5]);    //拿起右边的筷子
    eat
    signal(chopstick[i]);              //放下左边的筷子
    signal(chopstick[(i + 1) % 5]);    //放下右边的筷子
    think
}while(TRUE);

除了利用记录型信号量，也可以使用 AND 型信号量来解决，这样的写法更为简洁。

do{
    Sswait(chopstick[(i + 1) % 5], chopstick[i]);    //拿起筷子
    eat
    Ssignal(chopstick[(i+1)%5],chopstick[i]);    //放下筷子
    think
}while(TRUE);

可能的死锁

假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量 chopstick 均为 0，当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这样的死锁问题，可采取以下几种解决方法：

1. 至多允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子；
2. 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。

3. 奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定将是 1、2 号哲学家竞争 1 号筷子，3、4 号哲学家竞争 3 号筷子。即五位哲学家都先竞争奇数号筷子，获得后再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。

   读者-写者问题

   问题描述

   有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用。但若某个 Writer 进程和其他进程(Reader 进程或 Writer 进程）同时访问共享数据时，则可能导致数据不一致的错误。因此要求：

4. 允许多个 Reader 可以同时对文件执行读操作；

5. 只允许一个 Writer 往文件中写信息；
6. 任一 Writer 在完成写操作之前不允许其他 Reader 或 Writer 工作；
7. Writer 执行写操作前，应让已有的 Reader 者和 Writer 全部退出。

记录型信号量解法

为实现 Reader 与 Writer 进程间在读或写时的互斥，设置一个互斥信号量 Wmutex，再设置一个整型变量 Readcount 表示正在读的进程数目。又因为 Readcount 是一个可被多个 Reader 进程访问的临界资源，因此也应该为它设置一个互斥信号量 rmutex。

semaphore rmutex = 1;    //用于保证对 count 变量的互斥访问
semaphore wmutex = 1;    //用于实现对文件的互斥访问，表示当前是否有进程在访问共享文件
int readcount = 0;    //记录当前有几个读进程在访问文件

对 reader 而言，可以用代码描述如下：

void reader(){
    do{
        wait(rmutex)；    //reader 进程互斥访问 readcount
        if(readcount == 0)    //第一个 reader 进程开始读
        {
            wait(wmutex)；    //给共享文件“加锁”
        }
        readcount++;    //访问文件的 reader 进程数加 1
        signal(rmutex);
        perform read operation;    //读文件
        wait(rmutex)；    //各个 reader 进程互斥访问 readcount
        readcount--;    //访问文件的 reader 进程数减 1
        if(readcount == 0)
        {
            signal(wmutex);    //最后一个 reader 进程“解锁”
        }
        signal(rmutex);
    }while(TRUE);
}

对 Writer 而言，可以用代码描述如下：

void writer()
{
    do{
        wait(wmutex);    //写之前“加锁”
        perform write operation;
        signal(wmutex);    //写之后“解锁”
    }while(TRUE);
}

对于整个读者-写者问题过程，可以用代码描述如下：

void main() {
    cobegin
        reader();
        writer();
    coend
}

信号量集机制解法

此时读者一写者问题引入一个限制，最多只允许 RN 个读者同时读，为此又引入了一个信号量 L，并赋予其初值为 RN。通过执行 wait(L, 1, 1) 操作来控制读者的数目，每当有一个读者进入时，就要先执行 wait(L，1，1) 操作，使 L 的值减 1。当有 RN 个读者进入读后，L 便减为 0，第 RN + 1 个读者要进入读时，必然会因 wait(L，1，1) 操作失败而阻塞。

int RN;    //最多允许同时读取文件的 reader 进程数
semaphore L = RN；    //保证最多只有 RN 个 reader 进程同时读
semaphore mx = 1;    //标志是否有 writer 进程在操作文件 
void reader(){
    do{
        Swait(L, 1, 1);    //增加一个 reader 进程读文件
        Swait(mx, 1, 0);    //无 writer 进程写文件
        perform read operation;
        Ssignal(L, 1);    //减少一个正在读文件的 reader 进程
    }while(TRUE)；
}
void writer(){
    do{
        Swait(mx, 1, 1; L, RN, 0)    //无 reader 或 writer 进程在操作，“加锁”
        perform write operation;
        Ssignal(mx, 1);    //writer 进程“解锁”
    }while(TRUE);
}
void main(){
    cobegin
        reader();
        writer();
    coend
}

吸烟者问题

问题描述

假设一个系统有三个抽烟者进程和一个供应者进程，每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟需要有三种材料：烟草、纸和胶水。三个抽烟者中第一个拥有烟草，第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复。

解法

从事件的角度来分析，吸烟者问题有 4 个同步关系，分别是桌上有组合一时第一个抽烟者取走东西，桌上有组合二时第二个抽烟者取走东西，桌上有组合三时第三个抽烟者取走东西，最后是吸烟者发出完成信号，供应者将下一个组合放到桌上。因此需要设置 4 个信号量，来分别对应 4 个同步关系。

semaphore offerl = 0;    //桌上组合一的数量
semaphore offer2 = 0;    //桌上组合二的数量
semaphore offer3 = 0;    //桌上组合三的数量
semaphore finish = 0;    //抽烟是否完成
int i = 0;    //正在吸烟的吸烟者序号

对于材料提供者而言，可以用代码描述如下：

void provider(){
    while(1){
        if(i == 0){
            将组合一放桌上；
            wait(offer1);
        } 
        else if(i == l){
            将组合二放桌上；
            wait(offer2);
        } 
        else if(i == 2){
            将组合三放桌上；
            wait(offer3);
        }
        i = (i + 1) % 3;
        signal(finish);
    }
}

对于 3 位吸烟者，可以用代码描述如下：

void smoker1(){
    while(1){
        signal(offer1);
        从桌上拿走组合一，卷烟抽；
        wait(finish);
    }
}
void smoker2(){
    while(1){
        signal(offer2);
        从桌上拿走组合二，卷烟抽；
        wait(finish);
    }
}
void smoker3(){
    while(1){
        signal(offer3);
        从桌上拿走组合三，卷烟抽；
        wait(finish);
    }
}

4. 进程同步时的进程间的制约关系

进程之间可能存在着以下两种形式的制约关系，由于进程的异步性，如果缺乏进程同步会产生对共享变量或数据结构等资源不正确的访问次序，从而造成进程每次执行结果的不一致。

5. 临界资源和临界区，进程同步机制应遵循的准则

临界资源

互斥访问

进程共享各种资源，然而有很多资源一次只能供一个进程使用。一次仅允许一个进程使用的资源称为临界资源，如输入机、打印机、磁带机等许多物理设备都属于临界资源。访问这样的临界资源就需要通过互斥共享方式，在一段时间内只允许一个进程访问该资源。

临界区

每个进程中访问临界资源的代码称为临界区(critical section)，实现进程对临界资源的互斥访问可以转变为进程互斥地进入临界区。每个进程在进入临界区之前，需要先对临界资源进行检查。如果此刻临界资源未被访问就允许临界区的访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区；进程访问完临界资源后需要归还，并且要去掉被访问的标志。
因此需要在临界区前面增加一段用于检查的进入区(entry section)代码，在后面也要加上一段退出区(exit section)的代码，其它部分的代码称为剩余区。访问临界资源的循环进程可以用伪代码描述：

while(TURE)
{
    进入区
    临界区
    退出区
    剩余区
}

进程同步准则

实现进程互斥地进入自己的临界区而采用的同步机制应遵循以下原则：

第三章 处理机调度

1. 处理机调度的层次（高、中、低，概念）

一个作业从提交到获得处理机执行，直至作业运行完毕，可能需要经历多级处理机调度。
高级调度(High Level Scheduling)又称长程调度或作业调度，调度对象是作业，方向是从外存到内存。主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。放入就绪队列意味着作业获取竞争 CPU 的权利，调入时建立相对的 PCB，调出时撤销 PCB。
作业调度的频率较低，一般是几分钟发生一次，进行作业调度时调度程序必须决定操作系统可以接纳多少个作业。每次接纳的作业数量取决于多道程序的并发程度，当同时运行的作业太多时可能会影响操作系统的处理效率，当同时运行的作业太少时，又会导致系统资源利用率低下。
中级调度(Intermediate Scheduling)又称为内存调度，方向是从外存到内存，引入的目的是为了提高内存利用率和系统的吞吐量。主要功能是把那些暂时不能运行的进程挂起，调至外存等待。当它们已具备运行条件且内存又稍有空闲时，通过某种算法将进程再重新调入内存，并修改其状态为就绪状态。
低级调度(Low Level Scheduling)又称为进程调度或短程调度，调度的对象是进程(内核级线程)，方向是从内存到 CPU。主要功能是根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。
进程调度的运行频率很高，一般每隔几秒钟就要发生一次。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的 OS 中，都必须配置这级调度。

2. 调度算法（FCFS，SJF）

先来先服务

先来先服务(first-come first-served，FCFS)调度算法是最简单的调度算法，可用于作业调度和进程调度。作业调度时，系统将按照作业到达的先后次序来进行调度，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存并分配资源和创建进程，放入就绪队列。进程调度时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机运行。
FCFS 算法是从公平角度考虑的非抢占式算法，不会导致饥饿，虽然在单处理机系统中已很少作为主调度算法，但经常把它与其它调度算法相结合使用。

短作业优先

在实际情况中，短作业(进程)占有很大比例，而长进程的存在可能会导致大量短进程无法即使执行。短作业优先(short job first，SJF)的调度算法以作业的长短来计算优先级，作业运行时间越短其优先级越高，SJF 算法可以用于作业调度和进程调度。
SJF 调度算法对于 FCFS 算法有明显的改进，但仍然存在一些缺点。SJF 算法必须预知作业的运行时间，但是往往很难准确估计作业的运行时间。SJF 算法会使长作业的周转时间会明显地增长，甚至可能出现饥饿现象。同时 SJF 算法完全未考虑作业的紧迫程度，不能保证紧迫性作业被及时处理。

3. 死锁的定义、产生的原因、必要条件、处理死锁的方法

死锁的定义
死锁的定义是如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的(Deadlock)。

死锁出现的场合（产生的原因）

死锁通常是源于多个进程对资源的争夺，对不可抢占资源或对可消耗资源进行争夺时都可能引起死锁。

竞争不可抢占性资源引起死锁

例如系统中有 2 个临界资源 R1 和 R2，两个进程 P1 和 P2 的运行都需要 R1 和 R2 资源。如果进程 P1 或者 P2 中有个进程执行得比较快，在另一个进程开始之前就完成了工作并且归还资源，就不会产生死锁。 但是若进程 P1 先获得资源 R1，进程 P2 先获得资源 R2。后来 P1 又请求资源 R2，但是 R2 已被分配给了 P2 而导致 P1 阻塞。P2 又请求资源 R1，但是 R1 已被分配给了 P1 而导致 P2 阻塞。此时两个进程都被阻塞，同时它们都希望对方能释放出自己所需要的资源，最终谁都因不能获得自己所需的资源去继续运行，也无法释放出自己占有的资源陷入僵持状态。

竞争可消耗资源引起死锁

例如系统中有 P1、P2、P3 三个进程使用消息通信机制进行通信，m1、m2 和 m3 是发送的消息，属于可消耗资源。3 个进程的通信方式是 P1 产生 m1 发送给 P2，P2 产生 m2 发送给 P3，P3 产生 m3 发送给 P1 形成一个环。然后它们继续将信息发送给下一个进程，也就是 P1 产生 m3 发送给 P2，P2 产生 m1 发送给 P3，P3 产生 m2 发送给 P1。 此时由于 P1、P2、P3 三个进程都是先发送消息，再接受其他进程发给自己的消息。但是如果 3 个进程先执行接收操作，由于此时没有进程发送消息，3 个进程会不断等待其他进程发消息，同时自己因为没有收到消息也无法向其他进程发消息。

进程推进顺序不当引起死锁

进程在运行过程中，如果对资源进行申请和释放的顺序不合法也可能导致死锁。例如系统中有 2 个临界资源 R1 和 R2，两个进程 P1 和 P2 的运行都需要 R1 和 R2 资源。若进程 P1 先获得资源 R1，进程 P2 先获得资源 R2，2 个进程使用完资源后马上释放。后来 P1 又请求资源 R2，P2 又请求资源 R1，此时由于资源有正确释放所以不会引起死锁。 如果 2 个进没有及时释放资源，而是执行完之后统一释放就会发生进程死锁，这样的进程推进顺序就是非法的。

死锁的条件

处理方法
处理死锁的方法可归结为四种，四种方法对死锁的防范程度逐渐减弱，但资源利用率和并发程度逐渐加强。

4. 死锁的避免（银行家算法）

第五、六章 存储器管理

1. 动态分区分配算法（FF,NF,BF,WF,QF,BUDDY）

首次适应算法

首次适应(first fit，FF)算法要求空闲分区链以地址递增的次序链接，在分配内存时从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配失败。

该算法倾向于优先利用内存中低址部分的空闲分区，保留了高址部分的大空闲区。缺点是低址部分不断被划分，会留下许多难以利用的外部碎片。而每次查找又都是从低址部分开始的，会导致搜索的时间开销较大。

循环首次适应算法

为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，可以使用循环首次适应算法。循环首次适应(next fit，NF)算法在为进程分配内存空间时，是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区。实现该算法一般会使用循环链表，如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区。

算法能使内存中的空闲分区分布得更均匀，减少了查找空闲分区时的开销。但这样会导致高地址的大分区可能被划分为小分区来使用，使缺乏大的空闲分区给较大的进程。

最佳适应算法

最佳适应(best fit，BF)算法在每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业。该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链，这样第一次找到的能满足要求的空闲区必然是最佳的。

由于每次分配后所切割下来的剩余部分总是最小的，所以在存储器中会留下许多难以利用的碎片。

最坏适应算法

最坏适应(worst fit，WF)算法在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用。该算法要求将所有的空闲分区，按其容量以从大到小的顺序形成空闲分区链。

这个算法会使存储器中缺乏大的空闲分区，它的优点是可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利。同时最坏适应分配算法查找效率很高，查找时只要看第一个分区能否满足作业要求即可。

快速适应算法

快速适应(quick fit)算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。同时在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。该算法在搜索时先根据进程的长度，从索引表中去寻找到能容纳它的最小空闲区链表，然后从链表中取下第一块进行分配即可。

该算法在进行空闲分区分配时不会对任何分区产生分割，所以能保留大的分区，也不会产生内存碎片。优点是查找效率高，主要缺点在于分区归还主存时的算法复杂，系统开销较大。此外该算法在分配空闲分区时是以进程为单位的，一个分区只属于一个进程，因此会存在内部碎片。

伙伴系统

伙伴系统(buddy system)算法规定无论已分配分区或空闲分区，其大小均为 2 的 k 次幂(k 为整数，1 ≤ k ≤ m)。将这些空闲分区按分区的大小进行分类，对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。

当需要为进程分配一个长度为 n 的存储空间时，首先计算一个 i (2^i-1 < n ≤ 2^i)，然后在空闲分区大小为 2^i 的空闲分区链表中查找。若找到即把该空闲分区分配给进程。如果找不到表明长度为 2^i 的空闲分区已经耗尽，则在分区大小为 2^i+1 的空闲分区链表中寻找。若存在 2^i+1 的一个空闲分区，则把该空闲分区分为相等的两个分区，其中的一个分区用于分配，而把另一个加入分区大小为 2^i 的空闲分区链表中。如果还是找不到就继续搜索，以此类推。
在伙伴系统中，对于一个大小为 2^k，地址为 x 的内存块，其伙伴块的地址则用 buddyk(x)表示，其通式为：

在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比快速适应算法差.但由于它采用了索引搜索算法，比顺序搜索算法好。由于对空闲分区进行合并，减少了小的空闲分区，提高了空闲分区的可使用率，故优于快速适应算法，比顺序搜索法略差。

2. 分页存储中逻辑地址的结构，页表，地址变换

分页存储的结构

分页存储管理将进程的逻辑地址空间分成若干个页面，并为各页加以编号。相应地也把内存的物理地址空间分成若干个物理块，同样也加以编号。在为进程分配内存时，以块为单位，将进程中的若干个页分别装入到多个可以不相邻接的物理块中。若页面大小设置得较小，可以减小内存碎片并提高内存利用率，但会造成每个进程占用较多的页面，从而导致进程的页表过长、占用大量内存和降低页面换进换出的效率。如果选择的页面过大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此页面的大小应选择适中，且页面大小应是 2 的幂，通常为 1KB～8KB。
分页地址中的地址长度为 32 位，地址结构包含两部分内容。前一部分为页号 P，占在 12 ~ 31 位，地址空间最多允许有 1M 页。后一部分为位(偏)移量 W(页内地址)，占在 0 ~ 11 位，每页的大小为 4KB。

对某特定机器的地址结构是一定的，若给定一个逻辑地址空间中的地址为 A，页面的大小为 L，则页号 P 和页内地址 d 可按下式求得，其中 INT 是整除函数。例如系统的页面大小为 1KB，设 A = 2170B，则由公式可以求得 P = 2，d = 122。

页表

在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中。为了能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表实现从页号到物理块号的地址映射，简称页表。在进程地址空间内的所有页(0 ~ n)，依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。进程执行时通过查找该表，即可找到每页在内存中的物理块号。

基本的地址变换机构

为了能将用户地址空间中的逻辑地址转换为内存空间中的物理地址，在系统中必须设置地址变换机构。由于页内地址和物理地址是一一对应的(例如对于页面大小是 1KB 的页内地址是 0 ~ 1023，其相应的物理块内的地址也是 0 ~ 1023)，因此地址变换机构的任务实际上只是将逻辑地址中的页号转换为内存中的物理块号。
页表大多驻留在内存中，在系统中只设置一个页表寄存器 PTR(Page-Table Register)，存放页表在内存的始址和页表的长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的 PCB 中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。
当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址 A(相对地址)分为页号 P 和页内地址 W 两部分。在执行检索之前，先将页号与页表长度进行比较。如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间，需要产生地址越界中断。若未出现越界错误，则将页表始址 F 与页号 P 和页表项长度 M 的乘积相加，便得到该表项在页表中的位置，进而从页表得到该页的物理块号。将块号和页内地址送入物理地址寄存器的块内地址字段中，完成从逻辑地址到物理地址的变换。

例如若页面大小 L 为 1K 字节，页号 2 对应的内存块号 b = 8，要将逻辑地址 A = 2500 转换为物理地址 E。页面大小为 1K 字节，说明一个页面的大小为
2^10B = 1KB，首先根据公式计算出页号、页内偏移量：

页号 P = A / L = 2500 / 1024 = 2
页内偏移量 W = A % L = 2500 % 1024 = 452

根据题中条件可知，页号 2 没有越界，其存放的内存块号 b = 8，即可计算出物理地址。

物理地址 E = b * L + W = 8 * 1024 + 425 = 8644

在分页存储管理(页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统。

3. 页面置换算法（FIFO,LRU）

页面置换算法

内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。应将哪个页面调出，须根据一定的算法来确定，选择换出页面的算法称为页面置换算法(Page-Replacement Algorithms)。置换算法的好坏将直接影响到系统的性能，不适当的算法可能会导致进程发生“抖动”，一个好的页面置换算法应具有较低的页面更换频率

最佳置换算法

最佳置换算法是一种理论上的算法，其所选择的被淘汰页面将是以后永不使用或在最长未来时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率，但由于无法预知哪一个页面是未来最长时间内不再被访问的，因而该算法无法实现，但可以利用该算法去评价其它算法。
假定系统为某进程分配了三个物理块，有以下的页面号引用串。
Copy Highlighter-hljs7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
进程运行时先将 7，0，1 三个页面装入内存，当进程要访问页面 2 时将会产生缺页中断。此时 OS 根据最佳置换算法将选择页面 7 淘汰，这是因为页面 0 将作为第 5 个被访问的页面，页面 1 是第 14 个被访问的页面，而页面 7 则要在第18次页面访问时才需调入。以此类推，得到采用最佳置换算法在各个页面引用时的状态。由表格可看出，采用最佳置换算法发生了 6 次页面置换。

先进先出页面置换算法

FIFO 算法总是淘汰最先进入内存的页面，也就是选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，但该算法与进程实际运行的规律不相适应，因为在进程中有些页面经常被访问，FIFO 算法并不能保证这些页面不被淘汰。
假定系统为某进程分配了三个物理块，有以下的页面号引用串。
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
采用 FIFO 算法进，当进程第一次访问页面 2 时将把第 7 页换出，因为它是最先被调入内存的。在第一次访问页面 3 时，又将把第 0 页换出，因为它在现有的 2、0、1 三个页面中是最老的页。利用 FIFO 算法时，进行了 12 次页面置换，比最佳置换算法正好多一倍。

最近最久未使用置换算法

最近最久未使用 LRU(Least Recently Used)置换算法根据页面调入内存后的使用情况做出决策的，LRU 算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t。当需淘汰一个页面时，选择现有页面中其 t 值最大的页面淘汰。LRU 置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。可以为每个在内存中的页面配置一个移位寄存器记录未使用时间，也可以利用一个特殊的栈保存当前使用的各个页面的页面号。
假定系统为某进程分配了三个物理块，有以下的页面号引用串。
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
当进程第一次对页面 2 进行访问时，由于页面 7 是最近最久未被访问的，故将它置换出去。当进程第一次对页面 3 进行访问时，第 1 页成为最近最久未使用的页，将它换出。利用 LRU 算法时，进行了 9 次页面置换。

4. 抖动的预防

防止抖动的方法

为了保证系统具有较大的吞吐量，必须防止“抖动”的发生，下面是几个较常用的预防“抖动”发生的方法。

第七章 设备管理

1. I/O控制方式

在 I/O 控制方式的整个发展过程中，始终贯穿着这样一条宗旨：尽量减少主机对 I/O 控制的干预，把主机从繁杂的 I/O 控制事务中解脱。

轮询的可编程 I/O 方式

对设备的控制，早期是轮询的可编程 I/O 方式。在处理机向控制器发出一条 I/O 指令，启动输入设备输入数据时，要同时把状态寄存器中的忙/闲标志 busy 置为 1，然后便不断地循环测试 busy(称为轮询)。当 busy = 1 时表示输入机尚未输完一个字(符)，处理机应继续对该标志进行测试。直至 busy = 0，表明输入机已将输入数据送入控制器的数据寄存器中。于是处理机将数据寄存器中的数据取出，送入内存指定单元中，这样便完成了一个字(符)的 I/O。

使用轮询的可编程 I/O 方式的优点是实现简单，在读/写指令之后，加上实现循环检查的一系列指令即可。缺点是 CPU 和 I/O 设备只能串行工作，CPU 需要一直轮询检查，长期处于“忙等”状态，CPU 利用率低。

中断的可编程l/O方式

当前对 I/O 设备的控制，广泛采用中断的可编程 I/O 方式。当某进程要启动某个 I/O 设备工作时，便由 CPU 向相应的设备控制器发出一条 I/O 命令，然后立即返回继续执行原来的任务。设备控制器于是按照该命令的要求去控制指定 I/O 设备，此时 CPU 与 I/O 设备并行操作。

仅当输完一个数据时，才需 CPU 花费极短的时间去做些中断处理。这样可使 CPU 和 I/O 设备都处于忙碌状态，从而提高了整个系统的资源利用率及吞吐量。例如，从终端输入一个字符的时间约为 100ms，而将字符送入终端缓冲区的时间小于 0.1ms。若采用程序 I/O 方式，CPU 约有 99.9ms 的时间处于忙一等待中。但采用中断驱动方式后，CPU 可利用这 99.9ms 的时间去做其它的事情。该方法的缺点是每个字在 I/O 设备与内存之间的传输，都需要经过 CPU，频繁的中断处理会消耗较多的 CPU 时间。

轮询和中断的比较

中断令 CPU 不再需要不断轮询设备，而是向设备发出一个请求，然后就可以让对应进程睡眠，切换执行其他任务。当设备完成了自身操作，会抛出一个硬件中断，引发 CPU 跳转执行操作系统预先定义好的中断处理程序（interrupt handler)。中断允许计算与 I/O 重叠（overlap），这是提高 CPU 利用率的关键，操作系统可以令 CPU 在 I/O 操作时去做其他事情。
但使用中断并非总是最佳方案，假如有一个非常高性能的设备，它处理请求很快，通常在 CPU 第一次轮询时就可以返回结果。此时如果使用中断，反而会使系统变慢：切换到其他进程处理中断，再切换回之前的进程代价不小。另一个最好不要使用中断的场景是网络，网络端收到大量数据包，如果每一个包都发生一次中断，那么有可能导致操作系统发生活锁。

因此如果设备非常快，那么最好的办法反而是轮询，如果设备比较慢，那么采用允许发生重叠的中断更好。如果设备的速度未知，或者时快时慢，可以考虑使用混合（hybrid）策略，先尝试轮询一小段时间，如果设备没有完成操作，此时再使用中断。另一个基于中断的优化就是合并（coalescing），设备在抛出中断之前往往会等待一小段时间，在此期间，其他请求可能很快完成，因此多次中断可以合并为一次中断抛出，从而降低处理中断的代价。

直接存储器访问方式

虽然中断驱动 I/O 比程序 I/O 方式更有效，但它仍是以字(节)为单位进行 I/O 的。采用中断驱动 I/O 方式时的 CPU，是以字(节)为单位进行干预的。如果将这种方式用于块设备的 I/O，显然是极其低效的。与中断驱动方式相比，DMA (Direct Memory Access)直接存储器存取方式有这样几个改进：

1. 数据的传送单位是“块”,不再是一个字、一个字的传送；
2. 数据的流向是从设备直接放入内存，或者从内存直接到设备，不再需要经过 CPU；
3. 仅在传送一个或多个数据块的开始和结束时，才需要 CPU 干预。

当给 I/O 模块发送命令时，CPU 指明此次要进行的操作，并说明要读入多少数据、数据要存放在内存的什么位置数据在外部设备上的地址。控制器会根据 CPU 提出的要求完成数据的读/写工作，整块数据的传输完成后，才向 CPU 发出中断信号。

DMA 控制器由三部分组成：主机与 DMA 控制器的接口、DMA 控制器与块设备的接口、I/O 控制逻辑。

DMA 的优点是数据传输以“块”为单位，CPU 介入频率进一步降低。数据的传输不再需要先经过C PU 再写入内存，数据传输效率进一步增加，CPU 和 I/O 设备的并行性得到提升。缺点是 CPU 每发出一条 I/O 指令，只能读/写一个或多个连续的数据块。

I/O 通道控制方式

I/O 通道方式是 DMA 方式的发展，它把对一个数据块的读（或写）为单位的干预，减少为对一组数据块的读（或写）及有关的控制和管理为单位的干预。同时，又可实现 CPU、通道和 I/O 设备三者的并行操作，从而更有效地提高整个系统的资源利用率。不过实现复杂，需要专门的通道硬件支持。
例如当 CPU 要完成一组相关的读(或写)操作及有关控制时，只需向 I/O 通道发送一条 I/O 指令，以给出其所要执行的通道程序的首址和要访问的 I/O 设备。通道接到该指令后，通过执行通道程序便可完成 CPU 指定的 I/O 任务。

2. 中断处理程序

中断在操作系统是多道程序得以实现的基础，，因为进程之间的切换是通过中断来完成的。中断也是设备管理的基础，为了提高处理机的利用率和实现 CPU 与 I/O 设备并行执行，也必需有中断的支持。

中断和陷入

中断是指 CPU 对 I/O 设备发来的中断信号的一种响应，CPU 暂停正在执行的程序，保留 CPU 环境后，自动地转去执行该 I/O 设备的中断处理程序。执行完后再回到断点，继续执行原来的程序。I/O 设备可以是字符设备，也可以是块设备、通信设备等。由于中断是由外部设备引起的，故又称外中断。
另外还有一种由 CPU 内部事件所引起的中断，通常把这类中断称为内中断或陷入(trap)。若系统发现了有陷入事件，CPU 也将暂停正在执行的程序，转去执行该陷入事件的处理程序。中断和陷入的主要区别是信号的来源，即是来自 CPU 外部还是 CPU 内部。

中断向量表

为了处理上的方便，通常是为每种设备配以相应的中断处理程序，并把该程序的入口地址放在中断向量表的一个表项中。每一个设备的中断请求规定一个中断号，它直接对应于中断向量表的一个表项中。当 I/O 设备发来中断请求信号时，由中断控制器确定该请求的中断号，根据中断号去查找中断向量表取得中断处理程序的入口地址。经常会有多个中断信号源，每个中断源对服务要求的紧急程度并不相同，为此系统就需要为它们分别规定不同的优先级。

对多中断源的处理方式

当处理机正在处理一个中断时，如果又来了一个新的中断请求，可有两种处理方式：屏蔽(禁止)中断与嵌套中断。屏蔽(禁止)中断当处理机正在处理一个中断时，将屏蔽掉所有的中断，即处理机对任何新到的中断请求，都暂时不予理睬，而让它们等待。其优点是简单，但不能用于对实时性要求较高的中断请求。
嵌套中断是在设置了中断优先级的系统中，通常按这样的规则来进行优先级控制：

1. 当同时有多个不同优先级的中断请求时，CPU 优先响应最高优先级的中断请求；

2. 高优先级的中断请求可以抢占正在运行的低优先级中断的处理机。

   中断处理程序

   当一个进程请求 I/O 操作时，该进程将被挂起，直到 I/O 设备完成 I/O 操作后，设备控制器便向 CPU 发送一个中断请求，CPU 响应后便转向中断处理程序执行相应的处理，处理完后解除相应进程的阻塞状态。中断处理程序的处理过程可分成以下几个步骤：

3. 测定是否有未响应的中断信号：若没有继续执行下一条指令，若有则停止原有进程的执行，准备转去执行中断处理程序；

4. 保护被中断进程的 CPU 环境：先保护被中断进程的 CPU 环境，以便以后能恢复运行；
5. 转入相应的设备处理程序：确定引起本次中断的 I/O 设备，并向提供中断信号的设备发送确认信号；
6. 中断处理：对不同的设备，有不同的中断处理程序；
7. 恢复 CPU 的现场并退出中断：当中断处理完成以后，需要恢复 CPU 的现场，退出中断。

I/O 操作完成后，驱动程序必须检查本次 I/O 操作中是否发生了错误，最终向调用者报告本次 I/O 的执行情况。

3. 与设备无关软件

设备独立性软件

为了方便用户和提高 OS 的可适应性与可扩展性，在现代 OS 的 I/O 系统中都增加了与设备无关的 I/O 软件，以实现设备独立性(设备无关性)。其基本含义是：应用程序中所用的设备，不局限于使用某个具体的物理设备。为了实现设备独立性，必须再在设备驱动程序之上设置一层软件，称为与设备无关的 I/O 软件(设备独立性软件)。

引入设备独立性软件的动机

在早期 OS 中，应用程序在使用 I/O 设备时都使用设备的物理名称，这使应用程序与系统中的物理设备直接相关。当应用进程运行时，如果所请求的物理设备(独占设备类型)已分配给其它进程，系统无法将另外相同的设备(物理设备名不同)分配给它，致使该应用进程请求 I/O 失败而被阻塞。当应用程序所需要的设备在系统中已经被更新时，该应用程序将再也无法在该系统上运行。可见应用程序直接与物理设备相关是不灵活的，I/O 设备的利用率低。
为了实现与设备的无关性而引入了逻辑设备和物理设备两个概念，逻辑设备是抽象的设备名，并没有指定具体的设备。只要系统中有一台该类设备未被分配，进程就不会被阻塞。与设备的无关软件还可实现 I/O 重定向，是指用于 I/O 操作的设备可以更换，而不必改变应用程序。

与设备无关的软件实现

在与设备无关的软件中，包括了执行所有设备公有操作的软件，具体有如下几项。

其中设备的错误可分为如下两类：

设备名映射

当应用程序请求使用 I/O 设备时应当用逻辑设备名。但系统只识别物理设备名，因此在系统中需要配置一张逻辑设备表，用于将逻辑设备名映射为物理设备名。逻辑设备表 LUT(Logical Unit Table)的每个表目中包含了三项：逻辑设备名、物理设备名和设备驱动程序的入口地址。当进程用逻辑设备名请求分配 I/O 设备时，系统为它分配一台相应的物理设备，并在逻辑设备表上建立一个表目。当以后进程再利用该逻辑设备名请求 I/O 操作时，系统通过查找 LUT 可找到该逻辑设备所对应的物理设备和该设备的驱动程序。

在系统中可采取两种方式设置逻辑设备表，第一种方式是在整个系统中只设置一张 LUT。由于系统中所有进程的设备分配情况都记录在同一张 LUT 中，因而不允许在 LUT 中具有相同的逻辑设备名，在多用户环境下这通常是难以做到的。第二种方式是为每个用户设置一张 LUT，每当用户登录时，系统便为该用户建立一个进程，同时也为之建立一张 LUT 放入进程的 PCB 中。

4. 假脱机系统及缓冲

假脱机系统

假脱机(SPOOLing)技术，则可将一台物理 I/O 设备虚拟为多台逻辑 I/O 设备，这样就允许多个用户共享一台物理 I/O 设备。SPOOLing 的系统组成如下：

SPOOLing 系统有以下特点：

1. 提高了 I/O 的速度：从对低速 I/O 设备执行的 I/O 操作演变为对磁盘缓冲区中数据的存取；
2. 将独占设备改造为共享设备；
3. 实现了虚拟设备功能：宏观上虽然是多个进程在同时使用一台独占设备，而对于每一个进程而言，它们都会认为自己是独占了一个设备。

缓冲区

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合(如存储器管理中所用的联想寄存器）一般情况下利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区。
引入缓冲区的原因有：

1. 缓和 CPU 与 I/O 设备间速度不匹配的矛盾：CPU 的运算速率远远高于 I/O 设备的速率，如果没有缓冲区，在运行时会因为 I/O 设备跟不上 CPU 的速度导致 CPU 停下来等待；
2. 减少对 CPU 的中断频率，放宽对 CPU 中断响应时间的限制。随着传输速率的提高，需要配置位数更多的寄存器进行缓冲；
3. 解决数据粒度不匹配的问题：生产者所生产的数据粒度比消费者小时，生产者进程可以一连生产多个数据单元的数据。生产者比消费者粒度大时，生产者每次生产的数据消费者可以分几次从缓冲区中取出消费；
4. 提高 CPU 和 I/O 设备之间的并行性：生产者在生产了一批数据并将它放入缓冲区后，便可立即去进行下一次的生产。

5. 磁盘调度算法（FCFS,SSTF,SCAN,CSCAN）

为了减少对文件的访问时间，应采用一种最佳的磁盘调度算法，以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中主要是寻道时间，因此磁盘调度的目标是使磁盘的平均寻道时间最少。

调度样例

某磁盘组共有 200 个柱面，由外至内依次编号为 0，1，…，199。输入输出请求以 10、100、191、31、20、150、32 的次序到达，假定引臂当前位于柱面 98 处，移动方向为由外向内。对先到先服务、最短查找时间优先扫描、扫描算法、循环扫描算法分别给出寻道示意图，并计算总移动量。对扫描算法，假定引臂当前移动方向为由外向内，对循环扫描算法假定回扫方向由内向外。

先来先服务

先来先服务(FCFS)是最简单的磁盘调度算法，它根据进程请求访问磁盘的先后次序进行调度。

总移动量
=（98-10）+（100-10）+（191-100）+（191-31）+（31-20）+（150-20）+ (150-32)
= 88 + 90 + 91 + 160 + 9 + 130 + 118
= 686。
此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长，故 FCFS 算法仅适用于请求磁盘 I/O 的进程数目较少的场合。

最短寻道时间优先

最短寻道时间优先(SSTF)算法是基于贪心算法来设计的，要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种算法不能保证平均寻道时间最短。

总移动量
=（100-98）+（150-100）+（191-150）+（191-32）+（32-31）+（31-20）+ (20-10)
= 2 + 50 + 41 + 159 + 1 + 9 + 10
= 272
SSTF 算法平均每次磁头移动的距离明显低于 FCFS 算法的距离，较之 FCFS 有更好的寻道性能。

扫描算法

SSTF 算法会产生饥饿的原因在于，磁头有可能在一个小区域内来回来去地移动。扫描算法(SCAN)可以防止这个问题，可以规定只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。由于磁头移动的方式很像电梯，因此也叫电梯算法。

总移动量
=（100-98）+（150-100）+（191-150）+（199-191）+（199-32）+（32-31）+ (31-20) + (20-10)
=2 + 50 + 41 + 8 + 167 + 1 + 9 + 10
=288
扫描算法的优点是性能较好，平均寻道时间较短，不会产生饥饿现象。缺点是只有到达最边上的磁道时才能改变磁头移动方向，事实上有时并不需要到达最边上的磁道。同时当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时该进程必须等待磁头继续从里向外，然后再从外向里扫描完处于外面的所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。

循环扫描算法

SCAN 算法对于各个位置磁道的响应频率不平均，循环扫描(C-SCAN)算法可以解决这个问题。它规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

总移动量
=（100-98）+（150-100）+（191-150）+（199-191）+（10-0）+（20-10）+ (31-20) + (32-31)
= 2 + 50 + 41 + 8 + 10 + 10 + 9 + 1
= 131
C-SCAN 算法的优点是比起 SCAN，对于各个位置磁道的响应频率很平均。缺点是只有到达最边上的磁道时才能改变磁头移动方向，比起 SCAN 算法来平均寻道时间更长。

NStepSCAN算法

在 SSTF、SCAN 及 CSCAN 几种调度算法中，都可能出现磁臂停留在某处不动的情况。例如有一个或几个进程反复请求对某一磁道的 I/O 操作，从而垄断了整个磁盘设备，这一现象称为磁臂粘着”(Armstickiness)。
NStepSCAN 算法是将磁盘请求队列分成若干个长度为 N 的子队列，磁盘调度将按 FCFS 算法依次处理这些子队列。而每处理一个队列时又是按 SCAN 算法，对一个队列处理完后再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘 I/O 请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。当 N 值取得很大时，会使 N 步扫描法的性能接近于 SCAN 算法的性能，当 N = 1时 N 步 SCAN算法便蜕化为 FCFS 算法。

FSCAN 算法

FSCAN 算法是 N 步 SCAN 算法的简化，即 FSCAN 只将磁盘请求队列分成两个子队列，一个是由当前所有请求磁盘 I/O 的进程形成的队列，由磁盘调度按 SCAN 算法进行处理。另一个是在扫描期间，将新出现的所有请求磁盘 I/O 的进程放入等待处理的请求队列，这样所有的新请求都将被推迟到下一次扫描时处理。

第七、八章 文件

1. 文件的打开

文件的“打开”和“关闭”操作

当用户要求对一个文件实施多次读/写或其它操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，当用户第一次请求对某文件进行操作时，须先利用 open 系统调用将该文件打开。打开是打开就是在用户和指定文件之间建立起一个连接，具体指系统将指名文件的属性（包括该文件在外存上的物理位置)，从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引号）返回给用户。
如果用户已不再需要对该文件实施相应的操作，可利用关闭”(close)系统调用来关闭此文件，即断开此连接，OS 将会把该文件从打开文件表中的表目上删除掉。

2. 目录、文件共享，文件存储空间管理

目录管理的要求

为了能对计算机系统中的大量文件实施有效的管理，必须对它们加以妥善组织，这主要是通过文件目录实现的。文件目录是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。对目录管理的要求如下：

文件共享

系统应允许多个用户(进程)共享，这样在系统中只需保留该共享文件的一份副本。如果系统不能提供文件共享功能，就意味着凡是需要该文件的用户，都须各自备有此文件的副本，显然这会造成对存储空间的极大浪费。

有向无循环图

在严格的树形结构目录中，每个文件只允许有一个父目录，其它用户要想访问它必须经过其属主目录来访问该文件。树形结构目录是不适合文件共享的，如果允许一个文件可以有多个父目录，这些用户可用对称的方式实现文件共享，而不必再通过其属主目录来访问，此时的结构是有向无循环图 DAG(Directed Acyclic Graph)。当有多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到多个用户的父目录中。

索引结点

将文件的物理地址及其它的文件属性等信息放在索引结点中，在文件目录中只设置文件名及指向相应索引结点的指针。索引结点中设置一个链接计数变量 count，用于表示链接到本索引结点上的用户目录项数。若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的 count 值减 1。若 count > 0 说明还有别的用户要使用该文件，暂时不能把文件数据删除，当 count = 0 时系统负责删除文件。

符号链接

利用符号链接(Symbolic Linking)实现文件共享的基本思想，是允许一个文件或子目录有多个父目录，但其中仅有一个作为主(属主）父目录，其它的几个父目录都是通过符号链接方式与之相链接的（简称链接父目录)。当用户访问被链接的文件且正要读 LINK 类新文件时，OS 根据新文件中的路径名去找到被连接文件，然后对它进行读写。在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针，而共享该文件的其他用户则只有该文件的路径名。这样不会发生在文件主删除一共享文件后留下一悬空指针的情况，如果其他用户又试图通过符号链去访问一个已被删除的共享文件，则会因系统找不到该文件而使访问失败，此时再将符号链删除。
但是当其他用户去读共享文件时，系统是根据给定的文件路径名逐个分量(名）地去查找目录，因此在每次访问共享文件时都可能要多次地读盘。同时每增加一条链接，就增加一个文件名，当试图去遍历(traverse)整个文件系统时将会多次遍历到该共享文件。

3. 提高文件访问速度的途径、磁盘高速缓存

3. 索引结构（直接索引和混合索引）的原理