操作系统复习提纲

忘是亡心i 2023-01-02 07:30 143阅读 0赞

**图也没有，我复习用的。将就看吧，不排版了**

操作系统复习  
第一章 概述  
1、操作系统的概念、基本类型、基本特征、基本功能、管态/目态；

2、操作系统的目标、作用、结构设计方法；  
第二章 进程管理  
1、多道程序设计技术（多道程序设计技术是在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制下，相互穿插运行）；  
2、进程的概念、特征、基本状态及与程序的区别和联系；  
(1).为什么要引入进程:并发运行的程序相互制约  
(2).进程的概念:可并发执行的程序在一个数据集合上的一次执行过程。进程是进程实体的一次动态运行过程，是系统进行资源分配和调度的一个基本单位。  
(3).特征:  
(1)动态性——进程是程序在处理机上的一次执行过程。具有生命期。  
(2)并发性——多个进程实体同存于内存中，在一段时间内同时运行。以提高资源利用率。  
(3) 独立性— 进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位，而程序则不是。  
(4) 异步性–进程按各自独立的、不可预知的速度向前推进。  
(5) 结构性— 进程控制块(PCB)+程序段+相关的数据段=进程实体。

(4)进程和程序区别:

(4) .进程的三个基本状态  
(1).进程的基本状态-三态模型  
•执行态（running）：进程占有处理器正在运行。  
•就绪态（ready）：进程具备运行条件，等待系统分配处理器以便运行。  
•阻塞态（block）：又称为等待（wait）态或睡眠（sleep）态，进程不具备运行条件，正在等待某个事件的完成。

•运行态→阻塞态：等待使用资源或某事件发生；  
•阻塞态→就绪态：资源得到满足或事件发生；  
•运行态→就绪态：运行时间片到；  
出现有更高优先权进程。  
•就绪态→运行态：CPU空闲时选择一个就绪进程。  
(2)五态模型  
新建态—对应进程刚被创建的状态。  
终止态—进程的终止状态。

(3).七态模型  
(1)为什么要有“挂起”状态?  
由于进程的不断创建，系统资源已不能满足进程运行的要求，就必须把某些进程挂起（suspend），对换到磁盘镜像区中，暂时不参与进程调度，起到平滑系统负载的目的。  
•挂起就绪态（ready suspend）：表明进程具备运行条件但目前在辅助存储器中，当它被对换到主存才能被调度执行。  
•挂起等待态（blocked suspend）：表明进程正在等待某一个事件且在辅助存储器中。

• 该进程不能立即被执行。  
• 挂起进程可能会等待事件，但所等待事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件。  
• 进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行。  
• 结束进程挂起状态的命令只能通过操作系统或父进程发出。

3、PCB的概念、前趋图、进程图(进程图上题三个模型)；  
(1).PCB的概念:进程控制块,存放进程的管理和控制信息的数据结构.( 进程控制块是进程存在的唯一标志。  
)  
它是管理和控制的进程最重要的数据结构，在创建时，建立PCB，并伴随进程运行的全过程，直到进程撤消而撤消。PCB就象我们的户口。  
系统的所有PCB组织成链表或队列，常驻内存的PCB区。

了解**进程控制块中的信息**

1.  进程标识符信息  
    每个进程都必须有一个唯一的标识符  
    内部标识符：便于系统使用  
    外部标识符：便于用户使用
2.  处理机状态信息  
    处理机状态信息主要由处理机的各种寄存器中的内容组成。处理机运行时的信息存放在寄存器中，当被中断时这些信息要存放在PCB中。
3.  进程调度信息  
    进程优先级  
    进程调度所需的其他信息  
    事件  
    进程状态
4.  进程控制信息  
    程序和数据的地址  
    进程同步和通信机制  
    资源清单  
    链接指针

前趋图是一个有向无环图 (DAG-Directed Acyclic Graph)，用于描述进程之间执行的前后关系。

结 点 ： 描述一个程序段或进程，  
或一条语句。  
有 向 边： 结点之间的前趋关系“”  
Pi  Pj ：Pi 必须在 Pj 开始之前完成， Pi是Pj的直接前趋，Pj是Pi的直接后继  
初始结点: 没有前趋的结点  
终止结点: 没有后继的结点  
注意：前趋图中绝对不能出现循环！！！

4、原语的概念及进程控制原语的种类；  
\*\*进程控制是操作系统的内核通过原语来实现的。  
进程的创建与终止  
进程的阻塞与唤醒  
进程的挂起与激活

\*\*控制原语的种类:关锁：Lock(W)开锁：unLock(W) Wait操作 wait(S) Signal操作 signal(S)

1.  直接通信方式  
    通信原语：  
    Send(Receiver, message);发送一个消息给接收进程  
    Receive(Sender, message);接收Sender发来的消息

(1).原语(primitive)：由若干条指令构成的“原子操作(atomic operation)”过程，作为一个整体而不可分割－－要么全都完成，要么全都不做。许多系统调用就是原语。  
特征:“不可中断性”!

5、进程的同步与互斥的概念、临界资源与临界区的概念；  
同步是进程间共同完成一项任务时直接发生相互作用的关系！ 同步进程间具有合作关系,在执行时间上必须按一定的顺序协调进行  
互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系！ 互斥进程彼此在逻辑上是完全无关的它们的运行不具有时间次序的特征  
\*\*临界资源：一次仅允许一个进程使用的共享资源！如：打印机、磁带机、共享表格、共享变量等。  
\*\*临界区：每个进程中访问临界资源的那段程序！  
进程必须互斥进入相关临界区！

