操作系统PV习题课ppt课件.ppt

OperatingSystemConcepts 操作系统习题讲解 一 进程概念二 进程同步和互斥 OperatingSystemConcepts 进程概念 一 问题 如果系统中有N个进程 运行进程最多几个 最少几个 就绪进程最多几个 最少几个 等待进程最多几个 最少几个 OperatingSystemConcepts 解答 运行进程最多1个 最少0个 就绪进程最多N 1个 最少0个 等待进程最多N个 最少0个 OperatingSystemConcepts 进程同步和互斥 一 问题一 用P V操作解决下图之同步问题 OperatingSystemConcepts 一个数据上的操作顺序 get copy put Get不能向 满 的S中放 Copy不能从 空 的S中取 不能向 满 的T中放 Put不能 空 的T中取 OperatingSystemConcepts 同步 信号量 实际上也起到互斥作用 S Empty T Empty 初值为1 S Full T Full 初值为0 Get BeginRepeatP S Empty T get S V S Full Untilfalse End Copy BeginRepeatP S Full P T Empty S copy T V T Full V S Empty Untilfalse End Put BeginRepeatP T Full T put G V T Empty Untilfalse End OperatingSystemConcepts 进程同步和互斥 二 问题 用P V操作解决下面问题 OperatingSystemConcepts 信号量 S Door 初值为0 S Stop 初值为0 司机进程 BeginRepeatP S Door 启动 驾驶 停车 V S Stop Untilfalse End 乘务员进程 BeginRepeat关门 V S Door 售票 P S Stop 开门 Untilfalse End 同步要求 先关门 后开车 先停车 后开门 OperatingSystemConcepts 第二类读者写者问题 写者优先 1 共享读2 互斥写 读写互斥3 写者优先于读者 一旦有写者 则后续读者必须等待 唤醒时优先考虑写者 进程同步和互斥 三 OperatingSystemConcepts Varmutex semaphore 互斥信号量 初值为1 R semaphore 对应读者等待队列 初值为0 W semaphore 对应写者等待队列 初值为0 一般变量 Writing Boolean 初值false 有写者正在写 rc integer 初值0 共享读的读者数 rq integer 初值0 等待队列中读者数 wq integer 初值0 等待队列中写者数 OperatingSystemConcepts 读者进程 BeginRepeatP mutex If WritingORwq0 ThenBeginrq rq 1 V mutex P R P mutex resume End rc rc 1 V mutex Read OperatingSystemConcepts P mutex rc rc 1 If rc 0ANDwq0 ThenBeginwq wq 1 Writing true V mutex V W End ElseV mutex UntilfalseEnd OperatingSystemConcepts 写者进程 BeginRepeatP mutex If WritingORrc 0 ThenBeginwq wq 1 V mutex P W End ElseBeginWriting true V mutex Write OperatingSystemConcepts P mutex If wq0 ThenBeginwq wq 1 V mutex V W EndElse OperatingSystemConcepts If rq 0 ThenBeginWriting false While rq 0 Beginrq rq 1 V R EndEndElseBeginWriting false V mutex EndEndUntilfalse OperatingSystemConcepts 理发师问题 理发店里有一位理发师 一把理发椅和N把供等候理发的顾客坐的椅子 如果没有顾客 则理发师便在理发椅上睡觉 当一个顾客到来时 他必须先唤醒理发师 如果顾客到来时理发师正在理发 则如果有空椅子 可坐下来等 否则离开 进程同步和互斥 四 OperatingSystemConcepts VarSn semaphore 位子数目 初值为n S semaphore 理发师睡觉 初值为0 mutex semaphore 初值为1 顾客进程i P Sn 门外观望 P mutex 进门 V mutex V S 等候 理发 V Sn P mutex 出门 V mutex OperatingSystemConcepts 理发师进程 RepeatP S P mutex 叫人理发 V mutex 理发 Untilfalse OperatingSystemConcepts 问题 推广读写者问题中的消息缓冲处理 消息缓冲区为k个 有m个发送进程 n个接收进程 每个接收进程对发送来的消息都必须取一次 进程同步和互斥 五 OperatingSystemConcepts 解题思路 发送者发送消息后唤醒所有的接收者 所有的接收者都接收后空出缓冲区 接收者接收时要修改接收次数 接收计数和缓冲区的指针为临界资源 访问时要互斥 OperatingSystemConcepts TypeBufferType Recordmsg MessageType count integer mutex semaphore 初值为1 empty semaphore 初值为1 full array 1 n ofsemaphore 初值全为0 EndVarmutex semaphore 初值为1 s integer 初值为0 buff array 0 k 1 ofBufferType k是缓冲区大小 n是接收进程个数 m是发送进程个数 通过s进行 写互斥 OperatingSystemConcepts ProcedureSender i i integer i为发送进程的标号 Vars0 j integer BeginRepeatP mutex s0 s s s 1 modk V mutex P buff s0 empty 在buff s0 msg中写信息 P buff s0 mutex buff s0 count n V buff s0 mutex For j 1tondo V buff s0 full j Untilfalse End OperatingSystemConcepts ProcedureRecvr i integer i为接收进程的标号 Varj integer Beginj 0 RepeatP buff j full i 从buff j msg中读信息 P buff j mutex buff j co