操作系统——进程、线程、调度

本文为学习笔记，一部分来自于《现代操作系统》荷兰 Andrew S. Tanenbaum著，一部分来自于浙江大学李善平教授主讲的《操作系统》课程，网址：http://www.icourses.cn/coursestatic/course_6801.html

#进程
- 进程：资源分配的最小单位
- 定义：一个进程就是一个正在执行程序的实例；进程是某种类型的活动，它有程序、输入、输出以及状态
- 严格说，某个瞬间，CPU只能运行一个进程，一个程序运行了两次，那么就算运行了两次进程，进程可以拥有多个线程
- 守护进程（daemon）：运行在后台的进程
- 创建进程：
  - UNIX：fork
    - 父进程与子进程拥有相同的存储映像（image）
    - fork系统调用创建一个新（子）进程
    - fork之后，exec系统调用装入一个新程序
    - 父进程与子进程只有pid不一样，其他资源都一样，父进程的pid>0，子进程的pid=0
    - fork后执行父进程还是子进程，取决于内核所使用的调度算法
  - Windows：CreateProcess
- 进程的终止（可以让该进程的所有后辈进程都随之终止，也可以不这样做）：
  - 正常退出（自愿）
    - UNIX：exit
    - Windows：ExitProcess
  - 出错退出（自愿）
  - 严重错误（非自愿）
  - 被其他进程杀死（非自愿）
    - UNIX：kill
    - Windows：TerminateProcess
- 进程的状态：
  - 运行态（此进程实际占用CPU）
  - 就绪态（可运行，但因其他进程正在运行而暂时停止）
  - 阻塞态（除非某种外部事件发生，否则进程不能运行）
  1. 进程为等待而阻塞
  2. 调度程序选择另一个进程
  3. 调度程序选择这个进程
  4. 出现有效输入（外部事件）
- 为了实现进程模型，操作系统维护着一张表格（一个结构数组），即进程表（process table）
- 每个进程占用一个进程表项，该表项包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、帐号和调度信息
- CPU利用率=1－pⁿ
  - 一个进程等待I/O操作的时间与其停留在内存中的时间比为p
  - 内存中同时有n个进程
#线程
- 线程：“轻量级的进程”(lightweight process)
- 为什么多线程？
  - 并行实体共享同一个地址空间和所有可用数据的能力
  - 线程比进程更轻量级，所以它们比进程更容易、更快创建，也更容易撤销
  - 拥有多个线程允许这样活动彼此重叠进行，从而会加快应用程序执行速度
    - Windows 多线程
    - Linux 单线程
- 线程模型：
  - 多个线程共享同一个地址空间和其他资源，比如共享全局变量
  - 进程中的不同线程不像不同进程之间那样存在很大的独立性
  - 严格来说，同一时刻只有一个线程占用CPU，但高速切换给人带来并行运行的假象
  - 线程与进程一样，也具有三种状态，运行态、就绪态、阻塞态，并且转化关系也一样（见上文的图）
  - 每个线程都有其自己的堆栈，其中有一帧，供各个被调用但还没返回的过程中使用，在该帧存放了相应过程的局部变量以及过程调用完成之后使用的返回地址
  - 常见的线程调用：thread_yield，它允许线程自动放弃CPU从而让另一个线程运行，因为不同于进程，线程无法利用时钟中断强制让出CPU
- ###线程和进程的区别：
  - 调度：在引入线程的操作系统中，线程是调度和分配的基本单位，进程是资源拥有的基本单位。把传统进程的两个属性分开，线程便能轻装运行，从而可显著地提高系统的并发程度。在同一进程中，线程的切换不会引起进程的切换；在由一个进程中的线程切换到另一个进程中的线程时，才会引起进程的切换。
  - 并发性 ：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。
  - 拥有资源 ：不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。一般地说，线程自己不拥有系统资源（只有一些必不可少的资源），但它可以访问其隶属进程的资源。
  - 系统开销：由于在创建或撤消进程时，系统都要为之分配或回收资源，因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。进程切换的开销也远大于线程切换的开销。
