操作系统复习大纲【改进2】.doc

操作系统复习大纲

1. 设备无关性（独立性）
设备独立性是指操作系统把所有外部设备统一当作文件来看待，只要安装它们的驱动程序，任何用户都可以像使用文件一样，操纵、使用这些设备，而不必知道它们的具体存在形式。

2. 进程与程序的区别
①进程是程序的一次执行,属于动态概念,而程序是一组有序的指令集合,是一种静态概念。但进程离开了程序也就失去了存在的意义。
②一个进程可以执行一个或几个程序。反之,同一程序可能由几个进程同时执行。
③程序可作为软件资源长期保留,而进程是程序的一次执行过程,是暂时的。进程具有生命期。
④进程具有并发性,能与其它进程并发运行。而程序不具备这种特征。
⑤进程是一个独立的运行单位,也是系统进行资源分配和调度的一个独立单位。因此,进程具有独立性,但有时进程间又具有相互制约性。

3. 局部性原理、抖动。
①时间局部性：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。（程序循环、堆栈等是产生时间局部性的原因）
②空间局部性：在最近的将来将用到的信息很可能与现状正在使用的信息在空间地址上是临近的。

4. 抖动的处理（抖动的原因）。
抖动：在虚存中，页面在内存与外存之间的频繁调度，以至于调度页面所需时间比进程实际运行的时间还多（在页面置换中，刚被淘汰出的页马上又要用到，如此反复），此时系统效率急剧下降，甚至导致系统崩溃，这种现象叫做抖动。
抖动的原因：①页架数过少，频繁造成缺页中断；②页面置换算法的不合理，不合理的算法可能将不久要用到的页面淘汰出去；③程序结构，滥用转移指令。

5. 死锁的必要条件。
（1） 资源独占性：资源被各进程互斥使用，即一个资源每次只能被一个进程所占用；
（2） 资源不可抢夺性：一个资源被一个进程占用后，除非该进程用完自行释放，不能被别的进程强行抢占；
（3） 资源的部分分配：一个进程占有了一些分配给他的资源后，仍要求占用其他的资源。
（4） 循环等待资源：系统中若干进程之间对资源使用形成了一种循环等待的状况，即第一个进程占用了第二个进程所需资源，第二个占用第三个的，最后一个又占用第一个的。

6. 分页式、分段式，两者的主要区别。段页式，为何要分页分段？
为何要分页：分页管理是解决碎片问题的一种有效办法，它允许程序的存储空间是不连续的，用户程序的地址空间被划分为若干个固定大小的区域。
分页存储管理：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面。
为何要分段：满足用户程序员（1）方便编程，（2）信息共享，（3）信息保护，（4）动态增长，（5）动态链接的需要。P136
分段存储管理：将程序分成若干逻辑段，并对这些段分别分配存储空间。
两者的主要区别：
（1） 页是信息的物理单位，分页是为了便于系统管理，而段是信息的，逻辑单位，分段是为了满足用户的需要。
（2） 分页式存储管理的作业地址空间是一维的，而分段式存储管理作业地址空间是二维的。
（3） 页的长度由系统确定，是等长的，而段的长度由具有相对完整意义的信息长度确定，是不固定的。
为何有段页式：分页存储管理能有效提高内存的利用率，分段存储管理能很好地满足用户的需要，段页式存储管理则是分页和分段两种存储管理方式的结合，它同时具备了两者的优点。
段页式存储管理：先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。

7. 进程与线程的关系。
线程是进程的一个组成部分，没各进程创建时通常只有一个线程，需要时可创建其它线程；进程的多线程都在进程的地址空间活动；资源是分给进程的，不是分给线程的，线程执行中需要资源时，可从进程资源中划分；处理机调度的基本单位是线程，线程之间竞争处理机，真正在CPU运行的是线程，线程在执行时需要同步。
线程：进程
描述
1:1
每个线程的执行就是一个进程
n:1
每个进程定义一个地址空间并动态拥有资源
1:n
一个线程可以在多个进程间转移，同一进程可产生多个线程并运行
n:n
包含1:n和n:1的性质

