信号量与PV操作 ●记录型信号量及其应用 二元信号量 ●同时型傖号量及其应用 型信号量及其应用
信号量与PV操作 ⚫ 记录型信号量及其应用 ⚫ 二元信号量 ⚫ 同时型信号量及其应用 ⚫ 一般型信号量及其应用
3.31同步和同步机制 著名的生产者--消费者( Producer Consumer Problem)问题是计算机操作 系统中并发进程内在关系的一种抽象, 是典型的进程同步问题。在操作系统中, 生产者进程可以是计算进程、发送进程; 而消费者进程可以是打印进程、接收进 程等等。解决好了生产者-消费者问题就 解决好了一类并发进程的同步问题
3.3.1 同步和同步机制 ⚫ 著 名 的 生 产 者 - - 消费者 ( ProducerConsumer Problem) 问题是计算机操作 系统中并发进程内在关系的一种抽象， 是典型的进程同步问题。在操作系统中， 生产者进程可以是计算进程、发送进程； 而消费者进程可以是打印进程、接收进 程等等。解决好了生产者--消费者问题就 解决好了一类并发进程的同步问题
生产者-消费者间题表述如下: ●有n个生产者和m个消费者,连接在 个有k个单位缓冲区的有界缓冲上, 故又叫有界缓冲问题。其中,p和cj 都是并发进程,只要缓冲区未满, 生产者pi生产的产品就可投入缓冲 区;类似地,只要缓冲区不空,消 费者进程c就可从缓冲区取走并消耗 品
生产者--消费者问题表述如下： ⚫有n个生产者和m个消费者，连接在 一个有k个单位缓冲区的有界缓冲上， 故又叫有界缓冲问题。其中，pi和cj 都是并发进程，只要缓冲区未满， 生产者pi生产的产品就可投入缓冲 区；类似地，只要缓冲区不空，消 费者进程cj就可从缓冲区取走并消耗 产品
可以把生产者-消费者问题的算法描述如下 ●vark: integer; type item: any; buffer: arrayl0.k-l]of item; inout: integer:=0 coumter integer:=0 process producer while (true) /无限循环 produce an item in nextp; /*生产一个产品 e if(counter==k) sleep(; /缓冲满时,生产者睡眠 bufferin = nextp /将一个产品放入缓冲区 in:=(in+1)mod k; /指针推进 counter:=counter+l; /*缓冲内产品数加1 if( counter=1) wakeup( consumer);缓冲为空了,加进一件产品并 唤醒消费者
可以把生产者-消费者问题的算法描述如下： ⚫ var k:integer; ⚫ type item:any; ⚫ buffer:array[0..k-1]of item; ⚫ in,out:integer:=0; ⚫ coumter:integer:=0; ⚫ process producer ⚫ while (TRUE) /* 无限循环 ⚫ produce an item in nextp; /* 生产一个产品 ⚫ if (counter==k) sleep( ); /* 缓冲满时，生产者睡眠 ⚫ buffer[in]:=nextp; /* 将一个产品放入缓冲区 ⚫ in:=(in+1) mod k; /* 指针推进 ⚫ counter:=counter+1; /* 缓冲内产品数加1 ⚫ if (counter==1) wakeup( consumer); /* 缓冲为空了，加进一件产品并 唤醒消费者
o process consumer ● while(TRUE) /无限循环 f( counter==0)slep();/缓冲区空,消 费者睡眠 nextc:-bufferlout: /取一个产品 到 nextc out: =(out+1)mod k; /指针推进 counter=counter-l /取走 个产品,计数减1 if (counter==k-1)wakeup( producer);/ 缓冲满了,取走一件产品并唤醒生产者 consume thr item in nextc;/消耗产品
⚫ process consumer ⚫ while (TRUE) /* 无限循环 ⚫ if (counter==0) sleep ( ); /* 缓冲区空，消 费者睡眠 ⚫ nextc:=buffer[out]; /* 取一个产品 到nextc ⚫ out:=(out+1) mod k; /* 指针推进 ⚫ counter:=counter-1; /* 取走一 个产品，计数减1 ⚫ if (counter==k-1) wakeup( producer); /* 缓冲满了，取走一件产品并唤醒生产者 ⚫ consume thr item in nextc; /* 消耗产品
生产者和消费者进程对 counter 的交替执行会使其结果不唯 ●生产者和消费者进程的交替执行 会导致进程永远等待,造成系统 死锁
⚫生产者和消费者进程对counter 的交替执行会使其结果不唯一 ⚫生产者和消费者进程的交替执行 会导致进程永远等待，造成系统 死锁
前一节介绍的种种方法虽能保证互斥, 可正确解决临界区调度问题,但有明显 缺点。对不能进入临界区的进程,采用 忙式等待( busy waiting)测试法,浪费 CPU时间。将测试能否进入临界区的责 任推给各个竞争的进程会削弱系统的可 靠性,加重了用户编程负担。 1965年荷兰的计算机科学家 EWDijkstra提出了新的同步工具-信 号量和P、V操作
⚫前一节介绍的种种方法虽能保证互斥， 可正确解决临界区调度问题，但有明显 缺点。对不能进入临界区的进程，采用 忙式等待(busy waiting)测试法，浪费 CPU时间。将测试能否进入临界区的责 任推给各个竞争的进程会削弱系统的可 靠性，加重了用户编程负担。 ⚫ 1965年荷兰的计算机科学家 E.W.Dijkstra提出了新的同步工具--信 号量和P、V操作
记录型傖号量与P操作 ●信号量:一种软资源 ●原语:执行时不可被中断的过程 ●P操作原语和V操作原语
记录型信号量与PV操作 ⚫信号量：一种软资源 ⚫原语：执行时不可被中断的过程 ⚫ P操作原语和V操作原语
●信号量按其用途可分为两种: ●公用信号量:联系一组并发进程,相关的进 程均可在此信号量上执行P和Ⅴ操作。初值常常为1, 用于实现进程互斥。 私有信号量:联系一组并发进程,仅允许此 信号量拥有的进程执行P操作,而其他相关进程可 在其上施行V操作。初值常常为0或正整数,多用 于并发进程同步。 信号量按其取值可分为两种: 元信号量:仅允许取值为0和1,主要用于 解决进程互斥问题。 般信号量:允许取值为非负整数,主要用 于解决进程间的同步问题
⚫ 信号量按其用途可分为两种： ⚫ ⚫ 公用信号量：联系一组并发进程，相关的进 程均可在此信号量上执行P和V操作。初值常常为1， 用于实现进程互斥。 ⚫ ⚫ 私有信号量：联系一组并发进程，仅允许此 信号量拥有的进程执行P操作，而其他相关进程可 在其上施行V操作。初值常常为0或正整数，多用 于并发进程同步。 ⚫ 信号量按其取值可分为两种： ⚫ ⚫ 二元信号量：仅允许取值为0和1，主要用于 解决进程互斥问题。 ⚫ ⚫ 一般信号量：允许取值为非负整数，主要用 于解决进程间的同步问题
1、整型信号量 。设s为一个正整形量,除初始化外,仅能通过P、V 操作来访问它,这时P操作原语和Ⅴ操作原语定义 如下:。 P(s);当信号量s大于0时,把信号量s减去 否则调用P(s)的进程等待直到信号量s大于0时。 ●●V(s):把信号量s加1 ●P(s)和Vs)可以写成: P(s): while s<0 do null operation S:=s-1; V(S):s:=+1
1、整型信号量 ⚫ 设s为一个正整形量，除初始化外，仅能通过P、V 操作来访问它，这时P操作原语和V操作原语定义 如下：。 ⚫ ⚫ P(s)；当信号量s大于0时，把信号量s减去l， 否则调用P(s)的进程等待直到信号量s大于0时。 ⚫ ⚫ V(s)：把信号量s加1。 ⚫ P(s) 和V(s) 可以写成： ⚫ P(s)： while s≤0 do null operation ⚫ s：=s-1； ⚫ V(s)： s：=s+1；