操作系统基础

Posted on

进程

进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。

定义

  • 狭义定义：
    进程是正在运行的程序的实例。
  • 广义定义：
    进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。

进程创建与终止

  • 创建：
  1. 为新进程分配一个唯一的进程标识号，并申请一个空白的PCB(进程控制块，PCB是有限的)。若PCB申请失败则创建失败。
  2. 为进程分配资源，为新进程的程序和数据、以及用户栈分配必要的内存空间（在PCB 中体现）。注意：这里如果资源不足（比如内存空间），并不是创建失败，而是处于“等待状态”，或称为“阻塞状态”，等待的是内存这个资源。
  3. 初始化PCB,主要包括初始化标志信息、初始化处理机状态信息和初始化处理机控制信息，以及设置进程的优先级等。
  4. 如果进程就绪队列能够接纳新进程，就将新进程插入到就绪队列，等待被调度运行。
  • 终止：
  1. 根据被终止进程的标识符，检索PCB，从中读出该进程的状态。
  2. 若被终止进程处于执行状态，立即终止该进程的执行，将处理机资源分配给其他进程。
  3. 若该进程还有子进程，则应将其所有子进程终止。
  4. 将该进程所拥有的全部资源，或归还给其父进程或归还给操作系统。
  5. 将该PCB从所在队列（链表）中删除。
  • 进程派生：
    当操作系统为一个进程（父进程）的显式请求创建一个新的进程（子进程）时，这个动作叫做进程派生。

进程状态

  • 三状态模型
  1. 就绪(Ready)状态：指进程已处于准备好运行的状态，及进程已经分配到需要的系统资源，只要再获得CPU就可以执行；
  2. 执行(Running)状态：指进程获得了CPU正在执行，在单处理机系统中，最多只有一个进程处于该状态；
  3. 阻塞(Block)状态：指正在执行的进程，必须等待某事件发生才能继续执行（如：I/O请求、申请缓冲区失败等）。
    三状态模型
  • 五状态模型
  1. 新建(New)状态：初步创建进程，还未加入可执行进程组；
  2. 就绪(Ready)状态：表示该进程已经准备好占有CPU：
  3. 执行(Running)状态：表示该进程占有CPU；
  4. 阻塞(Block)状态：表示进程因为某一种原因而暂时不能占有CPU（等待事件执行）；
  5. 终止(Terminate)状态：表示进程已经执行结束。
    五状态

进程的阻塞和唤醒

  • 阻塞执行
  1. 找到将要被阻塞进程的标识号对应的PCB；
  2. 若该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行；
  3. 把该PCB插入到相应事件的等待队列中去；
  • 唤醒执行
  1. 在该事件的等待队列中找到相应进程的PCB；
  2. 将其从等待队列中移出，并置其状态为就绪状态；
  3. 把该PCB插入就绪队列中，等待调度程序调度。

进程切换

进程切换是指处理机从一个进程的运行转到另一个进程上运行，这个过程中，进程的运行环境产生了实质性的变化：

  1. 保存处理机上下文，包括程序计数器和其他寄存器；
  2. 更新PCB信息；
  3. 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列；
  4. 选择另一个进程执行，并更新其PCB；
  5. 更新内存管理的数据结构；
  6. 恢复处理机上下文。

进程切换与处理机模式切换是不同的，模式切换时，处理机逻辑上可能还在同一进程中运行。如果进程因中断或异常进入到核心态运行，执行完后又回到用户态刚被中断的程序运行，则操作系统只需恢复进程进入内核时所保存的CPU现场，无需改变当前进程的环境信息。但若要切换进程，当前运行进程改变了，则当前进程的环境信息也需要改变。

线程

线程（Thread）是程序执行流的最小单元，。

进程与线程的关系

  1. 线程是进程中的一个实体，是被系统（CPU）独立调度和分派的基本单位，没有单独地址空间，有独立的栈，局部变量，寄存器，程序计数器等。而进程则是资源的分配和调度的一个独立单元；
  2. 线程自己不拥有系统资源，只拥有一点儿在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源；
  3. 一个进程至少拥有一个线程；
  4. 进程结束后它拥有的所有线程都将销毁，而线程的结束不会影响同个进程中的其他线程的结束；
  5. 由于线程很“轻”，故线程的切换非常迅速且开销小（在同一进程中的）；
  6. 一个线程可以创建和撤消另一个线程，同一进程中的多个线程之间可以并发执行；
  7. 由于线程之间的相互制约，致使线程在运行中呈现出间断性；
  8. 线程也有就绪、阻塞和运行三种基本状态；
  9. 一个进程中一次有且只有一个用户级线程可被执行，一旦发生阻塞，整个进程也将被阻塞。