- 实现线程包：在用户空间中和在内核中
  1. 内核级线程：
    - 线程的创建、撤销和切换等，都需要内核直接实现，即内核了解每一个作为可调度实体的线程。
    1. 这些线程可以在全系统内进行资源的竞争。
    2. 内核空间内为每一个内核支持线程设置了一个线程控制块（PCB），内核根据该控制块，感知线程的存在，并进行控制。
    3. 在一定程度上类似于进程，只是创建、调度的开销要比进程小。有的统计是1：10
    - 内核线程的优点：
      1. 不需要任何新的、非阻塞的系统调用；
      2. 当有多个处理机时，一个进程的多个线程可以同时执行。
    - 内核线程的缺点：
      1. 由内核进行调度，如果线程的操作比较多，就会带来很大的开销。
  2. 用户级线程：
    - 用户级线程仅存在于用户空间。——>对比内核(3)
    1. 内核并不能看到用户线程。——>重要的区别
    2. 内核资源的分配仍然是按照进程进行分配的；各个用户线程只能在进程内进行资源竞争。
    - 用户进程的优点：
      1. 线程的调度不需要内核直接参与，控制简单；具有较好的可扩展性。
    - 内核线程的缺点：
      1. 资源调度按照进程进行，多个处理机下，同一个进程中的线程只能在同一个处理机下分时复用；
      2. 如果有一个线程引起页面故障，由于内核不知道有线程的存在，通常会把整个进程阻塞直到磁盘I/O完成为止，尽管其他线程是可以运行的。
- 多线程设计不是并行设计（而是切换进行）
#进程间通信（线程类似）
- 三个问题：
  - 如何传递消息？
  - 确保多个进程在关键活动时不会交叉
  - 正确的顺序
- 竞争条件（race condition）：两个或多个进程读写某些共享数据，而最后结果取决于进程运行时的精确时序
- 互斥（mutual exclusion）：解决竞争条件的手段，确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作
- 临界区域（critical region）：对共享内存进行访问的程序片段称作临界区域，或临界区（critical section）
- 解决并发的方案，需要满足4个条件：
  1. 空闲让进
  2. 忙则等待
  3. 有限等待
  4. 让权等待（阻塞的进程把CPU让给其他进程）
- 忙等待互斥的5种方法：
  1. 屏蔽中断：进程进入临界区后立即屏蔽所有中断，因为CPU只有在发生中断时才会进行进程切换，所以可以实现互斥。
    - 结论：对于操作系统而言是很用的，但是对于用户进程而言则不是一个合适的方法，因为把屏蔽中断的权力交给用户不明智
  2. 锁变量：软件解决方案，这把锁实际就是个变量，可用0来表示当前进程可以进入临界区，1表示已有进程在临界区中。
    - 最后还是有可能两个进程同时进入临界区
  3. 严格轮换法：
    - 虽然可以实现互斥，但不能让权等待
    - 忙等待（busy waiting）：连续测试一个变量直到某个值出现为止
  4. Peterson解法：忙等待的一种，不能让权等待
  5. TSL指令：需要硬件支持，同属于忙等待，不能让权等待
- 生产者-消费者问题
  - 描述：两个进程共享一个公共的固定大小的缓冲区，其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出消息。
  - 问题1：当缓冲区已满时，生产者还想向其中放入一个新的数据项要怎么办？
    - 解决：让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒它。
  - 问题2：当缓冲区为空时，消费者想从中取出一个数据项怎么办？
    - 解决：让消费者睡眠，待生产者放入数据项后再唤醒它
  - 代码：