8. 什么是死锁、饥饿。死锁与饿死的区别。
死锁：由于进程间相互竞争系统资源或通信而引起的一种阻塞现象。
饥饿：当等待时间给进程推进和响应带来明显影响时，称为进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称进程饿死。
死锁与饿死的区别：
（1） 从进程状态看，死锁进程都出于等待状态，忙式等待（处于运行或就绪状态）的进程并非处于等待状态，但却可能被饿死。
（2） 死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，其等待时限没有上界。
（3） 死锁一定发生了循环等待，而饿死则不然。这也表明通过资源分配图可以检测死锁存在与否，却不能检测是否有进程饿死。
（4） 死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个。饥饿和饿死与资源分配策略有关，因而防止饥饿与饿死可以从公平性考虑，确保所有进程不被忽略。

9. 安全性检测算法（已知流程图，写代码）。
数据结构：
Available: array[1..m]of integer; //系统可用资源
Claim: array[1..n,1..m]of integer; //进程最大需求
Allocation: array[1..n,1..m]of integer; //当前分配
Need: array[1..n,1..m]of integer; //尚需资源
Request: array[1..n,1..m]of integer; //当前请求

int Work[m]; 工作变量, 记录可用资源.
int Finish[n]; 工作变量, 记录进程是否可进行完.
1. Work = Available；Finish = false；
2. 寻找满足如下条件的i:
(1) Finish[i]==false；(2) Need[i]≤Work[i]；
如果不存在, 则转步骤4；
3. Work = Work + Allocation[i]；Finish[i] = true；
转步骤2
4. 如果对于所有i, Finish[i] = true, 则系统处于安全状态, 否则处于不安全状态.
F
Work:=Available;
Finish:=false;
有满足条件的j:
Finish[j]=false
Need[j]£Work
Finish[j]=true;
Work:=Work+Allocation[j]
T
"j ,finish[j]=true
T
F
安全
不安全

10. 进程的特征。
进程的特征：
（1） 并发性：可以与其他进程一起向前推进
（2） 动态性：动态产生、消亡，生存期内状态动态变化
（3） 独立性：一个进程是可以调度的基本单位
（4） 交往性：同时运行的进程可能发生相互作用
（5） 异步性：进程以各自独立，不可预知的速度向前推进
（6） 结构性：每个进程由一个PCB。

11. 进程的状态及其转移。

· 运行：进程当前处于运行状态。
· 就绪；进程已准备好运行，等待CPU。
· 阻塞；进程等待某些事件发生（如I/O操作、申请缓冲空间）后才能运行。
· 创建：进程刚产生，但还未被操作系统提交到可运行进程池中。
· 消失：进程被操作系统从可运行进程池中释放。
· 挂起：进程被操作系统从可运行进程池中释放。
带有挂起状态的进程状态图：
(a) 带有一个挂起状态的进程转换图
(b) 带有两个挂起状态的进程转换图

12. 最佳页面尺寸算法例：在一个分页系统中，设计算机的内存大小为M，作业平均尺寸为J，一个页表项占x个存储单位，问最佳页面尺寸P是多少？
每个进程需要的页数：J/P
占用 x·J/P 个存储单位
每个进程的内部碎片平均为： P/2
由页表和内部碎片带来的总开销： x·J/P+P/2
对P求导，令其等于0，得到方程：

由此得到最佳页面尺寸公式

13. 扔球问题。
（1）有一个充分大的池子，两个人分别向池中扔球，甲扔红球，乙扔蓝球，一次扔一个，开始时池中有红、蓝球各一个，要求池中球满足条件：1＜＝红球数／蓝球数＜＝2，用P V操作描述两个进程

信号量初值：r=1；b=1
扔红 扔蓝

P(r) P(b)

扔一个红 扔一个蓝

V(b) V(r)
V(r)
（2）一个充分大的池子，甲乙丙三人扔球，甲扔红，乙扔蓝，丙扔绿。开始时池子中又红绿蓝球各一个。要求：池中球满足要求：1<=红/蓝<=2 ，且蓝<=绿<=红+蓝

信号量初值：r，b1，g=1；b2=0

扔红 扔蓝 扔绿
P(r) P(b1) P(g)
扔一个红 P(b2) 扔一个绿
V(b1) 扔一个蓝 V(b2)
V(g) V(r)
V(r)
V(g)