线程状态

  1. 派生：典型情况下，在派生一个新的进程时，同时也会为该进程派生一个线程。随后，进程中的线程可在同一进程中派生另一个线程，并为新线程提供指令指针和参数；新线程拥有自己的寄存器上下文和栈空间，并放在就绪队列中；
  2. 阻塞：类似进程阻塞性；
  3. 接触阻塞：线程结束阻塞后被转移到就绪队列中等待执行；
  4. 结束：线程结束并释放寄存器上下文和栈。
    线程状态

线程分类

线程分为两大类：用户级线程（User-Level Thread, ULT）和内核级线程（Kernel-Level Thread, KLT）。

  • 用户级线程
    用户级线程指不需要内核支持而在用户程序中实现的线程，其不依赖于操作系统核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。不需要用户态/核心态切换，速度快，操作系统内核不知道多线程的存在，因此一个线程阻塞将使得整个进程（包括它的所有线程）阻塞。由于这里的处理器时间片分配是以进程为基本单位，所以每个线程执行的时间相对减少。
  • 内核级线程
    内核线程由操作系统内核创建和撤销。内核维护进程及线程的上下文信息以及线程切换。一个内核线程由于I/O操作而阻塞，不会影响其它线程的运行。Windows NT和2000/XP支持内核线程。

多线程

即便处理器只能运行一个线程，操作系统也可以通过快速的在不同线程之间进行切换，由于时间间隔很小，来给用户造成一种多个线程同时运行的假象。这样的程序运行机制被称为软件多线程。

管程

管程的概念

  1. 管程可以看做一个软件模块，它是将共享的变量和对于这些共享变量的操作封装起来，形成一个具有一定接口的功能模块，进程可以调用管程来实现进程级别的并发控制;
  2. 进程只能互斥地使用管程，即当一个进程使用管程时，另一个进程必须等待。当一个进程使用完管程后，它必须释放管程并唤醒等待管程的某一个进程;
  3. 在管程入口处的等待队列称为入口等待队列，由于进程会执行唤醒操作，因此可能有多个等待使用管程的队列，这样的队列称为紧急队列，它的优先级高于等待队列。

死锁

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

死锁产生的条件

  1. 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放；
  2. 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放；
  3. 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放；
  4. 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

死锁预防

只要打破四个必要条件之一就能有效预防死锁的发生：

  • 有序资源分配法
    这种算法资源按某种规则系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），申请时必须以上升的次序。系统要求申请进程：
  1. 对它所必须使用的而且属于同一类的所有资源，必须一次申请完；
  2. 在申请不同类资源时，必须按各类设备的编号依次申请。例如：进程PA，使用资源的顺序是R1，R2； 进程PB，使用资源的顺序是R2，R1；若采用动态分配有可能形成环路条件，造成死锁。

    采用有序资源分配法：R1的编号为1，R2的编号为2；
    PA：申请次序应是：R1，R2
    PB：申请次序应是：R1，R2
    这样就破坏了环路条件，避免了死锁的发生

  • 银行家算法
    在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
    为保证资金的安全，银行家规定：
  1. 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；
  2. 顾客可以分期贷款，但贷款的总数不能超过最大需求量；
  3. 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；
  4. 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.
    操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。

死锁避免

  1. 若一个进程的请求会导致死锁，则不启动该进程；
  2. 若一个进程增加的资源请求会导致死锁，则不允许这一资源分配。

死锁检测

  1. 针对每种资源类型只有一个实例的情况:
    该算法使用资源分配图的一个变种，称为等待图。从资源分配图中，删除所有资源类型的节点，合并合适边，就可以得到等待图。
    合并的过程如下：如果pi指向资源rj，而rj右指向pk，那么删除节点rj之后，直接得到pi->pk这样的结果。当前仅当等待图中有一个环，系统中存在死锁。检测环的算法复杂度为o（n^2）。
  2. 每种资源类型还有多个实例的情况:
    这种算法和银行家算法是类似的。不同的是：
    如果对某个i，finish[i]=false，那么说明系统处于死锁状态，且进程i死锁，时间复杂度为o（m*n^2）。

死锁恢复

打破死锁有两种方法：

  1. 简单地终止一个或多个进程以打破循环等待。——进程终止
  2. 从一个或多个死锁进程那里抢占一个或多个资源。——资源抢占

进程终止有以下两中方法：

  1. 终止所有死锁进程；
  2. 一次只终止一个进程直到取消死锁循环为止。

如果选择资源抢占，那么将必须考虑三个问题：

  1. 选择一个牺牲品；
  2. 回滚；
  3. 饥饿（在代价因素中加上回滚次数，回滚的越多则越不可能继续被作为牺牲品）。

参考

《Operating Systems-Internals & Design Principles》 Eighth Edition