操作系统学习记录2-进程管理

进程

进程的概念：进程是动态的，是程序的一次执行过程。进程实体（进程映像）是静态的

进程的几个特性

动态性是指进程是程序的一次执行过程，是动态的产生、变化和消亡的

并发性是指内存中的多个进程实体，进程可并发的执行

独立性是指进程独立运行、独立获取资源、独立接受调度

异步性是指进程按照各自独立、不可预知的速度推进，操作系统提供“进程同步机制”解决异步问题

结构性指每个进程都有一个PCB，由程序段和数据段、PCB构成。

 

进程的基本状态

创建态、就绪态、运行态、阻塞态、终止态

运行、就绪、阻塞

运行状态：有CPU和其他资源

就绪状态：无CPU，有其他资源

阻塞态：无CPU，无其他资源

 

就绪态到运行态：进程被调度

运行态到就绪态：时间片到了，CPU被高优先级进程抢占

运行态到阻塞态：等待系统资源的分配，或者等待某种事件发生（主动行为）

阻塞态到就绪态：资源分配到位，等待的事件发生（被动行为）

 

进程的控制：进程控制就是要实现进程状态的转换，用原语实现。

原语是一种特殊的程序，执行具有原子性，就是说一气呵成，不可中断。可以使用关中断和开中断两条特权指令是实现原子性。

 

创建原语：先申请空白PCB，再为新进程分配需要的资源，再初始化PCB，最后将PCB插入就绪队列。

引起创建的事件有用户登录、作业调度、提供服务、应用请求

 

撤销原语：先从PCB集合中找到终止进程的PCB，进程正在运行，则立刻剥夺CPU，并将CPU分配给其他进程，并终止其所有的子进程（进程间的关系是树形结构），再将该进程所拥有的资源归还给父进程或者操作系统，再将其PVB删除。

引起进程终止的事件有正常结束（exit系统调用）、异常结束（整数除以0，非法使用特权指令）、外界干预（用户自己杀掉）

 

阻塞原语和唤醒原语（需要成对使用）

阻塞原语：需要找到对应的PCB，保护进程运行的现场，将PCB状态信息设置为阻塞态，暂停进程运行，并将PCB插入等待队列。

唤醒原语：需要在等待队列中找到PCB，将PCB从等待队列移除，将进程设置为就绪态。

 

切换原语（运行到就绪-就绪到运行）：先将运行环境信息（进程上下文）存入PCB，PCB移入相关的队列，选择另一个进程执行，并更新其PCB，根据PCB恢复新进程所需的运行环境。

 

无论哪个进程控制原语，要做的无非三类事情：

更新PCB中的信息、将PCB插入合适的队列、分配回收资源。

 

进程的组织方式：链式方式和索引方式

链式方式将按照状态分为多个队列，操作系统持有指向各个队列的指针。

索引方式将按照进程状态的不同，建立几张索引表，操作系统持有指向各个索引表的指针。

 

进程的组成：PCB、程序段、数据段

PCB指的是进程描述信息（PID）、进程控制和管理信息、资源分配清单、处理机相关信息，他是给操作系统用的。

程序段指的是程序的代码

数据段指的是运行中的各种数据，如定义的变量

程序段和数据段是进程自己用的

 

进程间的通信：共享存储、消息传递、管道通信

共享存储是指设置一个共享内存的区域，并映射到进程的虚拟地址空间。共享空间互斥访问（由进程自己互斥实现），采用基于数据结构和基于存储区的共享两种方式实现。

消息传递传递结构化的消息，系统提供发送和接受原语，采用直接通信方式和间接通信方式（信箱）

管道通信设置一个特殊的共享文件（管道），本质上是内存缓存区，一个管道只能半双工通信，全双工需要2个管道，各个进程互斥访问管道（由操作系统实现），管道满时，写进程阻塞，管道空时，读进程阻塞。

管道相比共享存储优势在于可以允许一边写入，另一边读出，只要没空就能读，没满就能写。

 

线程

线程的概念

线程是基本的CPU执行单元，是程序执行流的最小基本单位，各个线程之间可以并发，提升了系统的并发度。进程只作为除了CPU以外的系统资源分配单元，线程作为处理机的分配单元。也就是说，进程是资源分配的基本单位，线程是调度的基本单位。