6、信号量及其应用；  
【典型题举例】系统中有三个进程GET、PRO和PUT，共用两个缓冲区BUF1和BUF2。  
假设BUF1中最多可放11个信息，现已放入了两个信息；BUF2最多可放5个信息，目前为空。  
GET进程负责不断地将输入信息送入BUF1中，PRO进程负责从BUF1中取出信息进行处理，并将处理结果送到BUF2中，PUT进程负责从BUF2中读取结果并输出。  
试写出正确实现GET、PRO、PUT的同步与互斥的算法（要求：（1）用类C语言描述，条理清楚，注释恰当；（2）信号量原语统一使用wait和signal）。

图1 进程合作

Semaphore e1=9,p1=2,e2=5,p2=0;  
Main()\{  
Cobegin  
Get();  
Pro();  
Put();  
coend  
\}  
Get  
While(1)\{  
Wait(e1);  
Put in buf1;  
Signal(p1);\}  
Pro  
Wait(p1);  
Get from buf1;  
Signal(e1);  
Wait(e1);  
Put in buf2  
Signal(p2);  
Put  
Wait(p2)  
Get from buf2  
Signal(e2)

生产围棋的工人不小心把相等数量的黑子和白子混装在一个箱子里，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：  
（1）进程A专门拣黑子，进程B专门拣白子；  
（2）每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子；  
分析：  
　　第一步：确定进程间的关系。由功能（2）可知进程之间是互斥的关系。  
　　第二步：确定信号量及其值。由于进程A和进程B要互斥进入箱子去拣棋子，箱子是两个进程的公有资源，所以设置一个信号量s，其值取决于公有资源的数目，由于箱子只有一个，s的初值就设为1。

semaphore s=1;  
　　main()\{  
　cobegin\{  
　　　　process A：while(1)\{  
　　　　 Wait(s);  
　　　　　 拣黑子；  
　　　　　 Signal(s);  
　　　　　 \}  
　　　　process B：while(1)\{  
　　　　 Wait(s);  
　　　　　 拣白子；  
Signal(s);  
\}  
　　　\}coend  
\}  
　semaphore s=1;  
　　main()\{  
　cobegin\{  
　　　　process A：while(1)\{  
　　　　 Wait(s);  
　　　　　 拣黑子；  
　　　　　 Signal(s);  
　　　　　 \}  
　　　　process B：while(1)\{  
　　　　 Wait(s);  
　　　　　 拣白子；  
Signal(s);  
\}  
　　　\}coend  
\}  
某车站售票厅共有20 个售票窗口，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需要在外面等待。每个购票者可看成一个进程。  
第一步：确定进程间的关系：售票厅是各进程共享的公有资源，当售票厅中多于20名购票者时，厅外的购票者需要在外面等待。所以进程间是互斥的关系。  
第二步：确定信号量及其值：只有一个公有资源-售票厅，所以设置一个信号量s。售票厅最多容纳20个购票者，即可用资源实体数为20，s的初值就设为20。  
　　semaphore s=20;  
　　main()\{  
cobegin\{  
　　　 process Pi(i=1,2,……)()\{  
　　　　 Wait(s);  
　　　　　进入售票厅；  
　　　　　购票；  
　　　　　退出；  
　　　　　Signal(s);  
　　　　\}  
　　　\}coend  
\}

例5：图书馆问题  
图书馆有100个座位，有一张登记表，要求：  
阅读者进入时登记，取得座位号；  
出来时，注销(注销也要使用登记表)；  
登记表同时只能由一个人使用；  
用信号量描述一个读者的使用过程。  
信号量SN：表示可用座位数，初值为100；  
信号量mutex：表示登记表是否正在使用，初值为1；  
Reader(int i)  
\{ Wait(SN)；  
Wait(mutex)；  
登记；  
Signal(mutex)；  
阅读;  
Wait(mutex);  
注销；  
Signal(mutex);  
Signal(SN);  
\}

用信号量实现简单同步  
同步（私有）信号量：  
用于实现进程间的同步，初值为0或为某个正整数n，仅允许拥有它的进程对其实施Wait操作。  
Signal操作由其合作进程来实施！

设2个信号量：  
empty—空缓冲区数（初值为1）  
full—满缓冲区数（初值为0）

供者进程  
while(1)  
\{ Wait（empty）;  
将信息送  
入缓冲区；  
Signal（full）;  
\}

用者进程  
while(1)  
\{ Wait（full）;  
从缓冲区  
取出信息；  
Signal（empty）;  
\}

例：有3个进程PA，PB和PC合作解决文件打印问题：  
PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录;  
PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；  
PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。  
要求：请用信号量机制来保证文件的正确打印。

设置4个信号量：empty1, empty2,full1,full2.  
empty1及empty2分别表示缓冲区1及缓冲区2是否为空，初值为1。  
full1，full2分别表示缓冲区1及缓冲区2是否有记录可供处理，其初值为0。

PA()  
\{While (1)  
\{ 从磁盘读一个记录；  
Wait(empty1);  
将记录存入缓冲区1；  
Signal(full1); \}\}

