操作系统学习笔记-进程的描述与控制

程序的顺序执行

程序的顺序执行具有以下特征：

• 顺序性：处理器的操作严格按照程序所规定的顺序执行，下一操作必须在当前操作结束后才能开始
• 封闭性：程序是在封闭的环境下执行的。即程序运行时独占全机的资源，资源的状态除初始态外，只有本程序才能改变；只要程序开始运行，其运行结果就不会受到外界的影响
• 可再现性：只要程序执行的环境和初始条件相同，程序重复执行的结果都相同，不管执行的过程是否一致

程序的并发执行

程序顺序执行的特性为程序员检测和校正程序错误带来了很大方便，但资源的利用率却很低，因此系统中引入了多道程序技术，使程序或程序段之间能并发执行
其特征为：

• 间断性：程序并发执行时，由于它们共享系统资源，但一个程序在运行至某一步需要占用某一系统资源时，却发现该资源被另一个并发的程序所占用，那它就必须暂停运行等待资源的空闲
• 失去封闭性：系统资源会被并发程序共享，影响，反过来说就是一个程序在运行时的环境，会受其它并发程序的影响，这就失去了封闭性
• 不可再现性：由于失去了封闭性，也导致程序失去了可再现性。例如两个程序共享一个变量，两个程序都会对这个变量进行不同的修改操作，当两个程序以不同的速度运行，变量的值的变化情况也会不一样，那么最终得到的执行结果自然也可能各不相同

进程

对进程的理解

在多道程序环境下，程序的执行是并发执行，因此它们将失去封闭性，并具有间断性以及不可再现性，也即失去了作为一个"程序"的特征，所以这种情况下并不能用程序来描述它们。所以为了对并发执行的程序加以描述和控制，引入了“进程”的概念
进程是程序的一次执行，是一个程序及其数据在处理机上顺序执行时所发生的活动，是具有独立功能的程序在一个数据集合上运行的过程，是系统进行资源分配和调度的独立单位
由程序段，数据段，和PCB三部分便构成了进程实体，又称进程映像。所谓进程创建与撤销，实质上就是进程实体中的PCB的创建与撤销
引入了进程实体的概念后，可以把传统OS中的进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

进程与程序的异同

• 程序是指令的集合，是一个静态的概念；进程是程序在处理机上的一次执行过程，是一个动态概念
• 程序是长期存在的，进程有生命周期：创建，活动，消亡…
• 程序仅是指令的有序集合；而进程由程序，数据，和进程控制块组成
• 进程跟程序并不是一一对应的。同一程序同时运行于若干个不同的数据集合上，将对应不同的线程；而一个进程也可以执行多个程序，如脚本的执行，开启一个进程来执行一个脚本，而这个脚本中又可以包含其它若干个程序

进程的特征

动态性，并发性，独立性，异步性。虽然进程并发执行时具有异步性，但其执行结果是可再现的，操作系统配置了相应的进程同步机制
进程的存在意味着，其处于某种状态(运行，就绪，等待…)，具有进程控制块，进程的执行程序被运行了(一个可执行文件)，进程位于某个队列中(跟所处状态对应)，某些系统资源被占用了，如内存，IO，处理机，外设

进程的基本状态及其转换

三种基本状态：就绪Ready，执行Running，阻塞Block

可以看到阻塞态不能直接转到执行态。首先，进程从执行态转到阻塞态，是因为进程由于发生某事件，如IO请求，暂时无法继续执行，因此转入阻塞态，此时引起进程调度，OS把处理机分配给另一个就绪进程。那么当阻塞态的进程又可以继续执行时，由于处理机正忙，它并不能第一时间获取处理机资源，所以只能先到就绪态等待进程调度
转换过程可以类比银行取钱业务，如当我们到达银行时，业务窗口可能都在忙，尽管我们所需资料如个人信息等都已经准备完毕了，也不能第一时间进行服务。只有等窗口叫号(进程调度)了才能得到服务。服务时可能被服务人员要求再填一份信息，此时就要暂时离开窗口去填写信息(阻塞)，此时窗口又会服务其它的顾客。当我们把信息填好后，可能所有窗口都在忙，又只能等下次叫号才能继续自己的业务了
实际情况中进程调度涉及到调度算法，会更复杂
除了上面提到的三种状态，通常还会有创建状态和终止状态

挂起操作

挂起操作指当该操作作用于某个进程时，该进程将被挂起，即该进程将处于静止状态。引入操作原语Suspend以及激活原语Active后。进程将可能发生以下几种状态的转换：