引入线程后，并发性提高，系统开销减小。

 

线程的实现方式：用户级线程和内核级线程

多线程模型分为一对一模型、多对一模型、多对多模型

一对一模型指的是用户级线程对应一个内核级线程

优点是各个线程分配到多核处理机并行执行，并发度高

缺点是需要操作系统支持，开销大

多对一模型指多个用户线程映射到一个内核级线程

优点是线程管理的开销小，缺点是并发度低，一个线程阻塞导致整个进程都阻塞

多对多模型指n个用户级线程映射到m个内核级线程，n>=m，他吸收了两者的优点。

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

 

线程的组织与控制

主要由TCB（线程控制块）和线程表

TCB内容包含线程标识符（TID），程序计数器PC，其他寄存器，堆栈指针，线程运行状态，优先级。PC、寄存器，堆栈指针需要在进程调度时进行保存与恢复。

 

CPU调度

CPU三级调度：高级调度（作业调度）、低级调度（处理机调度）、中级调度（内存调度）

高级调度是从外存的作业后备队列中挑出一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。

低级调度是从就绪队列中选取一个进程，将处理机分配，是操作系统中最基本的一种调度，频率很高。

中级调度是内存不够时，将进程的数据调出外存，并设置为挂起状态，被挂起的进程会组织成挂起队列。中级调度则是按照某种策略，将挂起状态的进程重新调入内存。

 

调度的时机

可以进行调度的情况：

进程主动放弃处理机：进程正常终止，，发生异常而终止，主动请求阻塞

进程被动放弃处理机：分配的时间片用完，有更紧急的事情处理，有更高优先级的进程进入就绪队列

不能调度与切换的情况：

处理中断的过程中，中断处理过程复杂，很难切换。

在操作系统的内核临界区中。一般是访问某种内核数据结构，普通的临界区可以调度切换

在原子操作过程中，不可中断。

进程切换是有代价的，过于频繁切换调度会降低系统效率。

调度方式：非剥夺调度和剥夺调度（非抢占和抢占）

调度器/调度程序：决定调度算法和时间片大小。

在创建新进程、进程退出、进程阻塞、IO中断发生时

 

闲逛进程：没有其他就绪进程时运行闲逛进程（抖腿）

优点级最低、可以是0地址指令、能耗低。

 

调度算法

CPU利用率：指CPU忙碌的时间占总时间的比例

利用率

系统吞吐量：指单位时间内完成作业的数量

吞吐量

周转时间：指作业被提交给系统开始，到作业完成为止这段时间间隔

周转时间 = 作业完成时间-作业提交时间

平均周转时间

带权周转时间 = ，必然>=1

平均带权周转时间 =

 

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

等待时间 = 周转时间-运行时间-IO时间

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和。

对于作业来说，处理进程后的等待时间，还要加上作业在外存后备队列等待的时间

 

响应时间：指用户提交请求到首次相应所用的时间

 

先来先服务（FCFS）、短作业优先（SJF）、高响应比优先（HRRN）

主要思考算法思想、算法规则、是用于作业调度还是进程调度、抢占式还是非抢占式、优点和缺点、是否会饥饿

先来先服务：

从公平角度，按照作业到达的先后顺序进行服务，作业调度和进程调度都可用，是非抢占式的算法。优点是公平简单，缺点是对长作业有利，对短作业不利。不会导致饥饿。

短作业优先：

追求最少的平均等待时间、平均周转时间。最短的作业/进程先得到服务，即可用在作业调度，也可用在进程调度。是非抢占的算法，但是也有抢占式版本的，即最短剩余时间优先算法。每次调度选择当前已到达的并且运行时间最短的作业。优点是对短作业有利，对长作业不利，会产生饥饿现象。如果一直得不到服务，则称为饿死。

在抢占式的短作业优先算法中，每当一个新的进程进入队列中时，需要进行一次调度，如果新到达的进程剩余时间比当前运行的进程剩余时间短，则抢占处理机，当前进程回到就绪队列，完成一个进程时也需要进行调度。

如果题目未说明，则默认是非抢占式的。

高响应比优先：