PB()  
\{While (1)  
\{ Wait(full1);  
Wait(empty2);  
将缓冲区1中的记录  
复制到缓冲区2；  
Signal(empty1);  
Signal(full2); \}\}

PC()  
\{While (1)  
\{Wait(full2);  
从缓冲区2取一个记录；  
Signal(empty2);  
打印记录;\}\}

semaphore empty1=1; empty2=1;full1=0;full2=0;  
main()  
\{ cobegin\{  
PA();  
PB();  
PC();  
\}coend \}

生产围棋的工人不小心把相等数量的黑子和白子混装在一个箱子里，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：  
（3） 当一个进程拣了一个棋子（黑子或白子）以后，必让另一个进程拣一个棋子（白子或黑子）。  
第一步：确定进程间的关系。由条件1、2、3可知，进程间的关系为同步关系。  
第二步：确定信号量及其值。进程A和B共享箱子这个公有资源，但规定两个进程必须轮流去取不同色的棋子，因而相互间要互通消息。对于进程A可设置一个私有信号量s1，该私有信号量用于判断进程A是否能去拣黑子，初值为1。对于进程B同样设置一个私有信号量s2，该私有信号量用于判断进程B是否能去拣白子，初值为0。  
semaphore s1=1,s2=0;  
main()  
\{ cobegin  
\{ PA();  
PB();  
\}coend \}  
PA()  
\{While (1)  
\{Wait(s1);  
拣黑子；  
Signal(s2);  
\}  
\}  
PB()  
\{While (1)  
\{ Wait(s2);  
拣白子；  
Signal(s1);  
\}  
\}

设信号量 :  
S1：是否允许司机启动汽车，初值为0  
S2：是否允许售票员开门，初值为0  
Driver()  
while (1)  
\{  
Wait(S1);  
启动汽车;  
正常行车；  
到站停车；  
Signal(S2); \}

Busman()  
while (1)\{  
关车门;  
Signal(S1)；  
售票；  
Wait(S2)；  
开车门；  
上下乘客；  
\}

semaphore s1=0, s2=0;  
main\{  
cobegin  
\{ Driver();  
Busman();  
\}coend  
\}  
生产者－消费者问题  
若干进程通过有限的共享缓冲区交换数据。其中，"生产者"进程不断写入，而"消费者"进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。

一个生产者，一个消费者，公用一个缓冲区 ；  
一个生产者，一个消费者，公用n个环形缓冲区 ；  
一组生产者，一组消费者，公用n个环形缓冲区

生产者进程  
while(TRUE)  
\{  
生产一个产品;  
Wait(empty);  
产品送往Buffer;  
Signal(full);  
\}

消费者进程  
while(TRUE)  
\{  
Wait(full);  
从Buffer取出一个产品;  
Signal(empty);  
消费该产品;  
\}

一个生产者，一个消费者，公用 n个环形缓冲区

Empty：表示缓冲区是否为空，初值为n。  
Full ：表示缓冲区是否为满，初值为0。  
设缓冲区的编号为1～n1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。  
生产者进程

while(TRUE)  
\{  
生产一个产品;  
Wait(empty);  
产品送往buffer（in）；  
in=(in+1)mod n；  
Signal(full);  
\}  
消费者进程

while(TRUE)  
\{  
Wait(full);  
从buffer(out)中取出产品；  
out=(out+1)mod n；  
Signal(empty);  
消费该产品;  
\}

Empty：表示缓冲区是否为空，初值为n。  
Full ：表示缓冲区是否为满，初值为0。  
Mutex1：生产者之间的互斥信号量，初值为1。  
Mutex2：消费者之间的互斥信号量，初值为1。

设缓冲区的编号为1～n1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。

生产者进程  
while(TRUE)  
\{  
Wait(empty);  
Wait(mutex1)；  
产品送往buffer(in)；  
in=(in+1)mod n；  
Signal(mutex1);  
Signal(full);  
\}  
消费者进程  
while(TRUE)  
\{  
Wait(full);  
Wait(mutex2)；  
从buffer(out)中取出产品；  
out=(out+1)mod n；  
Signal(mutex2)；  
Signal(empty);  
消费该产品;  
\}  
桌子上有一个水果盘，每一次可以往里面放入一个水果。爸爸专向盘子中放苹果，儿子专等吃盘子中的苹果。把爸爸、儿子看作二个进程，试用Wait/Signal操作使这二个进程能正确地并发执行。  
semaphore S\_PlateNum; // 盘子容量，初值为1  
semaphore S\_AppleNum; // 苹果数量，初值为0  
父亲进程  
while(TRUE)  
\{  
拿苹果；  
Wait(S\_PlateNum );  
往盘子中放入一个苹果；  
Signal(S\_AppleNum);  
\}  
儿子进程  
while(TRUE)  
\{  
Wait(S\_AppleNum);  
从盘中取出苹果；  
Signal(S\_PlateNum);  
吃苹果;  
\}  
桌上有一空盘，允许存放一只水果，爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用。  
请用Wait/Signal原语实现爸爸、儿子、女儿三个并发进程的同步。  
Semaphore S=1; //S 表示盘子是否为空；  
Semaphore S1=0; //S1表示盘中是否有苹果；  
Semaphore S2=0; //S2表示盘中是否有桔子；  
while(TRUE)  
\{  
Wait(S);  
将水果放入盘中;  
if (放入的是桔子)  
Signal(S2);  
Else  
Signal(S1);

\}  
while(TRUE)  
\{  
Wait(S2);  
从盘中取出桔子；  
Signal(S);  
吃桔子;  
\}  
while(TRUE)  
\{  
Wait(S1);  
从盘中取出苹果；  
Signal(S);  
吃苹果;  
\}  
父亲-母亲-儿子-女儿  
一个苹果或桔子  
Semaphore：s=1(空盘数);  
s1=0(苹果数);s2=0(桔子数);  
爸爸：while(true) \{ wait(s); 放苹果; signal(s1); \}  
妈妈：while(true) \{ wait(s); 放桔子; signal(s2); \}  
儿子：while(true) \{ wait(s2); 取桔子; signal(s); \}  
女儿：while(true) \{ wait(s1); 取苹果; signal(s); \}

