1、习题二1 操作系统中为什么要引入进程的概念？为了实现并发进程之间的合作和协调，以及保证系统的安全，操作系统在进程管理方面要做哪些工作？答：（1）为了从变化的角度动态地分析研究可以并发执行的程序，真实地反应系统的独立性、并发性、动态性和相互制约，操作系统中就不得不引入“进程”的概念； （2）为了防止操作系统及其关键的数据结构，受到用户程序有意或无意的破坏，通常将处理机的执行状态分成核心态和用户态；对系统中的全部进程实行有效地管理，其主要表现是对一个进程进行创建、撤销以及在某些进程状态之间的转换控制，2 试描述当前正在运行的进程状态改变时，操作系统进行进程切换的步骤。答：（1）就绪状态运行状态。处
2、于就绪状态的进程，具备了运行的条件，但由于未能获得处理机，故没有运行。（2）运行状态就绪状态。正在运行的进程，由于规定的时间片用完而被暂停执行，该进程就会从运行状态转变为就绪状态。（3）运行状态阻塞状态。处于运行状态的进程，除了因为时间片用完而暂停执行外还有可能由于系统中的其他因素的影响而不能继续执行下去。3 现代操作系统一般都提供多任务的环境，试回答以下问题。（1） 为支持多进程的并发执行，系统必须建立哪些关于进程的数据结构？答：为支持进程的并发执行，系统必须建立“进程控制块（PCB） ”，PCB 的组织方式常用的是链接方式。（2） 为支持进程的状态变迁，系统至少应该供哪些进程控制原语？答：
3、进程的阻塞与唤醒原语和进程的挂起与激活原语。（3） 当进程的状态变迁时，相应的数据结构发生变化吗？答：创建原语：建立进程的 PCB，并将进程投入就绪队列。 ；撤销原语：删除进程的 PCB，并将进程在其队列中摘除；阻塞原语：将进程 PCB 中进程的状态从运行状态改为阻塞状态，并将进程投入阻塞队列；唤醒原语：将进程 PCB 中进程的状态从阻塞状态改为就绪状态，并将进程从则色队列摘下，投入到就绪队列中。4. 什么是进程控制块？从进程管理、中断处理、进程通信、文件管理、设备管理 及存储管理的角度设计进程控制块应该包含的内容。答：（1）进程控制块是用来描述进程本身的特性、进程的状态、进程的调度信息及对资
4、源的占有情况等的一个数据结构；（2）为了进程管理，进程控制块包括以下几方面。a) 进程的描述信息，包括进程标识符、进程名等。b) 进程的当前状况。c) 当前队列链接指针。d) 进程的家族关系。为了中断处理，进程控制块的内容应该包括处理机状态信息和各种寄存器的内容。为了内存管理的需要，进程控制块的内容应该包括进程使用的信号量、消息队列指针等。为了设备管理，进程控制块的内容应该包括进程占有资源的情况。5 假设系统就绪队列中有 10 个进程，这 10 个进程轮换执行，每隔 300ms 轮换一次，CPU 在进程切换时所花费的时间是 10ms，试问系统化在进程切换上的开销占系统整个时间的比例是多少？答：
5、因为每隔 300ms 换一次进程，且每个进程切换时所花费的时间是10ms，则系统化在进程切换上的开销占系统整个时间的比例是10/（300+10 ）=3.2%6 试述线程的特点及其与进程之间的关系。答：（1）特点：线程之间的通信要比进程之间的通信方便的多；同一进程内的线程切换也因为线程的轻装而方便的多。同时线程也是被独立调度的分配的；（2）线程与进程的关系：线程和进程是两个密切相关的概念，一个进程至少拥有一个线程，进程根据需要可以创建若干个线程。线程自己基本上不拥有资源，只拥有少量必不可少的资源（线程控制块和堆栈）7 根据图 2-18，回答以下问题。（1） 进程发生状态变迁 1、3、4、6、7
6、的原因。答：1 表示操作系统把处于创建状态的进程移入就绪队列；3 表示进程请求 I/O 或等待某事件；4 表示进程用行的时间片用完；6 表示 I/O完成或事件完成；7 表示进程完成。（2） 系统中常常由于某一进程的状态变迁引起另一进程也产生状态变迁，这种变迁称为因果变迁。下述变迁是否为因果变迁：32,45,72,36，是说明原因。答：32 是因果变迁，当一个进程从运行态变为阻塞态时，此时 CPU 空闲，系统首先到高优先级队列中选择一个进程。45 是因果变迁，当一个进程运行完毕时，此时 CPU 空闲，系统首先到高优先级队列中选择进程，但如果高优先级队列为空，则从低优先队列中选择一个进程。72 是
7、因果变迁，当一个进程运行完毕时，CPU 空闲，系统首先到高优先级队列中选择一个进程。36 不是因果变迁。一个进程阻塞时由于自身的原因而发生的，和另一个进程等待的时间到达没有因果关系。（3） 根据此进程状态转换图，说明该系统 CPU 调度的策略和效果。答：当进程调度时，首先从高优先级就绪队列选择一个进程，赋予它的时间片为 100ms。如果高优先级就绪队列为空，则从低优先级就绪队列选择进程，并且赋予该进程的时间片为 500ms。这种策略一方面照顾了短进程，一个进程如果在 100ms 运行完毕它将退出系统，更主要的是照顾了 I/O 量大的进程，进程因 I/O 进入阻塞队列，当 I/O完成后它就进入了
8、高优先级就绪队列，在高优先级就绪队列等待的进程总是优于低优先级就绪队列的进程。而对于计算量较大的进程，它的计算如果在100ms 的时间内不能完成，它将进入低优先级就绪队列，在这个队列的进程被选中的机会要少，只有当高优先级就绪队列为空，才从低优先级就绪队列选择进程，但对于计算量大的进程，系统给予的适当照顾时间片增大为 500ms。 8 回答以下问题。（1） 若系统中没有运行进程，是否一定没有就绪进程？为什么？答：是，因为当 CPU 空闲时，系统就会在就绪队列里调度进程，只有当就绪队列为空时，系统中才没有运行程序。（2） 若系统中既没有运行进程，也没有就绪进程，系统中是否就没有阻塞进程？解释。答：
9、不一定，当运行的程序都因为请求 I/O 或等待事件时而进入阻塞，系统中就没有就绪进程。（3） 如果系统采用优先级调度策略，运行的进程是否一定是系统中优先级最高的进程？为什么？答：不一定，若优先级高的进程进入阻塞状态时，而且优先级高的就绪队列里没有等待的进程，这时就会调度优先级低的就绪队列的进程。9 假如有以下程序段，回答下面的问题。S1: a=3-x;S2: b=2*a;S3: c=5+a;(1) 并发程序执行的 Bernstein 条件是什么？答：若 P1 与 P2R 并发执行，当且仅当 R(P1)W(P2)R(P2) W(P1)W(P1)W(P2)= 时才满足。(2) 试画图表示它们执行时
10、的先后次序。S 1S 2S 3(3) 利用 Bernstein 条件证明，S1、S2 和 S3 哪两个可以并发执行，哪两个不能。答：R(s1)=x,W(s1)=a;R(s2)=a,W(s2)=b;R(s3)=a,W(s3)=c;(1).R(s1)W(s2) R(s2)W(s1)W(s1)W(s2)=a,则 s1 与 s2 不能并发执行；(2). R(s1)W(s3)R(s3) W(s1)W(s1)W(s3)=a,则 s1 与 s3 不能并发执行；(3). R(s2)W(s3)R(s3) W(s2)W(s2)W(s3)=,则 s2 与 s3 可以并发执行。习题三1 一下进程之间存在相互制约关系吗
11、？若存在，是什么制约关系？为什么？（1） 几个同学去图书馆借同一本书。答：互斥关系；因为他们要借同一本书，不可能同时借到，所以互斥。（2） 篮球比赛中两队同学争抢篮板球。答：互斥关系；因为争抢同一个篮板，存在互斥关系。（3） 果汁流水线生产中捣碎、消毒、灌装、装箱等各道工序。答：同步关系；他们必须相互协作才能使进程圆满完成。（4） 商品的入库出库。答：同步关系；因为商品出库可以为入库提供空间。（5） 工人做工与农民种粮。答：没有制约关系。2 在操作系统中引入管程的目的是什么？条件变量的作用是什么？答：用信号量可以实现进程的同步于互斥，但要设置许多信号量，使用大量的 P、V 操作，而且还要仔细安
12、排 P 操作的排列次序，否则将会出现错误的结果或是死锁现象。为了解决这些问题引进了管程；条件变量的作用是使进程不仅能被挂起，而且当条件满足且管程再次可用时，可以恢复该进程并允许它在挂起点重新进入管程。3 说明 P、V 操作为什么要设计成原语。答: 用信号量 S 表示共享资源，其初值为 1 表示有一个资源。设有两个进程申请该资源，若其中一个进程先执行 P 操作。P 操作中的减 1 操作有 3 跳及其指令组成：去 S 送寄存器 R;R-1 送 S。若 P 操作不用原语实现，在执行了前述三条指令中的 2 条，即还未执行 R 送 S 时（此时 S 值仍为 1） ，进程被剥夺 CPU，另一个进程执行也要
13、执行 P 操作，执行后 S 的值为 0，导致信号量的值错误。正确的结果是两个进程执行完 P 操作后，信号量 S 的值为-1 ，进程阻塞。4 设有一个售票大厅，可容纳 200 人购票。如果厅内不足 200 人则允许进入，超过则在厅外等候；售票员某时只能给一个购票者服务，购票者买完票后就离开。试问：（1） 购票者之间是同步关系还是互斥关系？答：互斥关系。（2） 用 P、V 操作描述购票者的工作过程。semaphore empty=200;semaphore mutex=1;semaphore waiting=0；void buy() p(waiting);p(mutex);买票；v(mutex);
14、v(empty);void waiting()p(empty);等待；waiting+;5 进程之间的关系如图 3-16 所示，试用 P、V 操作描述它们之间的同步。S 1S 2S 6S 4S 3S 5ABCDEFGsemaphore A,B,C,D,E,F,G=0；S1,V(A),V(B)；P(A),S2,V(C)；P(B),S3,V(D),V(E)；P(D),S4,V(F)；P(E),S5,V(G)；P(C),P(F),P(G),S6；6 有 4 个进程 P1、P2、P3、P4 共享一个缓冲区，进程 P1 向缓冲区存入消息，进程 P2、P3、P4 从缓冲区中取消息，要求发送者必须等三个进程
15、都取过本消息后才能发送下调消息。缓冲区内每次只能容纳一个消息，用 P、V 操作描述四个进程存取消息的情况。答：semaphore p1=0；semaphore p2，p3,p4=1；semaphore cout=0；semaphore mutex=1；void main（）P(p2)；P(p3)；P(4)；V(cout)；write p1()P（p1） ；P(metux)；P(cout)；存入消息；V(p1)；V(metux)；Read p2() P(mutex)；P(p1)；读消息；V(p1)；V(p2)；V(metux)；Read p3() P(mutex)；P(p1)；读消息；V(p1)
16、；V(p3)；V(metux)；Read p4() P(mutex)；P(p1)；读消息；V(p1)；V(p4)； V(metux)；7 分析生产者消费者问题中多个 P 操作颠倒引起的后果。答：semaphore mutex=1；semaphore empty=n；semaphore full=0；int i,j；ITEM buffern;ITEM data_p,data_c;void producer()/*生产者进程*/ void consumer() /*消费者进程*/while(true) while(true) P(mutex) ;P(mutex); P(full);P(empty)
17、; data_c=bufferj;bufferi=data_p; j=(j+1)%n;i=(i+1)%n; V(mutex);V(mutex); V(empty);V(full); 若把生产者进程的 P 操作颠倒，消费者进程的 P 操作颠倒（如图） ，则生产者进程执行到 V(mutex)时，消费者就可以执行 P(mutex) 但由于 full=0，消费者进程不可执行 P(full);当生产者进程执行完 V(full)后，full=1，但由于 mutex=0，消费者进程无法执行，造成死锁。8 读者写者问题中写者优先的实现。答: semaphore Wmutex，Rmutex=1；int Rcou
18、nt=0；semaphore mutex=1void reader（） /*读者进程*/while(true)P(mutex);P(Rmutex);If(Rcount=0) P(wmutex);Rcount=Rcount+1 ;V(Rmutex);V(mutex); read;/*执行读操作*/ ；P(Rmutex)；Rcount=Rcount-1；if （Rcount=0） V（wmutex） ；V（Rmutex） ；void writer() /*写者进程*/while(true)P(mutex); P(wmutex);；write；/*执行写操作*/；V(Wmutex);V(mutex)
19、;9 写一个用信号量解决哲学家进餐问题不产生锁死的算法。semaphore chopstick5=1,1,1,1,1;semaphore mutex=1;void philosopher ()while(true)P(mutex);P(chopsticki);P(chopstick(i+1)%5);V(mutex);；eat；V(chopsticki);V(chopstick(i+1)%5);think;；10 一个文件可有若干个不同的进程所共享，每个进程具有唯一的编号。假定文件可由满足下列限制的若干个不同的进程同时访问，并发访问该文件的哪些进程的编号的总和不得大于 n，设计一个协调对该文件访
20、问的管程。答：11 用管程解决读者写者问题，并采用公平原则。答：习题四1 某进程被唤醒后立刻投入运行，能说明该系统采用的是可剥夺调度算法吗？答：不能说明，因为如果现在就绪队列中没有进程，那么唤醒的进程会立刻投入运行。2 在哲学家进餐问题中，如果将先拿起左边筷子的哲学家称为左撇子，先拿起右边筷子的哲学家称为右撇子。请说明在同时存在左、右撇子的情况下，任何的就坐安排都不能产生锁死。答：任何的就坐安排都不会构成环路，这就符合避免死锁的条件，所以不会产生死锁。3 系统中有 5 个资源被 4 个进程所共享，如果每个进程最多需要 2 个这种资源，试问系统是否会产生锁死？答：不会产生死锁；因为因为资源数可以
21、满足进程的需要，当其中的一个进程争取到剩下的一个资源可以执行，当执行完成以后会释放资源，供其他进程使用，所以不会产生死锁。4 计算机系统有 8 台磁带机，由 N 个进程竞争使用，每个进程最多需要 3 台。问：N 为多少时，系统没有死锁的危险？答：当 n 为 1、 2、3 时，没有死锁的危险；因为当 n 小于 3 时，每个进程分配 2 台磁带机，还有磁带机剩余，那么当其中的一个进程得到剩余的磁带机则可运行，运行结束后会释放磁带机，供其他进程使用，系统不会有死锁的危险；当 n 为 4 时，每台分配 2 台时没有剩余，则会产生死锁，当大于 5 时同样会死锁。5 系统有 5 个进程，它们的到达时间和服
22、务时间如表 4-8 所示。新进程（没有运行过）与老进程（运行过的进程）的条件相同时，假定系统选新进程运行。表 4-8 进程情况进程名 到达时间 服务时间A 0 3B 2 6C 4 4D 6 5E 8 2若按先来先服务（FCFS） 、时间片轮法（时间片 q=1） 、短进程优先（SPN） 、最短剩余时间优先（SRT，时间片 q=1） 、响应比高者优先（HRRN ）及多级反馈队列（MFQ ，第一个队列的时间片为 1，第 i（i1）个队列的时间片 q=2（ i-1） ）算法进行 CPU 调度，请给出各个进程的完成时间、周转时间、带权周转时间，及所有的进程的平均周转时间和平均带权周转时间。答：A B C
23、 D E平均周转时间 平均带权周转时间到达时间服务时间完成时间周转时间带权周转02 4 6 83 6 4 5 23 9 1 3 1 8 2 03 791 2 1 21 1 . 1 7 2 . 2 5 2 . 4 68 . 62 . 5 6F C F SA B C D E平均周转时间 平均带权周转时间到达时间服务时间完成时间周转时间带权周转02 4 6 83 6 4 5 24 1 8 1 7 2 0 1 54 1 6 1 3 1 4 71 . 3 3 2 . 6 7 3 . 2 5 2 . 8 3 . 51 0 . 82 . 7 1时间片轮转A B C D E平均周转时间 平均带权周转时间到达时
24、间服务时间完成时间周转时间带权周转02 4 6 83 6 4 5 23 9 1 5 2 0 1 13 7 1 1 1 4 31 1 . 1 7 2 . 7 5 2 . 8 1 . 57 . 67 . 6S P NA B C D E平均周转时间 平均带权周转时间到达时间服务时间完成时间周转时间带权周转02 4 6 83 6 4 5 23 2 0 8 1 5 1 03 1 8 4 9 21 3 1 1 . 8 17 . 21 . 5 6S R TA B C D E平均周转时间 平均带权周转时间到达时间服务时间完成时间周转时间带权周转02 4 6 83 6 4 5 23 9 1 3 2 0 1 53
25、 7 9 1 4 71 1 . 1 7 2 . 2 5 2 . 8 3 . 582 . 1 4H R R NA B C D E平均周转时间 平均带权周转时间到达时间服务时间完成时间周转时间带权周转02 4 6 83 6 4 5 23 1 7 1 8 2 0 1 43 1 5 1 4 1 4 61 2 . 5 3 . 5 2 . 8 31 0 . 42 . 5 6M F Q6 设系统中有 5 个进程 P1、P2、P3、P4、P5 ，有 3 种类型的资源 A、B、C，其中 A 资源的数量是 17，B 资源的数量是 5，C 资源的数量是 20，T0 时刻系统状态如表 4-9 所示。表 4-9 T0
26、时刻系统状态已分配资源数量 最大资源需求量 仍然需求资源数进程 A B C A B C A B CP1 2 1 2 5 5 9 3 4 7P2 4 0 2 5 3 6 1 3 4P3 4 0 5 4 0 11 0 0 6P4 2 0 4 4 2 5 2 2 1P5 3 1 4 4 2 4 1 1 0(1) 计算每个进程还可能需要的资源，并填入表的“仍然需要资源数”的栏目。(2) T0 时刻系统是否处于安全状态？为什么？答：处于安全状态，因为序列是一个安全状态。(3) 如果 T0 时刻进程 P2 又有新的资源请求（0,3,4） ，是否实施资源分配？为什么？答：不实施资源分配，因为将所有资源都分配
27、给 p2 时，p2 的 C 是 5，不能够运行，进入死锁。(4) 如果 T0 时刻，若进程 P4 又有新的资源请求（2，0,1） ，是否实施资源分配？为什么？答：实施；因为 p4 请求资源后，存在安全状态。(5) 在（4）的基础上，若进程 P1 又有新的资源请求（0,2,0） ，是否实施资源分配？为什么？答：不实施；习题五1 存储管理的基本任务是为多道程序的并发执行提供良好的存储环境，这包括哪些方面？答：存储管理的基本任务是为多道程序的并发执行提供良好的存储器环境，它包括以下几个方面。（1）能让没到程序“各得其所” ，并在不受干扰的环境中运行时，还可以使用户从存储空间的分配、保护等事物中解脱出来。（2）向用户提供更大的存储空间，使更多的程序同时投入运行或是更大的程