```
  #define N 100
  int count = 0;
  void producer(void)
  {
       int item;
       while(TRUE){
            item = produce_item();
            if(count == N)sleep();
            insert_item(item);
            count = count + 1;
            if(count == 1)wakeup(consumer);
       }
  }
  void consumer(void)
  {
       int item;
       while(TRUE){
            if(count == 0)sleep();
            item = remove_item();
            count = count - 1;
            if(count == N-1)wakeup(producer);
            consume_item(item);
       }
  }
```
- 进程间通信（IPC：Interprocess Communication）：提供一套进程通信、进程同步的机制
- 消息系统：进程间相互通信的途径，不需要共享变量的介入
- 信号量（semaphore）：使用一个整型变量来累计唤醒次数，供以后使用，取值可以为0（表示没有保存下来的唤醒操作），或者为正值（表示有一个或多个唤醒操作）
- 互斥量（mutex）：如果不需要信号量的计数能力，可以简化，称作互斥量，它仅仅适用于管理共享资源或一小段代码，因为实现容易且高效，所以在实现用户空间线程包时特别有用
- 互斥量有两种取值，解锁（取0）和加锁（取其他值）
#调度
- 调度程序（scheduler）：当多进程同时竞争CPU时，只要有超过两个的进程处于就绪态，那么单CPU必须选择下一个要运行的进程，完成选择工作的程序称为调度程序（另称CPU调度器）
- CPU分配器（Dispatcher）：调度器决定了将CPU分配给谁，然后分配器将CPU控制权交给该进程，操作内容通常包括：
  - 上下文切换（switching context）：这通常是一种额外开销（overhead），切换时间取决于CPU硬件支持力度
  - 从内核态（kernel mode）转移至用户态（user mode）
- 调度算法（scheduling algorithm）：调度程序所使用的算法
- 进程行为：进程的行为一般分为I/O和计算（CPU），根据占用时间不同，分为I/O密集型（I/O burst）进程和CPU密集型（CPU burst）进程
- 有必要指出：随着CPU变得越来越跨，更多进程倾向于I/O密集型，因为CPU的改进比磁盘快得多
- 何时调度：
  1. 创建一个新进程之后，需要决定是运行父进程还是子进程（调度程序可以合法选择）
  2. 当一个进程退出时必须作出调度决策
  3. 当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时，必须选择另一个进程运行
  4. 在一个I/O中断发生时，必须作出调度决策
- 调度算法分为两类：
  1. 非抢占式（nonpreemptive）调度算法：挑选一个进程让它一直执行直至被阻塞或自动释放CPU（在这种情况下，该进程若交出CPU都是自愿的）
  2. 抢占式（preemptive）调度算法：挑选一个进程让它运行某个固定时间的最大值，结束时会被挂起，调度程序会选择另一个合适的进程来运行（优先级高的先调度），必须要有可用的时钟来发生时钟中断，不然只能用非抢占式调度算法
- 衡量调度程序（调度算法）好坏的几个指标：
  - 吞吐量（throughout）：系统每小时完成的作业数量
  - 周转时间（turnaround time）：从一个批处理作业提交时刻开始直到该作业完成时刻位置的统计平均时间
  - CPU利用率（CPU Utilization）
  - 等待时间
