操作系统期末知识点总结

第一章

1、操作系统：OS是一个大型的系统软件、它负责计算机的全部软件和硬件资源的管理，并为用户提供良好的应用界面，使整个计算机系统实现高效率和高度自动化

2、操作系统的形成

1）手工操作阶段

2）批处理系统（一系列作业的序列，称之为批）

（1）单道批处理系统：一批作业以脱机方式输入到存储介质上（磁带、磁盘），系统能对这批作业一个接一个连续自动处理，因在内存上只保持一道作业，故称单道批处理系统

（2）多道程序设计技术--多道批处理系统：在计算机内存中同时存放几道相互独立的程序，它们在管理程序控制下，相互交替执行，当某道作业因某种原因不需要CPU时，管理程序将另一道作业投入运行，这样使CPU和各种设备处于忙碌状态，从而大大提高了计算机的使用效率

（多道程序设计技术的硬件支持是：中断与通道技术、使主机与外设之间可以并行工作）

（特点：①多道②宏观上并行③微观上串行

优点：①资源利用率高②系统的吞吐量大

缺点：①有时用户的响应时间较长②交互性不好）

分时技术与分时操作系统（特点：用户有较快的响应时间、交互性好）（响应时间与就绪队列中进程数目和时间片大小有关）

3、操作系统的基本类型

1）批处理操作系统

2）分时操作系统

批处理操作系统和分时操作系统的不同点：

（1）追求的目标不同：

①批处理系统：提高系统资源利用率和作业的吞吐能力为目标

②分时系统：强调公平性，对于联机用户的立即型命令要快速响应

（2）适应作业不同：

①批处理系统：已调试好的大型作业

②分时系统：正在调试的小型作业

（3）资源利用率不同：

批处理系统可以合理安排不同负载的作业，使资源利用率达到最佳，作业可分为：以计算为主；以I/O为主；计算与I/O均衡

（4）作业控制方式不同：

①批处理系统：用户通过JCB书写作业控制流，预先提交，脱机工作

②分时系统：作业由用户从键盘输入控制命令，一交互方式联机工作

3）实时操作系统（特点：及时性和高可靠性）

4、操作系统的功能

1）处理机管理：为了提高处理机的效率，操作系统对处理机的管理采用多级调度（作业调度、进程调度、线程调度）

2）存储器管理（分区存储管理、页式存储管理、段式存储管理、段页式存储管理）

3）设备管理：

（1）设备无关性：程序中只使用设备的逻辑名，屏蔽设备的物理特性，方便用户使用

（2）设备的分配：独占型设备、共享型设备、虚拟设备、静态分配、动态分配

（3）设备传输的控制方式：程序查询方式、中断方式、DMA方式、通道方式等

（4）其它：如缓冲技术、SPOOL技术等

4）文件管理：

（1）文件的逻辑结构和物理结构

（2）磁盘空间的管理

（3）目录管理

（4）文件操作

（5）文件的安全与保护

5、操作系统的特征

1）并发性：指多个时间在同一时间间隔内发生，如：I/O操作与CPU处理重叠

2）共享性：

（1）空分复用：如内存中的多道程序、磁盘上的多个文件等

（2）时分复用：如时分系统中的CPU

并发和共享是操作系统的两个最为基本的特征，它们互为存在条件：一方面，若系统不允许并发执行，自然不存在资源共享的问题；另一方面，若不能对资源共享实施有效的管理，也将影响到并发执行

3）不确定性（异步性）：

只要运行环境相同，作业经过多次运行，都将获得相同的结果

4）虚拟性：如虚拟机、虚拟内存、虚拟设备

6、UNIX特性：

（1）UNIX系统是一个多用户、多任务的分时操作系统

（2）UNIX的系统结构可分为三部分：操作系统内核（是UNIX系统核心管理和控制中心，在系统启动或常驻内存），系统调用（供程序开发者开发应用程序时调用系统组件，包括进程管理、文件管理、设备状态等），应用程序（包括各种开发工具、编译器、网络通讯处理程序等，所有应用程序都在Shell的管理和控制下为用户服务）

（3）UNIX系统大部分是由C语言编写的，这使得系统易读、易修改、易移植

（4）UNIX提供了丰富的、精心挑选的系统调用，整个系统的实现十分紧凑、简洁

（5）UNIX提供了功能强大的可编程的Shell语言（外壳语言）作为用户界面具有简洁、高效的特点

（6）UNIX系统采用树状目录结构，具有良好的安全性、保密性和可维护性

（7）UNIX系统采用进程对换的内存管理机制和请求调页的存储方式，实现了虚拟内存管理，大大提高了内存的使用效率

（8）UNIX系统提供多种通信机制，如：管道通信、软中断通信、消息通信、共享存储器通信、信号灯通信

7、在单CPU和两台I/O设备I1、I2的多道程序设计环境下，同时投入三个作业job1、job2、job3运行，这三个作业对CPU和I/O设备的使用顺序和时间如下：

Job1:I2(30ms);CPU(10ms);I1(30ms);CPU(10ms);I2(20ms);

Job2:I1(20ms);CPU(20ms);I2(40ms);

Job3:CPU(30ms);I1(20ms);CPU(10ms);I1(10ms);

假定CPU、I1、I2都能并行工作，job1的优先级最高，job2次之，job3最低，优先级高的作业进程可以抢占优先级低的作业进程的CPU，但不能抢占I1和I2

试求：

（1）三个作业从投入到完成所需的时间

（2）从投入到完成的CPU利用率

（3）I/O设备利用率

解：

（1）

时间	10	20	30	40	50	60	70	80	90	100	110
CPU	Job3	Job3	Job2	Job1	Job2	Job3		Job1		Job3
I1	Job2	Job2			Job1	Job1	Job1	Job3	Job3		Job3
I2	Job1	Job1	Job1			Job2	Job2	Job2	Job2	Job1	Job1

Job1从投入到完成需要110ms；

Job2从投入到完成需要90ms；

Job3从投入到完成需要110ms；

（2）从投入到完成的CPU利用率：80/110=72.7%

（3）I1的利用率=80/110=72.7%

I2的利用率=90/110=81.8%

第二章：

1、处理机的状态：

（1）管态：OS的管理程序执行CPU的状态，在此状态下允许CPU使用全部的机器资源和全部指令

（2）用户态：用户程序执行时机器所处的状态，在此状态下禁止使用特权指令，不能直接取用资源和改变机器状态，只允许访问自己的存储区域

有些系统将OS执行时机器的状态进一步细分为核心态和管态，核心态具有上述管态的所有权限，而此时的管态比核心态的权限低，只允许使用一些在用户态所不能使用的资源，但不能使用修改机器状态的指令

eg.当CPU处于管态时，它可以执行的指令应该是计算机系统的全部指令

2、特权指令集

（1）改变机器状态的指令

（2）修改特殊寄存器的指令，如中断屏蔽寄存器、限界寄存器等

（3）设计外设的输入/输出指令

3、中断机制：

1）中断是实现OS功能的基础，是构成多道程序运行环境的根本措施，中断是OS各种功能的驱动源

2）当CPU正在执行程序时，出现某种非预期事件，CPU暂停当前程序的执行转而为该事件服务，当处理完该事件后，再继续原来程序的执行，这一过程称为中断

3）中断的类型：

（1）输入输出中断：

如：程序中断接口；DMA接口；通道

（2）外中断：CPU的外部装置所引起的中断

如：时钟中断；控制台中断

（3）机器故障中断：

如：电源故障；奇偶校验出错等

（4）程序性中断：

如：溢出；地址越界；地址出错；非法操作等

（5）访管中断：对OS提出需求时所发生的中断

例如：请求I/O服务；各种系统调用（如建立进程）等

4）中断的处理过程

（1）中断源的识别

（2）保护断点和现场

（3）执行中断服务程序

（4）回复断点和现场

4、假设一个计算机系统具有如下特征：处理一次中断，平均耗用1ms；一次进程调度，平均需要2ms；将cpu分配给选中的进程，又需要平均1ms；再假设其定时器芯片每秒产生100次中断，请回答：

（1）操作系统将百分之几的CPU时间用于时钟中断处理？

（2）如果操作系统采用轮转法调度，10个时钟中断为1个时间片，那么，操作系统将百分之几的CPU时间用于进程调度（包括调度，分配CPU和引起调度时的时钟中断处理时间）？

解：（1）100*1ms/1s=10%

（2）时间片的大小=10*（1s/100）=100ms

