找到该进程的PCB，从中读出该进程的状态，终止该进程的执行，如果该进程还有子孙进程，应该将它的所有子孙进程终止，防止它们成为不可控进程；然后回收进程所拥有的资源；最后将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其它程序来搜集信息。 (14) 什么是线程？请比较它与进程的异同。
解：
线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程基本上不拥有资源，只需要一些必不可少的资源(如程序计数器、一组寄存器和栈)。
进程和线程的差异：
1. 在传统的OS中，进程是拥有资源和独立调度分派的基本单位，在加入线程的OS
中，线程是代替进程成为独立调度和分派的基本单位，进程则仍是拥有资源的基本单位。
2. 并发粒度不同。除了不同进程的线程之外，同一个进程里的不同线程之间也可以并
发执行，所以线程拥有更好的并发性。 3. 拥有资源数量不同。进程是拥有资源的基本单位，线程除了一些在运行过程中必不
可少的资源外，基本上不拥有系统资源，它可以访问自己所在的进程的资源。 4. 管理开销不同。创建、撤销进程时系统都要为之分配和回收资源，所以进程切换用
的时间开销相对要多于线程。进程间通信很麻烦，而同一进程的线程则通过共享进程的资源很方便地通信和同步，同步开销小得多。
进程和线程有着很多相似的地方：都可以并发执行；都有就绪、执行、阻塞这些基本状态，也都可以在这些基本状态之间转换状态；从创建到撤销都有一定的生命周期；都需要同步工具。
(15) 处理器调度的层次有哪些？各层次的主要工作是什么？
解：
处理器调度的层次分为三级调度：高级调度、中级调度和低级调度。
? 高级调度：它需要做出两个决定，一个是要从驻留在外存后备队列中调入多少个
作业，二是要调入哪几个作业；然后为被选中的作业创建进程，并分配必要的系统资源，如内存、外设等，然后把新创建的进程放入就绪队列中，等待被调度执行。
? 中级调度：中级调度主要涉及进程在内存和外存之间的交换。当系统中的内存使
用情况紧张时，中级调度把内存中暂时不能运行的进程调到外存中等待，等内存有足够的空闲空间时，再由中级调度决定将外存上的某些具备了运行条件的就绪进程调入内存，把其状态修改为就绪状态并挂在就绪队列中，等待进程调度。 ? 低级调度：按照一定的算法从就绪队列中选择一个进程，然后将处理器分配给它。
执行低级调度功能的程序称作进程调度程序，由它实现处理器在进程间的切换。
(16) 抢占式调度的原则是什么？请简要说明。
解：系统使用抢占方式进行进程调度时需要遵循一定的原则，主要有以下几个方面： 1. 时间片原则。各进程按系统分配给的一个时间片运行，当该时间片用完或由于该进
程等待某事件发生而被阻塞时，系统就停止该进程的执行而重新进行调度。 2. 优先级原则。每个进程均被赋于一个调度优先级，通常一些重要和紧急的进程被赋
于较高的优先级。当一个新的紧迫进程到达时，或者一个优先级高的进程从阻塞状态变成就绪状态时，如果该进程的优先级比当前进程的优先级高，OS就停止当前进程的执行，将处理器分配给该优先级高的进程，使之执行。 3. 短进程优先原则。当新到达的作业对应的进程比正在执行的作业对应进程的运行时
间明显短时，系统剥夺当前进程的执行，而将处理器分配给新的短进程，使之优先
执行。
(17) 在批处理系统、分时系统、实时系统中，应分别采用哪种作业(进程)调度算法？
解：
批处理系统采用“先来先服务调度算法”；分时系统采用“时间片轮转法”；实时系统采用“高响应比优先调度算法”。
(18) 说明时间片轮转调度算法的基本思路。
解：
在采用时间片轮转调度算法的系统中，将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序暂停当前进程的执行，将其送到就绪队列的末尾，并通过CPU现场切换执行当前的队首进程，当然，进程可以未使用完一个时间片，就让出CPU(如阻塞)。这样可以保证就绪队列中的所有进程都有机会获得处理器而运行的机会，可以提高进程并发性和响应时间特性，从而提高资源利用率。 (19) 试说明多级反馈队列调度算法思想。
解：多级反馈队列调度算法则不必事先知道各进程的执行时间，又可以满足各种类型进程的调度需要，它是一种目前公认较好的进程调度算法。它的算法思想如下(设采用抢占式调度)：
1. 需要设置多个就绪队列，并且为它们分别赋予不同的优先级。每队列分配不同的时
间片，规定优先级越低则时间片越长。
2. 新进程就绪后，先插入队列1的末尾，按FCFS算法调度。若一个时间片未能执行
完，则降低插入到队列2的末尾；依此类推，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
3. 进程由于等待事件而放弃CPU后, 进入等待队列, 一旦等待的事件发生, 则回到原
来的就绪队列。
4. 只有当较高优先级的队列为空时，才调度较低优先级队列中的进程执行。如果进程
执行时有新进程进入较高优先级的队列，则需要重新调度，抢先执行新进程，并把被抢先的进程插入原队列的末尾。
(20) 什么是静态和动态优先级？如何确定静态优先级？
解：
静态优先级是在系统创建时确定的，一经确定之后在整个进程运行期间不再改变。 动态优先级是在进程运行前先确定一个优先级，进程运行过程中根据进程等待时间的长短、执行时间的多少、输入输出信息量的大小等，通过计算得到新的优先级。
(21) 在一个单道批处理系统中，一组作业的到达时间和运行时间如下表所示。试计算使用先来先服务、短作业优先、高响应比优先算法时的平均周转时间和平均带权周转时间。
作业 1 2 3 4 到达时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 解：
用T表示周转时间，用W表示带权周转时间
FCFS的作业调度情况如下： 作业 1 2 3 4 提交时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 开始时间 8.0 9.0 9.5 9.7 结束时间 9.0 9.5 9.7 9.8 周转时间 1.0 1.0 0.7 0.7 带权周转时间 1.0 2.0 3.5 7.0 FCFS的T =（1.0+1.0+0.7+0.7）/ 4 = 0.85 W =（1.0+2.0+3.5+7.0）/ 4 =3.375 SJF的作业调度情况如下： 作业 1 2 3 4 提交时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 开始时间 8.0 9.3 9.0 9.2 结束时间 9.0 9.8 9.2 9.3 周转时间 1.0 1.3 0.2 0.2 带权周转时间 1.0 2.6 1.0 2.0 SJF的T=（1.0+1.3+0.2+0.2）/ 4 = 0.675 W =（1.0+2.6+1.0+2.0）/ 4 = 1.65 高响应比优先的作业调度情况如下： 作业 1 2 3 4 提交时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 开始时间 8.0 9.0 9.6 9.5 结束时间 9.0 9.5 9.8 9.6 周转时间 1.0 1.0 0.8 0.5 带权周转时间 1.0 2.0 4.0 5.0 高响应比算法的T=（1.0+1.0+0.8+0.5）/ 4 = 0.825 W =（1.0+2.0+4.0+5.0）/ 4 = 3.0
第4章 进程同步与死锁
(1) 什么是进程同步？什么是进程互斥？
解：
同步是进程间的直接制约关系，这种制约主要源于进程间的合作。进程同步的主要任务就是使并发执行的各进程之间能有效地共享资源和相互合作，从而在执行时间、次序上相互制约，按照一定的协议协调执行，使程序的执行具有可再现性。
进程互斥是进程间的间接制约关系，当多个进程需要使用相同的资源，而此类资源在任一时刻却只能供一个进程使用，获得资源的进程可以继续执行，没有获得资源的进程必须等待，进程的运行具有时间次序的特征，谁先从系统获得共享资源，谁就先运行，这种对共享资源的排它性使用所造成的进程间的间接制约关系称为进程互斥。互斥是一种特殊的同步方式。
(2) 进程执行时为什么要设置进入区和退出区？
解：
为了实现多个进程对临界资源的互斥访问，必须在临界区前面增加一段用于检查欲访问的临界资源是否正被访问的代码，如果未被访问，该进程便可进入临界区对资源进行访问，并设置正被访问标志，如果正被访问，则本进程不能进入临界区，实现这一功能的代码成为“进入区”代码；在退出临界区后，必须执行“退出区”代码，用于恢复未被访问标志。 (3) 同步机构需要遵循的基本准则是什么？请简要说明。
解：
同步机制都应遵循下面的4条准则：
1. 空闲让进。当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行
有限的时间。
2. 忙则等待。当有一个进程在临界区时，其它欲进入临界区的进程必须等待，以保证
进程互斥地访问临界资源。
3. 有限等待。对要求访问临界资源的进程，应保证进程能在有限时间内进入临界区，
以免陷入“饥饿”状态。
4. 让权等待。当进程不能进入临界区时，应立即放弃占用CPU，以使其它进程有机会得到CPU的使用权，以免陷入“饥饿”状态。
(4) 整型信号量是否能完全遵循同步机构的四条基本准则？为什么？
解：
不能。在整型信号量机制中，未遵循“让权等待”的准则。
(5) 在生产者-消费者问题中，若缺少了V(full)或V(empty)，对进程的执行有什么影响？
解：
如果缺少了V(full)，那么表明从第一个生产者进程开始就没有对信号量full值改变，即使缓冲池存放的产品已满了，但full的值还是0，这样消费者进程在执行P(full)时会认为缓冲池是空的而取不到产品，那么消费者进程则会一直处于等待状态。
如果缺少了V(empty)，例如在生产者进程向n个缓冲区放满产品后消费者进程才开始从中取产品，这时empty=0，full=n，那么每当消费者进程取走一个产品时empty并没有被改变，直到缓冲池中的产品都取走了，empty的值也一直是0，即使目前缓冲池有n个空缓冲区，生产者进程要想再往缓冲池中投放产品会因申请不到空缓冲区而被阻塞。 (6) 在生产者-消费者问题中，若将P(full)和P(empty)交换位置，或将V(full)或V(empty)交换位置，对进程执行有什么影响？
解：
对full和empty信号量的P、V操作应分别出现在合作进程中，这样做的目的是能正确表征各进程对临界资源的使用情况，保证正确的进程通信联络。 (7) 利用信号量写出不会出现死锁的哲学家进餐问题的算法。
解：
对哲学家按顺序从0到4编号，哲学家i左边的筷子的编号为i，哲学家右边的筷子的编号为（i+1）%5。
semaphore chopstick[5]={1};
//定义信号量数组chopstick[5]，由于侉子是临街资源（互斥），故设置初值均为1。 Pi(){
//i号哲学家的进程 do{
if(i<(i+1)%5) {
wait(chopstick[i]);
wait(chopstick[(i+1)%5]); } else {
wait(chopstick[(i+1)%5]); wait(chopstick[i]); }
eat
signal(chopstick[i]);
signal(chopstick[(i+1)%5]); think }while(1); }
(8) 利用AND型信号量和管程解决生产者-消费者问题。
解：
利用AND信号量解决生产者－消费者问题的算法描述如下： var mutex,empty,full: semaphore:=1,n,0;
buffer: array[0,...,n-1] of item; in out: integer := 0, 0; begin
parbegin
producer: begin repeat . . .
produce an item in nextp; . . .
Swait(empty, mutex); buffer(in) := nextp; in := (in+1) mod n; Ssignal(mutex, full); until false; end
consumer: begin repeat
Swait(full, mutex); nextc := buffer(out); out := (out+1) mod n; Ssignal(mutex, empty); consume the item in nextc; until false; end parend end
利用管程机制解决生产者-消费者问题，首先需要建立一个管程ProducerConsumer，其中包含两个过程insert(item)和consumer(item)。生产者-消费者同步问题可以用伪代码描述如下：
monitor ProducerConsumer