综合考虑作业和进程的等待时间和要求服务的时间。每次调度时计算各个作业/进程的响应比，选择响应比最高的作业/进程。既可以用在进程调度，也可以用在作业调度。是非抢占式的算法。综合了前两个算法的优先，不会产生饥饿。

响应比 = ，响应比>=1

每次作业完成时进行调度，主动放弃CPU调度，计算所有就绪进程的响应比，选择响应比最高的进程上处理机。

 

这三种算法适用于早期的批处理系统，对用户来说交互性很差。

 

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

l 时间片轮转算法

时间片轮转调度算法的算法思想是每个进程都能公平的得到服务，轮流按照各个进程执行时间片，如果进程在一个时间片内没有做完的话，则会剥夺处理机，并将进程重新放回就绪队列队尾重新排队。时间片轮转用于进程调度。因为只有作业放入内存并且建立相应的进程后，才能分配处理机时间片。该算法为抢占式的算法，由时钟控制装置发出时钟中断来通知时间片已到。该算法常用于分时操作系统，更注重响应时间，不计算周转时间。

具体情况下，设置时间片的大小为2，如果在某一时刻一个进程下处理机，同时一个新进程到达，则默认该新进程先进入就绪队列，下来的进程则放在该新进程后面。

每当有新进程到时，将该进程插在就绪队列的末尾。

如果运行中的进程所剩的时间片没用完，运行完了后也会放弃处理机，并进行一次调度。

时间片轮转算法不会导致饥饿。

优点是公平，相应快，适用于分时操作系统

缺点是高频率的切换，会有一定的开销。而且不会区分任务的紧急程度。

 

l 优先级调度算法

优先级调度算法的算法是为了根据任务的紧急程度来决定处理次序。

每个任务/进程都有各自的优先级，调度时选择优先级最高的作业/进程。

既可以用于作业调度，也可以用于进程调度。甚至可以用在I/O调度当中。

是抢占式、非抢占式两种都有。两者的区别在于，非抢占式只需在进程主动放弃处理机时进行调度即可。抢占式还需要在就绪队列变化时，检查是否会发生抢占。

在非抢占式的算法中，进程会一次性执行完。在调度的时候，会根据到达进程的优先级进行调度，优点级最大优先调度。当优先级相同的时候，则调度先到的进程。

在抢占式的算法中，当进程主动放弃处理机的时候进行一次调度，同时，当就绪队列变化的时候也会检查是否抢占。

在优先级调度算法中，优先级分为静态优先级和动态优先级。

静态优先级在创建进程的时候确定，之后则一直不变。

动态优先级则是有一个初始值，根据情况动态地调整优先级。

在优先级的设置上，系统进程优先级大于用户进程，前台进程的优先级大于后台进程。操作系统更偏好I/O型进程，与其相对的是CPU型进程。

在优先级的调整上，如果某个进程在就绪队列中等了太长时间，则可以适当提高一些优先级。占用处理机过久的进程，会降低优先级。频繁进行I/O操作的进程，可以适当提升优先级

优先级调度算法的优点是用优先级区分紧急和重要程度，适用于实时操作系统。可以灵活调整各种作业/进程的偏好程度。缺点是如果有源源不断的高优先级的进程进来，则会导致饥饿。

优先级调度算法会导致饥饿。

 

l 多级队列反馈算法

多级队列反馈算法是对其他调度算法的折中平衡。

多级队列反馈算法将设置多级就绪队列。各级队列的优先级从高到低，时间片从小到大。

新的进程到达是进入第一级队列，按照先来先服务的原则，排队等待时间片。若用完时间片进程还未结束，则进入下一级的队列，如果已经是最下级的队列了，则将该进程放回该队列队尾。

只有k级队列为空时，才能为k+1级队列分配时间片。

该算法是抢占式的算法。在k级队列进程运行过程中，若更上级（0-k-1）的队列进入了一个新进程，新进程会抢占处理机，原来运行的进程会放回k级队列队尾。

优点是对各类型的进程相对公平，每个新到达的进程都能快速得到相应。短进程只用较少时间就能完成，不必实现估计进程的运行时间（避免用户作假），可以灵活地调整各类进程的偏好程度。比如CPU密集型进程，I/O密集型进程。比如将因I/O阻塞的进程放回原队列，使得保持较高的优先级。

