进程管理

进程基本概念

程序的顺序执行及其特征

• 程序的顺序执行：仅当前已操作执行完后，才能执行后续操作。
• 程序顺序执行时的特征：顺序性，封闭性，可在现性。
• 前趋图
  用结点代表各程序段的操作，用箭头代表操作的先后次序。则前趋图是一个有向无环图，记为:DAG(Directed Acyclic Graph) ，用于描述进程或语句之间的先后关系。Pi->Pj，称为Pi 是Pj的直接前趋， Pj 是Pi的直接后继。有“初始结点”、“终止结点”的提法。
  
  

程序的并发执行

程序的并发执行

若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。
对于多组输入I、计算C、打印P存在如下并发关系：

程序的并发执行特征

• 间断性:执行——停——执行
• 失去封闭性：例如当处理机分配给某个进程运行时，另一个进程必须等待。
• 不可在现性：执行结果与其执行的相对速度有关，是不确定的

进程的特征与状态

进程定义

• 进程是程序的一次执行。
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
• 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程的特征

• 结构特征：PCB ＋程序段＋相关数据＝进程实体
• 动态性：最基本的特征
• 并发性
• 独立性
• 异步性

进程与程序的区别与联系

（1）程序是指令的集合，是静态的概念。 进程是程序在处理机上的一次执行的过程，是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。
（2）进程是一个独立的运行单位，能与其它进程并发活动。而程序不是。
（3）进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。
（4）一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。

进程的三种基本状态

• 就绪状态：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态。
• 执行状态：进程占有CPU，并在CPU上运行 。
• 阻塞状态:也称为等待态、封锁态。指进程因等待某种事件的发生而暂时不能运行的状态。

挂起状态

在系统资源不足的情况下，操作系统会对在内存中的进程进行合理的安排，其中有的进程被暂时调离出内存，即处于“挂起”状态。当条件允许的时候，会被操作系统再次调回内存，重新进入就绪态等待处理机调度。

• 进程挂起的原因
  1.终端用户的请求。
  2.父进程请求。
  3.负荷调节的需要。
  4.操作系统的需要。
• 进程状态的转换
  1.活动就绪→静止就绪。
  2.活动阻塞→静止阻塞。
  3.静止就绪→活动就绪。
  4.静止阻塞→活动阻塞。
  

进程控制块

进程控制块的作用

存放进程的管理和控制信息的数据结构称为进程控制块。它是进程管理和控制的最重要的数据结构，在进程创建时，系统为该进程建立PCB，并伴随其运行的全过程，直到进程撤消而撤消PCB 。
PCB的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。PCB是OS感知进程存在的唯一依据。

进程控制块中的信息

• 进程描述信息
  • 进程标识符：
    1.内部标识符:为方便系统使用,在所有操作系统中，都为每个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。
    2.外部标识符：它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。
  • 进程家族关系： 父进程标识、子进程标识。
  • 用户：指示拥有该进程的用户。
• 处理机状态（CPU现场保护结构、进程上下文）
  ① 通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息。
  ②指令计数器PC，其中存放了要访问的下一条指令的地址。
  ③ 程序状态字PSW，其中含有状态信息，如条件码、执行方式、 中断屏蔽标志等。
  ④ 用户栈指针， 指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。
• 进程调度信息
  ① 进程状态，指明进程当前状态， 作为进程调度和对换时的依据。
  ②进程优先级，用于描述进程使用处理机的优先级别的整数， 优先级高的进程应优先获得处理机。
  ③进程调度所需的其它信息，它们与所采用的进程调度算法有关，如进程已等待CPU的时间总和、 进程已执行的时间总和等。
  ④事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。
• 进程控制信息
  ①程序和数据的地址， 指进程的程序和数据所在的内存或外存地(首)址,以便再调度到该进程执行时，能从PCB中找到其程序和数据。
  ②进程同步和通信机制，指实现进程同步和进程通信时必需的机制,如消息队列指针、信号量等。
  ③资源清单,是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单。
  ④链接指针，给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。

PCB的组织方式（除了线性方式外）

进 程 控 制

• 1.操作系统的执行模式，即CPU的状态有两种
  1）系统态：也叫核心态、管态，有较高的特权，可执行一切指令，访问所有寄存器和存储区。
  2）用户态：也叫目态，有较低的特权，可执行部分指令，访问部分寄存器和存储区。
• 2.OS内核
  是基于硬件的第一层软件扩充，提供操作系统最基本的功能。（包括与硬件紧密相关的如中断处理程序、设备驱动程序；基本的，公共的，运行频率较高的，如时钟管理、进程控制和某些关键的数据结构。）
• 3.进程控制
  系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态之间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。
