操作系统第六次作业.doc

操作系统第五次作业6.1 第一个著名的正确解决两个进程的临界区问题的软件方法是Dekker设计的。两个进程P0和P1共享以下变量： boolean flag2; /*initially false*/ int turn;进程Pi(i=0或1)的结构见图6.25，另一个进程是Pj(j=0或1)。试证明这个算法满足临界区问题的所有三个要求。答：临界区的问题的解答必须满足以下三个条件：1)互斥：如果进程Pi在其临界区内执行，那么其他进程都不能在其临界区内执行。2)有空让进：如果没有进程在其临界区内执行且有进程需进入临界区，那么只有那些不在剩余区内执行的进程可参加选择，以确定谁能下一个进入临界区，且这种选择不能无限推迟。3)有限等待：从一个进程做出进入其临界区的请求，直到该请求允许为止，其他进程被允许进入其临界区的次数有上限。为了表述方便，接下来用0,1来代替i，j；首先两个进程共享以下变量： boolean flag2; /*initially false*/ int turn;flag用来记录谁要访问临界区，就让对应的flag=true（例如P0要访问临界区，就让flag0=true），相当于“举手示意我要访问”。初始值为0表示一开始没人要访问。trun用于标识当前允许谁进入，turn=0则P0可进入，turn=1则P1可进入。接下来看进程P0的逻辑doflag0 = true; /首先P0举手示意我要访问while(flag1) /看看P1是否也举手了if(turn=1) /如果P1也举手了，那么就看看到底轮到谁flag0=false; /如果确实轮到P1，那么P0先把手放下（让P1先）while(turn=1); / donothing /只要还是P1的时间，P0就不举手，一直等flag0=true; /等到P1用完了（轮到P0了），P0再举手/Criticalsection /访问临界区turn = 1; / P0访问完了，把轮次交给P1，让P1可以访问flag0=false; / P0放下手/ remainder section /剩余区while（1）；P1的逻辑和P0相同：doflag1 = true; /首先P1举手示意我要访问while(flag0) /看看P0是否也举手了if(turn=0) /如果P0也举手了，那么就看看到底轮到谁flag1=false; /如果确实轮到P0，那么P1先把手放下（让P0先）while(turn=0); / donothing /只要还是P0的时间，P1就不举手，一直等flag1=true; /等到P0用完了（轮到P1了），P1再举手/Criticalsection /访问临界区turn = 0; / P1访问完了，把轮次交给P0，让P0可以访问flag1=false; / P1放下手/ remainder section /剩余区while（1）；为了证明第一点，要注意到只有当flag0=true并且turn=0的时候，进程P0才会进入临界区。而当flag0=true，flag1=true表示P0和P1都想进入临界区的时候，P0和P1谁能进入临界区取决于turn的值，当turn=0时，P0可以进入，当turn=1时，P1可以进入；turn的值只可能是0或1，而不可能同时为两个值，所以一次只能有一个进程在临界区内，满足互斥的条件。为了证明第二点和第三点，应注意到，只要条件flag1=true，turn=1成立，flag0的值就会被设置成false，并且P0陷入while循环语句，那么P0就能被阻止进入临界区。如果P1不准备进入临界区（flag1=false）或者没有轮到P1进入临界区（turn=0），那么P0就能进入临界区。当P1退出临界区的时候，它会设置flag0=true，以允许P0进入临界区。当P0访问完之后退出临界区，它会设置turn=1和flag0=false，表示P0访问完了，把轮次交给P1，让P1能够访问，所以P1会进入临界区，满足前进的条件；同时P1最多在P0进入临界区一次之后就能进入，满足有限等待的条件。综上所述，Dekker算法是满足临界区问题的所有三个要求的。6.4请解释为什么自旋锁不适用于单处理器系统中，而是往往使用于多处理器系统中？自旋锁是专为防止多处理器并发而引入的一种锁，它在内核中大量应用于中断处理等部分（对于单处理器来说，防止中断处理中的并发可简单采用关闭中断的方式，即在标志寄存器中关闭/打开中断标志位，不需要自旋锁）。在单处理机环境中可以使用硬件提供的swap指令或test_and_set指令实现进程互斥，（Swap指令：交换两个内存单元的内容；test_and_set指令取出内存某一单元(位)的值，然后再给该单元(位)赋一个新值，关于为何这两条指令能实现互斥我们不在赘述，读者可以了解其算法） 这些指令涉及对同一存储单元的两次或两次以上操作，这些操作将在几个指令周期内完成，但由于中断只能发生在两条机器指令之间，而同一指令内的多个指令周期不可中断，从而保证swap指令或test_and_set指令的执行不会交叉进行.但在多处理机环境中情况有所不同，例如test_and_set指令包括“取”、“送”两个指令周期，两个CPU执行test_and_set(lock)可能发生指令周期上的交叉，假如lock初始为0, CPU1和CPU2可能分别执行完前一个指令周期并通过检测(均为0)，然后分别执行后一个指令周期将lock设置为1，结果都取回0作为判断临界区空闲的依据，从而不能实现互斥. 如图4-3所示.为在多CPU环境中利用test_and_set指令实现进程互斥，硬件需要提供进一步的支持，以保证test_and_set指令执行的原子性. 这种支持目前多以“锁总线”(bus locking)的形式提供的，由于test_and_set指令对内存的两次操作都需要经过总线，在执行test_and_set指令之前锁住总线，在执行test_and_set指令后开放总线，即可保证test_and_set指令执行的原子性。6.7描述如何用swap（）指令来实现互斥并满足有限等待要求利用Swap指令实现进程互斥的算法描述如下：do waitingi = TRUE; key = TRUE; while (waitingi & key) / 进程排队 Swap(&lock, &key); waitingi = FALSE; / 进程标注自己已进入临界区 / 临界区 j = (i+1) % n; while (j != i) & !waitingj) j = (j+1) % n; if (j = i) / 当前无其他进程排队则释放锁 lock = FALSE; else waitingj = FALSE; / 强制拉取后一个进程进入临界区 / 剩余区 while(TRUE); 可以看出，剩余区前的 while 循环保证一个进程 Pi 强制拉取了排在其后的进程 Pj 进入临界区（如果有的话），这保证了有限等待。使用到的共享数据有：boolean waitingn：waitingi = TRUE 表明进程 i 已申请进入临界区并正在等待选择。boolean lock：lock 是进程间共享的锁。6.11 理发店问题。一家理发店有一间有n把椅子的等待室和一间有一把理发椅的理发室。如果没有顾客，理发师就去睡觉。如果顾客来时所有的椅子都有人，那么顾客将会离去。如果理发师在忙，而又有空闲的椅子，那么顾客会坐在其中一个空闲的椅子上。如果理发师在睡觉，顾客会摇醒他。编写一个程序来协调理发师和顾客。答： 设计程序如下所示： 理发师进程和顾客进程共享以下数据结构： Semaphore mutex，barber，cutomers； int waiting；其中barber( )表示理发师程序，customer( )表示顾客程序，椅子数量为n；信号量mutex提供了进程之间的互斥要求，并初始化为1；waiting表示正在等待的顾客数量；cut-hair表示正在理发；get-haircut表示准备理发。 barber() while(TRUE); /理完一位顾客，还有顾客么？ P(cutomers); /如果没有顾客，理发师睡觉 P(mutex); /进程互斥 Waiting-=1; /等候顾客数少一个 V(barber); /理发师去为一个顾客理发 V(mutex); /开放临界区 cut-hair(); /正在理发Customers;(