ch2操作系统第二章教学ppt.ppt

2.4.2读者-写者问题 信号量集解决读者-写者问题 增加最多同时允许RN个“读者”的限制 操作系统 CHAPTER 2 2.4.2读者-写者问题 信号量集解决读者-写者问题 增加最多同时允许RN个“读者”的限制 操作系统 CHAPTER 2 void writer(){ while(1){ Swait(mx,1,1；L,RN,0); 写操作 Ssignal(mx,1); } } void reader(){ while(1){ Swait(L,1,1); Swait(mx,1,0); 读操作 Ssignal(L,1); } } 2.4.3 哲学家进餐问题 问题描述 （由Dijkstra首先提出并解决） 5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支； 哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。 如何保证哲学家们的动作有序进行？如：不出现有人永远拿不到筷子； 操作系统 CHAPTER 2 2.4.3 哲学家进餐问题 记录型信号量解决哲学家进餐问题 每个筷子一个信号量，初值为1 可能死锁 至多允许4人使用左边 的筷子 仅当左右筷子都可用 时才去拿筷子 奇数哲学家先拿左边 偶数哲学家先拿右边 操作系统 CHAPTER 2 int chopstick[5]={1,1,1,1,1}; void philosopher_i(){ while(1){ wait(chopstick[i]); wait(chopstick[i+1]); eat; signal(chopstick[i]); signal(chopstick[i+1]); } } 扩展内容：解决互斥问题 软件方法[算法3] 类似于算法2，与互斥算法2的区别在于先修改后检查。可防止两个进程同时进入临界区。 操作系统 CHAPTER 2 flag[i] = true; while (flag[j]); critical section flag[i] = false; remainder section flag[j] = true; while (flag[i]); critical section flag[j] = false; remainder section Pi Pj 扩展内容：解决互斥问题 软件方法[算法3] 缺点 Pi和Pj可能都进入不了临界区。即在切换自己flag之后和检查对方flag之前有一段时间，结果都切换flag，都检查不通过。 操作系统 CHAPTER 2 flag[i] = true; while (flag[j]); critical section flag[i] = false; remainder section flag[j] = true; while (flag[i]); critical section flag[j] = false; remainder section Pi Pj 扩展内容：解决互斥问题 软件方法[算法4] 结合算法1和算法3，是正确的算法 同时使用flag[]和turn 在进入区先修改后检查，并检查并发修改的先后 检查对方flag，如果不在临界区则自己进入 －－空闲则入 否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入 －－先到先入，后到等待 操作系统 CHAPTER 2 扩展内容：解决互斥问题 软件方法[算法4] 操作系统 CHAPTER 2 flag[i] = true; turn=j; while(flag[j]turn==j); critical section flag[i] = false; remainder section Pi flag[j] = true; turn=i; while(flag[i]turn==i); critical section flag[j] = false; remainder section Pi 扩展内容：解决互斥问题 硬件方法[Test-and-Set指令] 该指令读出标志后将其设置为TRUE boolean TS(boolean *lock) { boolean old; old = *lock; *lock = TRUE; return old; } lock表示资源的两种状态：TRUE表示正被占用，FALSE表示空闲 操作系统 CHAPTER 2 扩展内容：解决互斥问题 硬件方法[利用TS实现进程互斥] 每个临界资源设置一 个公共布尔变量lock， 初值为FALSE 在进入区利用TS进行 检查