14. 设有一个Ｔ型路口，其中A、B、C、D处各可容纳一辆车，车行方向如下图所示，试找出死锁并用有序分配法消除之。要求资源编号合理。
解：(1)Ｅ方向两台车分别位于A和B；S方向一台车位于C；W方向一台车位于D。(2)S方向两台车分别位于B和C；E方向一台车位于A；W方向一台车位于D。

设位置资源C、B、A、D的编号从低到高依次为1、2、3、4，管理四个位置的信号量分别为s1,s2,s3,s4，信号量的初值均为1。车辆活动如下：

semaphore s1=1,s2=1,s3=1,s4=1;

13

W ：直行
P(s1); // 按序申请
P(s4); 驶入 D;
驶入 C;
V(s4);
驶出 C;
V(s1);

E ：左转
P(s2);
驶入 B;
P(s3) ；
驶入 A;
V(S2)
P(s4) ；
驶入 D;
V(s3) ；
驶出 D;
V(s4);

S ：左转
P(s1);
驶入 C;
P(s2) ；
驶入 B;
V(S1)
P(s3) ；
驶入 A;
V(s2) ；
驶出 A;
V(s3);

15. 银行家算法（死锁检测，有流程图，写代码）。
1. 如果Request[i]≤Need[i], 则转步骤2; 否则进程申请资源量超过所申明最大资源需求量, 带错返回.
2. 如果Request[i]≤Available[i], 则转步骤3; 否则本次申请当前无法满足, 进程pi必须等待.
3. 系统假设分配资源, 将相应的数据结构修改为:
Available = Available - Request[i];
Allocation = Allocation + Request[i];
Need[i] = Need[i] - Request[i];
4. 如果上述分配所导致的新状态是安全的, 则转步骤5; 否则取消分配：
Available = Available + Request[i];
Allocation = Allocation - Request[i];
Need[i] = Need[i] + Request[i];
进程pi等待.
5．确认分配，进程pi继续.
Available:=Available+Request[I]
Allocation[I]:=Allocation[I]-Request[I]
Need[I]:=Need[I]+Request[I]
pi等待
Pi请求资源
Available:=Available-Request[I]
Allocation[I]:=Allocation[I]+Request[I]
Need[I]:=Need[I]-Request[I]
Request[I]£Need[I]
请求超量，错返
Request[I]£Available
不满足，等待
安全
确认，pi继续
F
T
F
T
T
F

16. 临界区。
人们把每个进程中访问临界资源的那段代码成为临界区。

17. 读着优先、写者优先（代码）。
（1） 读者优先
如果有读者来时，
①无读者和写者，新读者可以读；
②如有写者等待，但有其他读者正在读，则新读者可以读；
③有写者写，新读者则等待
Var wsem:semaphore; (initial value: 1)

Writer：
while(1){
<other action>
P(wsem);
<write operation>
V(wsem);
}

int readCount = 0;
semaphore wsem = 1;
semaphore mutex = 1;

reader()：
while(1){
<other actions>
P(mutex);
readCount = readCount+1;
if (readCount == 1)
P(wsem);
V(mutex);
<read operations>
P(mutex);
readCount = readCount-1;
if (readCount == 0)
V(wsem);
V(mutex);
}

变量wsem用来保证读者与写者之间的互斥，以及写者与写者之间的互斥；变量readCount用来记录读者的数目；变量mutex用来实现读者对于变量readCount访问的互斥.
问题：读者源源不断，readcount不归0，写者会被饿死。这是不合理的，因为写者的操作是更新数据，应当优先进行，否则读者将读到已经过时的数据
策略：一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。

（2） 写者优先
如果有写者来时，
①无读者，新写者可以写；
②如有读者正在读，则新读者等待；
③有其他写者正在写，新写者则等待。

int writeCount = 0;
semaphore wsem,rsem = 1;
semaphore mutexY = 1;
writer()：
while(1){
<other actions>
P(mutexY);
writeCount = writeCount+1;
if (writeCount == 1)
P(rsem);
V(mutexY);
P(wsem);
<write operations>
V(wsem);
P(mutexY);
writeCount = writeCount-1;
if (writeCount == 0)
V(rsem);
V(mutexY);
}