• 活动就绪 -> 静止就绪：当进程处于未被挂起的就绪状态时称此为活动就绪状态Readya。当用挂起原语将该进程挂起后，该进程将转变为静止就绪状态Readys，此时进程不再被调度执行
• 活动阻塞 -> 静止阻塞：当进程处于未被挂起的阻塞状态时，称它是处于活动阻塞状态Blockeda，当用Suspend原语将其挂起后，进程便转变为静止阻塞状态Blockeds，处于该状态的进程在其所期待的事件出现后将转变为静止就绪状态Readys，可以理解为虽然就绪了，但还是被挂起，所以只能静止就绪
• 静止就绪 -> 活动就绪：处于Readys状态的进程若用激活原语Active激活后，将转变为活动就绪
• 静止阻塞 -> 活动阻塞：处于静止阻塞状态的进程用Active激活后将转变为Blockeda状态

进程控制块PCB

OS的核心为每个进程专门定义了一个数据结构——进程控制块PCB(Process Control Block)，PCB作为进程实体的一部分，记录了操作系统所需的用于描述进程的当前情况以及管理进程运行的全部信息，是操作系统中最重要的记录型数据结构，它使一个在多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程

包含的信息

主要包括：

• 进程标识符
• 处理机状态
• 进程调度信息
• 进程控制信息

进程控制

进程控制的任务就是，对系统中所有进程从创建，存在到消亡的全过程实施有效的管理和控制。具有创建新进程，对运行进程进行控制，撤销进程的能力
进程控制由OS系统的内核完成，内核通过原语操作来实现

内核，用户态与内核态

现代操作系统一般将OS划分为若干层次，再将OS的不同功能分别设置在不同的层次。通常将一些与硬件紧密相关的模块(如中断处理程序等)，各种常用设备的驱动程序以及运行频率较高的模块(如时钟管理，进程调度和许多模块所公用的一些基本操作)，都安排在紧靠硬件的软件层次中，将它们常驻内存，相当于基于硬件的第一次软件扩充，即通常被称为的OS内核
这种安排方式的目的在于两方面：一是便于对这些软件进行保护，防止遭受其他应用程序的破坏；二是可以提高 OS 的运行效率
相对应的，为了防止OS本身及关键数据(如PCB等)遭受到应用程序有意或无意的破坏，通常也将处理机的执行状态分成系统态和用户态两种：

1. 系统态：又称为管态，也称为内核态。它具有较高的特权，能执行一切指令，访问所有寄存器和存储区，传统的 OS 都在系统态运行
2. 用户态：又称为目态。它是具有较低特权的执行状态，仅能执行规定的指令，访问指定的寄存器和存储区
   一般情况下，应用程序只能在用户态运行，不能去执行OS指令及访问OS区域，这样可以防止应用程序对OS的破坏

大多数OS内核都包含了以下两大方面的功能：

1. 支撑功能。包括中断处理，时钟管理和原语操作。所谓原语( Primitive)，就是由若干条指令组成的，用于完成一定功能的一个过程。它们是原子操作
2. 资源管理功能。包括进程管理，存储器管理，设备管理

进程创建

一个进程可以创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程称为子进程
子进程可以继承父进程所拥有的资源，例如，继承父进程打开的文件，继承父进程所分配到的缓冲区等。当子进程被撤消时，应将其从父进程那里获得的资源归还给父进程。此外，在撤消父进程时，也必须同时撤消其所有的子进程

Linux中创建进程

Linux通过fork函数创建进程，且创建出来的进程为子进程，创建它的为父进程。而Windows中就没有这种设定，创建出来的进程间具有平等地位，Windows通过createProcess创建进程
Linux中，在一个程序中调用fork创建进程后，后续程序代码在父进程跟子进程中都会执行

引起进程创建的事件

1. 用户登录
2. 作业调度
3. 提供服务，当运行中的用户程序提出某种请求，系统就创建一个专门的进程来提供用户所需服务，多个进程并发执行提供服务
4. 应用请求，以上三种都是系统内核为用户创建一个新进程，而这种是由用户进程自己创建新进程(第3是由于用户程序此时需要进行如打印的功能，向系统提出了这个请求，但是不是自己创建进程来完成，而是系统接收到这个请求，创建出进程来完成那个功能；而第4是在应用程序中自己就建立进程，没有先发出请求)

创建步骤

OS调用进程创建原语Creat：

1. 申请空白PCB。为新进程申请获得唯一的数字标识符，并从PCB集合中索取一个空白PCB(一个系统的PCB是有限的)
2. 为新进程分配所需资源
3. 初始化进程控制块
4. 插入就绪队列

进程终止

正常结束，异常结束，外界干预(通过kill杀死进程，在Linux中，杀死父进程，子进程不会一起被杀掉，Linux会让其它线程成为它的父进程)

进程的阻塞和唤醒

引起进程阻塞和唤醒的事件

