logo资料库

操作系统的经典PV操作详解.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.13M 资料格式：doc 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    经典 P、V 操作问题详解 lionxcat@gmail.cn 一、基本概念 1. 信号量 struct semaphore { int value; // 仅且必须附初值一次，初值非负 PCBtype* wait_queue; // 在此信号量上阻塞的进程队列 // 信号量实例为 S } S; 2. P、V 操作 P(S){ S := S-1; if (S<0) 调用进程自己阻塞自己，等待在 S 的等待队列末尾; } V(S){ S := S+1; if (S≤0) 从 S 等待队列头释放一进程就绪在就绪队列尾; 调用进程继续执行; } 3. 使用方法 (i). P、V 操作成队出现，处理互斥时出现在同一进程中；处理同步时出现在不同进程中。 (ii). 同步 P 先于互斥 P 调用，V 的顺序无关。 4. 另类 P、V 操作导致的问题(或信号量的栈实现方法或漏斗法) [习题P174-23] 某系统如此定义 P、V 操作： P(S): V(S): (1)上面定义的 P、V 操作是否合理？有什么问题？ (2)现有四个进程 P1、P2、P3、P4 竞争使用某一个互斥资源（每个进程可能反复使用多次），试 用上面定义的 P、V 操作正确解决 P1、P2、P3、P4 对该互斥资源的使用问题。 S = S-1; 若 S＜0，本进程进入 S 信号量等待队列的末尾；否则，继续执行。 S＝S+1; 若 S≤0，释放等待队列中末尾的进程，否则继续运行。 答： (1)不合理：先进后出；可能“无限等待”，即等待队列头的进程得不到释放。 (2)思路：令每个信号量上的等待队列中始终只有一个进程。解决方案如下：(n 个进程) n 个进程至多有 n-1 个等待。设置 n-1 个信号量，每个进程阻塞在不同的信号量上，使每个等待 队列至多有一个进程等待。用循环模拟队列。 Semaphore S[n-1]; // S[i]的初值为 i+1
    Procedure_i() { int j; DO_PRE_JOB(); for(j=n-2; j>=0; j--) P(S[j]); DO_JOB_IN_CRITICAL_SECTION(); for(j=0;j<=n-2;j++) V(S[j]); …… } 二、经典进程同步问题 总述：进程同步问题主要分为以下几类：一（生产者－消费者问题）；二（读者写者问题）；三（哲 学家就餐问题）；四（爱睡觉的理发师问题）；五（音乐爱好者问题）；六（船闸问题）；七（红黑 客问题）等。其中前两类都是用于处理进程之间通信的问题：生产者－消费者问题主要实现进程 的消息机制，而读者－写者问题用于实现管道通信。哲学家就餐问题是经典的互斥转同步防止死 锁的多资源争夺。理发师问题适合 I/O 或外部设备的管理，如打印调度。红黑客问题是解决不同 条件触发事件的思想方法。 I. 生产者—消费者问题(初始缓冲区为空) 问题：生产者生产产品放到缓冲区，消费者从缓冲区取产品消费。 ①单缓冲区[书P119](适合单或多生产消费者)： 同步：生产者不能往满缓冲区放产品(S1(1))；消费者不能从空缓冲区取产品(S2(0))。 void Producer() { while (true){ void Consumer() { while (true){ 生产一个产品; P(S1); 申请一个空的缓冲区 放到缓冲区; V(S2); 返回一个满的缓冲区 P(S2); 申请一个满的缓冲区 从缓冲区取一个产品; V(S1); 返回一个空的缓冲区 消费产品; }} ②环行多缓冲区（或无穷缓冲区）单生产消费者[习题P173-13]： 同步：生产者不能往满缓冲区放产品(S1(n))；消费者不能从空缓冲区取产品(S2(0))。n 为缓冲区 }} 大小。 互斥：设置指示下一个空缓冲区的位置变量(i(0))和指示下一个产品在缓冲区的位置变量(j(0))，由 于只有一个生产者和消费者，i 和 j 无须互斥访问。此问题无互斥关系。 void Producer() { while (true){ 生产了一个产品; P(S1); 把产品放入缓冲区; i = (i+1)%n; // 无穷缓冲区无须’%n’ V(S2); }} ③环行多缓冲区多生产消费者[书P120]： }} void Consumer() { while (true){ P(S2); 取一个产品; j = (j+1)%n; // 无穷缓冲区无须’%n’ V(S1); 消费产品;
    同步：生产者不能往满缓冲区放产品(S1(n))；消费者不能从空缓冲区取产品(S2(0))。n 为缓冲区 大小。 互斥：设置指示下一个空缓冲区的位置变量(i(0))，生产者之间互斥(mutex1(1))；设置指示下一个 产品在缓冲区的位置变量(j(0))，消费者之间互斥(mutex2(1))。也可以生产者和消费者之间 都互斥(把 mutex1 和 mutex2 都换成一个 mutex(1))。 void Producer() { while(true){ void Consumer() { while(true){ 生产一个产品; P(S1); 申请一个空的缓冲区 P(mutex1); 一个生产者申请制造产 品 缓冲区 放到缓冲区; i = (i+1)%n; 指针移动到下一空的 区 V(mutex1); 释放生产者 V(S2); 释放一个满的缓冲区 }} P(S2); 申请一个满的缓冲区 P(mutex2); 一个消费者申请消费 从第 j 个缓冲区取一个产品; j = (j+1)%n; 指向下一个满的缓冲 V(mutex2); 释放消费者 V(S1);释放一个空的缓冲区 消费产品; }} ④用进程通信(信箱通信)的方法解决上述问题[习题P175-27]: void Consumer() void Producer() { { msgbuff mb; // empty message msgbuff mb; //message buffer while (1){ for(int i=0 ; i
    P(m-mutex); 把缓冲区挂到 m-q 上; V(b-mutex); } V(m-mutex); V(m-syn); } ⑥进程信箱通信[书P130，06 年秋讲义]： 问题：发送进程把信息发到信箱中，接收进程随时取信。 同步：发送进程不能向满信箱中发信(full(0))；接收进程不能从空信箱中取信(empty(1))。 receive(N,X) // 从信箱 N 中取一封信放到 X send(N,M) // 把信件 M 发到信箱 N 中 { { 查找信箱 N; 查找信箱 N; P(empty); P(full); 把 M 送入信箱 N; 从信箱 N 中取一封信放到 X; V(full); V(empty); } } ⑦进程通信多发送接收者问题[习题P174-16]： 问题：n1 个进程通过 m 个缓冲区向 n2 个进程发送消息，每个消息所有接收进程都接收一次。 同步：发送者不能向满缓冲区发信息(mutex_send[m](1))； 接收者不能从空缓冲区接收信息(mutex_receive[m](0))。 互斥：设置指示下一个空缓冲区变量(cur(0))，发送进程互斥访问(mutex_cur(1))； 设置 buffer_count[m](0)记录某个缓冲区被读过几次，若某个缓冲区被读过 n2 次，则可以 释放，接收者互斥访问 buffer_count(mutex_count[m](1))。 阻塞分析：若接收者试图接收空缓冲区被阻塞在 mutex_receive[k]上，则其他要访问同一缓冲区 的接收者被堵塞在 mutex_count[k]上；若此时发送者向缓冲区 k 写入信息，则由第一个接 收者释放其他接收者。 若有一发送者被阻塞在 mutex_send[cur]上，则其他发送者被阻塞在 mutex_cur 上。 void send() { while (true){ P(mutex_cur); cur = (cur+1)% m; // 若阻塞则表示 cur 满 P(mutex_send[cur]); 写入 buffer[cur]; // cur 内容等待被读取 V(mutex_receive[cur]); V(mutex_cur); } } void receive() { While (true){ for (int i=0; i
    II. 读者—写者问题 读者—写者问题与生产者—消费者问题最大区别在于前者不存在同步问题，就是说不考虑读者没 有东西读的问题，没有可读的直接“走人”。而后者如果没有东西消费，就会阻塞等待。 第一类(读者优先)[书P121]： 问题：写者在写，则其余写者和读者等待； 有读者在读，则其他读者可读，直到没有读者写者才能写。 互斥：写者之间互斥以及所有读者和写者之间互斥(write(0/1))；读者之间不互斥； readcount 记录当前读者个数(readcount(0))，多个读者对 readcount 互斥访问，访问后加 上 1(mutex(1)); readcount 是一个可被多个读者进程访问的临界资源，所以需要设置一个 互斥信号 mutex 阻塞分析：当有读者在读时，所有写者堵塞在 write 上；有写者在写时，第一个读者阻塞在 write 上，其余的阻塞在 mutex 上，所有写者阻塞在 write 上。 void Reader() { P(mutex);一开始，读者申请一个位置去看书 void Writer() { P(write); readcount++;然后逐渐有更多的读者读书，自动加上 写; 1 if (readcount==1) // 第一个读者，可能有写者在写 P(write);为写者申请一个空间写东西 V(mutex);读者要释放空间或缓冲区了 P(mutex);为读者申请能读书的资源 readcount--;读者读不到足够的书 读者逐渐减少 if (readcount==0) // 没有读者了，释放写者 V(write); V(mutex);释放读者，让作者写书 } V(write);// 释放的可能是读者或写者 } /*相对读者优先，即写者可以释放写 者；也可改为绝对读者优先，即只要 有读者在，写者写完优先释放读者。 方法类似于写者优先。*/ 第二类(写者优先)[习题P175-24]： 问题：写者在写，则其余写者和读者等待；写者写完，优先释放下一个写者； 读者在读，若无写者等待，则其他读者可读；读者在读，若有写者等待，则其他读者等待。 互斥：写者之间互斥(write(1))，读者和写者之间互斥(read(1))；读者之间不互斥； 记录当前读者个数(readcount(0))和写者个数(writecount(0))，读者对 readcount 互斥访问 (mutex1(1))，写者对 writecount 互斥访问(mutex2(1))； 为保证在有读者等待的时候，新写者到来也优先释放写者，让等待的读者继续等待，不能 将读者和写者阻塞在同一队列上(mutex3(1))。 阻塞分析：当有写者在写时，其余写者阻塞在 write 上，第一个读者阻塞在 read 上，其他的读者 堵塞在 mutex3 上。当一个写者写完后，若有写者等待，则唤醒一个写者，否则唤醒第一 个读者，由第一个读者唤醒其余读者。 当有读者在读时，一读者 R 通过 P(read)还未 V(read)，此时新到来的第一位写者 W 阻塞在 read 上，其余写者阻塞在 mutex2 上；新到来的第一位读者 R1 阻塞在 read 上，其余读者 阻塞在 mutex3 上：（1）若正在等待的第一位写者 W 先于读者 R1 到来，则他先被读者 R 释放，接着 W 会释放其余写者，使原阻塞在 mutex2 上的写者通过 mutex2，重新阻塞在 write 上，而所有等待的读者仍然阻塞在原来的地方；（2）否则读者 R 先释放读者 R1，R1 代替 R 的位置，原来等待在 mutex3 上的第一位读者 R2 被阻塞在 read 上，但此时 R2 在
    read 等待队列上必处于写者 W 之后，成为情况（1）。因此可以看到，在下面的方案中， 新写者到来后，最多再放行一位读者。 void Reader() { P(mutex3);//若去掉则读者和写者先来后到 void Writer() { P(mutex2); P(read); P(mutex1);// 其实有了 read 无需 mutex1 writecount++; if (writecount==1) P(read); readcount++; if (readcount==1) P(write); V(mutex1); V(read); V(mutex3); reading; P(mutex1); readcount--; if (readcount==0) V(write); V(mutex1); } V(mutex2); P(write); writing; V(write); P(mutex2); writecount--; if (writecount==0) V(read); V(mutex2); } III. 哲学家就餐问题 [书P122，06 年秋讲义] 问题：n 个哲学家，n 支筷子，仅当一个哲学家两边的筷子都可用时才可以拿筷子。 互斥：设置 n 个哲学家的状态变量(state[n](thinking/hungry/eating)，初始值全 thinking)，用于判 断一个哲学家的左右筷子是否能用；设置 n 个信号量(s[n]，初始全 0)，用于判断哲学家是 否能吃饭。每个哲学家对 state 和 s 互斥访问(mutex(1))。 void Philosopher(int i) { Thinking; P(mutex); void test() { if (state[i]==hungry && state[(i-1)%n]!=eating && state[(i+1)%n]!=eating) { // 能吃饭，后面的 P(s[i])不会阻塞 state[i] = eating; V(s[i]); } state[i] = hungry; test(i); // 能吃饭吗？ V(mutex); P(s[i]); // 能吃饭！其对应的 V 操作在 test 里 拿起左右筷子吃饭；吃完放下左右筷子； } P(mutex); state[i] = thinking; // 吃完了，帮忙看看左右的能吃饭吗 test((i-1)%n); test((i+1)%n); V(mutex); }
    IV. 爱睡觉的理发师问题 单理发师[习题P174-18，01、06 年试题，06 年秋讲义] 问题：理发师只在理发椅前，要么理发要么睡觉；理发师睡觉时，第一个顾客唤醒理发师；理发 师在理发时，其余顾客在 n 张椅子上等待；椅子不够时，顾客离开。 同步：没有顾客时理发师不能理发，只能睡觉(customer(0))；理发师睡觉的时候顾客不能理发， 需先唤醒(barber(1))。 互斥：设置变量 wait_count(0)来记录当前等待的顾客数，理发师和顾客以及顾客之间对其互斥访 问(mutex(1))。 void Barber() { while (true){ void Costumer() { P(mutex); // 防止两顾客同坐最后一个椅子 P(customer); // 有顾客吗？没有就睡觉 if (wait_count
    V. 音乐爱好者问题 [习题P174-19，99 年试题，06 年秋讲义] 问题：三个 musiclover 各有 walkman、CD、battery，三样齐全才能听音乐；老板一次只借出三样 中的任何两样，收回后才再次借出。 同步：没有 musiclover 老板不能借出东西(musiclover(0))；没有东西 musiclover 不能听音乐，设置 no_wc(0)、no_cb(0)、no_bw(0)表示没有三样东西的其中两样。 void musiclover(lover i) { while (true){ void boss() { While(true){ int prov = genprovide(); // 借出某两种 if (prov==1) V(no_wc); else if (prov==2) V(no_cb); else V(no_bw); P(musiclover); // 有人来借 prov 吗/还了才能借 }} } } if (i==battery){ P(no_wc); 拿到东西，听音乐; } else if (i==walkman){ P(no_cb); 拿到东西，听音乐; } else { P(no_bw); 拿到东西，听音乐; } V(music_lover); // 听完了，还给老板 VI. 船闸问题 [习题P174-20，98、03 年试题，06 年秋讲义] 问题：A、B 两地船只单向通过 T 级船闸的问题。 互斥：设置记录 A 到 B 和 B 到 A 的方向船只个数(A2B_count(0), B2A_count(0))，两个方向的船只 互斥访问(mutexA(1), mutexB(1))。再设置船闸信号量(lock(1))，用于开关船闸。 void shipA() { P(mutexA); A2B_count++; if (A2B_count==1) P(lock); V(mutexA); 通过船闸; P(mutexA); A2B_count--; if (A2B_count==0) V(lock); V(mutexA); } shipB 和 shipA 类似，将所有 A、B 互换就行 这是北大习题课答案。 双向通航问题限制条件多而易变，此处不再讨 论。 若限制 T 级船闸只能过 T 只船，则需增加一个 信号量(max_count_mutex(T))。 void shipA() { P(mutexA); A2B_count++; if (A2B_count==1) P(lock); V(mutexA); P(max_count_mutex); 通过船闸; V(max_count_mutex); P(mutexA); A2B_count--; if (A2B_count==0) V(lock); V(mutexA); } VII. 红黑客问题 [2004 年试题] 问题：船每次坐满四个人才能开；三个红客+一个黑客或一个红客+三个黑客不能同船。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料