OS_theory_2

进程的定义、组成、组织方式、特征

进程的状态与转换

进程控制

进程的创建

进程的终止

进程的阻塞和唤醒

进程的转换

总结

进程通信

线程概念和多线程模型

引入线程的变化

线程的属性

总结

处理机调度的概念、层次

七状态模型

三层调度的联系和对比

总结

进程调度的时机、切换与过程、方式

进程调度的时机

总结

调度算法的评价指标

FCFS、SJF、HRRN调度算法

调度算法：时间片轮转、优先级、多级反馈队列

进程同步、进程互斥

进程互斥的软件实现方法

进程互斥的硬件实现方法

信号量机制

用信号量机制实现进程互斥、同步、前驱关系

生产者-消费者问题

多生产者-多消费者问题

总结

细节注意

吸烟者问题

读者、写者问题

问题

解决方案

改进

总结

哲学家进餐问题

问题

总结

管程

管程的定义

管程的基本特征

拓展1：用管程解决生产者消费者问题

总结

死锁的概念

死锁、饥饿、死循环的区别

死锁产生的必要条件

注意死锁发生时一定有循环等待，但发生循环等待时未必死锁（循环等待是死锁的必要非充分条件）

如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

死锁发生的时机

死锁的处理策略

总结

死锁的处理策略——预防死锁（静态策略）

死锁的处理策略——避免死锁（动态策略）

死锁的处理策略——检测与解除

进程管理

并发和并行

并发(Concurrent)

设两个活动a和b,在某一个指定时间t后,只要a和b都处在起点和终点之间的某一处,那就称之为并发.

并行(Parallel)

设两个程序,如果在同一个时间度量下同时运行在不同的处理机上,则陈这两个程序是并行的.

对比

并行一定并发,并发不一定并行.

并发执行的特征

间断性: 并发程序具有”执行—暂停—执行”间断性的活动规律.

非封闭性: 多个程序会共享系统中的资源,该资源状态会被多个程序改变,程序之间会互相影响.

不可再现性: 在输入相同的情况下,输出还和执行次序有关.

Bernstein条件

该条件是判断程序并发执⾏行结果是否可再现的充分条件。

定义

$R(S_i)$: $S_i$的读子集,表示在$S_i$中被引用的变量的集合.

$W(S_i)$: $S_i$的写子集,表示在$S_i$中被修改的变量的集合.

两个进程可并发,当且仅当下列条件同时成立的时候:

$R(S1)∩W(S1)=∅$
$W(S1)∩R(S1)=∅$

也可以理解为两个进程对于同一个共享变量的权力对等的时候才是可并发的,既二者都是读或者二者都是写.

进程

定义

进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

特征

动态性：进程是程序的一次执行过程。因创建而诞生，因调度而执行，因无资源而暂停，因撤销而消亡。

并发性：多个进程实体同时存在于内存中，能在一段时间内同时运行。

独立性：在传统os中，进程是独立运行的基本单位。

异步性：进程之间相互制约，进程自己以各自独立的不可预知的速度向前推进。

结构特征：程序段，数据段，进程控制块PCB。

进程应该包括：

程序代码

程序数据

PC值

一组通用寄存器的值（不是寄存器本身），堆，栈

一组系统资源（比如打开的文件）

进程的状态与控制

进程的状态

进程有三种基本状态：就绪状态，执行状态，阻塞状态。

就绪状态：进程已经获得了除处理器资源外的所有资源，等待调度。

执行状态：占用处理器资源，处于此状态的进程数目小于等于处理器数量. 在没有其他进程可以执行时, 通常会自动执行系统的idle进程(相当于空操作)。

阻塞状态：正在执行的进程，因为某种原因无法继续执行，放弃处理器资源。

进程控制块

进程控制块在进程控制中的作用：

随着进程创建而创建，随着进程撤销而撤销

是进程的唯一标志

限制系统进程数目（有些操作系统PCID只有6bit，最多容纳64个进程）

进程控制块是进程管理与控制中最重要的数据结构，每一个进程均有一个PCB。其包含以下内容：

进程标识符：每一个进程都必须有一个唯一的标识符, 可以是字符串, 也可以是数字. 在进程创建时被系统赋予。

程序与数据地址：把PCB与其对应的程序与数据联系起来。

进程状态：表示进程状态，为了方便管理，os将相同状态的进程统一管理。