1. 向系统请求共享资源失败
2. 等待某种操作的完成
3. 新数据尚未到达
4. 等待新任务的到达

阻塞是一种进程的主动行为

进程的挂起和激活

挂起时，为方便用户或父进程考察该进程的运行情况，会把该进程的PCB复制到某指定的内存区域

进程同步

为保证多个进程有条不紊地运行，在多道程序系统中必须引入进程同步机制
进程同步机制地主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则或时序共享系统资源，并能很好地相互合作，从而使程序执行具有可再现性

两种形式的制约关系

• 间接制约：对于临界资源 (即一次仅允许一个进程访问)，多个进程对其只能互斥地访问。这类资源必须由系统实施统一分配，用户使用前应先提出申请而不能直接使用(CPU不是临界资源)
• 直接制约：源于进程之间的相互合作，比如一个进程要等另一个线程完成了什么操作它才能继续运行

临界区

人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)
在进入临界区之前需要先检查临界资源是否正被访问，如果未被访问，那么进程就可以进入临界区对该资源进行访问，并设置其正被访问的标志；如果正被访问，则本进程不能进入临界区。这部分检查代码称为进入区
相应地，在临界区后也要加上一段称为退出区的代码，用于将临界资源恢复为未被访问
除此之外剩下的其他代码都称为剩余区

同步机制应遵循的规则

• 空闲让进：当临界资源处于空闲状态应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源
• 忙则等待：当临界资源正在被访问，其它试图进入临界区的进程必须等待
• 有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免“死等”
• 让权等待：当进程不能进入自己的临界区时，应立即释放处理机 (即CPU执行权)，以免“忙等”

硬件同步机制

关中断：在进入锁测试之前关闭中断，知道完成所测试并上锁之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发掉队，也就不会发生进程或线程切换
关中断的缺点：滥用关中断可能导致严重后果；关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；不适应于多CPU，在一个处理器上关中断了并不能防止进程在其它处理器上执行相同的临界段代码

信号量机制

整型信号量

整形信号量定义为一个用于表示资源数目的整型量S，除了初始化外，仅能通过两个原子操作 wait(S) 和 signal(S)来访问，分别称为P，V操作：

wait(S){while(S<=0);S--;}signal(S){S++;}

S初值设为1，当第一个进程进行P操作时，S变为0，其它进程尝试P操作时会一直卡在循环，知道第一个进程执行完毕，令S恢复到0，其它进程才可以进入临界区
当利用信号量实现互斥时，PV操作总是成对出现在同一进程中
当利用信号量实现前趋关系时，PV操作总是成对出现在不同进程中
可以看出，整型信号量机制不符合让权等待的规则

记录型信号量

记录型可以解决整型信号量的“忙等”的问题，而且可以对等待访问资源的多个进程进行管理。记录型信号量的结构以及对应的PV操作如下：