int readCount = 0;
semaphore wsem,rsem = 1;
semaphore mutexX,mutex = 1;
reader()：
while(1){
<other actions>
P(mutex);
P(rsem);
P(mutexX);
readCount = readCount+1;
if (readCount == 1)
P(wsem);
V(mutexX);
V(rsem);
V(mutex);
<read operations>
P(mutexX);
readCount = readCount-1;
if (readCount == 0)
V(wsem);
V(mutexX);
}

变量wsem用来保证读者与写者之间的互斥，以及写者与写者之间的互斥；变量writeCount用来记录写者的数目；变量mutexY用来实现读者对于变量writeCount访问的互斥；变量readCount用来记录读者的数目；变量mutexX用来实现读者对于变量readCount访问的互斥;mutex用来实现rsem上不要有长的排队等待。

18. 资源分配图的化简。
可以通过对资源分配图的约简，来判断系统是否处于死锁状态．
资源分配图中的约简方法如下：
(1)寻找一个非孤立且没有请求边的进程结点pi,若无算法结束；
(2)去除所有pi的分配边使pi成为一个孤立结点；
(3)寻找所有请求边均可满足的进程pj,将pj的请求边全部改为分配边；
(4)转步骤(1)．
若算法结束时，所有结点均为孤点，则称资源分配图是可以完全约简的，否则称为不可完全约简的．文献已经证明，系统处于死锁状态的充分必要条件是资源分配图不可完全约简．这一结论称为死锁定理．
定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简．

对于问题1，假设进程p3申请资源类r2中的一个实例，由于没有空闲的资源实例，将增加一条申请边(p3,r2)，形成图 5－2. 此时, 出现了两个环路: p1® r1® p2® r3® p3® r2® p1 和p2® r3® p3® r2® p2. 进一步分析可以验证，此时系统已经发生死锁，且进程p1、p2和p3都参与了死锁.
对于问题2，此图中亦有一个环路: p1®r2®p4®r1®p1
然而并不存在死锁. 注意观察p2可能会释放资源类r1中的一个资源实例, 该资源实例可分配给进程p3, 从而使环路断开.
综合上述分析可以看出, 如果资源分配图中不存在环路, 则系统中不存在死锁; 反之, 如果资源分配图中存在环路, 则系统中可能存在死锁, 也可能不存在死锁.

19. 堆栈型置换算法证明，LRU（PPT）。
一般来说，分配给程序的主存页面数越多，虚页装入到主存到中的机会也就越多，因此命中率也可能越高，至少不应该下降，通常把满足这种关系的页面替换算法称为堆栈型替换算法。
设长度为L的任何页面地址流，t为已经处理过t-1个页面的时间点，n为分配给该地址流的实存页架数，Bt(n)表示在t时间点，n个页架实存中的页面集，Lt表示到t时已经遇到过的地址流中相异页的页数，如果置换算法中具有：
n<Lt时，Bt(n) ﹝Bt(n+1)
n≧Lt时，Bt(n) = Bt(n+1)
对任意一个程序的页地址流作两次主存页面数分配，分别分配m个和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：Bt（m）≤ Bt（n）
最近最少使用(Least Recently Used，LRU)页面置换算法则是根据页面调入内存后的使用情况，选择最近最少使用的页面予以淘汰。
因为LRU算法满足，n<Lt时，Bt(n)(包含于符号)Bt(n+1)
n>=Lt时，Bt(n)=Bt(n+1)
n表示分配给程序的实页数，Bt(n)表示t时刻在n个实页中的虚页集合，Lt为t时刻不同虚页的页面数。由于在主存中保留的是最近使用过的页面。如果先给某一个程序分配n个主存页面，那么在t时刻，这n个主存页面都是最近使用过的页面。如果再给这个程序多分配一个主存页面，那么在t时刻，这n＋1个主存页面也都是最近使用过的页面。因此，在这n＋1个主存页面中必然包含了前面的n个主存页面。所以， LRU算法都是堆栈型算法。