现场保留区：当进程放弃处理器的时候，应把处理器中的各种状态信息保存起来，待重新获得处理器之后恢复现场。

同步互斥机制相关的域：用于实现进程间互斥，同步所需的信号量。

进程通信机制相关的域：用于实现进程间通信所需的字段

资源清单：列出所拥有的除处理器外的资源记录，如拥有的I/O设备，打开的文件列表。

家族关系：关于父进程，子进程的信息。

链接字：根据进程所处的现行状态，进程相应的PCB加入到不同的队列中，PCB链接字指出该进程所在队列中下一个PCB的首地址。（链表指向下一个结点的指针。）

PCB的组织方式

线性表
不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。

链接方式
系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运行队列等。

索引方式
该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。

中断处理触发的进程切换流程

栈储存进程的PC

硬件从中断向量中载入新进程的PC

汇编程序保存寄存器的值

汇编程序建立新的栈

C语言中断服务运行

调度器决定下一个进程

C语言程序返回到汇编代码

汇编程序开启下一个新进程

进程上下⽂文切换 vs 陷⼊入内核

进程从用户态到内核态的切换和进程之间的切换不同，mode switch还是在本进程之内，所以上下文切换的时候主要是寄存器上下文切换，栈的切换（防止恶意程序读共享栈中的内核数据导致信息泄露）。

线程

线程的引入

进程的不足：

一个进程只能在一个时间干一件事

多个进程直接切换开销很大

多个进程共享数据和通讯开销很大

因此引入了线程，线程可以看成轻量级的进程（但是线程和进程是两码事），线程之间的共享数据，并发执行，上下文切换更轻松。

进程和线程

进程是系统进行资源分配和调度的一个独立单位，它同时包含两个概念：资源拥有者和可执行单元。
操作系统将资源拥有者称为进程（process，task），可执行单元称为线程（Thread）。

一个进程可以有多个线程，但是一个线程只能同时被一个进程拥有。

进程是资源分配的基本单位，线程是处理机调度的基本单位，所有线程共享其所属进程的所有资源和代码。

线程执行过程中很容易协作同步，而进程需要通过消息通信进行同步。

线程的划分制度更小，并发性更高。

线程既共享进程的数据，也有自己的堆栈。

线程不能单独执行，但是每一个线程都有程序的入口、执行序列以及程序出口。它必须组成进程才能被执行。

线程实现

用户级线程

线程在用户空间, 通过library模拟的thread,不需要或仅需要极少的kernel支持。
其上下文切换比较快，不需要更改页表。

主要功能

创建和销毁线程

线程之间传递信息和数据

调度线程执行

保存和恢复线程上下文

用户级线程库: POSIX Pthreads, Mach C-threads, Java Threads.
POSIX Pthreads:

用于线程创建和同步的 POSIX 标准 API(IEEE 1003.1c).

可在用户级或内核级实现.

API 规定了线程库的行文, 但不限定实现方法.

类 Unix 操作系统中很常见: Solaris, Linux, MacOS X.

优缺点
优点:

线程切换与内核无关

线程的调度由应用决定,容易进行优化

可移植性强,只要线程库支持即可

缺点

很多系统调用会引起阻塞,内核因此会阻塞所有相关线程

内核只能将处理器分配给进程(进程是资源分配的基本单位)，即使有多个处理器，也无法实现一个进程中的多个线程的并行执行。

内核级线程

线程在内核空间. 内核有多个分身, 每一个分身都可以用来处理一个任务. 这用来处理非同步事件很有效, 内核可以对每一个非同步事件产生一个分身来进行处理.

支持内核线程的操作系统内核称作多线程内核

优缺点
优点:

内核可以在多个处理器上调度一个进程的多个线程实现同步并行执行

阻塞只发生在线程级别

内核中的一些处理可以通过多线程实现

缺点:

一个进程中的线程切换需要内核参与,线程的切换涉及到两个模式的切换(进程-进程、线程-线程)

效率低下

线程比较

内核支持线程是OS内核可感知的，而用户级线程是OS内核不可感知的

用户级线程的创建，撤销和调度不需要OS内核的支持；内核支持线程的创建，撤销和调度则需要OS内核支持

用户级线程执行系统调用的时候将中断当前进程，而内核支持线程系统调用的时候只中断线程。

在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行

在有内核支持线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。