一个时间片要处理10个时钟中断，需要10*1ms=10ms

时间片到后再进行一次进程调度，需要2ms

再将CPU分配给选中的进程，又需要平均1ms

故：系统将CPU时间的（10+1+2）/100=13%用于进程调度

第三章：用户界面

导致CPU从用户态向核心态转换的情况：

（1）程序请求OS服务，执行系统调用

（2）程序在运行时，产生中断或异常事件，运行程序被中断，转向中断服务程序或异常处理程序

第四章：并发处理

1、并发执行程序的特点：

（1）间断性：如果Ci-1完成后，若，Ii未完成，则Ci也无法处理，导致计算程序段暂停

（2）失去程序的封闭性：程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去封闭性

（3）不可再现性：当初始条件相同时，程序多次执行，其结果必然重复出现，称为可再现性

2、进程：（包括程序段、数据段、栈段、进程控制块）

（1）进程是一个具有独立功能的程序关于某个数据集合的一次运行活动

（2）从核心看来，进程是分了类的，根据一组规则操纵的数据结构

3、进程和程序的关系：

1）进程与程序的联系：

（1）进程=程序（程序段、数据段、栈段）+进程控制块（PCB）

（2）程序是构成进程的组成部分之一，一个进程存在的目的就是执行其所对应的程序

2）进程和程序的区别：

（1）程序是静止的，进程是动态的（有生命周期的）

（2）进程是能独立运行的单位，能与其他进程并发执行

（3）进程是资源分配的基本单位，也是CPU调度的基本单位

4、进程的特征：

（1）并发性：可以与其他进程在宏观上同时向前推进

（2）动态性：进程是执行中的程序

（3）独立性：进程是资源分配和调度的基本单位

（4）交互性：进程在运行时可能会与其他进程发生直接或间接的相互作用

（5）异步性：每个进程都可以相对独立，不可预知的速度向前推进

（6）结构性：每个进程都对应一个进程控制块

5、进程的状态：

（1）就绪状态：获得了除CPU以外的所有资源，一旦获得CPU控制权，就可以立即运行

（2）运行状态：当就绪进程由OS的进程调度程序调度，得到CPU控制权，占用CPU运行的状态

（3）等待状态（阻塞状态、睡眠状态）：若某一进程正在等待某一事件的发生而暂时停止，这时，即使获得CPU控制权也无法执行

（4）创建态：进程刚刚创建（如建立PCB），完成初始化，但未分配内存等资源

（5）终止态：正常结束或异常结束

6、进程控制块PCB包括：（UNIX的PCB=proc结构+user结构，其中proc结构常驻内存；user结构常驻辅存，进程执行时调入内存）

（1）进程标识符：由OS创建进程时给出，要求唯一

（2）进程的状态：作为进程调度时分配处理机的主要依据，为了便于对进程实施管理，通常把具有相同状态的进程链接在一起，组成各种队列，如就绪队列、各种等待队列

（3）当前队列指针：指向相同状态的下一个PCB

（4）总链指针：就系统中所有进程的PCB勾链起来

（5）程序开始地址：表示进程的程序从此开始执行

（5）进程优先级

（7）CPU现场保护区

（8）通信信息：eg.记录消息缓冲队列指针htpr

（9）家族信息：eg.父进程的标识符ppid
（10）占有资源清单

7、在进程基本状态转换图中，增加换出（将进程换出至辅存）和换入（将进程从辅存换入至主存）两个操作，试画出进程状态转换图

8、进程控制原语有：创建原语、撤销原语、阻塞原语、唤醒原语、延迟原语

9、进程的创建可来源于：

（1）用户向系统提交作业或程序

（2）OS创建服务进程

（3）已存在的进程创建新的进程，如父进程创建子进程

10、进程的创建过程：

（1）申请一个空闲的PCB

（2）初始化PCB，如进程号、优先级、状态等

（3）为新的进程分配资源，如内存等

（4）为新进程插入就绪队列

11、引起进程终止的事件：

（1）正常结束，如程序执行完毕

（2）异常结束，如溢出

（3）外界干预，如程序执行时用户ctrl+break

11、引起进程阻塞的事件：

（1）请求OS服务

（2）请求中断处理

（3）新的数据还未到达

（4）无新工作可做

13、进程的相互制约关系：

（1）竞争关系：原本不存在逻辑关系的各进程因共享资源而产生的制约关系，又称互斥关系（eg.学生在图书馆占座位）

（2）协作关系（同步）：一组并发进程，为了完成任务需要分工协作，这种协作进程之间需要排定执行的先后次序（如一个作业分为输入i、计算c、输出p三个过程段）

14、进程互斥：是指若干进程因相互争夺独占型资源而产生的竞争制约关系

（1）临界资源：一次仅允许一个进程使用的资源（独占型资源）如：打印机、公共变量、链表、数据结构等（对临界资源必须互斥使用，否则会发生错误）

（2）临界区：每个进程中访问临界资源的那段代码，又称临界段

15、互斥应遵循的原则：

（1）空闲让进：临界资源处于空闲状态时，应允许一个请求进入临界区地进程立即进入自己的临界区

（2）忙则等待：当已有进程进入自己的临界区时，其它所有试图进入临界区的进程必须等待

（3）有限等待：要求访问临界资源的进程，应保证能在有限的时间内进入自己的临界区

（4）让权等待：当进程不能进入自己的临界区时，应立即释放CPU，以免进程陷入“忙等待”

16、同步机构：（系统提供了lock(w)和unlock(w)原语）

（1）实现互斥方法之一：锁

（2）对每个临界资源设置一个锁位W，按惯例，w=0，表示资源可用；w=1，表示资源已被占用

（3）当进程使用临界资源之前必须完成上锁操作，即w置1；当进程使用完临界资源后，须开锁操作，即w置0

lock(w) {
    while(w==1) {
        保护当前进程的现场至进程的PCB；
        将当前进程的PCB插入w的等待队列；
        置该进程为“等待”状态；
        转os的进程调度；
    }
    w=1；
}

unlock(w) {
    if(w的等待队列不空) {
        移出等待队列的首元素；
        将该进程插入就绪队列；
        置该进程为“就绪”状态；
    }
    w=0；
}

17、信号灯（信号量semaphore）和P、V操作：

struct semaphore{
    // s初值>=0，其值只能由P、V操作改变
    int s;
    // q是初始状态为空的排队站
    Queue q;
}
// 申请一个资源，如果申请不到就进入等待状态
// s>=0时，没有影响
// s<0时，当前进程由运行状态变为等待状态
P(s) {
    s--；
    if(s < 0) {
        保留当前进程的现场；
        将该进程插入s的等待队列q中；
        置该进程为“等待”状态；
        转OS的进程调度程序；
    }
}
// 释放一个资源，如果有进程因申请不到该资源而等待的话，就唤醒一个等待的进程
V(s) {
    s++；
    if(s<=0) {
        移出s等待队列q的首元素；
        将该进程插入就绪队列；
        置该进程为“就绪”状态；
    }
}

18、有n个并发进程

（1）mutex=1，表示没有进程进入临界区

（2）mutex=0，表示有一个进程进入临界区

（3）mutex=-1，表示有一个进程进入临界区，另一个进程等待进入

（4）对于n个并发进程，分析mutex的取值范围以及每个值的物理意义，对于n个并发进程，mutex的值可为1、0、-1、……、-（n-1），当mutex<0时，|mutex|的值为等待进入临界区的进程数

19、进程同步：并发进程在一些关键点上可能需要互相等待或互通消息（eg.一组合作进程按逻辑需要所确定的次序执行；共享缓冲区或贡献数据的合作进程同步）

20、用P、V操作描述进程流图中这3个进程的同步：

Semaphore Sa=0；
Main() {
    cobegin
    Pa();Pb()Pc();
    coend
}
Pa() {
    ……
    V(Sa);
    V(Sa);
}
Pb() {
    P(Sa);
    ……
}
Pc() {
    P(Sa);
    ……
}

21、生产者--消费者问题

同步规则：缓冲区空，消费者进程等待；

缓冲区满，生产者进程等待；

设置2个同步信号量，1个互斥信号量

Semaphore Full=0；		//表示缓冲区中产品的数目
          Empty=n；		//表示空缓冲区的数目
          Mutex=1；		//互斥访问有界缓冲区
