第一章:【王道考研 操作系统】【第一章】操作系统的概述、特征、发展、体系结构 中断与系统调用
第二章 1~5:【王道考研 操作系统】【第二章】进程概念 进程控制 进程通信 线程概念和多线程模型
第二章 6~8:【王道考研 操作系统】【第二章】处理机调度 进程调度算法
第二章
9. 进程同步、进程互斥
进程具有 异步性 的特征,异步性是指,各并发执行的进程以各自独立的、不可预知的速度向前推进。
9.1 进程同步
进程具有 异步性 的特征。异步性是指,各并发执行的进程以各自独立的、不可预知的速度向前推进,因此并发操作的 先后顺序 是不确定的。
进程同步 即解决异步中进程先后顺序不确定的问题,让并发的进程按要求 有序地推进。
9.2 进程互斥
进程的并发需要 共享 的支持。各个并发执行的进程不可避免的需要共享一些系统资源。
临界资源 指一个时间段内只允许一个进程使用的资源。对临界资源的访问,必须 互斥 地进行。
进程互斥 指当一个进程访问某临界资源时,另一个想要去访问该临界资源的进程必须等待;当前访问临界资源的进程访问结束、释放资源之后,另一个进程才能去访问。
9.2.1 实现过程
临界区 是进程中访问临界资源的代码段;进入区 和 退出区 是负责实现互斥的代码段。
9.2.2 实现互斥须遵循的 原则
-
空闲让进:临界区空闲时,允许一个请求进入临界区的进程立即进入临界区;
-
忙则等待:当已有进程进入临界区时,其他试图进入临界区的进程必须等待;
-
有限等待:对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿);
-
让权等待:当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。
9.2.3 软件实现方法
-
单标志法
两个进程再访问完临界区后会把使用临界区的权限转交给另一个进程,即 每个进程进入临界区的权限只能被另一个进程赋予。(设置 当前允许进入临界区的进程号)
-
双标志先检查
设置一个布尔型数组 flag[],数组中各个元素用来 标记各个进程想进入临界区的意愿。
进程在进入临界区之前先检查当前有没有别的进程想进入临界区,若没有,则把flag[i]设为true,之后开始访问临界区。(先检查 后上锁)
-
双标志后检查
(先上锁 后检查)
-
Peterson 算法
如果双方都争着想进入临界区,可以让进程 主动让对方先使用临界区。谁进入临界区取决于谁 最后谦让临界区的使用权。
-
总结
9.2.4 硬件实现方法
-
中断屏蔽方法
利用 开/关中断 指令 实现。与原语的实现思想相同,即在某进程开始访问临界区到结束访问为止都不允许被中断,也就不能发生进程切换。
-
TestAndSet(TS指令 )TestAndSetLock指令( TSL指令)
TSL指令 是用硬件实现的,执行的过程不允许被中断,只能一气呵成。
以下用C语言描述 TSL的逻辑:
-
Swap指令(也叫 Exchange指令 / XCHG指令)
Swap指令 是用硬件实现的,执行的过程不允许被中断,只能一气呵成。
以下用C语言描述 TSL的逻辑:
-
总结
10. 信号量机制
信息量 就是一个变量 (可以是一个整数,也可以是更复杂的记录型变量),可以用来表示 系统中某种资源的数量。
用户进程可以通过使用操作系统提供的 一对原语 来对 信号量 进行操作,从而实现进程互斥、同步。原语 是一种特殊的程序段,其执行只能一气呵成,不可被中断,由 关中断/开中断指令 实现。
一对原语:wait(S) 原语 和 signal(S) 原语,常简称为 P、V 操作,S为信号量。这对原语可用于实现系统资源的 申请 和 释放。
10.1 整型信号量
用一个 整数型变量 做为信号量,用来表示某种资源的数量。
对信号量的操作有 初始化、P操作、V操作。wait 和先检查后上锁逻辑相同,但由于原语不会被中断。
10.2 记录型信号量
整型信号量的缺陷是存在 “忙等” 问题,因此提出了 “记录型信号量”——用记录型数据结构表示。
当一次P(S)操作后,S.value<0表示该类资源已分配完毕,进程调用 block原语 进行自我阻塞,主动放弃处理机,并插入等待队列S.L中。该机制遵循了 让权等待 原则,不会出现 “忙等” 现象。
当一次V(S)操作后,S.value<=0表示依然有进程在等待该类资源,进程调用 wakeup原语 唤醒等待队列中的第一个进程。
-
总结
10.3 用信号量机制实现进程互斥
10.4 用信号量机制实现进程同步
10.5 用信号量机制实现前驱关系
-
总结
11. 经典进程互斥同步问题
PV操作 题目分析步骤:
两个进程同时写入缓冲区,有可能导致 数据覆盖 的问题。因此无论缓冲区大小,任何时刻应该只有一个进程访问缓冲区!
11.1 生产者-消费者问题
-
问题描述
系统中有一组生产者进程和一组消费者进程。生产者进程 每次生产一个产品放入缓冲区,消费者进程 每次从缓冲区中取出一个产品并使用。
生产者、消费者共享一个初始为空、大小为n的 缓冲区,缓冲区是 临界资源,各进程必须 互斥 地访问。
只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待;只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。(同步,产品数量~空闲缓冲区的数量)
-
实现
实现互斥的P操作一定要在实现同步的P操作之后!否则,可能会发生 死锁。
V操作不会导致进程阻塞,因此两个V操作顺序可以交换。
11.2 多生产者-多消费者
11.3 读者-写者问题
11.4 哲学家问题