typedef struct{int value;//临界资源数目struct process_control_block *list;//存储等待进程的链表指针}//S->value的初值表示系统中某类资源的数目wait(semaphore *S){S->value--;if(S->value < 0) block(S->list); //资源已分配完毕，进程调用block原语进行自我阻塞，放弃处理机，并插入链表中//此时S->value的绝对值表示在链表中已阻塞的进程的数目}signal(semaphore *S){S->value++;//加一后S->value还是<=0的话，说明仍有等待资源的进程被阻塞，故调用wakeup原语将链表中的第一个等待进程唤醒if(S->value <= 0) wakeup(S->list);}

如果S->value初值为1，此时的信号量转化为互斥信号量，用于进程互斥

AND型信号量

前面的进程互斥问题针对的是多个并发进程仅共享一个临界资源的情况，有部分场景是一个进程往往需要获得两个或更多的共享资源才能执行其任务
假设现有进程A和B，它们都要求访问共享数据D和E，分别对应信号量Dmutex和Emutex，令它们初值都为1。那么当两个进程发生如下操作时：

process A:wait(Dmutex);wait(Emutex);process B:wait(Emutex);wait(Dmutex);

A访问到D，且还未释放。B访问到E，且还未释放。此时A需要访问E才能继续运行，而B需要访问D才能继续运行。那么两个进程就处于僵持状态。无外力作用下，两者都将无法从僵持状态中解脱出来，称为死锁
AND同步机制的基本思想是，将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配

进程间通信

进程通信，即进程之间的信息交换。根据OS的发展历程分为低级通信以及高级通信。例如信号量机制即为一种低级进程通信，之所以称为低级通信的原因是：效率低，生产者每次只能往缓冲区中投放一个消息，消费者每次也只能从缓冲区中取得一个消息；通信对用户不透明，进程之间通信所需的共享数据结构的设计，进程的互斥跟同步，都需要程序员实现
目前的高级通信机制可归结为四类：共享存储器系统Shared-Memory System，管道通信系统Pipe，消息传递系统Message passing system，客户机-服务器系统Client-Server system

• 共享存储器系统：又分为基于共享数据结构的通信方式以及基于共享存储区的通信方式。基于共享数据结构，如生产者-消费者问题中的缓冲区，这种情况下OS仅提供共享存储器，对于数据结构的设置以及进程间的同步都需要程序员完成，属于低级通信；基于共享存储区，先在内存中划分出一块共享存储区，进程需要通信时向系统申请获得共享存储区中的一个分区，然后对其中的数据进行正常的读写，操作完毕再归还给存储区
• 管道通信系统：基于一个共享文件pipe文件，进程从文件中读写数据。管道机制必须有三个方面的协调能力：互斥，即一个进程对文件进行读/写操作时，另一个进程必须等待；同步，当写进程写完数据时会进入睡眠等待状态，等读进程将数据取走后再把它唤醒，同理，当读进程读一个空pipe时，也应睡眠等待，直到写进程将数据写入管道才唤醒；确认对方是否存在，只有对方存在才能进行通信
• 消息传递系统：将数据封装在消息message中，利用OS提供的一组通信原语进行消息传递，实现进程间的数据交换。发送进程利用OS提供的发送原语直接把消息发送到目标进程的，称为直接通信；发送和接收进程都通过共享中间实体(邮箱)进行操作的，称为间接通信
• 客户机-服务器系统：可分为三类：套接字，远程过程调用和远程方法调用

线程

线程的引入

进程具有两个属性：既是一个拥有资源的独立单位，又是一个资源调度和分配的基本单位。由于进程是一个资源的拥有者，在其创建，撤销，切换中，系统必须为之付出较大的时空开销：创建进程时，系统必须为它分配其所必需的，除处理机以外的所有资源，如内存空间，IO设备，以及建立相应的PCB；撤销进程时，又必须先对其所占有的资源执行回收操作，然后再撤销PCB；进程切换，对进程进行上下文切换时，需要保留当前进程的CPU环境，设置新选中进程的CPU环境，因而须花费不少的处理及时间
故系统中的进程数目不宜过多，进程切换的频率也不宜过高，这就限制了并发程度的进一步提高
既然如此，那就设法将进程的两个属性分开，不把作为调度和分配的基本单位也同时作为有用资源的单位，而对于拥有资源的基本单位，又不对之进行频繁的切换
在这种思想的指导下便形成了线程的概念。线程只作为调度和分配的基本单位，而不作为资源分配的基本单位。一个进程常包括多个线程，其基本上不拥有系统资源，只有少量资源如IP，寄存器，栈，但共享其所属进程所拥有的全部资源。又称之为轻量级进程

线程的属性

• 轻型实体
• 独立调度和分派额基本单位
• 可并发执行
• 共享进程资源

线程和进程的比较

调度性

传统OS中，进程是独立调度和分派的基本单位，因而进程是能独立运行的基本单位。引入了线程后，线程作为调度和分派的基本单位，因而线程是能独立运行的基本单位。线程切换时，仅需保存和设置少量寄存器内容，切换的代价远低于进程。同一进程中，线程的切换不会引起进程的切换，但从一个进程的线程切换到另一个进程的线程时必然会引起进程的切换

并发性

引入线程的OS中，不仅进程之间可以并发执行，一个进程的多个线程之间也可以并发执行，这使得OS具有更好的并发性，更有效地提高系统资源的利用率和系统吞吐量；此外，有的应用程序需要执行多个相似的任务。如一个网络服务器经常会接到许多客户的请求，如果仍采用单线程 的进程来执行任务，则每次只能为一个客户服务，但如果在液体个进程中可以设置多个线程，其中一个专用于监听客户请求，则每当有一个客户请求时，便立即创建一个新的线程来处理该客户的请求 (实际开发中的并发问题)

拥有资源

进程可以拥有资源并作为系统中拥有资源的基本单位；而线程仅有一点必不可少的保证独立运行的资源，如线程控制块TCB，程序计数器，寄存器和堆栈。除此之外多个线程还可以共享所属进程的资源，访问进程所拥有的资源

独立性

同一进程的不同线程之间的独立性要比不用进程之间的独立性低得多

系统开销

不管是创建，撤销，还是切换，在线程上的操作都要比进程的快许多。此外，由于一个进程中的多个线程具有相同的地址空间，线程之间的同步和通信也比进程的简单

支持多处理机系统

对于传统的单线程进程，不管系统中有多少个处理机，该进程只能运行在一个处理机上。但对于多线程进程，就可以把一个进程的多个线程分配到多个处理机上并行执行，加快了进程的完成