#操作系统概念阅读笔记6 ##进程同步 共享数据的并发访问可能会产生数据的不一致。下面是各种机制,用以确保共享同一逻辑地址空间的协作进程可有序地执行,从而能维护数据的一致性
##临界区问题 临界区问题是设计一个以便进程协作的协议
临界区问题三项要求
- 互斥:如果进程Pi在其临界区内执行,那么其它进程都不能在其临界区内执行
- 前进:如果没有进程在其临界区内执行且有进程需进入临界区,那么只有那些不在剩余区内执行的进程可参加选择,以确定谁能下一个进入临界区,且这种选择不能无限推迟
- 有限等待:从一个进程做出进入临界区的请求,知道该请求允许为止,其它进程允许进入其临界区的次数有上限。
代码被分为4个区
进入区 临界区 退出区 剩余区
抢占内核模式和非抢占内核模式处理临界区问题
硬件同步
- 通过硬件实现临界区最简单的办法就是关CPU的中断。从计算机原理我们知道,CPU进行进程切换是需要通过中断来进行。如果屏蔽了中断那么就可以保证当前进程顺利的将临界区代码执行完,从而实现了互斥。这个办法的步骤就是:屏蔽中断–执行临界区–开中断。但这样做并不好,这大大限制了处理器交替执行任务的能力。并且将关中断的权限交给用户代码,那么如果用户代码屏蔽了中断后不再开,那系统岂不是跪了?
- 还有硬件的指令实现方式,这个方式和接下来要说的信号量方式如出一辙。但是通过硬件来实现,这里就不细说了
信号量
-
这也是我们比较熟悉P V操作。通过设置一个表示资源个数的信号量S,通过对信号量S的P和V操作来实现进程的的互斥。
-
P和V操作分别来自荷兰语Passeren和Vrijgeven,分别表示占有和释放。P V操作是操作系统的原语,意味着具有原子性。
-
P操作首先减少信号量,表示有一个进程将占用或等待资源,然后检测S是否小于0,如果小于0则阻塞,如果大于0则占有资源进行执行。
- V操作是和P操作相反的操作,首先增加信号量,表示占用或等待资源的进程减少了1个。然后检测S是否小于0,如果小于0则唤醒等待使用S资源的其它进程
-
信号量的主要缺点就是都要求忙等待。忙等待的结果会造成自旋锁
- 解决忙等:正常情况下,当一个进程执行wait()操作时,发现信号量值不为正,则它必须等待。然而,我们可以让该进程不是忙等而是阻塞自己。阻塞操作将一个进程放入到与信号量相关的等待队列中,并将该进程的状态切换成等待状态。接着控制转到CPU调度程序,以选择另一个进程来执行。后期需要运行这个进程时,只需要wakeup()该进程即可。
- 信号量的关键之处是它们原子地执行
死锁与饥饿
- 死锁:两个或多个进程无限地等待一个事件,而该事件只能由这些等待进程之一来产生。
- 无限期阻塞或饥饿:进程在信号量内无限期等待
经典同步问题
有限缓冲问题
读者-写者问题
- 第一读者-写者问题:没有读者会因为有一个写者在等待而会等待其他读者的完成。
- 第二读者-写者问题:如果一个写者等待访问对象,那么不会有新读者开始读操作
哲学家进餐问题
问题描述:
有五个哲学家,他们的生活方式是交替地进行思考和进餐。哲学家们公用一张圆桌,周围放有五把椅子,每人坐一把。在圆桌上有五个碗和五根筷子,当一个哲学家思考时,他不与其他人交谈,饥饿时便试图取用其左、右最靠近他的筷子,但他可能一根都拿不到。只有在他拿到两根筷子时,方能进餐,进餐完后,放下筷子又继续思考。
解决方法:
- 最多只允许4个哲学家同时坐在桌子上
- 只有两只筷子都可用时才允许一个哲学家拿起它们(他必须在临界区内拿起两只筷子)
- 使用非对称解决方法,即奇数哲学家先拿起左边的筷子,接着拿起右边的筷子,而偶数哲学家正相反。
管程
- 管程是一种程序结构,结构内多个字程序(对象或模块)形成的多个工作线程互斥访问共享资源
- 管程实现了在一个时间点,最多只有一个线程在执行管程的某个子程序
-
管程
- 管程的名称
- 局部于管理内部的共享数据结构说明
- 对该局部于管理内部的共享数据设置初始值访问
- 对该数据结构进程操作的一组进程