该算法会导致饥饿。

 

以上三种算法都适用于交互式系统

 

进程优先级排序：系统进程（内存管理进程）>交互式进程（游戏，打字软件）>批处理进程（AI训练模型等）

 

 

 

上下文切换

上下文的概念

进程上下文的切换实际就是任务切换。当处理器决定运行其他任务时，需要保存该运行任务的状态，也就是CPU处理器的全部内容

同步与互斥（PV）

临界资源和临界区

临界区是指的是访问临界资源的那段代码

对于临界资源的访问，需要互斥的进行

需要遵守的原则：空闲让进，也就是说临界区空闲时，应该允许一个进程访问。忙则等待，临界区正在被访问时，其他试图访问的进程需要等待。有限等待，要在有限的时间内进入临界区，保证不会饥饿。让权等待，进不了临界区的进程要释放处理机，防止忙等。

 

同步机制规则

单标志法，双标志先检查法，双标志后检查法，Peterson算法

单标志法在进入区只检查，不上锁。在退出区把临界资源的使用权转交给另一个进程。不遵守空闲让进的原则。

双标志先检查法在进入区检查后上锁，退出区解锁。不遵守忙则等待的原则。

双标志后检查法在进入区先加锁后检查，退出区解锁。不遵守空闲让进，有限等待的原则，可能导致饥饿。

Peterson算法在进入区主动谦让，不遵循让权等待的原则，会发生忙等。

硬件同步机制

中断屏蔽方法、TestAndSet方法、Swap指令

中断屏蔽方法使用开关中断指令实现，简单高效，只适用于单处理机。只适用于操作系统内核进程。

Ts方法和swap方法通过old记录是否已被上锁，再将lock设置为true，检查临界区是否已被上锁（若已被上锁，则循环重复前几步）优点是实现简单，适用于多处理机环境。缺点是不满足让权等待。

互斥锁

在进入临界区时获得锁，在推出临界区时释放锁。缺点是忙等待，当其中一个进程在临界区时，其他进程会连续调用acquire（）。互斥锁适用于多处理机系统，一个线程可以在一个处理器上运行，不会影响其他进程的执行。需要连续循环忙等的互斥锁，都可以称为自旋锁。

信号量机制

用户可以通过操作系统的一对原语来对信号量进行操作。信号量是一个变量，表示系统中某种资源的数量。一对原语：wait和signal也就是俗称的PV操作。

在整型信号量的操作只有三种，初始化，P，V，存在的问题是不满足让权等待的原则，会发生忙等。

记录型信号量用记录型数据结构表示信号量。记录型信号量在资源不够时，使得进程进入阻塞队列。在释放资源时将唤醒阻塞队列的一个进程。该机制遵循了让权等待的原则

S.Value表示某种资源数，S.L表示等待该资源的队列

在P操作中，先value--，再执行block原语

在V操作中，先value++，再执行wakeup原语

可以用记录型信号量实现系统资源的申请和释放

可以用记录型信号量实现进程互斥、进程同步

 

信号量机制

实现互斥方法：

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

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

在进入区申请资源，在退出区释放资源

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

P、V操作必须成对出现

 

实现同步方法：

分析什么地方需要实现同步关系，保证一前一后的两个顺序。

设置同步信号量S，初值为0

在前操作之后执行V（S）

在后操作之前执行P（S）

信号量S代表某种资源，刚开始是没有这种资源的，P2需要这种资源，而这种资源只能由P1产生。

 

实现前驱关系

画出前驱图，把每个前驱关系看成一个同步问题

为每一对前驱关系各设置一个同步信号量

在前操作后对相应的同步信号量执行V操作

在后操作之前对相应的同步信号量执行P操作

 

管程

为什么要引入管程：解决复杂的PV操作

管程的定义

是一种特殊的软件模块

局部于管程的共享数据结构说明

对该数据结构进行操作的一组过程（函数）

局部于管程的共享数据设置初始值的语句

有一个名字

每次仅允许一个进程在管程内执行某个内部过程

 

需要在管程中定义共享数据，用于访问该共享数据的入口。通过这些特定的入口才能访问共享数据。管程有很多入口，每次只能开放其中一个入口，只能让一个线程或进程进入。互斥特性是由编译器负责实现的，可以在管程中设置条件变量及等待/唤醒操作以解决同步问题。

 