Main() {
    Cobegin
    P1();......Pm();
    C1();......Ck();
    Coend
}
Pi() {
    while(1) {
        生产一个产品；
        P(empty);
        P(mutex);
        产品送入缓冲区；
        V(mutex);
    V(full);
    }
}
Vj() {
    while(1) {
        P(full);
        P(mutex);
        从缓冲区中取出产品；
        V(mutex);
        V(empty);
        消费一个产品
    }
}

22、某工厂有两个生产车间和一个装配车间，两个生产车间分别市场A、B两个零件，装配车间的任务是把A、B两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1、F2上，F1存放零件A，F2存放零件B，F1和F2的容量均可以存放10个零件，装配工人每次从货架上取一个A零件和一个B零件然后组装成产品，请用PV操作进行正确的管理

解：

Semaphore Sa=10;
          Ta=0;
          Sb=10;
          Tb=0;
          M1=1;
          M2=1;
Main() {
    Cobegin
    workshopA();
    workshopB();
    workshopC();
    Coend
}
workshopA() {
    while(生产未完成) {
        生产A产品；
        P(Sa);
        P(M1);
        放入A产品货架；
        V(M1);
        V(Ta);
    }
}
workshopB() {
    while(生产未完成) {
        生产B产品;
        P(Sb);
        P(M2);
        放入B产品货架；
        V(M2);
        V(Tb);
    }
}
workshopC() {
    while(装配未完成) {
        P(Ta);
        P(M1);
        取出A产品；
        V(M1);
        V(Sa);
        P(Tb);
        P(M2);
        取出B产品；
        V(M2);
        V(Sb);
        装配产品；
    }
}

23、过独木桥问题

//互斥独木桥
Semaphore bridgemutex=1; 
          //互斥count1
          M1=1;				
          //互斥count2
          M2=1;				
//记录从西向东的过桥人数
int count1=0;						
    //记录从东向西的过桥人数
    count2=0;						
Main() {
    Cobegin
    West_easti() ;
    East_westj();
    Coend
}
West_easti() {
    P(M1);
    count1++;
    //第一个人上桥时封装对向上桥
    if(count1==1)
        P(bridgemutex);			
    V(M1);
    从西向东过桥；
    P(M1);
    count1--;
    // 最后一个人下桥时解封对象上桥
    if(count1==0)
        V(bridgemutex);
    V(M1);
}
East_westj() {
    P(M2);
    count2++;
    // 第一个人上桥时封锁对向上桥
    if(Count2==1)
        P(bridgemutex);
    V(M2);
    从东向西过桥；
    P(M2);
    count2--;
    // 最后一个人下桥时解封对象上桥
    if(count2==0)
        V(bridgemutex);
    V(M2);
}

24、下面的描述中，（ABD）是正确的

A、进程执行的相对速度不能由自己来控制

B、P、V操作都是原语操作

C、利用信号量的P、V操作可以交换大量信息

D、同步是并发进程之间存在的一种制约关系

解：利用信号量的P、V操作是为了实现互斥，而不是交换大量信息

第五章：死锁

1、死锁：是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进

2、产生死锁的原因：

（1）系统资源不足（根本原因）

（2）进程推进顺序非法

2、产生死锁的四个必要条件：

（1）互斥条件：在一段时间内，某资源只能有一个进程占有，如果此时还有其他进程要求该资源，要求者只能阻塞，直到占有该资源的进程用毕释放，即资源是互斥的（独木桥一次仅允许一个人对向通过）

（2）不剥夺条件：进程获得的资源，再未使用完之前，不能被其他进程剥夺，只能由自己释放（不能将对方推下桥）

（3）部分分配条件：在等待一新资源的同时，进程继续占有已分配到的资源（都已占据桥面，等待对方让开）

（4）环路条件：即进程集合{P1、P2、……、Pn}中，P1等待P2占有的资源；P2等待P3占有的资源；……；Pn等待P1占有的资源；形成环路（互相等待对方的位置）

4、解决死锁问题的策略

1）静态预防死锁

（1）破坏“互斥条件”（难以否定）

（2）破坏“不剥夺条件”：若某进程的资源申请被拒绝时，则必须释放所有已获得，如果需要再和其他资源一起申请

（3）破坏“部分分配条件”：各进程所需要的全部资源只能一次申请，并且在没有获得全部资源之前，进程不能投入运行

（4）破坏“环路条件”：系统将所有的资源按类型进行编号，所有进程对资源的请求必须按资源的序号递增（或递减）的次序提出，这样，所形成的资源分配图中，不可能出现环路

由于所施加的限制条件太严格，可能导致系统资源利用率和系统吞吐量降低

2）动态避免死锁

在资源的动态分配中，用某种方法防止系统进不安全状态，从而避免死锁发生，最具代表性的是“银行家算法”

eg.假定系统有五个进程{P0、P1、P2、P3、P4}和三类资源{A、B、C}，数量为{10、5、7}，在T0时刻的资源分配情况如下：

进程\资源	MAX A B C	Allocation A B C	Need A B C	Available A B C
P0	7 5 3	0 1 0	7 4 3
P1	3 2 2	2 0 0	1 2 2	3 3 2
P2	9 0 2	3 0 2	6 0 0
P3	2 2 2	2 1 1	0 1 1
P4	4 3 3	0 0 2	4 3 1

（1）T0时刻的安全性

（2）P1请求资源Request1(1，0，2)；

（3）P4请求资源Request4(3，3，0)；

（4）P0请求资源Request0(0，2，0);

解：（1）

进程\资源	Work A B C	Need A B C	Allocation A B C	Work+Allocation A B C
P1	3 3 2	1 2 2	2 0 0	5 3 2
P3	5 3 2	0 1 1	2 1 1	7 4 3
P4	7 4 3	4 3 1	0 0 2	7 4 5
P0	7 4 5	7 4 3	0 1 0	7 5 5
P2	7 5 5	6 0 0	3 0 2	10 5 7

故T0时刻存在一个安全序列{P1、P3、P4、P0、P2}，故系统是安全的

（2）若进程P1请求资源Req（1，0，2），银行家算法判断如下：

①判断Req（1，0，2）<=Need1（1，2，2），表示Req为合法请求

②判断Req（1，0，2）<=Available（3，3，2），表示Req为可满足的请求

③试探性分配：Available-=Req；变为（2，3，0）

Allocation+=Req；变为（3，0，2）

Need-=Req；变为（0，2，0）

④新状态的安全性：

进程\资源	Work A B C	Need A B C	Allocation A B C	Work+Allocation A B C
P1	2 3 0	0 2 0	3 0 2	5 3 2
P3	5 3 2	0 1 1	2 1 1	7 4 3
P4	7 4 3	4 3 1	0 0 2	7 4 5
P0	7 4 5	7 4 3	0 1 0	7 5 5
P2	7 5 5	6 0 0	3 0 2	10 5 7

故：新状态是安全的，可找到安全序列{P1、P3、P4、P0、P2}，因此可以分配资源，Available变为（2，3，0）

（3）若进程P4请求资源Req（3，3，0），银行家算法判断如下：

①判断Req（3，3，0）<=Need4（4，3，0），表示Req为合法请求

②判断Req（3，3，0）>Available（2，3，0），可知，Request不是可满足的请求，故新状态是不安全的，因此，不能满足进程P4的资源请求Req（3，3，0）

（4）若进程P0请求资源Req（0，2，0），银行家算法判断如下：

①判断Req（0，2，0）<=Need0（7，4，3），表示Req为合法请求

②判断Req（0，2，0）<=Available（3，3，2），表示Req为可满足的请求

③试探性分配：Available-=Req；变为（2，1，0）

Allocation+=Req；变为（0，3，0）

Need-=Req；变为（7，2，3）

④新状态的安全性：因为Available（2，1，0）不能满足任何进程的资源需求，即找不到安全序列，此时系统进入不安全状态，因此，不能满足进程P0的资源请求Req（0，2，0）

3）检测死锁/解除死锁

预先不采取任何限制性的措施，也不检查系统是否进入不安全状态，允许系统在运行过程中发生死锁，但可通过系统设置的检测机构，及时地检测出死锁地发生，并精确地确定与死锁有关地进程和资源，然后采取适当地措施，从系统中将已发生死锁清除掉，如撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态地进程，使之转为就绪状态继续运行

第六章：处理机调度

1、处理机调度

（1）为了提高处理机的效率，处理机采用多级调度

（2）用户作业从进入系统成为后备作业开始，直到运行结束退出系统为止，需要经过不同级别的调度

（3）批处理OS可能经历作业调度、进程调度、线程调度

（4）分时OS可能经历进程调度、线程调度