父亲-母亲-儿子-女儿  
两个苹果或桔子  
Semaphore：s=2(可用位置); s1=0(苹果数);  
s2=0(桔子数);mutex=1;  
爸爸：wait(s); wait(mutex);放苹果; signal(mutex); signal(s1);  
妈妈：wait(s); wait(mutex); 放桔子; signal(mutex); signal(s2);  
儿子：wait(s2); wait(mutex); 取桔子; signal(mutex); signal(s);  
女儿：wait(s1); wait(mutex); 取苹果; signal(mutex); signal(s);  
练习题：某寺庙有小和尚、老和尚若干。  
有一个水缸，由小和尚打水入缸供老和尚饮用。  
水缸可容纳10桶水。  
水取自同一井中。每次只能容纳一个桶取水。  
水桶总数为3个。每次入、取水仅为一桶，且不可同时进行。  
给出有关取水、入水的算法描述。  
semaphore empty=10;// 表示缸中目前还能装多少桶水，  
初始时能装10桶水  
semaphore full=0;// 表示缸中有多少桶水，  
初始时缸中没有水  
semaphore buckets=3;// 表示有多少只空桶可用，  
初值为3  
semaphore mutex\_well=1;// 用于实现对井的互斥操作  
semaphore mutex\_bigjar=1; // 用于实现对缸的互斥操作  
young\_monk()\{  
while(1)\{  
Wait(empty);  
Wait(buckets);  
go to the well;  
Wait(mutex\_well);  
get water;  
Signal(mutex\_well);  
go to the temple;  
Wait(mutex\_bigjar);  
pour water into the big jar;  
Signal(mutex\_bigjar);  
Signal(buckets);  
Signal(full);  
\}  
\}  
old\_monk()\{  
while(1)\{  
Wait(full);  
Wait(buckets);  
Wait(mutex\_bigjar);  
get water;  
Signal(mutex\_bigjar);  
Signal(empty);  
drink water;  
Signal(buckets);  
\}  
\}

**哲学家进餐问题**  
放在桌子上的筷子是临界资源，在一段时间内只允许一个哲学家使用。为实现对筷子的互斥使用，用一个信号量表示一只筷子，五个信号量构成信号量数组。  
semaphore chopstick\[5\];  
所有信号量均被初始化为1。  
semaphore chopstick\[5\] =\{1, 1, 1, 1, 1\};  
Process i()  
\{ while(true)\{  
think;  
Swait(chopstick\[ ( i +1) % 5\] , chopstick\[ i \] );  
eat;  
Ssignal(chopstick\[ ( i +1) % 5\] , chopstick\[ i \] );  
\}  
\}

7、线程的概念及种类、引入线程的目的；

目的:  
减少程序在并发执行时所付出的时空开销，使操作系统具有更好的并发性。

线程：进程中一个相对独立的执行流。线程是CPU执行单位,作为CPU调度单位。

用户级线程 User-level threads  
内核支持线程 Kernel Supported threads  
组合方式

补充:

8.程序顺序执行时的特征  
(1) 顺序性  
处理机的操作严格按照程序所规定的顺序执行。  
(2) 封闭性  
程序一旦开始执行，其计算结果不受外界因素的影响。  
(3) 可再现性  
程序执行的结果与它的执行速度无关(即与时间无关)，而只与初始条件有关。  
例如:  
I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2，I3与P1是可以同时执行的。

9操作系统内核主要包含两个功能：  
（1）支撑功能

（2）资源管理功能

内核：计算机硬件的第一层扩充软件  
第三章 处理机调度与死锁  
1、 调度的层次与作用；  
处理机调度的层次  
高级调度(长程调度)：作业调度 高级调度适用于  
批处理系统 ：需要作业调度  
分时系统 ：不需作业调度  
实时系统 ：不需作业调度  
中级调度(中程调度)：内存调度  
目的：为了提高内存利用率和系统吞吐量。  
低级调度(短程调度)：进程调度  
在多道批处理、分时、实时OS中，都有LLS。  
调度的对象是进程（或内核级线程）  
主要功能：根据某种算法，决定就绪队列中的哪个进程应获得处理机 ，并由分派程序将处理机分配给被选中的进程。

调度的职能  
(1) 记录系统中所有进程的有关情况  
(2) 确定分配处理机的原则  
(3) 分配处理机给进程  
(4) 从进程收回处理机  
2、常用调度算法及计算；(看笔记:FCFS,SJF,高响应比优先调度算法,轮转调度算法(看课本))  
【典型题举例】设有三个作业，它们的提交时间及运行时间如下表，若采用短作业优先调度策略，试给出作业串行运行时的调度次序，计算平均周转时间。  
作业　提交时间　运行时间　  
J1　　　 0　　　　4  
J2　　　 2　　　 8  
J3　　　 3　　　　5

