操作系统学习笔记（Ⅱ）：进程

目录

1 进程 

1.1 定义、组成、组织方式与特征

1.定义

2.组成

​3.组织方式

4.进程的特征 

1.2 进程的状态与转换

1.状态

2.进程状态的转换

1.3 进程控制

1.基本概念

2.进程控制相关的原语

1.4 进程通信

1.共享存储

2.消息传递

3.管道通信

1.5 线程概念和多线程模型

1.定义

2.属性

3.实现方式

4.多线程模型

2 处理机

2.1 处理机调度

1.调度

2.调度层次

3.挂起

2.2 进程调度

1.时机

2.切换与过程

3.方式

2.3 调度算法的评价指标

1.CPU利用率

2.系统吞吐量

3.周转时间

4.等待时间

5.响应时间

2.4 调度算法（批处理系统）

1.FCFS

2.SJF

3.HRRN

2.5 调度算法（交互式系统）

1.时间片轮转调度算法

2.优先级调度算法

3.多级反馈队列调度算法

3 进程同步与互斥

3.1 进程同步与互斥

1.异步性

2.同步性

3.互斥性

3.2 进程互斥软件实现方法

1.单标志法

2.双标志先检查

3.双标志后检查

4.peterson算法

3.3 进程互斥硬件实现方法

1.中断屏蔽方法

2.TestAndSet

3.Swap指令

3.4 信号量机制

1.整型信号量

2.记录型信号量

3.5 用信号量实现

1.进程互斥

2.进程同步

3.进程的前驱关系

3.6 生产者-消费者问题

1.问题描述

2.分析

3.实现

3.7 多生产者-多消费者问题

1.问题描述

2.问题分析

3.实现

3.8 吸烟者问题

1.问题描述

2.分析

3.实现

3.9 读者-作者问题

1.问题描述

2.分析

3.实现

3.10 哲学家进餐问题

1.问题描述

2.分析

3.实现

3.11 管程

1.定义和基本特征

2.管程解决生产消费者问题

4 死锁

4.1 死锁的概念

1.定义

2.死锁、饥饿与死循环

3.必要条件

4.死锁发生情况

5.处理策略

4.2 静态策略：预防死锁

1.破坏互斥条件

2.破坏不剥夺条件

3.破坏请求和保持条件

4.破坏循环等待条件

4.3 动态策略：避免死锁

1.安全序列

2.系统不安全状态

3.银行家算法

4.4 检测和解除

1.检测

2.解除

---

1 进程 

1.1 定义、组成、组织方式与特征

1.定义

系统为每个运行的程序配备一个数据结构，称为进程控制块（PCB），用来描述进程的各种信息。程序段、数据段、PCB组成了进程实体，简称为进程。进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

2.组成

进程由PCB、程序段、数据段组成

3.组织方式

4.进程的特征 

1.2 进程的状态与转换

1.状态

2.进程状态的转换

1.3 进程控制

1.基本概念

进程控制就是实现进程状态的转换。

用原语实现进程控制。其特点是执行期间不允许中断，这种操作为原子操作。

原语采用关中断指令和开中断指令实现。

2.进程控制相关的原语

包括创建原语、撤销原语、阻塞原语、唤醒原语、切换原语

1.4 进程通信

各进程之间拥有相互独立的内存空间地址，进程通信就是进程之间的信息交换

1.共享存储

提供一个访问时互斥的共享空间，包括基于数据结构（低级）和基于存储区（高级）的共享。

2.消息传递

以格式化消息传递，包括直接通信方式（消息直接挂到接收进程的消息缓冲队列上）或间接通信方式（消息先发到中间实体中） 

3.管道通信

在内存中开辟一个大小固定的缓冲区，只能采取半双工通信（某一时间段只能单向传输，双向通信要设置两个管道），各进程要互斥地访问管道。数据以字符流形式写入管道，管道写满后系统调用将被阻塞，等待读进程将数据取走后，读进程系统调用被阻塞。

1.5 线程概念和多线程模型

1.定义