混合实现

系统实现内核级线程
用户实现用户级线程
可以认为用户的进程是建立在内核线程上的

线程模型

有些系统同时支持用户线程和内核线程由此产生了不同的多线程模型，即实现用户级线程和内核级线程的连接方式。

Many-to-One 模型

将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成

该模型和纯的用户线程类似，线程的操作不需要经过内核，效率高，但是系统调用将中断整个进程

One-to-One 模型

每个用户级线程映射到一个内核级线程

该模型和纯的内核线程类似，系统调用效率高，线程之间可并发，但是线程的创建开销很大

Many-to-Many 模型

将n个用户级线程映射到m个内核级线程上，要求m <= n。

在多对一模型和一对一模型中取了个折中，克服了多对一模型的并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程，开销太大的缺点。又拥有多对一模型和一对一模型各自的优点，可谓集两者之所长。

进程调度

进程调度就是CPU选择合适的就绪态进程(Runnable|Ready)获得CPU计算资源。

cpu调度再CPU资源稀缺，任务量繁重的时候很重要。合理的调度机制能保证每个进程都能再合适的时间处理完成。比如用户交互的进程对于延迟要求很高，如果调度的时候该进程很久能获得一次CPU资源，那么用户的使用体验及其糟糕。

其要解决的问题如下：

合适分配CPU

如何分配CPU（进程的上下文切换）

按照什么原则选择下面一个要执行的进程

调度类型|CPU的三级调度

高级调度：又称“宏观调度”，作业调度。从用户工作流程的角度，一次提交若干个作业，对每个作业进行调度。

中级调度：又称“内外存交换”，从**存储器资源*的角度，将进程的部分或全部换出到外存上，将当前所需部分换入内存。指令和数据必须再内存里才能被CPU访问。

低级调度：又称“微观调度”，“进程或线程调度”，从CPU资源的角度的调度，调度频繁，要求高效率。

三级调度

进程的特性和分类

I/O Bound(I/O密集型)

频繁进行I/O,花费大量时间在等待I/O
计算花费时间短,计算少

CPU Bound(CPU密集型)

计算量大

进程(线程)调度的分类

根据是否在时钟中断作出调度决策

非抢占式: 该方法等待进程主动放弃CPU才做出调度决策,时钟中断不会做调度决策.

抢占式:给每个进程一个固定的最大时间段,如果到了最大时间段进程还在运行,则强行挂起进程,执行调度策略,在时钟中断的时候做调度决策.

根据不同的应用领域

批处理系统:减少切换改善性能,尽力让每个作业完成工作,使用非抢占式算法或分配长时间周期的抢占算法.

交互式系统:该系统服务于多个用户,要避免一个用户霸占CPU,使用抢占式算法

实时系统:该系统及时性要求很高,满足确定性的截止时间需求,抢占式为主,非抢占式也有应用.

调度算法的目标

普适性目标

公平:给每个进程公平的CPU份额,相似的进程获得相似的份额,不同类型的进程可以有区别(每个进程都需要完成,但是完成途径不同,比如及时性要求高的进程优先级高,但每次给的块小,及时性要求低的进程,每次给的块大,但优先级低)

严格:~~强制力~~ 保证策略严格执行

平衡: 尽量让系统每个部件忙碌,组合CPU密集型和I/O密集型进程

简单:易于实现

轻量:执行开销小

不同系统的特异性目标:

批处理系统

提升吞吐量(每小时完成的作业数)

减少周转时间(一批作业从提交到完成所经历的统计平均时间)

CPU利用率:接近100说明硬件不够用了

对批处理系统的度量指标:

吞吐量:作业数/总执行时间

周转时间:完成时间-提交时间

带权周转时间:周转时间/服务时间(执行时间) 反映作业等待执行的情况

平均周转时间:一组作业周转时间之和/作业数

平均带权周转时间:一组作业带权周转时间之和/作业数

交互式系统

最小化响应时间:用户输入一个请求到系统首次相应

等比例变化:任务花费时间随着其复杂度应该线性增长

满足截止时间:满足所有或者大多数应用的截止时间,保证及时性

可预测性:保证可预测性和规律性

批处理系统的调度算法

FCFS(First Come First Serveice)算法

按照作业进入就绪状态的次序分派CPU,占有CPU之后知道执行完成或者阻塞主动放弃CPU才调度下一个作业.