2、作业的状态：

（1）后备状态：作业在辅存上，并建立JCB，等待调度

（2）执行状态：作业进入主存，到作业计算完成为止

（3）完成状态：从作业计算完成开始，到善后处理完毕并退出系统为止

3、作业调度的功能：主要是完成作业从后备到执行、执行到完成状态的转变（当作业处于执行状态时，其对应的进程不一定处于执行状态）

4、调度目标：（这些目标本身有些是相互冲突的）

（1）对所有作业应该是公平合理的

（2）应使设备有高的利用率

（3）系统吞吐量大

（4）有较快的响应时间

5、作业调度算法

（1）先来先服务调度算法（FCFS算法）：作业按来到的先后次序进行调度（对短作业不利）

（2）短作业优先调度算法（SJF算法）：从后备作业中选择执行时间最短的作业作为下一次服务的对象（只照顾短作业的利益，而不考虑长作业的利益）

（3）相应比高者优先调度算法（相应比rp=等待时间/执行时间）：当调度时，需计算后备作业的响应比，然后选择相应比高者投入运行（每次需要调度时都要计算响应比，较复杂）

6、一个单处理机分时系统收到了三个作业，作业的提交情况见下表：

作业	作业提交时间	运行时间	I/O时间	CPU时间
A	10.0	0.36	0.18	0.18
B	10.2	0.32	0.16	0.16
C	10.4	0.36	0.18	0.18

现假设：在单CPU上分时运行两道作业时，若每道作业的I/O等待时间皆占各种总运行时间的50%，则CPU将有20%的时间空闲，请写出各个作业的结束时间（为计算方便，时间采用十进制）

分析：当有一道作业时，CPU有50%的时间空闲，50%的时间计算

当有两道作业时，CPU有20%的时间空闲，80%的时间计算

解：10.0-10.2时间段内，作业A到达，一道作业，作业A计算0.1，还需要0.08；

10.2-10.4时间段内，作业B到达，两道作业，0.2*80%=0.16的CPU时间计算，作业A和作业B分别使用CPU，各使用0.08，故10.4时作业A结束，作业B还需0.08；

10.4-10.6时间段内，作业C到达，两道作业，0.2*80%=0.16的CPU时间计算，作业B和作业C分别使用CPU，各使用0.08，故10.6时作业B结束，作业C还需0.1；

10.6时间以后，一道作业，CPU有50%的时间空闲，50%的时间计算，故0.2*50%=0.1，10.8时作业C结束

因此：作业A的结束时间为：10.4

作业B的结束时间为：10.6

作业C的结束时间为：10.8

7、进程调度的时机的可能情况：

（1）正在执行的进程执行完毕

（2）执行的进程因中断调用、自陷、请求I/O服务等而阻塞

（3）在分时系统中，进程分配的时间片用完

（4）在可剥夺方式中，有优先级更高的进程要求处理

8、静态优先权（在进程建立时确定，且规定他在进程的整个运行期间保持不变）确定优先级的依据：

（1）进程所需资源的要求，如进程的执行时间及内存需要量少的应赋予较高的优先级

（2）进程类型，如系统进程的优先权应高于用户进程

（3）根据用户类型，如按用户付费用的多少来确定优先权

9、动态优先权：在进程创建时所赋予的优先权，可以随着进程的推进而改变，以便获得更好的调度性能

10、进程的两个基本属性：

（1）进程是一个可拥有资源的独立单位

（2）进程又是一个可以独立调度和分配CPU的基本单位

11、由于进程是一个资源拥有者，因而在进程的创建、撤销和切换中，涉及资源的释放，系统必须付出较大的时空开销，正因如此，在系统中所设置的进程数目不宜过多，进程切换的频率也不宜过高，但这也限制了并发进程的进一步提高

12、（1）进程作为资源分配的基本单位

（2）线程是在进程内用于调度和占有CPU的基本单位

（3）每个线程可以用一个现场表示，现场由PC、GR、PSW组成，这样线程切换时，就不涉及资源的分配和释放

13、当一个线程执行时，它只有一个线程，如果需要进程可以继续创建新的线程，也就是一个进程可以包含多个控制线程，每个线程运行进程中的一个程序段，这样，进程就有多个执行路径，增强了并行处理能力（线程完全继承父进程占有的资源，但它活动时具有自己的运行现场）

14、线程与进程的比较：

（1）调度：

线程作为CPU调度的基本单位，进程作为资源调度的基本单位

在同一进程中，线程的切换不会引起进程的切换；由一个进程的线程切换到另一个进程的线程时，将会引起进程的切换

（2）并发性：

在引入线程的OS中，不仅进程之间可以并发执行，而且一个进程中的多个线程之间也可并发，因而使OS具有更好的并发性，从而能更有效地使用系统资源和提高系统的吞吐量

（3）拥有资源：

进程是拥有资源的一个独立单位；线程自己不拥有系统资源（也有一点必不可少的资源），但可访问其隶属进程的资源，即一个进程的代码段、数据段及系统资源可供同一进程的所有线程共享

（4）系统开销：

线程切换只需保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作，进程切换的开销远大于线程切换的开销远大于线程切换的开销

15、线程的状态及变迁

（1）创建：建立的新生线程处于新建状态，已完成初始化

（2）就绪：进入线程就绪队列，一旦分到CPU时间，就可立即运行

（3）运行：一个线程正占用CPU，执行它的程序

（4）等待：让出CPU，暂时终止自己的执行，进入等待状态

（5）终止：一个线程已经退出，当该信息还未被其他线程所收集

16、在一个两道批处理系统中，有一作业序列，其到达时刻/估计运行时间列表及优先数如下：

作业	到达时刻	估计运行时间（分钟）	优先数
JA	10：00	40	5
JB	10：20	30	3
JC	10：30	50	4
JD	10：50	20	6
JE	11：00	30	2

假设作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法（表中所列优先数即为进程优先数，数值越小优先级越高）（哪个作业短就调入哪个作业，然后再通过优先级判断处理哪个作业）

（1）列出各作业的执行时间，即列出每个作业运行的时间片段，例如：作业i的运行时间序列为：10：00-10：40、11：00-11：20、11：30-11：50（结束）

（2）计算这批作业的平均周转时间和带权平均周转时间

解：（1）

10：00 JA到达，JA进入内存，PA执行

10：20 JB到达，JB进入内存，JB的优先级更高，PB执行，此时PA已执行20分钟，还需20分钟

10：30 JC到达，JC后备

10：50 JD到达，JD后备，JD进入内存，JB终止，PB完成，PA执行

11：00 JE到达，JE后备

11：10 JA终止，PA完成，JE进入内存，PE执行

11：40 JE终止，PE完成，JC进入内存，PC执行

12：30 JC终止，PC完成，PD执行

12：50 JD终止，PD完成

故：

	运行时间	平均周转时间	带权平均周转时间
JA	10：00-10：20；10：50-11：10	70	1.75
JB	10：20-10：50	30	1
JC	11：40-12：30	120	2.4
JD	12：30-12：50	120	6
JE	11：10-11：40	40	1.33

（2）

这批作业的平均周转时间为：（70+30+120+120+40）/5=76

带权平均周转时间=（1.75+1+2.4+6+1.33）/5=2.496

17、在一个两道批处理系统中，有一作业序列，其到达时刻及估计运行序列如下：

作业	到达时刻	估计运行时间（分钟）
1	10：00	35
2	10：10	30
3	10：15	45
4	10：20	20
5	10：30	30

系统采用最高响应比优先的作业调度算法（响应比=等待时间/估计运行时间），作业进程的调度采用短作业优先的抢占式调度算法（即根据相应比决定调入哪个作业进入内存，然后根据短作业优先算法决定处理哪个作业）

（1）列出各作业的执行时间，即列出每个作业运行的时间片段

（2）计算这批作业的平均周转时间

解：（1）10：00 J1到达，J1进入内存，P1执行

10：10 J2到达，J2进入内存，此时P1已经执行了10分钟，还需25分钟

10：15 J3到达，J3后备，此时P1还需20分钟

10：20 J4到达，J4后备，此时P1还需15分钟

10：30 J5到达，J5后备，此时P1还需5分钟

10：35 J1终止，P1完成，J4进入内存，P4执行

10：55 J4终止，P4完成，J3进入内存，P2执行

11：25 J2终止，P2完成，J5进入内存，P5执行

11：55 J5终止，P5完成，P3执行

12：40 J3终止，P3完成

