球。
（3）果汁流水线生产中捣碎、消毒、灌装、装箱等各道工序。存在同步关系，因为后一道工序的开始依赖于前一道工序的完成。
（4）商品的入库和出库。存在同步关系，因为商品若没有入库就无法出库，若商品没有出库，装满了库房，也就无法再入库。
（5）工人做工与农民种粮。工人和农民之间没有相互制约关系。 2、说明P、V操作为什么要设计成原语？
用信号量S表示共享资源，其初值为1表示有一个资源。设有两个进程申请该资源，若其中一个进程先执行P操作。P操作中的减1操作由3条机器指令组成：取S送寄存器R；R-1送R；R送S。若P操作不用原语实现，在执行了前述三条指令中的2条，即还未执行R送S时（此时S的值仍为1），进程被剥夺CPU，另一个进程执行也要执行P操作，执行后S的值为0，导致信号量的值错误。正确的结果是两个进程执行完P操作后，信号量的值为-1，进程阻塞。
V操作也同样。所以要把信号量的P、V操作设计成原语，要求该操作中的所有指令要么都做，要么都不做。
3、设有一个售票大厅，可容纳200人购票。如果厅内不足200人，则允许进入，超过则在厅外等候；售票员某时只能给一个购票者服务，购票者买完票后就离开。试问：（1）购票者之间是同步关系还是互斥关系？（2）用P、V操作描述购票者的工作过程。
购票者之间是互斥关系。
P、V操作描述购票者的工作过程如下： semaphore empty=2000; semaphore mutex=1; void buyer() { P(empty); P(mutex); 购票; V(mutex); V(empty); }
售票大厅可容纳200人购票，说明最多允许200人共享售票大厅。引入一个信号量empty，初值为200；由于购票者必须互斥地购票，故再设置一个信号量mutex，初值为1。
4、分析生产者和消费者问题中多个P操作颠倒引起的后果。
答：如果将生产进程的两个P操作，即P（empty）和P（mutex）的位置互换，生产者和消费者问题描述如下：
semaphore mutex=1; semaphore empty=n; semaphore full=0; int i,j;
ITEM buffer[n], data_p, data_c;
void producer() /*生产者进程*/ { while(true)
{ produce an item in data_p; P（empty） P（empty）
buffer[i] = data_p;
i=(i+1)%n; V（nutex）; V（full）; }
}
void consumer() /*消费者进程*/ { while(true) { P（full） P（mutex）
data_c = buffer[j];
j=(j+1)%n; V（nutex）; V（empty）;
consume the item in data_c; }
}
按上面的描述，当生产者进程生产了n个产品而使缓冲区满时，生产者如若继续执行，可能顺利通过P（mutex）。但当执行P（empty）时，由于缓冲区已满，生产者将在信号量empty上等待。若之后消费者欲取产品，执行P（full）顺利通过，但当执行P（mutex）时，由于生产者获得了进入临界区的权力，消费者只能在mutex上等待。此时生产者在empty上等待，消费者在mutex上等待，从而导致生产者等待消费者取走产品，消费者等待生产者释放缓冲区，这种相互等待就造成系统死锁。
4 调度与死锁
1、某进程被唤醒后立即投入运行，能说明系统采用的是可剥夺调度算法吗？
不能。如果当前就绪队列为空，被样被唤醒的进程就是就绪队列中唯一的一个进程，于是调试程序自然选中它投入运行。
2、在哲学家进餐问题中，如果将先拿起左边筷子的哲学家称为左撇子，将先拿起右边筷子的哲学家称为右撇子。请说明在同时存在左、右撇子的情况下，任何的就座安排都不能产生死锁。
该题的关键是证明该情况不满足产生的四个必要条件之一。在死锁的四个必要条件中，本题对于互斥条件、请求与保持条件、不可剥夺条件肯定是成立的，因此必须证明环路条件不成立。
对于本题，如果存在环路条件必须是左、右的哲学家都拿起了左（或右）边的筷子，而等待右（或左）边的筷子，而这种情况只能出现在所有哲学家都是左（或右）撇子的情况下，但由于本题有右（或左）撇子存在，因此不可能出现循环等待链，所以不可能产生死锁。
3、系统中有5个资源被4个进程所共享，如果每个进程最多需要两个资源，试问系统是否会产生死锁？ 由于资源数大于进程数，所以系统中总会有一个进程获得的资源数大于等于2,该进程已经满足了它的最大需求，当它运行完毕后会把它占有的资源归还给系统，此时其余3个进程也能满足最大需求而顺利运行完毕。因此系统不会产生死锁。
4、计算机系统中有8台磁带机，由N个进程竞争使用，每个进程最多需要3台。问当N为多少时，系统没有死锁的危险？
当N<4时，系统没有死锁的危险。因为当N为1时，它最多需要3台磁带机，系统中共有8台，其资源数已足够1个进程使用，因此绝对不会产生死锁；当N为2时，两个进程最多需要6台磁带机，系统中共有8台，其资源数也足够两个进程使用，因此也不会产生死锁；当N为3时，无论如何分配，3个进程中必有进程得到3台磁带机，该进程已经达到它的最大需求，当它运行完毕后可释放这3台磁带机，这就保证了其他两个进程也可顺利执行完毕。因此当N<4时，系统没有死锁的危险。
当N＝4时，假设4个进程都得到两个资源，此时系统中已没有剩余资源，而4个进程都没有到达它们的最大需求，所以系统有可能产生死锁。同理，当N>4时，也有产生死锁的危险。
5、设系统中有5个进程P1、P2、P3、P4和P5，有三种类型的资源A、B和C，其中A资源的数量是17，B资源的数量是5，C资源的数量是20，T0时刻系统状态如下表。回答以下问题：（1）计算每个进程还可能需要的资源，并填入表的“仍需要资源数”栏目中。（2）T0时刻系统是否处于安全状态？为什么？（3）如果T0时刻进程P2又有新的资源请求（0,3,4），是否实施资源分配？为什么？（4）如果T0时刻进程P4又有新的资源请求（2,0,1），是否实施资源分配？为什么？（5）在第（4）题的基础上，若进程P1又有新的资源请求（0,2,0），是否实施资源分配？为什么？ 进程 P1 P2 P3 P4 P5 已分配资源数量 A 2 4 4 2 3 B 1 0 0 0 1 C 2 2 5 4 4 最大资源需求量 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 仍然需求资源数 A B C
（1）5个进程P1、P2、P3、P4和P5仍然需要A、B和C，三类资源数量如下表： 进程 P1 P2 P3 P4 P5 已分配资源数量 A 2 4 4 2 3 B 1 0 0 0 1 C 2 2 5 4 4 最大资源需求量 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 仍然需求资源数 A 3 1 0 2 1 B 4 3 0 2 1 C 7 4 6 1 0 （2）由已知条件，系统中A、B和C，三类资源的总数是（17,5,20），从表中可以计算出已分配情况是（15,2,17），剩余可用资源的数量是（2,3,3），如果先让进程P5执行，可以满足它的最大需求。当进程P5运行完毕，又可释放它占有的资源，使系统中可用资源的数量增加为（5,4,7）；此时可让P4执行，满足它的最大需求后又可释放它占有的资源，使系统中可用资源的数量增加为（7,4,11）；然后让P3执行，满足它的最大需求后又可释放它占有的资源，使系统中可用资源的数量增加为（11,4,16）；之后可让P2和P1执行。这样所有进程都可运行完毕，系统是在T0时刻存在安全序列{P5,P4,P3,P2,P1}，所以系统是安全的。
（3）如果T0时刻进程P2又有新的资源请求（0,3,4），进程P2请求资源数（C资源只剩下3个，而进程P2请求4个）大于剩余可用资源的数据（2,3,3），所以不能分配。
（4）如果T0时刻进程P4又有新的资源请求（2,0,1），按银行家算法进行检查，进程P4请求资源数（2,0,1）+已分配资源数量（2,0,4）小于进程P4的最大需求数量（4,2,5）；另外进程P4请求资源数（2,0,1）小于剩余可用资源的数量（2,3,3）；如果满足进程P4新的资源请求，进程P4新仍然需求资源数变为（0,2,0），如下表所示。 进程 已分配资源数量 A B C 最大资源需求量 A B C 仍然需求资源数 A B C P1 P2 P3 P4 P5 2 4 4 4 3 1 0 0 0 1 2 2 5 5 4 5 5 4 4 4 5 3 0 2 2 9 6 11 5 4 3 1 0 0 1 4 3 0 2 1 7 4 6 0 0 系统中剩余可用资源的数量为（0,3,2）；用安全算法进行检查可以得到安全序列{P4,P5,P3,P2,P1}，所以系统是安全的，可以满足进程P4的资源请求。
（5）在第（4）题的基础上，若进程P1又有新的资源请求（0,2,0），按银行家算法进行检查，进程P1请求资源数（0,2,0）+已分配资源数量（2,1,2）小于进程P4的最大需求数量（5,5,9）；另外进程P1请求资源数（0,2,0）小于剩余可用资源的数量（0,3,2）；如果满足进程P1新的资源请求，进程P1新仍然需求资源数变为（3,2,7），如表所示。 进程 P1 P2 P3 P4 P5 已分配资源数量 A 2 4 4 2 3 B 1 0 0 0 1 C 2 2 5 4 4 最大资源需求量 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 仍然需求资源数 A 3 1 0 0 1 B 2 3 0 2 1 C 7 4 6 0 0 系统中剩余可用资源的数量为（0,1,2），已不能满足任何进程的资源需要，故系统进入不安全状态，此时不能将资源分配给进程P1。
5 存储管理
1、存储管理的基本任务是为多道程序的并发执行提供良好的存储器环境，这包括哪些方面？ 存储管理的基本任务是为多道程序的并发执行提供良好的存储器环境，它包括以下几个方面：（1）能让每道程序“各得其所”，并在不受干扰的环境中运行时，还可以使用户从存储空间的分配、保护等事物中解脱出来；（2）向用户提供更大的存储空间，使更多的程序同时投入运行或使更大的程序能在小的内存中运行。（3）为用户对信息的访问、保护、共享以及程序的动态链接、动态增长提供方便；（4）能使存储器有较高的利用率。
2、页式存储管理系统是否产生碎片？如何应对此现象？
页式存储管理系统产生的碎片称为内碎片，它是指一个进程的最后一页没有占满一个存储块而被浪费的存储空间。减少内碎片的办法是减小页的大小。
3、在页式存储管理系统中页表的功能是什么？当系统的地址空间很大时会给页表的设计带来哪些新问题？
页式存储管理系统中，允许将进程的每一页离散地存储在内存的任何一个物理页面上，为保证进程的正常运行，系统建立了页表，记录了进程每一页被分配在内存的物理块号。页表的功能是实现从页号到物理块号的地址映射。
当系统的地址空间很大时，页表也会变得非常大，它将占有相当大的内存空间。例如，对于一个32位地址空间的页式系统，假设页的大小为4KB，则一个进程的页表项最大可达到1MB。如果每个页表项占4B，则页表要占用4MB的连续内存空间。为了解决这个问题可以从以下两个方面入手。（1）将页表离散存放。（2）只将页表的一部分调入内存，其余部分放在外存。
具体的实现方案是采用两级页表。对页表分页，使每个页面的大小与内存的物理块的大小一致。并为它们进行编号，将各个页面放在不同的物理块中。然后为这些离散分配的页表再建立一张页表，称为外层页表（或页目录），此时的逻辑地址可描述为：
外层页号+页号+页内位移
对于要运行的进程，将其外层页表调入内存，对所有的页表而言只需调入少量的页表，使用时如果找不到相应的页表，则产生中断，请求操作系统将需要的页表调入内存。
两级页表适应了大地址空间的需要，需要虚拟存储技术的支持，增加了地址变换的开销和管理的复杂度。此外根据需要还可以设计三级页表、四级页表等。
4、什么是动态链接？用哪种存储管理方案可以实现动态链接？
动态链接是指进程在运行时，只将进程对应的主程序段装入内存，在主程序运行过程中，当需要用到哪个子程序段和数据段时，再将这些段装入内存，并与主程序段链接上。
通常一个大的程序是由一个主程序和若干个以及一些数据段组成的。而段式存储管理方案中的段就是按用户的逻辑段自然形成的，因此可实现动态链接。
5、某进程的大小为25F3H字节，被分配到内在的3A6BH字节开始的地址。（1）若使用上、下界寄存器，寄存器的值是多少？如何进程存储保护？（2）若使用地址、限长寄存器，寄存器的值是多少？如何进程存储保护？
（1）若使用下、下界寄存器，上界寄存器的值是3A6BH，下界寄存器的值是3A6BH+25F3H=605EH，当访问内在的地址大于605EH、小于3A6BH时产生越界中断。
（2）若使用地址、限长寄存器，地址寄存器值是3A6BH，限长寄存器的值是25F3H，当访问内存的地址小于3A6BH，超过3A6BH+25F3H=605EH时主生越界中断。
6、在系统中采用可变分区存储管理，操作系统占用低地址部分的126KB，用户区的大小是386KB，若采用空闲分区表管理空闲分区。若分配时从高地址开始，对于下述的作业申请序列：作业1申请80KB；作业2申请56KB；作业3申请120KB；作业1完成；作业3完成；作业4申请156KB；作业5申请80KB。试用首次适应法处理上述作业，并回答下面问题。（1）画出作业1、2、3进入内存后。内存分布情况。（2）画出作业1、3完成后。内存的分布情况。（3）画出作业4、5进入内存后。内存分布的情况。
（1）作业1、2、3进入内存后，内存分布如下图
0KB 操作系统126KB 126KB 256KB 作业3:120KB 376KB 作业2:56KB 432KB 作业1:80KB 512-1KB （2）作业1、3完成后，内存的分布情况如下图