特点

公平,容易理解和实现

有利于长作业

有利于CPU密集型作业,不利于I/O密集型作业

SJF(Shortest Job First)算法

又称SPN(Shortest Proess Next)算法.对预期执行作业段的作业优先分配处理机,后面来的短作业不抢占正在执行的作业

优点

对FCFS的改进,提升了吞吐量

改善了平均周转时间和平均带权周转时间

缺点

对长作业不利

难以准确估计作业执行时间时

如果正在执行进程很慢,后面的短作业无法执行(因为是非抢占调度)

SRTN(Shortest Remaining Time Next)

对SJF的改进,变成了抢占式调度.当一个新就绪的进程到达时,如果它比当前运行进程具有更短的完成时间,系统抢占当前进程,选择新的进程执行.
缺点:

长时间的进程可能被源源不断的短进程打断,进入进程饥饿.

HRRN(Hightest Response Ratio Next)最高响应比优先算法

是FCFS和SJF算法的折中.既考虑作业的运行时间,又考虑作业的等待时间,照顾短作业又避免饿死长作业.
每次进行调度的时候,先计算后备作业队列每个作业的的响应优先级,优先级最大的作业运行.
Response Priority = 1 + 已等待时间/要求运行时间
算法效果:
多作业容易等到很高的响应比,长作业等待时间足够长之后,也能获得足够高的响应比.
缺点:
每次计算响应比又一定时间开销,性能略差

交互式系统的调度算法

RR(Round Robin)时间片轮转算法

通过时间片轮转,提高进程并发性和响应时间特性,进而提高资源利用率.
各个就绪进程按照FCFS原则,排成一个队列,每次调度时将CPU分配给队首进程,时间片结束或者进程放弃CPU,则进行CPU切换,该队列进入就绪态队列末尾,或者进入阻塞态.

PS( Priority Scheduling)优先级调度

该算法是对RR的改进.优先级调度赋予每个进程不同优先级,高优先级先运行,可以静态或者动态赋予进程优先级.
静态优先级
进程创建时指定,运行过程中不再改变.该优先级根据进程类型,资源需求,用户要求等创建.

动态优先级
在进程运行过程中可以动态改变优先级,以便获得更好的调度性能.

在队列中,等待时间越长则优先级提高,防止进程饥饿

进程每执行一个时间片就降低优先级,防止进程霸占CPU

I/O密集型进程优先级较高

MQ(Multi Queue)多级队列算法

本算法引入多个就绪队列,通过对各队列的区别对待,达到一个综合的调度目标.

对多个进程按照优先级进行分类,每类一个队列,各个队列之间按照PS进行调度,队列里面按照FCFS调度.

MFQ 多级反馈队列算法

引入多级优先队列,队列优先级越高则时间片越短,越低则越高.进程在某个队列运行完时间片之后,会被移入下一级队列,队列内部FCFS,队列间PS.
MFQ = PS(动态优先级) + FCFS + MQ

彩票调度

为了给不同进程不同的调度份额,CPU资源使用权以彩票的形式发给进程,每次进行随机抽奖,中奖的进程得到资源.通过控制一个进程得到的彩票数比例,可以控制其得到系统资源的概率.

线程调度

用户级线程:内核调度进程,进程调度线程

内核级线程:内核直接调度线程

优先级倒转及其调度方法

优先级倒转现象

例如有三个进程A,B,C,优先级依次降低.A和C共享资源X.这时C占有共享资源,一直没有放锁,A需要使用X,但因为C的优先级太低,A需要等待很久才能使用C.
这种高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞的现象叫优先级倒转现象

解决办法–优先级置项

还是上面那个例子,当C进入临界区之后,C所占有的处理机不允许被抢占.
缺点

如果临界区过长,A进程还是会等很长时间

优先级继承

当A因为临界区被阻塞的时候,C继承A的优先级,并一致保持到C退出临界区.

实时系统的调度算法

实时系统分为硬实时系统和软实时系统,硬实时系统要求绝对满足截至时间要求,软实时系统可以偶尔不满足截至时间要求.

静态表调度

通过对所有周期性任务的分析预测,事先确定一个固定的调度方案.
优点

无任何动态计算,开销小

无灵活性,只适用于完全固定的任务场景

单调速率调度RMS

RMS是单处理器下的最优静态调度算法

定义