作业	运行时间	周转时间（分钟）
J1	10：00-10：35	35
J2	10：55-11：25	75
J3	11：55-12：40	145
J4	10：35-10：55	35
J5	11：25-11：55	85

（2）这批作业的平均周转时间为：（35+75+145+35+85）/5=75分钟

第七章：主存管理

1、主存管理的主要功能：

（1）逻辑地址到物理地址的映射

（2）主存的分配和回收

（3）存储保护：保护进入主存的各道作业都在自己的存储空间内运行，互不干扰，防止一道作业由于发生错误而破坏其他作业或系统程序

（4）提高主存利用率：使多道程序能动态共享主存中的信息，如段式系统中，代码段是可共享的

（5）“扩大”主存容量：借助虚拟存储技术，为用户提供比主存空间大的地址空间

2、分区存储管理

固定分区：将内存用户区划分为若干固定大小的区域，每个区域中驻留一道程序

动态分区：根据用户程序的大小，动态对内存进行划分，可以提高内存的利用率

3、分区的分配和回收

（1）首次适应算法

空闲区队列中空闲区按地址从小到大排序

（2）最佳适应算法

空闲区队列中空闲区按大小从小到大排序

（3）最坏适应算法

空闲区队列中空闲区按大小从大到小排序

4、回收空闲块

上邻空闲区（空闲区总数不变）

下邻空闲区（空闲区总数不变）

上、下邻空闲区（空闲区总数减一）

上、下不相邻空闲区（空闲区总数加一）

5、什么时候进行拼接

回收一个分区时立即拼接，这样主存中总是只有一个连续的空闲区而无碎片，开销大

当找不到足够大的空闲区，而空闲区总和可以满足作业需求时拼接，开销小，但空闲区管理复杂

6、拼接技术的缺点：

拼接程序花费CPU时间

拼接时，必须停止所有的其他工作，对于交互用户，导致响应时间不规律；对于实时用户，由于不能及时响应而可能造成严重后果

有时为拼接所花费的系统开销要大于拼接技术带来的效益

当所有空闲区之和无法满足某一作业需求时，该作业永远无法运行

7、虚拟存储器的大小受以下因素限制：

一定容量的主存

大容量的辅存，存放多道程序

地址变换机构，如虚地址要放入地址寄存器，如果地址寄存器为32位，则虚存最大为2^32=4G

8、虚拟存储器的最大容量是由计算机系统的地址结构和外存空间决定的，即等于min（计算机地址，内存+辅存）

9、缺页中断与一般中断的区别：

缺页中断发生在指令的执行过程中，一般中断发生在指令周期之后

一条指令的执行可能有多次缺页中断

10、页表

页号

块号

中断位i

辅存地址

改变位

引用位

（1）中断位i：用来标示该页是否在内存

i=0：此页不在主存

i=1：此页不在主存，请求调入

（2）辅存地址：表示该页在辅存中的位置

（3）改变位：用来标示该页最近是否被修改过

改变位=0：表示该页最近未被修改过，淘汰时，该页不写回辅存

改变位=1：表示该页最近被修改过，淘汰时，该页需要写回辅存（全写法、写回法、写一次法）

（4）引用位：用来标示该页最近是否被访问过

引用位=0：表示该页最近没有被访问过

引用位=1：表示该页最近已被访问过

11、置换算法

（1）最佳算法（optimal算法）：淘汰的页面将是永不使用，或者是在最长时间内不再被访问的页面

（2）先进先出算法（FIFO算法）：总是选择在主存中居留时间最长的一页淘汰

（3）LRU算法：当需要淘汰一页时，选择最长时间未被使用的那一页淘汰掉

LRU近似算法（clock算法）：页表中每个主存块号有一个“引用位”，当某块中的页面被访问时，“引用位”置“1”，而页面管理程序周期性（设周期为T）地将所有“引用位”重新置“0”，这样，在T时间内，被访问页面的“引用位”为“1”，未被访问页面的“引用位”为“0”，当需要置换一页时，选择“引用位”为“0”的页淘汰掉

缺点：①T太大，可能所有块为“1”

②T太小，可能“引用位”为“0”的块相当多

③若缺页中断发生在页面管理程序将所有“引用位”清零时，有可能将常用的页面淘汰掉

12、抖动（颠簸）：导致系统效率急剧下降的主存和辅存之间的频繁页面置换现象

13、抖动的预防

1）采用局部置换策略

当进程发生缺页后，仅在自己的内存空间范围内置换页面，不允许从其它进程获得新的物理块

缺点：

（1）不能从根本上防止抖动的发生

该进程发生抖动后，会长期处于磁盘I/O的等待队列，从而影响了其他进程的缺页中断的处理时间

（2）当多道程序度偏高时，挂起一些进程

如：优先级低的缺页进程；剩余执行时间较大的进程等

（3）在调度程序中引入工作集算法（工作集又称驻留集：在某段时间间隔内，进程要访问的页面的集合，仅在每个进程在内存中都有足够大的驻留集时，才能从外存调入新的作业，这样，才不致因新作业的调入而导致缺页率的增加）

（4）L=S准则：用于调整多道程序的道数，使产生缺页的平均时间L等于处理缺页的平均时间S，此时，CPU的利用率最大

14、在页式系统中，若采用FIFO页面淘汰算法，会产生一种奇怪的现象，分配给作业的内存块越多，进程执行时的缺页率反而越高，也称为“Belady现象”

15、段表

段号

段长

段首址

中断位

辅存地址

引用位

改变位

RWEA

其他

（1）中断位i：用来标示该段所在位置

i=0：此段在内存

i=1：此段在外存

（2）辅存地址：表示该段在辅存中的位置

（3）改变位：用来标示该段最近是否被修改过

改变位=0：表示该段最近未被修改过，淘汰时，该段不写回辅存

改变位=1：表示该段最近被修改过，淘汰时，该段需要写回辅存（全写法、写回法、写一次法）

（4）引用位：用来标示该段最近是否被访问过

引用位=0：表示该段最近没有被访问过

引用位=1：表示该段最近已被访问过

RWEA：存取方式保护

R表示读权，W表示写权，E表示执行权，A表示可添加

16、段式和页式管理的比较

（1）每个段是一段有意义的信息，段长可动态增加；每个页的信息无意义，页长固定不变

（2）段式管理中以分段为单位交换，页式管理中需多次缺页中断才能把所需信息完整调入内存

（3）段式便于对具有完整逻辑功能的信息段进行共享，而页式管理的共享实现较难

（4）段式管理便于实现动态链接，可用段名加上段入口地址等方法在执行过程中调入相应的段进行动态链接

（5）段式系统便于共享和存储保护，但存在碎片问题，且每个段的长度受内存可用区大小的限制

（6）页式管理克服了碎片，但不利于共享

17、段页式管理

（1）要得到指令或数据的物理地址须经过二次访问主存：（访问段表，得到页表起始地址；访问页表，得到主存块号）

（2）中断位在页表设置，存取保护在段表设置

（3）引用位、修改位在页表设置

（4）不同进程的段表中，如果段号指向相同的页表地址，则可以实现该段的共享

18、页和页表

（1）内存划分为大小相同的块

（2）每个区划分为大小相同的页面，典型的页面大小为1KB、2KB或4KB

（3）块的大小=页的大小

（4）页可以在内存中不连续存放，所以需要为每个区建立一个页表

19、在一个页式虚拟存储内存管理系统中，页面大小为1K字节，某个进程分配到的内存块数为3，并按下列地址顺序引用内存单元：1200，2152，1865，0506，4536，1396，0030，3300，0733，1860，上述数字均为十进制数，且开始时内存中尚未装入任何页，试用先进先出（FIFO）和最近最久未使用（LRU）两种置换算法，分别计算程序访问过程中所发生的缺页率

解：根据页面大小和引用单元地址，请求页面的应用次序为：1，2，1，0，4，1，0，3，0，1，当分配的内存块数为3时，采用FIFO和LRU置换算法的页面载入及替换情况如下：

FIFO算法：

页面号	1	2	1	0	4	1	0	3	0	1
内存块1	1	2	2	0	4	1	1	3	0	0
内存块2		1	1	2	0	4	4	1	3	3
内存块3				1	2	0	0	4	1	1
是否发生缺页	×	×		×	×	×		×	×

缺页率：7/10=70%

LRU算法：

页面号	1	2	1	0	4	1	0	3	0	1
内存块1	1	2	1	0	4	1	0	3	0	1
内存块2		1	2	1	0	4	1	0	3	0
内存块3				2	1	0	4	1	1	3
是否发生缺页	×	×		×	×			×