P1 0 8  
P2 1 4  
P3 2 1  
进程 已占有资源 最大需求数  
A　B　C　D A　B　C　D  
P1 0　0　1　2 0　0　1　2  
P2 1　0　0　0 1　7　5　0  
P3 1　3　5　4 2　3　5　6  
P4 0　6　3　2 0　6　5　2  
P5 0　0　1　4 0　6　5　6  
P4 4 3

3、死锁的概念、产生的原因及必要条件；  
死锁的概念:  
指进程之间无休止地互相等待!  
饥饿（Starvation）:指一个进程无休止地等待！  
产生的原因  
(1).竞争资源。  
资源类型：  
可剥夺和非剥夺性资源  
永久性资源和临时性资源  
(2).进程间推进顺序非法。  
必要条件:

1.  互斥条件  
    指进程对所分配到的资源进行排他性使用;  
    即在一段时间内某资源只由一个进程占用;  
    如果此时还有其他进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。
2.  请求和保持条件  
    指进程已经保持了至少一个资源，但又提出了新的资源请求;  
    而该资源又被其他进程占有;  
    此时请求进程阻塞，但又对自己已获得的资源保持不放。
3.  不剥夺条件  
    指进程已获得的资源，在未使用完之前，不能被剥夺;  
    只能在使用完时由自己释放。  
    4.环路等待条件  
    指在发生死锁时，必然存在一个“进程—资源”的环形链;

4、处理死锁的基本方法；  
一、预防死锁——消除产生死锁的必要条件（静态）  
二、避免死锁——分配资源时防止进入不安全状态（动态）  
三、检测死锁——不预防死锁，随时检测死锁（动态）  
四、解除死锁——出现死锁就解除（动态）

5、银行家算法及计算；(看笔记)

（1）如果Requesti\[j\]<= Need\[i,j\],便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。  
（2）如果Requesti\[j\]<= Available\[j\],便转向步骤3；否则，表示尚无足够资源，Pi需等待。  
（3）系统试探着把资源分配给进程Pi ，并修改下面数据结构中的数值：  
Available\[j\]:= Available\[j\]- Requesti\[j\];  
Allocation\[i,j\]:=Allocation\[i,j\]+Requesti\[j\];  
Need\[i,j\]:=Need\[i,j\]-Requesti\[j\];  
（4）系统执行安全性算法，检查此次资源分配后系统是否处于安全状态以决定是否完成本次分配。

【典型题举例】  
 某系统有A、B、C、D四类资源可供五个进程P1.P2.P3.P4.P5共享。系统对这四类资源的拥有量为：A类3个、B类14个、C类12个、D类12个。进程对资源的需求和分配情况如下,请问现在是否是安全状态，请说明原因及判断过程。  
 化简下图的资源分配图，并说明有无进程处于死锁状态。

第四章 存储管理  
1、存储管理的目的、功能；  
功能:  
内存分配与回收  
内存共享与保护  
内存扩充  
地址变换  
目的:  
方便用户和提高主存利用率  
2、重定位的概念及方法；  
概念:把程序中的逻辑地址变成内存中的物理地址的过程叫做重定位。  
方法:  
绝对装入方式  
在编译时，如果知道程序驻留在内存的什么位置，那么编译程序将产生绝对地址的目标代码。  
程序中的逻辑地址与实际内存地址完全相同，无需对程序和数据的地址进行变换。  
优点：装入过程简单。  
缺点：过于依赖硬件结构，不便多道程序系统。  
静态重定位装入方式  
在多道程序环境下，目标模块的起始地址通常从0开始，程序中的其它地址都是相对于起始地址计算的；  
因此应采用可重定位装入方式，根据内存的实际情况，将装入模块装入到内存的适当位置。  
动态重定位装入方式  
程序装入内存后，并不立即实施地址变换，而是把这种地址转换推迟到程序真正运行时才进行；  
装入内存后仍是相对地址；  
应设置一个重定位寄存器。

3、内碎片、外碎片；

4、常用分区分配算法及对应的空闲区排列方式；  
(1)单一连续分配  
内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。  
最简单，适用于单用户、单任务的OS。  
优点：易于管理。  
缺点：  
对要求内存空间少的程序，造成内存浪费；  
程序全部装入，很少使用的程序部分也占用内存。  
(2)固定分区分配  
基本原理及技术  
系统提前把内存分为一些大小相等或不等的分区(partition)，每个进程占用一个分区。操作系统占用其中一个分区。  
适用于多道程序系统和分时系统  
支持多个程序并发执行  
划分分区的方法:

(3)动态(可变)分区分配  
动态创建分区：  
在装入程序时按其初始要求分配；  
或在其执行过程中通过系统调用进行分配或改变分区大小。  
优点：没有内碎片。  
缺点：有外碎片；

(4)动态可重定位分区分配

常用的分配算法

(1) 首次适应算法FF(First Fit)  
(2) 循环首次适应算法NF(Next Fit)  
(3) 最佳适应算法BF(Best Fit)  
(4) 最坏适应算法WF(Worst Fit)

