操作系统计算题总结.pdf

一、第三章的计算有点多 （ＰＶ操作，银行家算 法，低级调度算法） ＰＶ操作 操作系统的进程管理中，PV是重点和难点 信号量：信号量是个数据结构。 struct semaphore{int value;pcb *blockqueue;}mutex; 其中value是信号量的值；blockqueue是等待使用该信号量的进程排成的 队列的对手指针。 p操作：当一个进程对信号量mutex执行p操作时，执行两个动作： mutex.valu– ； // 申请一个资源 if (mutex.value0) // 申请失败 sleep(); //本进程进入该信号量等待队列睡眠 v操作：当一个进程对信号量mutex执行v操作时，执行两个动作： mutex.value++ ； //释放一个资源 if (mutex.value=0) //如果有进程在等待信号量 wakeup(); //从该信号量的等待队列中唤醒一个进程 注：操作系统会保证PV操作的原子性，也就是说当一个进程执行PV操 作，检测信号量时，不受中断。 看一下PV操作实现的功能： 实现进程之间的互斥； 实现进程之间的同 步； （接下来的两个例题是互斥与同步的 典型） 区别：互斥是为了保证资源一次只能由一个进程使用，互斥进程彼此在 逻辑上是完全无关的，它们的运的运行不具有时间次序的特征。而同步 是为了实现进程通信，同步进程之间具有合作关系，在执行时间上须按 照一定顺序协同进行。 1.互斥：进出教室问题：有一个变量count ，初值为0，一个学生进入 教室则count++，出教室则count–- 。 mutex = 1; IN: OUT : p(mutex); p(mutex); count++; count–; v(mutex); v(mutex); 过程：一个学生进入教室执行IN，p操作，mutex.value = 0 ；假设在进行 count++之前遇到了中断，而中断之后跳回来时正好这个学生又在出教 室，那么这时候就会执行OUT ，mutex.value = -1，该OUT进程进入睡 眠，返回IN进程，count = 1，v操作，mutex.value = 0 （说明有等待使用 count 的进程）；唤醒OUT进程，count = 0，v操作，mutex.value = 1。 注意上面划线部分的假设。PV操作在这就是为了保证这种竞争情况的发 生。 2. 同步：桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹 果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹 果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现 爸爸、儿子、女儿三个并发进程的同步。 分析：在本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一 个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中 的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则 允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种 变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类 消费者只消费其中固定的一类产品。 解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为 空，其初值为l；信号量So表示盘中是否有桔子，其初值为0 ；信号量Sa 表示盘中是否有苹果，其初值为0 。同步描述如下： int S ＝1;int Sa ＝0;int So ＝0; main() {cobegin father(); son(); daughter(); coend ｝ father() {while(1) {P(S); 将水果放入盘中; if （放入的是桔子）V(So); else V(Sa); } } son() {while(1) {P(So); 从盘中取出桔子; V(S); 吃桔子; ｝ } daughter() {while(1) {P(Sa); 从盘中取出苹果; V(S); 吃苹果; ｝ ｝ 一些