计算机操作系统：52

管程 monitor的特点
局部数据变量只能被管程的过程访问
一个进程通过调用某过程进入管程
只有一个进程能够进入，其他进程被挂起互斥管程是由若干过程、局部数据、初始化序列组成的软件模块利用条件变量实现同步
Cwait(c)
– 挂起当前进程
– 管程变成可用状态
Csignal(c)
– 执行等待队列中的头个进程
– 队列空则信号丢失管程的结构局部数据条件变量过程 1
过程 k
初始化代码
…
条件 c1
cwait(c1)
cwait(cn)
csignal
紧急队列条件 cn
…
进入进程队列管程管程等待区 出口使用管程解决生产者 /消费者问题
Monitor boundedbuffer;
Char buffer[n];
Int nextin,nextout;
Int count;
Int notfull,notempty;
Void append(char x)
{if count==n cwait(notfull);
Buffer[nextin]=x;
Nextin=(nextin+1)%n;
Count++;
Csignal(notempty);
}
Void take(char x)
{if count==0 cwait(notempty);
x= Buffer[nextout];
Nextout=(nextout+1)%n;
Count--;
Csignal(notfull);
}
Nextin=0;nextout=0;count=0;
使用管程解决生产者 /消费者问题
Void producer()
Char x
{while true
{produce (x);
Append(x);
}}
Void consumer()
Char x
{while true
{take(x);
consume (x);
}}
Void main()
{parbegin(producer,consumer);}
管程的问题
如果 csignal不在进程末尾
– 需要两次进程切换
必须确保 csignal之后立刻执行唤醒的进程
– 不能有新进程进入
Cnotify(x)
– 唤醒等待队列的头个进程
– 原进程继续执行有界缓冲区管程代码
void append(char x)
{while count==n cwait(notfull);
Buffer[nextin] =x;
Nextin=(nextin+1)%n;
Count++;
Cnotify(notempty); } void take(char x){while count==0 cwait(notempty);
x = Buffer[nextout];
Nextout=(nextout+1)%n;
Count--;
Cnotify(notfull); }
Cnotify的优点
唤醒进程执行前再次测试－ while
给每个条件变量设置监视计时器
Cbroadcast原语
– 不知道该唤醒几个进程
– 不知道该唤醒哪个进程
识别错误发出的信号消息传递
Send(目标，消息 )
Receive(来源，消息 )
Send(distination,message)
Receive(source,message)
消息系统设计特点同步 Send 阻塞，无阻塞receive 阻塞，无阻塞，到达测试寻址 直接 receive-显式，隐式间接 静态 /动态，所有权格式 内容，长度排队规则 先进先出，优先级常用的同步组合
阻塞 send 阻塞 receive
无阻塞 send 阻塞 receive
无阻塞 send 无阻塞 receive
会合 renezvous
直接寻址
Send(接收者，消息 )
receive(发送者，消息 )
指定接收进程指定发送进程不指定发送进程，返回参数间接的进程通信信箱
P1
Pn
…
端口 Q1
Q1
Qn
…
信箱P1
Q1
Qn
…
客户机服务器广播
P1 信箱 Q1
P1
Pn
…
消息格式消息类型目标 ID
源 ID
消息长度控制信息消息内容消息头消息体使用消息实现互斥
Const int n=进程数；
Void p(int i)
{message msg;
While true
{receive(mutex,msg);
临界区；
Send(mutex,msg); }}
Void main()
{create_mailbox(mutex);
Send(mutex,null);
Parbegin(p(1),…p(n));}
使用消息解决有界缓冲区的 P/C问题
Const int capacity=buf容量
Const int null=空消息；
Int i;
Void producer()
{message pmsg;
While true
{receive(mayproduce,pmsg);
Pmsg=produce();
Send(mayconsume,pmsg); }}
Void consumer()
{message cmsg;
While true
{receive(mayconsume,cmsg);
Consume(cmsg);
Send(mayproduce,null); }}
使用消息解决有界缓冲区的 P/C问题
Void main()
{create_mailbox(mayproduce);
Create_mailbox(mayconsume);
For(int i=1;i<=capacity;i++)
Send(mayproduce,null);
Parbegin(producer,consumer);}
读写问题
多个进程可以同时读
多个进程不能同时写
不能同时读写
writer reader
读写问题－
写优先
Int readcount,writecount;
Semaphore x=1,y=1,z=1；
Semaphore wsem=1,rsem=1;
writer reader
读写令牌 -wsem
打印机－ s P2 P3 P4P1
关于 wsem
writer reader
读写令牌 -wsem R1W1
第一个读进程－必须申请令牌读写令牌 -wsem R2R1
后续读进程－不用申请令牌读写令牌 -wsem W3R或 W
写进程－必须申请令牌读写问题－读优先Int readcount;
Semaphore x=1,wsem=1;
Void reader()
{while true
{wait(x);
Readcount++;
If readcount==1 wait(wsem);
Signal(x);
Readunit();
Wait(x);
Readcount--;
If readcount==0 signal(wsem);
Signal(x); }}
Void writer()
{while true
{wait(wsem);
Writeunit();
Signal(wsem); }}
Void main()
{readcount=0;
Parbegin(reader,writer);}
写优先的信号量
writer reader
rsem 等待的头个读进程
wsem W1 W2 等待读进程结束的写进程
R3
…
R1 - R2 - W1 - W2 - R3 - R4 - R5……
获得 rsem
获得 z
z R4 R5 等待的后续读进程…
读写问题－
写优先 1Void reader(){while true
{wait(z);
Wait(rsem);
Wait(x);
Readcount++;
If readcount==1 wait(wsem);
Signal(x);
Signal(rsem);
Signal(z);
Readunit();
Wait(x);
Readcount- -;
If readcount==0 signal(wsem);
Signal(x); }}
读写问题－
写优先 2Void writer()
{while true
{wait(y);
Writecount++;
If writecount==1 wait(rsem);
Signal(y);
wait(wsem);
Writeunit();
Signal(wsem);
Void main()
{readcount=writecount=0;
Parbegin(reader,writer);}
Wait(y);
Writecount--;
If writecount==0
signal(rsem);
Signal(y); }}
使用消息传递解决
Void reader(int i)
{message rmsg;
While true
{rmsg=i;
Send(readrequest,rmsg);
Receive(mbox[i],rmsg);
Readunit();
Rmsg=I;
Send(finished,rmsg);}}
Void writer(int i)
{message rmsg;
While true
{rmsg=i;
Send(writerequest,rmsg);
Receive(mbox[j],rmsg);
writeunit();
Rmsg=i;
Send(finished,rmsg);}}
使用消息传递解决
Void controller()
{While true
{if count>0
{if !empty(finished)
{receive(finished,msg);
Count++;}
Else if !empty(writerequest)
{receive(writerequest,msg);
Writer_id=msg.if;
Count=count-100;}
Else if ! empty(readrequest)
{receive(readrequest,msg);
Count--;
Send(msg.if,’ok’);}}
If count==0
{send(writer_id,’ok’ );
Seceive(finished,msg);
Count=100;}
While count<0
{receive(finished,msg);
Count++;}}}