5、基本分页（分段）的概念、页（段）表的作用、地址变换过程及物理地址计算；  
基本分页存储管理方式  
1.分页存储管理的基本方法  
将程序的逻辑地址空间划分为固定大小的页;  
物理内存划分为固定大小的块（页架）;  
程序加载时，分配其所需的所有页，这些页不必连续。需要CPU的硬件支持。

页面和物理块

分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片称为页，并为各页加以编号，从0开始。  
同时把内存空间分成与页面相同大小的若干个存储块，称为块。  
在为进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻的物理块中。  
进程的最后一页经常装不满而形成“页内碎片”。

假定地址长度32位:  
每页的大小为4KB , 即：011位为位移量(页内地址)  
则：12 31位为页号，地址空间最多允许有1M页  
设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？  
解：（1）页式存储管理系统的逻辑地址为：  
其中页内地址表每页的大小即 2048B=2\*1024B=2^11B，所以页内地址为11位。  
其中页号表最多允许的页数即 16页=2^4页，所以页号为4位。  
故逻辑地址至少应为15位。  
（2）物理地址为：  
其中块内地址表每块的大小与页大小相等，所以块内地址也为11位。  
其中块号表内存空间最多允许的块数即 8块=2^3块，所以块号为3位。  
故内存空间至少应为14位，即2^14 =16KB

1.分段地址结构  
由于整个作业的地址空间是分成多个段，因而是二维的，亦即，其逻辑地址由段号(段名)和段内地址所组成。

该地址结构允许一个作业最长有64K个段，每段的最大长度为64KB。

对于下表所示的段表，请将逻辑地址(0，137)，  
(1，4000)，(2，3600)，(5，230)转换成物理地址。

【典型题举例】  
（1）某页式存储系统页表如下，设每页1KB，请写出逻辑地址为8300时所对应的页号和页内地址，以及在内存中对应的物理地址。（请详细写出运算过程）  
系统页表：  
页号 0 1 2 3 4 5 6 7 8  
块号 3 5 6 10 8 7 1 2 4

（2）已知如下段表：  
段号 0 1 2 3 4  
基址 219 2300 90 1327 1952  
长度 600 14 100 580 96  
在分段存储管理下系统运行时，下列逻辑地址（第一位表示段号，第二位表示段内位移）的物理地址是什么？  
（a）：（1，10）  
（b）：（4，112）  
6、分页与分段的区别、各自的优缺点；

7、快表的作用、内存访问时间的计算；

第五章 虚拟存储器  
1、虚拟存储器的基本概念、理论依据、基本特征及关键技术；  
是指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。  
其容量接近于外存，其运行速度接近于内存速度，而每位的成本却又接近于外存。  
\*\*在虚存管理中，虚拟地址空间是指逻辑地址空间，  
实地址空间是指物理地址空间；  
前者的大小受CPU可寻址范围(机器地址长度)的限制，  
而后者的大小受物理内存大小的限制。

\*\*基本特征:  
多次性：一个作业被分成多次调入内存运行  
对换性：允许在作业的运行过程中进行换进、换出。  
虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。  
虚拟性以多次性和对换性为基础。

实现虚存技术的物质基础  
二级存储结构——内存+外存  
动态地址转换机构——将逻辑地址转换成物理地址  
虚拟存储管理实现技术  
请求分页虚拟存储管理  
请求分段虚拟存储管理  
请求段页式虚拟存储管理

2、熟知请求分页基本思想；  
1）请求分页=分页+请求  
逻辑空间分页 物理空间分块  
页与块同样大 页连续块离散  
用页号查页表 硬件做重定位

（2）作业部分装入内存  
（3）作业所占的内存块不连续  
（4）硬件通过页表生成访问内存的地址  
（5）若发生缺页，则进行缺页中断处理，将该页调入内存  
（6）利用快表可以加速地址转换  
3、页面置换算法、缺页率计算、LRU算法的硬件实现方法、抖动、Belady异常、缺页中断；  
【典型题举例】  
在页式虚拟存储管理的计算机系统中，运行一个共有7页的作业，且作业在主存中分配到3块主存空间，作业执行时访问页的顺序为1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 3, 7, 6, 3, 2, 1, 2, 3, 6。假设3个物理块初始为空，所有页面都采用请调式LRU替换算法，要求图示出内存页面变化情况，并计算缺页率。  
(LRU)置换算法 :

某程序大小为460个字，考虑如下访问序列：10，11，104，170，73，309，189，245，246，434，458，364，页帧大小为100个字，请给出页面访问串（即页面走向）。  
解:  
页号＝逻辑地址/页帧大小，所以访问串为：  
0，0，1，1，0，3，1，2，2，4，4，3  
也可简化为：0，1，0，3，1，2，4，3

4、虚拟内存下内存访问时间的计算；  
【典型题举例】  
没有快表的情况(设访存一次所需的时间为t)：  
查找页表找到对应页表项，需要访存一次;  
通过对应页表项中的物理地址访问对应内存单元，需要访存一次;  
因此，EAT=t+t=2t  
有快表的情况：设访问快表的时间为λ，快表的命中率为a，则  
EAT=a(λ+t)+(1-a)(λ+t+λ+t)  
对一个将页表存放在内存中的分页系统：  
（1）若访问内存需要0.2us，有效访问时间为多少？  
（2）如果加一快表，且假定设置快表的命中率高达90%，则有效内存访问时间又是多少？（快表查询需要时间忽略）。  
分页系统要访问两次，第一次要访问页表，将页号换成页地址，并与偏移量相加，得出实际地址，第二次要访问实际的地址的，所以所用时间是0.4μs，如果有快表，命中率为90%，则访问时间为0.2*90%+0.4*10%=0.18+0.04=0.22μs