• 4.原语
  系统态下执行且执行时不允许中断的某些具有特定功能的程序段。（原子性）
  

进程的创建

• 进程图
  
• 引起创建进程的事件
  (1) 用户登录。Timesharing OS
  (2) 作业调度。 Batch OS 由系统内核创建
  (3) 提供服务。
  (4) 应用请求。应用进程的请求，由自己创建
• 进程的创建原语
  (1) 申请空白PCB。
  (2) 为新进程分配资源。
  (3) 初始化进程控制块。
  (4) 将新进程插入就绪队列，如果进程就绪队列能够接纳新进程， 便将新进程插入就绪队列。
  
  
  

进程的终止

• 引起进程终止(Termination of Process)的事件
  

• 异常结束
  ①越界错误。指程序所访问的存储区，已越出该进程的区域。②保护错。进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问。
  ③非法指令。程序试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令。④特权指令错。用户进程试图去执行一条只允许OS执行的指令。⑤运行超时。进程的执行时间超过了指定的最大值；
  ⑥等待超时。进程等待某事件的时间， 超过了规定的最大值。⑦算术运算错。进程试图去执行一个被禁止的运算，如被0除。
  ⑧I/O故障。这是指在I/O过程中发生了错误等。

• 进程的终止原语
  (1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。
  (2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。
  (3) 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。
  (4) 将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统。
  (5) 将被终止进程(它的PCB)从所在队列(或链表)中移出， 等待其他程序来搜集信息。

• 进程的阻塞与唤醒

  • 1.引起进程阻塞和唤醒的事件
    1) 请求系统服务
    2) 启动某种操作
    3) 新数据尚未到达
    4) 无新工作可做

  • 2.进程阻塞原语block：是进程自身的一种主动行为
    

  • 3.进程唤醒原语wakeup()：
    

• 进程的挂起与激活

  • 1.进程的挂起
    当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起， 系统将利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。
    执行过程是：
    首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。 为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。
  • 2.进程的激活过程
    当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active( )将指定进程激活。
    执行过程是：
    激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。

进程同步

互斥的基本概念

• 1.临界资源
  系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。

• 2.临界区（互斥区）
  在每个进程中访问临界资源的程序段叫临界区。

• 3.进程互斥
  在操作系统中，当某一进程正在访问某临界区时，就不允许其它进程进入，否则就会发生(后果)无法估计的错误。我们把进程之间的这种相互制约的关系称为互斥。

• 4.同步机制应遵循的规则（使用互斥区的原则）
  空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入。
  忙则等待：当已有进程在临界区时，其它要求使用临界区的进程必须等待
  有限等待：任何进入互斥区的要求应在有限的时间内得到满足。（进程在临界区内仅逗留有限的时间）
  让权等待：当进程不能进入自己的临界区时，应立即释放处理机。

互斥的实现

• 加锁法
  
• 信号量机制
  • 1.整型信号量
    最初由Dijkstra把整型信号量S定义为一个具有非负初值的整型变量，代表资源的实体。
    除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V原语。可描述为：
    
  • 2.记录型信号量
    在整型信号量机制并未遵循“让权等待”的准则， 而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。
    为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：
    
    
    
    
  • 3.AND型信号量
    
    
    
  • 4.信号量集:S为信号量，t为下限，d为需求
    

同步

进程同步的概念

• 1.直接制约
  一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。
• 2.同步
  一组相互合作的并发进程，为了协调其推进速度，有时需要相互等待与相互唤醒，进程间的这种相互制约关系称为进程同步。
  

用信号量实现进程同步

• 1.共享缓冲区的合作进程的同步
  
  

生产者—消费者问题

对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲区，并通知消费者进程；否则，等待；
对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待.
同时，缓冲区是个临界资源，因此，诸进程对缓冲区的操作程序是一个共享临界区，因此，这里还有个互斥的问题

哲学家进餐问题

管 程 机 制

管程的基本概念

• 管程的定义
  ① 局部于管程的共享变量说明；
  ② 对该数据结构进行操作的一组过程；
  ③ 对局部于管程的数据设置初始值的语句。
  
  
• 管程的特征
  1.模块化
  2.抽象数据类型
  3.信息屏蔽
• 条件变量
  
• 利用管程解决生产者消费者问题
  
  
  

进程通信

进程通信：低级通信，高级通信。

进程通信的类型

• 共享存储器系统
  1.基于共享数据结构的通信方式。
  2.基于共享存储区的通信方式。
• 消息传递系统
  不论是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。在消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位的，程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和间接通信方式两种.
• 管道(Pipe)通信
  所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)， 以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。
  为了协调双方的通信，管道机制必须提供以下三方面的协调能力：
  ① 互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。
  ② 同步，指当写(输入)进程把一定数量的数据写入pipe，便去睡眠等待， 直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。
  ③ 确定对方是否存在，只有确定了对方已存在时，才能进行通信。