任务周期越小,频率越高,其优先级越高,最先调度优先级最高的任务

如果两个任务的优先级一样,则随机选择

最早截止期优先EDF

定义

任务截止日期越早,其优先级越高,最先调度优先级最高的任务

如果两个任务的优先级一样,则随机选择

多处理机调度

AMP(Asymmetric Multi-Processor)非对称多处理系统

AMP指多处理器系统中各个处理器的地位不同,不同处理器负责不同分工,比如一个执行os功能,一个执行I/O.

该处理系统由主处理机管理一个公共就绪队列,并分派进程给从处理器执行.

SMP(Symmetric Multi-Processor)对称式多处理系统

和AMP相反,SMP中各个处理器的地位相同.

静态分配

每个CPU设立一个就绪队列，进程从开始执行到完成，都在同一个CPU上。

优点
调度算法开销小

缺点
难以准确预测执行时间,容易出现忙闲不均

动态分配
各个CPU采用一个公共就绪队列，队首进程每次分派到当前空闲的CPU上执行。可防止系统中多个处理器忙闲不均。

自调度

各个CPU采用一个公共就绪队列，每个处理机都可以从队列中选择适当进来执行。需要对就绪队列的数据结构进行互斥访问控制。是最常用的算法,实现时易于移植。

优点
不需要专门的处理机从事任务分派工作

缺点
当处理机个数较多时,对就绪队列的访问可能成为系统的瓶颈

成组调度

将一个进程中的一组线程,每次分配时到一组处理机上执行,在剥夺处理机时也同时对这一组线程进行.

优点

通常这样的一组线程在应用逻辑上相互何做,成组调度提高了这些线程的执行并行度,有利于减少阻塞和加快推进速度,最终提高系统吞吐量.

每次调度可以完成多个线程的分派,在系统内线程总数相同时能够减少调度次数,从而减少调度算法的开销.

专用处理机调度
为进程中的每个线程都固定分配一个CPU, 直到该线程执行完成.
只适用于CPU数量众多的高度并行系统, 单个CPU的利用率已经不太重要.

进程同步

进程同步主要体现于多个进程同时访问临界区(对共享资源进行访问的程序片段).
其原则为:

空闲让进:没人在临界区则进入

忙则等待:有进程在临界区则等待

有限等待:进入临界区的进程要及时离开临界区,防止死锁

让权等待:进程长时间不能进入临界区则应该放出处理器,防止轮询

基于忙等待的互斥方法

严格轮换法

设立公用变量turn,描述允许进入临界区的进程标识.

while(true){
    while(turn != 0); // until the turn = 0,into  the critical region
        doSomething();
        turn = 1;
}

问题:
一个进程可能被一个不在临界区的进程阻塞

Peterson算法

进入临界区判断其他进程对其有没有兴趣,如果有则等待

void enter_region(int process)
{
    int other = 1 > - process;

    interested[process] = 1;
    turn = process;
    while(turn == process && interested[other] == 1);
}

特点:
如果同一个时刻两个进程都进入临界区，interested和turn是竞争访问，后设置turn的进程会循环，先设置的进入

硬件指令机制

Test and Set Lock指令简称TSL,执行该指令的CPU会通过锁住内存总线,禁止其他CPU访问内存
XCHG:原子性的交换两个位置的内容

Bakery Algorithm

设置静态变量,每进入一个进程分配一个序号,如果多个进程分配到同一个序号,则根据进程号再排序.最后进程根据序号和进程号排序,最小的先进.

总结

在没有进入临界区,进程会等待,消耗CPU资源,对于这些进程应该将其阻塞,带到空闲再进入Runnable队列.

信号量机制

信号量是一种新的变量类型 Semaphore , 只能通过初始化和标准原语 P/V 来访问, 作为OS核心代码执行, 不受进程调度打断.

P(s):表示将要操作共享资源

while(s==0); //阻塞
s--;

V(s):表示释放操作资源

s++;

对于不同的操作系统,初值设置可以不一样.

互斥

A:P(s)→临界区→V(s)
B:P(s)→临界区→V(s)

同步

A:代码A→P(s)→代码A
B:代码B→V(s)
s初始值为0,A进程等待B完成之后才能继续进行

汇合

A:a1→V(a)→P(b)→a2
B:b1→V(b)→P(a)→b2

屏障

VAR n //numofProcess
VAR count = 0