线程是程序执行流的最小单位，进一步提高了系统的并发度；同一进程内的线程切换无需切换进程环境，能减小系统开销。

2.属性

·线程是处理机调度的单位

·多CPU计算机中，各个线程可占用不同的CPU

·每个线程都有一个线程ID、线程控制块（TCB)

·线程有就绪、阻塞、运行三种基本状态

·线程几乎不拥有系统资源

·同一进程的不同线程间共享进程的资源

·由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预

·同一进程中的线程切换，不会引起进程切换

·不同进程中的线程切换，会引起进程切换

·切换同进程内的线程，系统开销很小

·切换进程，系统开销较大

3.实现方式

·用户级线程：由应用程序通过线程库实现，线程切换在用户态完成。

·内核级线程：线程的管理由操作系统内核完成，线程切换在核心态完成。

内核级线程是处理机分配的单位 

4.多线程模型

·多对一模型：多个用户级线程映射到一个内核级线程，系统开销小，但并发度不高。

·一对一模型：多个用户级线程映射到一个内核级线程，并发能力强，但系统开销大。

·多对多模型：n个用户级线程映射到m(n >= m)个内核级线程，克服了上述两种模型的缺点。

2 处理机

2.1 处理机调度

1.调度

处理机调度就是从就绪队列中按照一定算法选择一个进程并将处理机分配给其运行，以实现进程的并发执行。

2.调度层次

·高级调度（作业调度）：按一定原则从外存上处于后备队列的作业中挑选一个作业，给其分配内存，并建立相应的进程，以使其获得竞争处理机的权利

·中级调度（内存调度）：虚拟存储技术将暂时不能运行的进程调至外存等待，其进程状态为挂起。被挂起的进程PCB会被放到挂起队列中。中级调度就是决定将哪个挂起转台的进程调入内存中。发生频率高于高级调度

·低级调度（进程调度）：按照某种算法从就绪队列中选取进程，将处理机分配给它。

3.挂起

挂起状态可分为就绪挂起、阻塞挂起两种状态

2.2 进程调度

1.时机

·当前运行的进程主动或被动的放弃处理机

2.切换与过程

·不能进行进程调度与切换的情况：中断处理中很难进行进程切换；进程在操作系统内核程序临界区（访问某内核数据结构，与普通临界区有区别 ）中；在原子操作过程中

进程切换是有代价的 

3.方式

2.3 调度算法的评价指标

1.CPU利用率

 CPU工作时间占总时间比例

2.系统吞吐量

单位时间内完成作业的数量

3.周转时间

作业被提交给系统开始，到作业完成为止的这段时间间隔。

4.等待时间

指进程/作业处于等待处理机状态时间之和

5.响应时间

指从用户提交请求到首次产生响应所用的时间。

2.4 调度算法（批处理系统）

1.FCFS

先来先服务算法

2.SJF

短作业优先算法

 抢占式段作业优先算法的平均周转时间、平均带权周转时间、平均等待时间优于非抢占短作业优先算法

3.HRRN

高响应比优先算法 (非抢占式调度算法)

2.5 调度算法（交互式系统）

1.时间片轮转调度算法

若时间片太大，时间片轮转调度算法会退化成FCFS算法，因此时间片设置不能太大。时间片太小会导致进程切换过于频繁。

2.优先级调度算法

优先级分为静态和动态优先级

抢占式的优先级调度算法:每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是会发生抢占。

3.多级反馈队列调度算法

3 进程同步与互斥

3.1 进程同步与互斥

1.异步性

具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

2.同步性

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

3.互斥性

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

对临界资源的互斥访问，可分为进入区（实现互斥）、临界区（进程中访问临界资源）、退出区（实现互斥）和剩余区

实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循如下原则：

·空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区;

·忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待;

·有限等待：对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）;