缺页率：5/10=50%

20、某计算机系统采用二级页表的分页存储管理方式，虚拟地址格式如下所示：

10位	10位	12位
页目录号	页表索引	页内地址

回答下列问题：

（1）逻辑地址的页（页面）大小和物理地址的块（页框）大小各为多少？进程的虚拟地址空间大小为多少页？

（2）若某指令周期内先后访问了虚拟地址0100 0000H和0111 2048H，则进行地址转换时共访问了多少个二级页表？要求说明理由

解：（1）逻辑地址的页大小和物理地址的块大小各为4KB，进程的虚拟地址空间大小为2^32B，含有2^32/2^12=2^20页

（2）只需要访问一个二级页表，因为虚拟地址0100 0000H和0111 2048H的最高10位的值都是4，访问的是同一个二级页表

21、某计算机采用二级页表的分页存储管理方式，按照字节编址，页大小为2^10字节，页表项为2字节，逻辑地址结构为：

页目录号P1

页号P2

页内偏移地址w

逻辑地址空间大小为2^16页，则整个逻辑地址空间的页表目录中包含的表项数是多少？

解：因为页大小为2^10字节，页表项为2字节

故：页表项数为2^10/2 = 2^9，即页号P2为9位

因为逻辑地址空间大小为2^16页，所以P1+P2=16位，即P1=7位

故：页表目录中包含的表项数为2^7=128项

22、已知一个采用了LRU置换算法的虚拟页式存储管理系统，其页面尺寸为4KB，内存访问速度为100ns/次，快表访问速度为20ns/次，缺页中断处理时间为25ms/次，今有一个长度为30KB的进程进入系统，分配给该进程的内存块有3块，进程的所有页面都是在该进程运行中动态装入，若访问快表的命中率为20%，对于下属页面号访问序列：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

请问：（1）该进程有多少个页面？

（2）计算平均有效访存时间为多少？

解：（1）该进程有30KB/4KB=7.25，故页面数为8

（2）LRU算法：

页面号	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
内存块1	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
内存块2		7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0
内存块3			7	0	1	2	2	3	0	4	2	2	0	3	3	1	2	0	1	7
是否缺页	×	×	×	×		×		×	×	×	×			×		×		×

平均有效访存时间T=（1-p）*ma+p*缺页中断处理时间

其中，p为缺页率，ma为不缺页的平均访问时间

p=12/20=0.6

ma=（20+100）0.2+（100+100）*0.8=184ns

T=0.4*0.184+0.6*25000=15000.0736μs

23、在一请求分页系统中，页面大小为1K，一作业共有7个页面，为作业分配4个物理块，其中页面0，1，2，3分别装入到物理块2，6，4，1中

试写出页面3中的语句MOV AX，[2700]在执行过程中的地址变换的过程

若作业的页面走向为0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 2，并采用LRU页面置换算法，试计算缺页中断次数

解：（1）逻辑地址LA=2700=1K*2+652可知页号为2，页内偏移W=652

查页表可知页块号为4

物理地址pa=1K*4+652=4748

（2）LRU算法

页面号	0	1	2	3	2	1	3	2	5	2	3	6	2	1	4	2
内存块1	0	1	2	3	2	1	3	2	5	2	3	6	2	1	4	2
内存块2		0	1	2	3	2	1	3	2	5	2	3	6	2	1	4
内存块3			0	1	1	3	2	1	3	3	5	2	3	6	2	1
内存块4				0	0	0	0	0	1	1	1	5	5	3	6	6
是否缺页									×			×		×	×

已知页面0 1 2 3已经装入内存，故一共产生缺页中断4次

24、有一矩阵：VAR A:ARRAY[1..100，1..100]OF integer；按先行后列次序在辅存存储，在一个虚拟系统中，采用LRU淘汰算法，一个进程有3块内存空间，可以存放200个整数，其中第一块存放次序，且假定次序已经在内存

程序A：FOR i:=1 TO 100 DO

FOR j:=1 TO 100 D0

A[i,j]:=0

程序B：FOR j:=1 TO 100 DO

FOR i:=1 TO 100 D0

A[i,j]:=0

分别就程序A和B的执行过程计算缺页次数

解：数组A共有100*100个变量，每页可存放200个，共占100*100/200=50页

程序A对页面的访问顺序：

发生缺页中断次数为50次

程序B对页面的访问顺序：

发生缺页中断次序为50*100=5000次

第八章：输入输出管理

1、I/O设备的分类

1）按操作特性分类：

（1）存储设备：存储信息的设备

（2）I/O设备：向CPU输入信息和输出经加工处理的信息

2）按信息交换单位分类（如UNIX系统采用）

（1）字符设备：信息传送的单位是字节

（2）块设备：信息传送的单位是块，如512B整数倍/块

3）按共享属性分类：

（1）独占设备：在一段时间内只允许一个进程访问的设备，如打印机

（2）共享设备：在一段时间内可允许多个进程访问的设备，如磁盘

（3）虚拟设备：通过虚拟技术将一台独占设备变换为若干台逻辑设备，供若干个用户使用，通常将经过虚拟技术处理后的设备称为虚拟设备，如虚拟打印机

2、I/O设备管理的功能（目标：方便用户的使用，提高设备利用率）

1）状态跟踪：由设备控制块（DCB）动态记录设备状态的变化及有关信息

2）设备存取与分配：按照设备类型和相应的分配算法，决定将I/O设备分配给哪一个要求该设备的进程：

（1）静态分配：作业进入系统时就进行分配，退出系统时就收回全部资源

（2）动态分配：进程需要使用某设备而提出申请时进行分配，使用完毕后立即将其收回

3）设备控制：将用户的I/O请求转换为设备能识别的I/O指令，并实施设备驱动和中断处理工作，主要由设备驱动程序完成

4）实现其它功能：缓冲区的管理；实现设备的独立性

3、设备独立性：是指用户在编制程序时所使用的设备与实际使用的设备无关，也就是用户程序中仅仅使用逻辑设备名

4、设备独立性的优点：

（1）屏蔽了设备的物理特性，方便用户使用

（2）改善了资源的利用率

（3）提高了系统的可扩展性和可适应性

5、设备控制块：是记录设备的硬件特性、链接和使用情况等信息的数据结构，当设备装入系统时，DCB被创建，基本内容由：

1）设备名

2）设备属性：描述设备现行状态的一组属性，如：

（1）传输速度

（2）工作方式：如全双工，半双工

（3）校验方式：如奇偶校验、CRC校验

（4）延迟时间

3）指向命令转换表的指针：每个I/O请求都要转换成调用一个能执行I/O操作的设备例程

4）在I/O总线上的设备地址：每个设备都有地址，可以采用统一编址，也可以采用单独编址

5）设备状态：如设备控制器或通道，忙或空闲

6）当前用户进程指针：当前正在使用该设备的进程

7）I/O请求队列指针：指向因请求设备而未得到满足的进程队列

6、缓冲区：在内存中划出一块存储区，专门用来临时存放I/0数据

7、在OS中引入缓冲的主要原因

（1）缓和CPU和I/O设备间速度不匹配的矛盾

（2）减少对CPU的中断频率，放宽对中断响应时间的限制（eg.假设每传送1bit便中断1次，如果增加一个8位的寄存器，当传输1B时才中断1次，否则需要中断8次）

（3）提高CPU和I/O设备的并行性

8、缓冲技术分为：

（1）单缓冲

（2）双缓冲：为输入或输出分配两个缓冲区，交替使用，使CPU与设备的并行操作进一步提高

（3）环形缓冲

（4）缓冲池：从主存中分配一组缓冲区组成缓冲池；为了提高缓冲区的利用率，广泛采用公共缓冲池，池中缓冲区可供多个进程共享；使用缓冲池的主要原因是避免消费者多次访问相同的数据时会重复产生相同数据的问题

9、缓冲区按使用情况分类：

（1）空缓冲队列

（2）输入队列：由装满输入数据的缓冲区所链成的队列

（3）输出队列：由装满输出数据的缓冲区所链成的队列

10、设备分配方式及安全性：

1）静态分配是作业开始执行之前，由系统一次分配该作业所要求的全部设备，直到该作业被撤销，独占设备一般采用静态分配，但设备的使用效率低，由于破坏“部分分配条件”，静态分配方式不会出现死锁