P(a)
count++
V(a)
if count == n: 直到所有进程都完成了,才能继续b操作
    V(b)
P(b)
V(b)

多路复用

s = n,就能保证最多n个线程同时进行

信号量集

AND型信号量集

基本思想: 一次性分配全部所需共享资源给进程, 待进程使用完后, 再一次性释放.

SP (S1, S2, ..., Sn) :
    while(1) {
        if ( S1 >= 1 && S2 >= 1 && ... && Sn >= 1){}
            S1 = S1 > - 1;
            S2 = S2 > - 1;
            ...
            Sn = Sn > - 1;
            break;
        }
    }
SV (S1, S2, ..., Sn) :
    S1 = S1 + 1;
    S2 = S2 + 1;
    ...
    Sn = Sn + 1;

一般信号量集

基本思想: 在AND型信号量集的基础上进行扩充. 进程对信号量 Si 的测试值为 ti, 占用值为 di.

SP (S1, t1, d1, S2, t2, d2, ..., Sn, tn, dn) :
    while(1) {
        if (S1 >= t1 && S2 >= t2 && ... && Sn >= tn ){
            S1 = S1 > - d1
            S2 = S2 > - d2
            ...
            Sn = Sn > - dn
            break;
        }
    }
SV (S1, d1, S2, d2, ..., Sn, dn) :
    S1 = S1 + d1
    S2 = S2 + d2
    ...
    Sn = Sn + dn

特殊情况

SP(S,d,d):表示每次申请d个资源，当资源数量少于d个时，便不
予分配

SP(S,1,1):表示互斥信号量

SP(S,1,0):S≥1是允许多个进程,S=1禁止任何进程

优缺点

优点:

简单,表达能力强

缺点:

不够安全,可能死锁.

实际编程中,多个共享数据,加重了编程负担

管程(Monitor)

为了应付信号量不够安全,和编程负担过重的问题,提出了管程用于集中分散的临界区,统一管理个进程对可共享资源的访问.

管程可以由函数库的形式实现,是一种高级同步原语.

为每个共享资源设立一个管程,由用户编写,对共享变量的访问通过其共有接口实现,有点像面向对象的思路.

管程的实现

下面是java 对管程实现的思路

class Monitor{
    private int buffer[] = new int[N];
    private int count = 0,lo = 0,hi = 0;
    private static final int N = 10;

    public synchronized void insert(int val){ //对生产者的接口
        if(count == N){
            go_to_sleep();
        }
        buffer[hi] = val;
        hi = (hi+1)%N;
        count++;
        if(count == 1) notify();
    }

    public synchronized void get(int val) { //对消费者的接口
        if(count == 0){
            go_to_sleep();
        }
        int ret = buffer[lo];
        lo = (lo+1)%N;
        count--;
        if(count == N-1) notify();
        return ret;
    }
}

如上面代码的思路,管程就是将零碎的共享资源进行封装,提供统一的接口进行操作,在管程里面对共享资源的操作都是互斥的.
管程中有如下信息:

临界资源:管程管理的共享资源,每一个临界资源的创立都有一个对应的等待队列.

控制变量:管程内部,用于控制进程运行状态的变量(上述代码中的N,hi,lo)

操作原语:对控制变量和临界资源进行操作的一组代码,是提供给外部的唯一指定途径

优缺点

优点

统一管理临界资源,更加安全

缺点

依赖语言

不适用于分布式系统

进程通信的主要方法

通信的分类

低级通信:只能传递状态和整数值

缺点:

传输信息量小

用户直接实现通信的细节,容易出错

高级通信:能够传送任意数量的数据,包括三类:管道,共享内存,信息系统

管道通信(Pipe):管道是用于连接读进程和写进程以实现两个进程通信的共享文件,又称管道文件.在UNIX系统中分为无名管道和有名管道

无名管道(Pipe)

该管道是单向管道,数据只能向一个方向流动,而且该管道只能用于父子进程和兄弟进程之间.单独构成一种独立的文件系统

管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在在内存中。

数据的读出和写入:

一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。

由此可见,两个进程对管道文件的权限不同,一个只读,一个只写(无名管道是单向管道)

有名管道(Named Pipe 或 FIFO)

有名管道克服了无名管道只能用于亲缘关系之间通信的问题.

该管道通过提供一个路径名与之关联,只要通过访问该路径,就能凭借该管道通信.