- ###调度算法（批处理、交互式、实时）：
  - 批处理系统：
    - 先来先服务（FCFS：first-come first-served）
      - 容易理解：建立一个队列，选取进程运行时，从队列头部选取，添加进程时，添加到队列的尾部
      - 但是通过例子可以发现，短进程比长进程先执行，平均等待时间会缩短
    - 最短作业优先法（shortest job first）
      - 前提：预知进入就绪队列的进程执行时间
      - 原理：假设有4个进程，其运行时间分别为a，b，c，d，第一个进程在a时刻结束，第二个进程在a+b时刻结束，以此类推，平均周转时间为（4a+3b+2c+d）/4，可以看到a对平均值的影响最大，所以a应该取最小值才好，这样平均周转时间才能取到最小值
      - 抢占式SJF算法：当一个进程进入就绪队列，如果它的CPU时间小于当前拥有CPU的进程的剩余“预估”时间，前者抢占后者的CPU，称为 Shortest-Remaining-Time-First(SRTF)，不能实现
      - SJF算法是最优的算法
      - SJF有致命缺陷，如何预估进入就绪队列的进程的执行时间？
        
        不可能准确地预测，比如需要用户输入，这是不可知的
        
        只能根据过去的CPU burst cycle来预测
      - HRN（Highest response Ratio Next）
        
        HRN = （W + T）/ T
        
        W为等待时间，T代表预估CPU时间
  - 交互式系统：
    - 轮转调度（Round Robin，RR）
      - 时间片（quantum）：每个进程被分配一个时间段，即允许该进程在该时间段中运行，如果在时间片结束时该进程还在运行，则将剥夺CPU给下一个进程，如果该进程在时间片结束前阻塞或结束，则CPU立即切换
      - 假设n个就绪进程，时间片q，每个就绪进程得到1/n的CPU时间，任何就绪进程最多等待(n-1)q单位时间
      - 平均周转时间通常优于SJF
      - 响应时间一定优于SJF
      - 性能分析：
        
        q如果很大，则FIFO
        
        q如果很小，则进程切换，或称上下文切换（context switch）开销太大，所谓上下文切换是：从一个进程切换到另一个进程是需要一定的时间的，所以q必须远远大于上下文切换时间
      - 结论：时间片设得太短会导致过多的进程切换，降低了CPU的效率；而设得太长有可能引起对短的交互请求的响应时间变长，通常将时间片设为20ms~50ms是合理的这种
    - 优先级调度（Priority Schedule）
      - 每个进程都有一个优先数（priority number），通常是整数
      - Scheduler每次会选取就绪队列中，优先级最高的进程执行
      - 当优先级定义为“进程需要的CPU时间”时，SJF算法就是优先级调度
      - 优先级可由系统动态确定，例如：有些进程为I/O密集型，其多数时间在等待I/O操作，当这样的进程需要CPU时，应尽快地给它CPU，已便它能很快地执行完CPU操作然后去等待I/O操作，下一个进程就可以同时进入CPU。如何实现这样的效果呢？一个简单算法：其优先级设为1/f，f为该进程在上一个时间片所占的部分。
      - 进程饥饿（Starvation）：优先级较低的进程可能永远得不到CPU
      - 解决：Aging思想，优先级要考虑就绪进程在就绪队列里的等待时间，因此，若一个进程在就绪队列中等待，那它的优先级会单调递增
    - 多级队列（Multilevel Queue）
      - 把就绪队列拆分成几个队列
      - 每个队列有其自己的调度算法，比如前台就绪队列需交互性，采用轮转法，后台就绪队列需批处理，采用先来先服务法
      - CPU怎么在队列间分配？
        
        固定优先权法，例如，先前台队列，再后台队列
        
        时间片办法，例如，80%的CPU时间给前台队列，20%的CPU时间给后台进程
    - 多级反馈队列（Multilevel Feedback Queue）
      - 基于多级队列，但另外考虑了进程在就绪队列之间可以迁移
      - 定义这样的算法应该着重考虑：
        
        队列个数
        
        每级队列的调度算法
        
        如何将就绪进程升级至高层次队列
        
        如何将就绪进程降低至低层次队列
        
        当一个就绪进程进入就绪队列时，应该去哪一级？
  - 实时调度
    - 硬实时（hard real time）调度：调度机制确保一个关键任务能在指定时间前完成
    - 软实时（soft real time）调度：调度机制尽量给予关键任务最高优先级，尽量在指定时间前完成
- 调度算法目标：1）公平；2）保持系统素有部分尽可能忙碌；
  - 批处理：1）吞吐量；2）周转时间；3）CPU利用率。
  - 交互式：1）最小响应时间；2）均衡性。
  - 实时：1）满足截止时间；2）可预测性。
- 调度算法评估：
  - 确定模型法（Deterministic modeling）：采用事先设定的特定负荷，计算在给定负荷下每个算法的性能
  - 排队模型（Queueing models）
  - 编程实现该算法，观察其执行情况
  - 仿真

本文落笔于 2018-09-08