2）动态分配是进程在执行过程中需要设备时，通过系统调用命令像系统提出设备请求，系统按照分配策略实施分配，一旦I/O完成，就释放该设备，共享设备采用动态分配方法，有利于提高设备利用率

（1）当进程发出I/O请求后，便立即进入阻塞状态，直至I/O请求完成后才被唤醒，此时，一个进程只能提出一个I/O请求，因而它不可能同时操作多个外部设备，由于破坏了“环路条件”，因此不会死锁

（2）允许某些进程发出I/O请求后仍可继续运行，且在需要时又可发出多个请求，仅当进程所请求的设备为另一个进程占用时，才进入阻塞状态，在一个进程同时操作多个设备的情况下是有可能出现死锁的

11、SPOOL技术（外设联机同时操作技术、假脱机技术）

1）预输入：在作业执行之前，OS已将作业信息通过独占设备预先输入到磁盘上，称为“预输入”，此后，作业执行使用数据时，不必再启动独占设备读入，而只要从磁盘输入数据就可以了

2）缓输出：在作业执行时，也不必直接启动独占设备输出数据，而只要将作业输出数据写入磁盘中存放，在作业执行完毕后，由OS来组织信息输出，称为“缓输出”

3）特点：

（1）提高了I/O速度，缓和了CPU与低速I/O设备的矛盾

（2）将独占设备改造为共享设备

（3）实现了虚拟设备功能

12、I/O控制方式：

（1）程序循环测试I/O方式

（2）中断方式

（3）DMA方式

（4）通道方式

13、控制设备I/O工作的核心模块称为设备驱动程序，设备驱动程序与设备类型是一一对应的，对于某一类设备，OS具有相同的设备驱动程序

14、设备驱动程序包括：

（1）I/O接口程序：把逻辑设备映射为相应的物理设备，检查提供给它的参数的正确性，启动所需要的服务

（2）I/O处理进程：从I/O请求队列中取出iorb，启动相应的I/O操作，然后进入等待状态，直至I/O完成，当设备的I/O完成后，发出中断信号，启动中断服务程序，进行数据的传送，然后唤醒I/O处理进程，由I/O处理进程把数据送到目的地，然后，删除此iorb，唤醒请求I/O的用户进程（I/O处理进程一般处于阻塞状态）

（3）中断服务程序：可以由硬件厂商提供；由程序设计人员完成

15、磁盘调度算法：

（1）先来先服务（FCFS）：按进程访问磁盘的先后次序进行调度（缺点：未对寻道进行优化）

（2）最短寻道时间优先（SSTF）：选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象（缺点：某些进程的请求总也得不到服务）

（3）扫描算法（SCAN）（电梯调度算法）：在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象

（4）循环扫描算法（CSCAN）：它规定磁头单向移动

16、在某个运行时刻，有如下表示的磁盘访问的请求队列，假设磁头当前在第15个柱面，磁头移动方向为从小到大：

请求序列	柱面号
1	15
2	20
3	9
4	16
5	24
6	13
7	29

请给出：

（1）最短寻道时间优先算法和电梯调度算法的柱面移动数

（2）分析OS并不采用效率更高的最短寻道时间优先法的原因

解：（1）SSTF算法：

请求柱面号排序	下一个磁道号	移动磁道数
9	20	11
13	9	4
->15	16	1
16	13	3
20	24	4
24	29	5
29

总共柱面移动数为28道

SCAN算法：

请求柱面号排序	下一个磁道号	移动磁道数
9
13	9	4
->15	16	1
16	20	4
20	24	4
24	29	5
29	13	16

总共柱面移动数为34道

（2）由于磁头在读写操作的过程中可能不断有新的读写柱面的请求加入，最短寻道时间优先算法会使柱面两端的请求处于“饥饿态”，故一般不采用最短寻道时间优先法，电梯调度算法比较公平

17、多道程序系统中，供用户使用的内存空间有100KB，磁带机2台，打印机1台，系统采用可变式分区分配方式管理内存，对磁带机和打印机采用静态分配方式，并假设输入/输出操作的时间忽略不计。现有一作业序列如下：

作业号	到达时间	要求计算时间	要求内存量	申请磁带机数	申请打印机数
1	8：00	25min	15K	1台	1台
2	8：20	10min	30K	-	1台
3	8：20	10min	60K	1台	-
4	8：30	20min	20K	1台	-
5	8：35	15min	10K	1台	1台

假设作业调度采用FCFS算法，优先分配内存的底地址区域且不准移动已在内存中的作业，在内存中的作业平分CPU时间，试问：

（1）作业调度的次序是什么？

（2）写出所有作业的周转时间。

解：（1）

8：00 J1到达，J1进入内存，P1执行，磁带机还剩一台

8：20 J2到达，J2后备

????????J3到达，J3进入内存，P1、P3分时执行

????????P1已执行20分钟，还需5分钟

????????此时还剩磁带机0台，打印机0台

8：30 P1终止，J1完成

????????P3已执行5分钟，还需15分钟

????????归还设备，此时还剩磁带机1台，打印机1台

?????????J4到达，J4进入内存，P3、P4分时执行

?????????此时还剩磁带机0台，打印机1台

8：35 J5到达，J5后备

9：00 P3终止，J3完成

????????P4已执行15分钟，还需5分钟

????????归还设备，此时还剩磁带机1台，打印机1台

????????J2进入内存，P2、P4分时执行

????????此时还剩磁带机1台，打印机0台

9：10 P4终止，J4完成

????????P2已执行5分钟，还需5分钟

????????归还设备，此时还剩磁带机2台，打印机0台

9：15 P2终止，J2完成

????????归还设备，此时还剩磁带机2台，打印机1台

????????J5进入内存，P5执行

9：30 P5终止，P5完成

故：作业调度的次序是1、3、4、2、5

（2）

作业1的周转时间为：8：30-8：00=30min

作业2的周转时间为：9：15-8：20=55min

作业3的周转时间为：9：00-8：20=30min

作业4的周转时间为：9：10-8：30=40min

作业1的周转时间为：9：30-8：35=55min

第九章：文件系统

1、文件是具有文件名的且在逻辑上具有完整意义的信息的集合

2、文件系统是OS中负责管理和存取文件信息的软件机构，它由管理文件内所需的数据结构（如文件控制块、目录表、存储分配表）和相应的管理软件，以及访问文件的一组操作所组成

3、文件系统的功能：

（1）用户可以对文件进行操作，如：创建、删除、读写文件等

（2）可以共享彼此的文件，如链接

（3）提供存取控制，如R、W、X等权限

（4）实现辅存空间的自动管理

（5）按文件名访问

（6）提供后备与复原能力，如回收站

（7）保密功能，如文件口令、文件加密

（8）界面友好

4、文件的逻辑结构：这是从用户观点出发，所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于物理特性

5、文件的物理结构：是指文件在外存上的存储组织形式，它与存储介质的存储特性有关，存储介质通常划分为大小相同的物理块，物理块是分配和存储信息的基本单位，如磁盘块的大小是512B的整数倍（1KB/块、4KB/块），为便于管理，一般也把文件信息划分为与物理块大小相等的逻辑块

6、文件的逻辑结构可以分为：

1）记录式文件（有结构的文件）：由一组相关记录组成，记录的长度可分为定长和不定长两类：

（1）定长记录文件：文件中所有记录的长度都是相同的，如数据库中的表文件

（2）不定长记录文件：文件中各记录的长度不尽相同

2）流式文件（无结构的文件）：流式文件是相关的有序字符的集合，文件的长度即为所含字符数，如C语言的源程序、写字板的.TXT文件等

7、文件的存取方式：

（1）顺序存取：如磁带文件

（2）随机存取：如磁盘文件

8、文件的物理结构可分为：

（1）连续文件：将文件信息依次存放在外存连续的物理块中（特点：顺序存取速度快，但文件存储要求连续的存储空间，会产生碎片，同时也不利于文件的动态扩充）

（2）串联文件：文件存储的物理块不必连续，在每个物理块的最后一个字做为指针，指向下一个物理块的位置（特点：没有外存碎片，动态增删比较方便，但串联文件只能按照文件的指针顺序访问，因而查找效率较低）

（3）索引文件：为了能随机的访问文件的任何一部分，可以采用索引文件结构，每个文件需建立一个索引表，索引表中的每个表项为文件的逻辑块号和与之对应的物理块号（可以存储文件的最大长度=直接寻址+一次间址+二次间址+三次间址）（如何提高存储文件的最大长度？系统安装时增加磁盘块的大小，如4KB、8KB或16KB）