该管道对于不同进程的数据管理是FIFO,先进先出.

信息传递

信息传递的方式提供了两个通信原语(是一个系统调用):

send(destination,&message)

receive(source,&message)

调用方式:

阻塞调用

非阻塞调用(maybe内核线程)

主要问题:

解决信息丢失,延迟问题

编址问题

传递过程:
调用send()之后,首先陷入内核态,然后复制message于消息缓冲区.之后将消息缓冲区挂载到接受进程的消息队列.之后调用receive()函数则将消息队列的消息复制过来.

共享内存

该方式是最有用的进程通信方式,因为省去了开销很大的缓冲复制过程.

共享内存意味着同一块物理内存被映射到了两个不同进程的进程地址空间.通过信号量等方法实现共享内存的互斥和同步.

经典进程同步问题

生产者消费者模型

基础生产者消费者问题:

SEMAPHORE full = 0
SEMAPHORE empty = N
SEMAPHORE mutex = 1         // protect buffer

VAR buffer[N]
VAR buf_in = 0
VAR buf_out = 0

PRODUCER () :
    WHILE TRUE :
        next = // produce `next` //
        P(empty)
        P(mutex)
        buffer[buf_in] = next
        buf_in = (buf_in + 1) % N
        V(mutex)
        V(full)
CONSUMER () :
    WHILE TRUE :
        P(full)
        P(mutex)
        next = buffer[buf_out]
        buf_out = (buf_out + 1) % N
        V(mutex)
        V(empty)
        // consume `next` //

扩展问题:设有一个可以装A, B两种物品的仓库, 其容量无限大, 但要求仓库中A, B两种物品的数量 $C_A$ 和 $C_B$ 满足下述不等式:

$−M≤C_A−C_B≤N(M,N∈Z+)$

SEMAPHORE mutex = 1
SEMAPHORE sem_a = N
SEMAPHORE sem_b = M

A () :
    WHILE TRUE :
        P(sem_a)   
        P(mutex)
        // A --> warehouse //
        V(mutex)
        V(sem_b) //增加B的上限
B () :
    WHILE TRUE :
        P(sem_b)
        P(mutex)
        // B --> warehouse //
        V(mutex)
        V(sem_a)

读者写者问题

读者优先:

int readers = 0
Semaphore mutex = 1 //互斥
Semaphore roomEmpty = 1 //是否能容下其他人
Semaphore turnstile = 1 //闸机控制

Reader:
//进入
P(turnstile)
V(turnstile)
P(mutex)
    readers ++;
    if readers == 1:
        P(roomEmpty) //不允许写者进入
V(mutex)
//read critical region

//离开
P(mutex)
    readers--
    if readers == 0:
        V(roomEmpty)
V(mutex)

Writer:
P(turnstile) //禁止其他读者进入
    P(roomEmpty) //等待里面的读者出来
    //write critical region
V(roomEmpty)
V(turnstile)

公平

int readers = 0
Semaphore roomEmpty = 1 //是否能容下其他人
Semaphore turnstile = 1 //闸机控制

Reader:
//进入
P(turnstile)
V(turnstile)
P(roomEmpty)
//read critical region
V(roomEmpty)


Writer:
P(turnstile) //禁止其他读者进入
    P(roomEmpty) //等待里面的读者出来
    //write critical region
V(roomEmpty)
V(turnstile)

死锁

定义

死锁:如果一个进程集合中的每个进程都在等待只能由该进程集合中其他进程才能引发的事件，那么该进程集合就是死锁的。

资源死锁:如果每个进程等待的事件是释放该进程集合中其他进程所占有的资源。

必要条件

互斥条件:指进程对所分配到的资源进行排他性使用,即在一段时间内资源只能有一个进程占用

保持和请求条件:已经获得资源的线程可以请求新的资源

不剥夺条件:指进程已获得的资源,再未使用完之前不能被强制剥夺,只能在使用完时由自己释放

环路等待条件:指在发生死锁时,必然存在两个或多个进程组成的环形链,每个进程都在等待环形链中下一个节点占用的资源.

死锁处理方法

鸵鸟算法

OS无所作为,全部交给程序员来负责

死锁检测与死锁恢复

允许死锁发生,当检测死锁放生之后,采取措施恢复
死锁检测算法:

基于资源分配图,每类一个资源