消息传递通信机制

• 消息：报文
  
• 消息传递通信机制的实现方法
  • 间接通信方式－－信（邮）箱
    • 信箱
      
    • 信箱通信原语
      
    • 信箱类型
      
      
  • 直接通信方式－－消息缓冲队列
    
    
    
    
    
    
    
    

管道通信方式 Pipe

• 1.定义
  也称共享文件方式，是连接读、写进程的一个特殊文件，它允许进程按先进先出方式传递数据，是单向的字符流式文件。
• 分类
  
• 原理
  
  

线程

线程基本概念

• 线程
  有时称轻型进程(Light Weight Process)、轻权进程、进程元等。在引入线程的操作系统中，线程是进程中的一个实体，是独立调度和分配的基本单位。
  线程（英语：thread）是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。在Unix System V及SunOS中也被称为轻量进程（lightweight processes），但轻量进程更多指内核线程（kernel thread），而把用户线程（user thread）称为线程。
  

• 线程的属性
  (1)轻型实体：除少量私有资源外，基本不拥有系统资源

  TCP	程序计数器	堆栈与寄存器

  (2)独立调度和分派的基本单位
  (3)独立调度和分派的基本单位
  (4)共享进程资源：同一进程内的各个线程都可共享该进程拥有的资源，首先表现在所有线程都具有与进程相同的地址空间。
  (5)动态性

• 线程的状态

  • (1)状态参数：在OS中的每一个线程都可以利用线程标识符和一组状态参数进行描述。状态参数通常有这样几项：
    ① 寄存器状态： 它包括程序计数器PC和堆栈指针中的内容；
    ② 堆栈： 在堆栈中通常保存有局部变量和返回地址；
    ③ 线程运行状态： 用于描述线程正处于何种运行状态；
    ④ 优先级：描述线程执行的优先程度；
    ⑤ 线程专有存储器： 用于保存线程自己的局部变量拷贝；
    ⑥ 信号屏蔽： 即对某些信号加以屏蔽。
  • (2) 线程运行状态
    如同传统的进程一样，在各线程之间也存在着共享资源和相互合作的制约关系，致使线程在运行时也具有间断性。 相应地，线程在运行时，也具有下述三种基本状态：
    ① 执行状态：表示线程正获得处理机而运行。
    ②就绪状态：指线程已具备了各种执行条件，一旦获得CPU便可执行的状态。
    ③阻塞状态：指线程在执行中因某事件而受阻，处于暂停执行时的状态。

• 线程的基本操作：
  ①派生（spawn）：
  也称“孵化”，即创建。可由进程或线程派生。当系统创建一个新进程时，同时为其派生一个“初始化线程”，以后该线程可根据需要派生其他线程。
  ②阻塞（block）：也称为“封锁”
  ③唤醒（unblock）：也称为“激活”、“活化”
  ④调度（schedule）
  ⑤结束（finish）

• 多线程OS中的进程
  在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。 多线程OS中的进程有以下属性：
  (1) 作为系统资源分配的单位。
  (2) 可包括多个线程。
  (3) 进程不是一个可执行的实体。

• 引入线程的好处
  ①创建一个新线程花费时间少（结束亦如此）
  ②两个线程的切换花费时间少
  ③同一进程内线程间通信简便、快速：共享内存和文件，无须调用 内核
  ④细化了系统并发的粒度

• 线程和进程比较

  调度	在传统的OS中，进程既是拥有资源的基本单位，又是独立调度的基本单位，而在引入线程的OS中，线程是独立调度的基本单位，进程是拥有资源的基本单位。
  并发性	在引入线程的OS中，不仅进程间可以并发执行，而且同属于一个进程的多个线程之间也可以并发执行。因而使OS具有更好的并发性。
  拥有资源	不论是传统的OS，还是支持多线程的OS，进程都是拥有资源的基本单位，它有权申请系统的各类资源。一般的，线程除了拥有很少的私有资源外，可以共享其所属进程的资源。（即进程的代码段、数据段和系统资源）
  系统开销	由于在创建、撤销进程时系统要为之分配和回收资源；进程各状态间切换时，也需要保护当前进程的执行环境，设置或恢复被调度进程的执行环境；而线程不拥有系统资源，切换时只需保存和设置少量寄存器的内容，因此进程切换的开销远大于线程。此外由于同一进程间的各线程具有相同地址空间，故它们的同步与通信也比较容易。

线程间的同步和通信

• 互斥锁(mutex)
  
• 条件变量
  
  
• 信号量机制
  (1) 私用信号量(private samephore)。
  (2) 公用信号量(public semaphort)。

线程的分类