9、索引文件在存储区占两个区，索引区和数据区，访问索引文件的步骤：

（1）查索引表，由逻辑块号得物理块号

（2）由物理块号访外存获得所要求的信息

（3）特点：可以随机访问，易于进行文件的增删，但索引表的使用增加了存储空间的开销，文件操作需要两次访问外存

10、文件映照结构（文件分配表FAT）

引导块

文件目录区

文件映照图（文件分配表）

数据区

（1）系统有文件映照图，图中每个表项用来记录磁盘块号（勾链字）

（2）每个文件的文件目录项中，用户描述文件物理结构的表项指向文件映照图的某个位置，其内容为该文件的第一块的块号，其后的各块在文件映照图中依次勾链，文件的最后一块用尾标记表示

（3）特点：存储链指针需要一定的存储空间，文件映照图一般比较大，不宜保存在主存，在最坏情况下，可能要把整个文件映照图全部读入主存，才能找到文件在磁盘中的所有物理块，所以，把文件所占的磁盘空间尽量靠近是有利的，而不应将文件散布在整个磁盘上（如定期做碎片整理工作）

11、文件存储空间的管理实质上是空闲块的组织与管理等，它包括空闲块的组织、分配和回收等

12、空闲文件目录（空闲表）：

（1）思想：外村上一片连续的空闲区可以看成是被一个空闲文件所占用，系统为所有的空闲文件单独建立一个目录，表目中的内容包括第一个空闲块的地址和空闲块的个数

（2）空闲文件目录方法适用于连续文件的分配和回收

（3）空闲文件目录的分配和回收与内存管理中的分区存储管理的空闲块的分配和回收类似

（4）缺点：当空闲块较碎时，会造成表很大，从而影响文件分配时查找表的速度；另外还存在碎片问题

13、空闲块链：

（1）思想：把文件存储设备上所有的空闲块链接在一起，当申请者需要空闲块时，分配程序从链头开始摘取所需要的空闲块，然后调整链首指针，当回收空闲块时，把释放的空闲块插入链中

（2）方法一：每个空闲块中包含指向下一空闲块的指针（特点：每申请一块都要读出空闲块并取得指针，申请多次时读盘）

（3）方法二：将空闲块号组成空闲块链，每个结点的内容包括：当前（或下一个）空闲块号和指向下一个结点的指针

14、位示图：（大小=磁盘容量/磁盘块大小/8）

（1）思想：每个磁盘块都对应1bit，“1”表示已分配，“0”表示未分配

（2）利用位示图来进行空闲块分配时，只需查找图中的“0”位，并将其置为“1”位，反之，回收时，只需把相应的位由“1”改为“0”即可

（如何减少位示图的大小？增加磁盘块的大小）

15、UNIX空闲块的管理（成组链接法）

（1）UNIX的文件系统（文件卷）由四个部分组成：

引导块

管理块

索引节点区

数据区

……

管理块（也称超级块），它记载着文件卷的使用情况

（2）思想：从尾向前，空闲块每100块一组，最后一组99块，其余的就是直接管理的盘块号和盘块数，放入S_free[]和S_nfree中，每一组的最后一块作为索引表，用来登记下一组100块的盘块号和盘块数

（3）假设空闲块数为N，那么组数=int(N/100)+1直接管理的空闲块数=(N mod 100)+1

16、文件目录

（1）是一张记录所有文件的名字及其存放地址的目录表，表中还应包括文件的说明和控制方面的信息

（2）文件控制块（FCB）的有序集合即为文件目录

17、UNIX的FCB内容（索引节点或i节点）

1）文件所有者标识：

（1）i_uid：文件的所有者号

（2）i_gid：文件所属组号

2）文件类型（i_type）：

（1）d：目录文件

（2）-：普通文件（正规文件）

（3）b：块设备文件

（4）c：字符设备文件

（5）p：管道文件

3）文件存取权限（i_mode）：

系统按用户、用户组、其它用户三类对文件进行保护，每类都具有R、W、X的存取权，并且可以用chmod命令进行设置，默认权限：普通文件（664），可执行文件（775）

4）文件链接计数（i_link）：

初值为1，同一文件系统中每建立一个硬链接，i_link+1；删除一个文件时，i_link-1，当i_link=0时，才能真正删除该文件（链接文件和被链接文件具有相同的i节点号）

5）文件存取时间(i_time)

（1）i_atime：最后一次访问时间

（2）i_mtime：最后一次修改时间

（3）i_ctime：创建时间

6）文件长度：i_size

7）磁盘地址索引表：i_addr[13]

（在i节点中缺少文件的什么信息？该信息放在何处？缺少文件名，文件名在数据区）

18、一级文件目录：为了实现“按名存取”的功能，在整个文件系统中只建立一张目录表，每个文件占一项表目，主要由文件名和文件说明信息组成。一级目录结构易于实现，管理简单，但当系统中文件数增多时，查找时间较长，且易于发生重名问题

19、二级文件目录（二级目录可以解决重名问题，并可获得较高的查找速度；但二级目录缺乏灵活性，无法反映真实世界复杂的文件结构形式，如：一个用户不能定义同名文件）

将文件目录分成主文件目录和用户文件目录两级

（1）主文件目录（MFD）：记录用户名及相应用户目录所在的储存位置

（2）用户文件目录（UFD）：登记该用户的文件控制块的信息

20、多级文件目录（树形目录结构）：

1）在多级目录结构中，第一级目录称为根目录，目录树中非叶节点称为子目录，叶节点为文件

2）在多级目录中，用户要访问某个文件时，需要指出访问路径，从根目录出发的路程称为绝对路径，从当前目录出发的路径称为相对路径

3）当采用多级目录组织后，不同用户可以给不同文件起相同的名字，可以把文件组织的有条有理，非常便于管理

4）文件目录的查询方法：

（1）线性检索算法

（2）哈希检索算法：即目录信息存放在一个哈希表中（冲突）

（3）采用B+树存储目录信息，可以使磁盘访问次数减少到最小

21、文件共享：是指某一个或某一部分文件可以让实现规定的某些用户共同使用（例如：基于索引节点的文件共享）

22、文件的安全（文件保护机制）：

（1）设置文件的存取权限

（2）口令

（3）加密技术

23、文件操作：文件系统提供一组使用文件的系统调用

（1）打开文件：把该文件的有关目录表复制到主存中约定的区域，建立用户和这个文件的联系

（2）关闭文件：系统将其在主存中相应的目录表删去，切断用户与该文件的联系；若在文件打开期间，该文件做过某种修改，则应将其写回辅存

24、文件的备份：为了能在软、硬件失效的意外情况下恢复文件，保证数据的连续可用性，文件系统应当提供适当的机构，以便复制备份，建立文件拷贝的基本方法由两种：

1）周期性转储（全量转储）：按固定的时间周期把外存中所有的文件的内容转存到某种介质上，在系统失效时，使用这些转存磁带或磁盘，将所有文件重新建立并恢复到最后一次转存时的状态

（1）缺点：费时，在转储过程中要停止使用文件系统

（2）优点：把文件进行重新组合，使分散分布的文件变为连续分布

2）增量转储：每隔一段时间，将上次转储后修改过的文件和新增加的文件转储到某种介质上，实际工作中，两种转储方式常配合使用，当文件系统失效时，可以采用的恢复办法：

（1）从最近一次的全量转储盘中转入全部系统文件，使系统得以重新启动，进行后续的恢复操作

（2）从最近一次全量转储盘中恢复所有数据文件

（3）由近及远从增量盘上恢复文件

25、某个文件系统中，外存为硬盘，物理块大小为512字节，有文件A，包含589个记录，每个记录占255个字节，每个物理块放2个记录，文件A所在的目录如图所示，文件目录采用多级树型目录结构，由根目录节点、作为目录文件的中间结点和作为信息文件的树叶组成，每个目录项占127字节，每个物理块放4个目录项，根目录的第一块常驻内存

（1）若文件的物理结构采用链式存储方式，链占2个字节，那么要将文件A读入内存，至少需要存取几次硬盘？

（2）若文件为连续文件，那么要读文件A的第487个记录至少要存取几次硬盘？

（3）一般减少读盘次数，可采用什么措施？此时可减少几次存取次数？

解：（1）文件589个记录，每个物理块2个记录，共需要295个物理块

需存取4+295=299或3+295=298次硬盘

（2）第487个记录在第244块中，需存取4+244=248次硬盘

（3）减少目录，将A放在根目录下，可减少3次