基于资源向量计算,每类多个资源

死锁预防

破坏死锁的四个必要条件.

死锁避免

在资源分配之前判断是否安全,仅当安全才进行分配.需要依赖执行前获取额外信息.

资源分配图

每类资源一个的死锁检测
按照资源请求和释放的序列对图进行操作，并在每步操作后检查是否存在环。
可用作分析是否存在死锁的工具

资源向量计算

矩阵介绍:

E:存在资源向量:表示每类资源的总量

A:可用资源向量:表示当前未分配可使用的资源数

C:当前分配矩阵:表示第i个行向量对应第i个进程已经分配到的各类资源数量

R:请求矩阵:第i个行向量表示进程i所需要的资源数量
$∑C_{ij}+A_j=E_j$

算法步骤:

寻找进程$P_i$,其在R矩阵中对应的第i行小于等于A

如果找到,将C矩阵的第i行加入A,标记该进程执行完毕,转到第一步

如果找不到,结束

死锁恢复

资源抢占法:
挂起一些占有资源的进程，剥夺它们的资源以解除死锁，将资源分配给另一个死锁进程使其能够执行完毕，然后再激活被挂起的进程

杀死进程法:

杀死一个或者若干个进程,杀死的线程应该是重新执行无副作用的进程,根据资源情况,杀死环内或者环外的进程

回滚法:

设置检查点,根据死锁时所需要的资源,将一个拥有资源的进程滚回一个未占用资源的检查点状态,从而使得其他死锁进程能够获得响应的资源

死锁预防

打破互斥:允许进程同时访问某些资源

打破保持和请求条件:在进程开始执行前请求所需的全部资源。只有当系统能够满足当前进程的全部资源需求时，才一次性地将所申请的资源全部分配给该进程，否则不分配任何资源。或者请求之前先释放资源,再尝试获得所有资源

缺点:

资源不可预测

资源利用率低

降低进程并发

打破不可抢占条件:
允许进程强行从占有者哪里夺取那些资源.

打破循环等待条件:实行资源有序分配策略。即把资源事先分类编号，所有进程对资源的请求必须严格按资源序号递增的顺序提出，使进程在申请，占用资源时不会形成环路，从而预防了死锁。

缺点:增加开销,增加了进程对资源的占用时间

哲学家就餐问题

5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子(叉子)，每两个哲学家之间放一支；哲学家必须拿到左右两只筷子才能吃饭。
方法:

破除循环等待:

至多允许四个哲学家同时拿起筷子,保证至少一个哲学家就餐.

奇数号哲学家先拿左再拿右,偶数人反之

同时拿起两根筷子,或者不拿起

Charles's Castle

OS_theory_2

OS_theory_2

进程的定义、组成、组织方式、特征

进程的状态与转换

进程控制

进程的创建

进程的终止

进程的阻塞和唤醒

进程的转换

总结

进程通信

线程概念和多线程模型

引入线程的变化

线程的属性

总结

处理机调度的概念、层次

七状态模型

三层调度的联系和对比

总结

进程调度的时机、切换与过程、方式

进程调度的时机

总结

调度算法的评价指标

FCFS、SJF、HRRN调度算法

调度算法：时间片轮转、优先级、多级反馈队列

进程同步、进程互斥

进程互斥的软件实现方法

进程互斥的硬件实现方法

信号量机制

用信号量机制实现进程互斥、同步、前驱关系

生产者-消费者问题

多生产者-多消费者问题

总结

细节注意

吸烟者问题

读者、写者问题

问题

解决方案

改进

总结

哲学家进餐问题

问题

总结

管程

管程的定义

管程的基本特征

拓展1：用管程解决生产者消费者问题

总结

死锁的概念

死锁、饥饿、死循环的区别

死锁产生的必要条件

死锁发生的时机

死锁的处理策略

总结

死锁的处理策略——预防死锁（静态策略）

死锁的处理策略——避免死锁（动态策略）

死锁的处理策略——检测与解除

进程管理

并发和并行

并发(Concurrent)

并行(Parallel)

对比

并发执行的特征

Bernstein条件

定义

进程

定义

特征

进程的状态与控制

进程的状态

进程控制块

PCB的组织方式

中断处理触发的进程切换流程

进程上下⽂文切换 vs 陷⼊入内核

线程

线程的引入

进程和线程

线程实现

用户级线程