第六章 设备管理  
1、设备管理的任务、功能及目标；  
完成用户提出的I/O请求  
提高I/O速率  
提高设备的利用率  
为更高层的进程方便地使用这些设备提供手段。  
2、I/O设备的分类，设备、控制器及通道的关系；  
1.I/O设备的类型  
★按使用特性分类  
①存储设备，也称外存、辅存，是用以存储信息的主要设备。该类设备存取速度较内存慢，但容量却大得多，价格也便宜。  
②I/O设备，它又可分为输入设备、输出设备和交互式设备。  
★按传输速率分类  
①低速设备：其传输速率仅为每秒钟几个字节至数百个字节的一类设备，如键盘、鼠标器。  
②中速设备：传输速率在每秒钟数千个字节至数十万个字节的一类设备，如行式打印机、激光打印机等。  
③高速设备：传输速率在数十万字节至千兆字节的一类设备，如磁带机、磁盘机、光盘机等。

设备与控制器之间的接口  
①数据信号线：用于在设备和设备控制器之间传送数据信号。  
②控制信号线：由设备控制器向I/O设备发送控制信号时的通路。  
③状态信号线：用于传送指示设备当前状态的信号。

3、通道的基本概念及分类；

虽然在CPU与I/O设备之间增加了设备控制器后，已能大大减少CPU对I/O的干预，但当主机所配置的外设很多时，CPU的负担仍然很重。  
CPU和设备控制器之间又增设了通道。  
目的:是使一些原来由CPU处理的I/O任务转由通道来承担，从而把CPU从繁杂的I/O任务中解脱出来。  
　2.通道类型  
　　1) 字节多路通道(Byte Multiplexor Channel)  
2) 数组选择通道(Block Selector Channel)  
3) 数组多路通道(Block Multiplexor Channel)

4、I/O控制方式及推动发展的因素、各自适用的场合；  
I/O控制方式主要有  
程序轮询方式:该方式采用用户程序直接控制主机与外部设备之间输入/输出操作。CPU必须不停地循环测试I/O设备的状态端口，当发现设备处于准备好(Ready)状态时，CPU就可以与I/O设备进行数据存取操作。  
中断方式:  
当I/O设备结束(完成、特殊或异常)时，就会向CPU发出中断请求信号，CPU收到信号就可以采取相应措施。当某个进程要启动某个设备时，CPU就向相应的设备控制器发出一条设备I/O启动指令，然后CPU又返回做原来的工作。  
DMA方式:  
DMA方式也称为直接主存存取方式，其思想是：允许主存储器和I/O设备之间通过“DMA控制器(DMAC)”直接进行批量数据交换，除了在数据传输开始和结束时，整个过程无须CPU的干预。  
I/O通道控制方式:  
通道(Channel)也称为外围设备处理器、输入输出处理机，是相对于CPU而言的。是一个处理器。也能执行指令和由指令的程序，只不过通道执行的指令是与外部设备相关的指令。是一种实现主存与I/O设备进行直接数据交换的控制方式。  
5、缓冲区的概念、分类及引入目的；单缓冲、双缓冲计算处理数据的时间；

在单缓冲区中，当上一个磁盘块从缓冲区读入用户区完成时，下一个磁盘块才能开始读入，也就是当最后一块磁盘块读入一用户区完毕时所用时间为150*10=1500us，加上处理最后一个磁盘块的时间50us,得1550us。双缓冲区中，不存在等待磁盘块从缓冲区读入用户区的问题，10个磁盘块可以连续从外存读入主存缓冲区，加上将最有一个磁盘块从缓冲区送到用户区的传输时间50us以及处理时间50us,也就是100*10+50+50=1100us

【典型题目举例】  
 某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。试计算在单缓冲区和双缓冲区结构下，读入并分析该文件的时间分别是多少，并画图说明计算过程。  
6、I/O软件的层次、各层主要功能、设备独立性的概念；  
设备独立性是指用户程序独立于具体使用的物理设备的一种特性。  
(I) 用户层I/O软件，实现与用户交互的接口，用户可直接调用该层所提供的、与IO操作有关的库函数对设备进行操作。  
(2) 设备独立性软件，用于实现用户程序与设备驱动器的统接口、设备命名、设备的保护以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间。  
(3) 设备驱动程序，与硬回件直接相关，用于具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序。  
(4)中断处理程序，用于保存被中答断进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断进程的现场后，返回到被中断的进程。

7、SPOOLING技术的概念、作用及SPOOLING系统的组成；  
 SPOOLing技术是一类典型的虚拟设备技术,通常是用独占设备来模拟共享设备。（F）  
操作系统在用户层中还提供了一些非常有用的程序，比如假脱机系统，以及在网络传输文件时常使用的守护进程等，它们是运行在内核之外的程序，但它们仍属于I/O系统。  
SPOOLING的组成  
主要有四部分：  
(1).输入井和输出井。是磁盘上开辟的两个大存储空间。输入井模拟脱机输入的磁盘设备，输出井模拟脱机输出时的磁盘。  
(2).输入缓冲区和输出缓冲区。输入缓冲区暂存由输入设备送来的数据，后送输入井；输出缓冲区暂存从输出井送来的数据，后送输出设备。  
(3).输入进程和输出进程。利用两个进程模拟脱机I/O时的外围处理机。  
(4).井管理程序。用于控制作业与磁盘井之间信息的交换。