经典的同步问题:

生产者消费者问题

多消费者问题

吸烟者问题

读者写者问题

哲学家进餐问题

 

死锁

死锁的原因

互相等待对方的资源，导致各进程都阻塞，都无法向前推进

死锁一定是至少有两个或者两个的进程同时发生死锁

饥饿是可能只有一个进程发生饥饿

死锁和饥饿是操作系统的问题，死循环是管理者的问题

 

死锁的必要条件

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

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

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

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

发生死锁一定是有循环等待，但是发生循环等待未必死锁。

发生死锁的条件：

对系统资源的争夺、进程推进顺序非法、信号量的使用不当

 

死锁的处理方法

预防死锁：破坏死锁四个必要条件中的一个或几个

避免死锁：用某种方法防止系统进入不安全状态。从而避免死锁

死锁的检测和解除：允许死锁的发生，操作系统会负责检测死锁的发生，然后采取某种办法解除死锁

 

不允许死锁发生：静态策略（预防死锁）、动态策略（避免死锁）

预防死锁：

破坏互斥条件：将临界资源改造为可共享使用的资源（spooling）

缺点是可行性不高，很多时候无法破坏互斥条件

破坏不剥夺条件：申请的资源得不到满足的时候，立刻释放所有的资源。申请的资源被其他进程占用时，由操作系统协助剥夺。

缺点是实现复杂，剥夺资源导致部分工作失效，反复申请和释放导致系统开销大，可能导致饥饿。

破坏请求和保持条件，运行前分配好所需要的资源，之后一起保持。缺点是资源利用率低，可能导致饥饿。

破坏循环和等待条件，给资源编号，必须按从小到大的顺序申请资源。缺点是不方便增加新的设备，会导致资源浪费，用户编程麻烦。

 

避免死锁：

安全序列

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

系统处于安全状态，一定不会发生死锁，如果系统进入不安全状态，未必会发生死锁。

银行家算法的核心思想是在资源分配前预先判定这次分配是否会导致系统进入不安全状态。如果进入不安全状态，则暂时不答应这次请求，让该进程先阻塞等待。

安全性算法的思想是先找出剩余可用资源能否满足各进程的需求，如果可以则将该进程加入安全序列，并更新剩余可用资源，将该进程所持有的资源全部回收。不断重复上述过程，看最终是否让所有进程都加入安全序列。

假设系统有n个进程，m种资源。银行家算法先建立最大需求矩阵MAX，已分配矩阵Allocation，需求矩阵Need，Max-Allocation=Need，还要建立长度为m的一维数组Available，表示系统还剩的可用资源。

进程P向系统请求资源时，用一个长度为m的一维数组Request，表示申请的各种资源量。用银行家算法预判本次分配是否会导致系统进入不安全状态。

如果Request<Need，便继续，否则出错。

如果Request<Available，便继续，否则无可用资源，P需要等待

系统尝试分配资源给P，并修改相应数据。

执行安全性算法，检查此次分配后系统是否处于安全状态，如果安全才正式分配，否则恢复相应数据，让P阻塞等待。

 

死锁的检测和解除：

死锁检测：用于检测系统中是否发生了死锁

用某种数据结构保存资源的请求和分配信息

提供一种算法，利用上述信息检测系统是否进入死锁状态。

两种节点：进程节点和资源节点

两种边：进程节点-》资源节点：表示进程想申请几个资源（每条边一个）

资源节点-》进程节点：表示进程分配了几个资源（每条边一个）

能消除所有边，则称这个图是可完全简化的，一定没有发生死锁。

不能消除所有边，那么就是发生了死锁。

最终还连着的那些边的那些进程就是处于死锁状态的进程

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。

 

死锁解除：认定系统发生了死锁，利用该算法可以将系统从死锁中解脱出来。

解除死锁的办法：

资源剥夺法：挂起某些死锁进程，并将这些资源分配给其他死锁进程。

撤销进程法：强制撤销部分甚至全部死锁进程，剥夺该资源，实现简单但是代价很大。

进程回退法：让一个或者多个进程回退到足以避免死锁的地步，要求系统记录进程的历史信息。