20. 在非抢占调度算法中，SPN具有最小平均等待时间。
假如有4道作业，它们的提交时间及运行时间如下表所示：
作业号
提交时刻
运行时间（分钟）
1
8：00
120
2
8：30
30
3
9：00
6
4
9：30
12
采用单道运行，试问下述调度算法下，它们的调度顺序，并分别计算各调度算法下三个作业的平均周转时间 T 和平均带权周转时间 W。
T=1/N（∑Ti）,Ti=结束时刻-提交时刻; W=1/N（∑Wi）, Wi= Ti /作业 i 实际执行时间
SPN(SJF)：调度顺序为1 3 4 2
作业号
到达时刻
要求运行时间（分钟）
结束时刻
周转时间Ti（分钟）
带权周转时间Wi
1
8：00
120
10：00
120
1
3
9：00
6
10：06
66
11
4
9：30
12
10：18
48
4
2
8：30
30
10：48
138
4.6

T=1/4（120+66+48+138）=93分钟
W=1/4（1+11+4+4.6）=5.15
以下证明是本人拙劣作品，证明过程还存在不严谨之处，请注重思路，细节上的东西因为时间问题暂不想追究。
设有n个作业，将作业根据运行时间从小到大排序为（即由SPN算法得出的工作序列）A1 A2 … An，其对应的运行时间为t1 t2 … tn，等待时间为a1 a2 … an，总等待时间为Wa
现任取两个作业i 与j 互换位置（i<j）,并记新序列的等待时间为 b1 b2 … bn，总等待时间为Wb
则两种序列的等待时间及总等待时间为：

a1= 0
a2= t1
。
。
。
ai= t1+t2+…+t(i-1)
a(i+1)= t1+t2+…+ti
。
。
。
a(j+1)= t1+t2+…+tj
= a(i)+t(i+1)+…+tj
a(j+2)= a(i)+t(i+1)+…+t(j+1)

。
。
。
an= t1+t2+…+tn
Wa=Σai (i=1, ...,n)
b1= 0= a1
b2= t1= a2
。
。
。
bi= ai
b(i+1)= ai+tj
。
。
。
b(j+1)= ai+tj+t(i+1)+...+ti

b(j+2)= ai+ tj+t(i+1)+...+ti+t(j+1)
= a(j+2)
。
。
。
bn= an
Wb=Σbi (i=1, ... ,n)

△ W= Wb—Wa
= [b(i+1)+…+b(j+1)] — [a(i+1)+….+a(j+1)]
= (j-i)(tj-ti)
∵j>i 且 tj≥ti
∴ △W≥0 即 Wb≥Wa
又 平均等待时间W=总等待时间/n
因此在非抢占调度算法中，SPN具有最小平均等待时间。

21. 信号量相关概念、值。
S.value的初值表示系统中某类资源的数目， 因而又称为资源信号量
对它的每次P操作，意味着进程请求一个单位的该类资源，因此描述为S.value∶ =S.value-1
当S.value＜0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。
对信号量的每次V操作，表示执行进程释放一个单位资源，故S.value∶ =S.value+1操作表示资源数目加1。
若加1后仍是S.value≤0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用V原语，将S.L链表中的第一个等待进程唤醒。
如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。

22. FAT12 FAT16 FAT32 簇的大小。
设硬盘大小为M

文件系统
FAT12
FAT16
FAT32
簇个数

簇大小
M/
M/
M/

23. 分布式操作系统中，进程间的通信方式。
（1） 共享存储器系统
①基于共享数据结构的通信方式
②基于共享存储区的通信方式
（2） 消息传递系统
①直接通信方式
②间接通信方式
（3） 管道系统
24. 若在一个分页存储管理系统中，……
A：逻辑地址 L：页面大小 P：页号 d：地址
P=int[A/L] d=A mod L
若在一分页存储管理系统中，某作业也表如下所示，一直页面大小为1024字节，试将逻辑地址1011，2148，4000，5012转化为相应物理地址
页号
块号
0
2
1
3
2
1
3
6
分析页面存储管理的结构是一维的，即逻辑地址（或物理地址）只用一个数值即可表示，给定逻辑地址A，页面大小L，则页面号P。。。地址d可按下式求得p=int[A/L] |d=A modL其中int是取整函数，mod是取余函数
解本题，为秒速方便，设页号P，页内位移d则：（1）对于逻辑地址1011，p=int(1011/1024)=0,d=1011mod1024=1011,查页表第0页在第2块，所以物理地址为1024^2+1011=3059
（2）2148 p=2 d=100第2页第1块物理地址1024+100=1124
（3）p=3 d=928第三页第六快物理地址1024*6+928=7072
（4）p=4 d=916页号超过页表长度，缺页中断。