·让权等待：(进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

3.2 进程互斥软件实现方法

1.单标志法

算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

  但其不满足空闲让进原则

2.双标志先检查

算法思想:设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = ture”意味着0号进程PO现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为 true之后开始访问临界区。

 但有可能两个进程同时访问临界区，不满足忙则等待原则

3.双标志后检查

但有可能两个进程都无法访问临界区，不满足空闲让进和有限等待原则，并最终产生饥饿现象

4.peterson算法

 不满足让权等待原则

3.3 进程互斥硬件实现方法

1.中断屏蔽方法

利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

优点:简单、高效；缺点:不适用于多处理机;只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)

2.TestAndSet

执行过程不可被中断 

优点：适用于多处理机环境；缺点：不满足让权等待原则

3.Swap指令

执行过程不可被中断 

优缺点与TSL指令一致

3.4 信号量机制

上述软硬件解决方法都无法实现让权等待。提出的信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量。对信号量的操作只能包括初始化、wait(P操作)、signal(V操作)

1.整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

不满足让权等待原则 

2.记录型信号量

3.5 用信号量实现

1.进程互斥

·分析并发进程的关键活动，划定临界区

·设置互斥信号量mutex，初值为1

·在临界区之前执行P(mutex)

·在临界区之后执行V(mutex)

不同临界资源需要设置不同的互斥信号量

2.进程同步

·分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码)

·设置同步信号量s,初始为0

·在“前操作”之后执行V(S)

·在“后操作”之前执行P(S)

3.进程的前驱关系

在每一对前驱关系中设置一个同步变量，按上述操作执行

3.6 生产者-消费者问题

1.问题描述

2.分析

3.实现

 实现互斥的P操作一定要在实现同步的P操作之后。

3.7 多生产者-多消费者问题

1.问题描述

2.问题分析

 

3.实现

3.8 吸烟者问题

1.问题描述

2.分析

3.实现

3.9 读者-作者问题

1.问题描述

2.分析

3.实现

改进 

3.10 哲学家进餐问题

1.问题描述

2.分析

3.实现

 

3.11 管程

信号量机制存在编写困难、易出错的问题

1.定义和基本特征

管程是一种特殊的软件模块，有这些部分组成：局部于管程的共享数据结构说明；对该数据结构进行操作的一组过程；对局部于管程的共享数据设置初始值的语句；管程有一个名字。

管程的基本特征：局部于管程的数据只能被局部于管程的过程所访问；一个进程只有通过调用管程内的过程才能进入管程访问共享数据；每次仅允许一个进程在管程内执行某个内部过程。

2.管程解决生产消费者问题

需要在管程中定义共享数据；需要在管程中定义用于访问这些共享数据的“入口”；只有通过这些特定的“入口”才能访问共享数据；管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入；可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待，可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

4 死锁

4.1 死锁的概念

1.定义

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。 

2.死锁、饥饿与死循环

3.必要条件

互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁。

不剥夺条件:进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

请求和保持条件:进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。

循环等待条件:存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

4.死锁发生情况

·对系统资源的竞争

·进程推进顺序非法

·信号量使用不当

5.处理策略

预防、避免、检测及解除

4.2 静态策略：预防死锁

1.破坏互斥条件

将互斥使用的资源改造为允许共享使用，但多数时候无法破坏互斥条件

2.破坏不剥夺条件

·即使某些资源未结束，也需主动释放

·系统协助强行剥夺资源

但实现较为复杂、会造成系统开销、且有可能造成资源工作失效

3.破坏请求和保持条件

采用静态分配方法，在进程运行前就申请其全部资源，但可能造成资源浪费与进程饥饿

4.破坏循环等待条件

采用顺序资源分配法，给系统资源编号，每个进程按编号递增顺序请求资源，同类资源一次申请完。 但不方便新增设备，进程实际使用资源顺序可能与编号递增顺序不一致，导致资源浪费且用户编程较困难。

4.3 动态策略：避免死锁

1.安全序列

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。安全序列可能有多个。

2.系统不安全状态

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。

系统处于不安全状态时，有可能发生死锁

3.银行家算法

寻找一个安全序列，找不到就不得分配资源

 

 

4.4 检测和解除

1.检测

 

2.解除