8、磁盘访问过程及访问时间的确定、块号与柱面、磁道、扇区号的对应关系、磁盘调度算法及其计算；扇区的优化；  
(看输入输出I/O第六章145页ppt)  
【典型题目举例】  
 若磁头的当前位置为100 柱面，磁头正向磁道号减小方向移动。现有一磁盘读写请求队列，柱面号依次为：190 , 10 , 160 , 80 , 90 , 125 , 30 , 20 , 29 , 140 , 25 。若采用电梯调度算法，试计算移臂经过的柱面数和平均寻道长度。

第七章 文件管理  
1、文件系统的组成、功能；  
文件系统由三部分组成：文件系统的接口，对对象操纵和管理的软件集合，对象及属性。  
文件系统功能:  
用户角度：  
实现“按名存取”  
系统角度：  
文件存储空间的管理  
文件的存储与检索  
文件的共享与保护。

2、打开、关闭操作的目的；  
把该文件的有关控制信息（ FCB ）读入内存，建立相应的数据结构，以建立用户和该文件的联系，方便读写,避免多次重复地检索目录，节省检索开销，提高操作速度。  
文件描述符/文件句柄。  
3、文件逻辑结构；  
   
文件逻辑结构的类型:  
顺序文件  
记录寻址  
索引文件  
索引顺序文件  
直接文件和哈希文件

文件组织的两种观点  
⑴用户观点（逻辑结构）  
研究的是用户思维中的抽象文件，也叫逻辑文件。其目的是为用户提供一种结构清晰、使用简便的逻辑组织。用户按此去存储、检索和加工处理有关文件信息。  
⑵实现观点（物理结构）  
研究的是存储在物理设备介质上的实际文件，即物理文件。其目的是选择一些性能良好、设备利用率高的物理结构。系统按此和外部设备打交道，控制信息的传输。

逻辑结构分类  
（1）是否有结构  
①有结构文件：由一个以上的记录构成的文件，  
又称为记录式文件；  
定长记录/变长记录。  
②无结构文件：由字符流构成的文件，  
又称为流式文件。  
⑵文件的逻辑组织方式  
①顺序文件  
②索引文件  
③索引顺序文件

4、文件的目录结构、索引节点及文件控制块的作用；  
 如何加快目录检索？

 目录项分解法：即把FCB分成两部分，符号目录项：文件名，文件号，基本目录项：除文件名外的所有字段

5、了解文件的共享和保护措施。  
第八章 磁盘存储器的管理  
1、文件的物理结构；  
常用的物理结构有连续文件结构、串联文件结构、索引文件结构三种。  
2、 FAT表的作用、FAT表大小的计算；  
FAT技术  
利用文件分配表FAT记录每个文件所有盘块之间的链接。  
Windows NT、Windows 2000和Windows XP操作系统则采用NTFS(新技术文件系统)

【典型题目举例】  
假设盘块大小为512B，硬盘的大小为100MB，如果采用显式链接管理方式，对应的FAT为多少字节？  
 100MB/512B=200K个块；  
 需要18个二进制位来描述块号；  
 按照FAT表的组织结构，每个表项需要扩充成20位即2.5个字节；  
 所以FAT表的大小=2.5B\*200K=500KB。  
3、 混合索引分配方式的结构及相关计算；  
【典型题目举例】  
 某磁盘文件系统，采用混合索引分配方式，13个地址项记录在FCB中，第0-9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为512字节，盘块号需要用3个字节来描述，问：  
1）该文件系统允许文件的最大长度是多少？  
2）若要读取字节地址为5000B处的文件数据，试计算得到其映射到的物理地址（磁盘块号及偏移量），请写明计算过程。  
4、文件空闲区的管理方法（空闲表、空闲链、位示图与成组链接法）；  
【典型题目举例】  
假设一个磁盘组有 100 个柱面，编号为 0-99，每个柱面有 32 个磁道，编号为 0-31，每个磁道有16 个扇区，编号为0-15。现采用位示图方法管理磁盘空间，磁盘块与扇区大小相等，令磁盘块号按柱面顺序和磁道顺序编排（从0编起）。请回答下列问题：（5分）  
1)若采用32 位的字组成位示图，共需要多少个字?  
2)第40 字的第18 位对应于哪个柱面、哪个读写磁头和哪个扇区?  
1)（16×32×100）/32=1600,需要1600 个字。  
2）块号是1298：40×32+18=1298  
柱面号是2：\[1298/(16×32)\]=2  
磁头号是17：\[（1298 mod (16×32)）/16\]=17  
扇区号是2：（1298 mod （16×32））mod 16=2  
 某UNIX操作系统的空闲盘块号栈内容为：空闲块数为3，依次登记的空闲块号为77、89、60，问此时若一个文件A需要5个盘块，系统进行分配后又有个文件B被删除，它占用的盘块块号为100、101、109、500，分析分配和回收过程，说明上述操作过后空闲盘块号栈里的空闲块个数及内容如何？  
5、了解提高磁盘I/O速度的途径。