Operating Systems

This is my personal notes for Operating Systems.

线程和进程

参考博客

• (1) 简介

  • 进程(process)

    进程是资源分配的基本单位。

    进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。

    

    注: Waiting 也常写为 Blocked

  • 线程(thread)

    线程是独立调度的基本单位。

    一个进程中可以有多个线程，它们共享进程资源。

    QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件。

  • 区别

    Ⅰ 拥有资源

    进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

    Ⅱ 调度

    线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

    Ⅲ 系统开销

    由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

    Ⅳ 通信方面

    线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

• (2) 多线程并发

  由于多个线程是共同占有所属进程的资源和地址空间的，那么就会存在一个问题：如果多个线程要同时访问某个资源，怎么处理？ 这个问题就是并发安全性问题。

  此外，可能有朋友会问，现在很多时候都采用多线程编程，那么是不是多线程的性能一定就由于单线程呢？答案是不一定，要看具体的任务以及计算机的配置。比如说：对于单核CPU，如果是 CPU密集型任务，如解压文件，多线程的性能反而不如单线程性能，因为解压文件需要一直占用 CPU资源，如果采用多线程，线程切换导致的开销反而会让性能下降。但是对于比如交互类型的任务，肯定是需要使用多线程的。而对于多核CPU，对于解压文件来说，多线程肯定优于单线程，因为多个线程能够更加充分利用每个核的资源。

  虽然多线程能够提升程序性能，但是相对于单线程来说，它的编程要复杂地多，要考虑线程安全问题。因此，在实际编程过程中，要根据实际情况具体选择。

  并发(一个时刻只有一个线程执行, 但是是交替的)
  

  并行(一个时刻有多个线程同时执行)
  

• (3) 并发历史

  早期的计算机不包含操作系统，它们从头到尾只执行一个程序，并且这个程序能够访问计算机中的所有资源。这对于昂贵且稀有的计算机资源来说是一种浪费；

  操作系统的出现使得计算机能同时运行多个程序，不同的程序都在单独的进程中运行，并且操作系统为各个独立执行的进程分配资源( eg: 通过粗粒度时间分片使程序共享资源，如 CPU 等 )。这无疑提高了计算机资源的利用率；

  在早期的分时系统中，每个进程的执行都是串行的。串行编程模型的优势在于其简单性和直观性，因为它每次只做一件事情，做完之后再做另一件。这种串行编程模型仍然存在着计算机资源利用率不高的问题；

  促使进程出现的因素同样也促使着线程的出现。线程允许在同一个进程中同时存在多个程序控制流。线程会共享进程范围内的资源，但每个线程都有各自的 程序计数器 、 栈 以及 局部变量 等等；

  线程也被成为轻量级进程。在大多数现代操作系统中，都是以线程为基本的调度单位，而不是进程。如果没有明确的协同机制，那么线程将彼此独立执行。由于同一个进程的所有线程都将共享进程的内存地址空间，因此这些线程都能访问相同的变量，这就需要实现一种比进程间共享数据粒度更细的数据共享机制。如果没有明确的同步机制来协同对共享数据的访问，将造成不可预测的结果。

多线程, 多进程, 协程

• 多进程：密集CPU任务，需要充分使用多核CPU资源（服务器，大量的并行计算）的时候，用多进程。 缺陷: 多个进程之间通信成本高，切换开销大。

• 多线程：密集I/O任务（网络I/O，磁盘I/O，数据库I/O）使用多线程合适。缺陷：同一个时间切片只能运行一个线程，不能做到高并行，但是可以做到高并发。

• 协程：又称微线程，在单线程上执行多个任务，用函数切换，开销极小。不通过操作系统调度，没有进程、线程的切换开销。

进程有哪几种状态？

• 就绪状态(Ready)：进程已获得除处理机以外的所需资源，等待分配处理机(Scheduler)资源；

• 运行状态(Running)：占用处理机资源运行，处于此状态的进程数小于等于CPU数；

• 阻塞状态(Blocked)： 进程等待某种条件，在条件满足之前无法执行；

  Note: 还可能有PREEMPT(Block的一种)

  

孤儿进程与僵尸进程

• 孤儿进程

  一个父进程退出，而它的一个或多个子进程还在运行，那么这些子进程将成为孤儿进程。

  孤儿进程将被 init 进程（进程号为 1）所收养，并由 init 进程对它们完成状态收集工作。

  由于孤儿进程会被 init 进程收养，所以孤儿进程不会对系统造成危害。

• 僵尸进程

  一个子进程的进程描述符(PCB)在子进程退出时不会释放，只有当父进程通过 wait() 或 waitpid() 获取了子进程信息后才会释放。如果子进程退出，而父进程并没有调用 wait() 或 waitpid()，那么子进程的进程描述符仍然保存在系统中，这种进程称之为僵尸进程。

  僵尸进程通过 ps 命令显示出来的状态为 Z（zombie）。

  系统所能使用的进程号是有限的，如果产生大量僵尸进程，将因为没有可用的进程号而导致系统不能产生新的进程。

  要消灭系统中大量的僵尸进程，只需要将其父进程杀死，此时僵尸进程就会变成孤儿进程，从而被 init 进程所收养，这样 init 进程就会释放所有的僵尸进程所占有的资源，从而结束僵尸进程。

进程间的通信的几种方式

• 简介

  进程同步与进程通信很容易混淆，它们的区别在于：

  进程同步：控制多个进程按一定顺序执行；
  进程通信：进程间传输信息。

  进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

• 管道（pipe）
  管道是通过调用 pipe 函数创建的，fd[0] 用于读，fd[1] 用于写。

    #include <unistd.h>
    int pipe(int fd[2]);
  

  

• 命名管道（named pipe/FIFO)

      #include <sys/stat.h>
      int mkfifo(const char *path, mode_t mode);
      int mkfifoat(int fd, const char *path, mode_t mode);
  

  FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。
  

• 信号量（semaphore)
  它是一个计数器，用于为多个进程提供对共享数据对象的访问。

• 消息队列

  消息队列是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；

  相比于 FIFO，消息队列具有以下优点：

  • 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
  • 避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；
  • 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。

  消息队列相当于一个中间书架, 写进程可以自由地向书架上放书而不用和读进程同步，而读进程也可以在合适的时间有选择的读取书籍。

• 共享内存
  可以说这是最有用最及时的进程间通信方式。它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等；

• 套接字 (socket) 与其它通信机制不同的是，它可用于不同机器间的进程通信。

线程间的通信的几种方式

线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

• 锁机制：包括互斥锁、条件变量、读写锁
  • 互斥锁提供了以排他方式防止数据结构被并发修改的方法。
  • 读写锁允许多个线程同时读共享数据，而对写操作是互斥的。
  • 条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
• 信号量机制(Semaphore)：包括无名线程信号量和命名线程信号量
  • 它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
• 信号机制(Signal)：类似进程间的信号处理
  • Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作

信号量(semaphore)

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。

• down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
• up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。 down 和 up 操作需要被设计成atomic，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。

如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

    typedef int semaphore;
    semaphore mutex = 1;
    void P1() {
        // 加锁
        down(&mutex);
        // 进入临界区
        // 解锁
        up(&mutex);
    }

    void P2() {
        // 加锁
        down(&mutex);
        // 进入临界区
        // 解锁
        up(&mutex);
    }

• 生产者消费者问题

  问题描述：
  使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

  因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

  为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

  注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

    #define N 100
    typedef int semaphore;
    semaphore mutex = 1;
    semaphore empty = N;
    semaphore full = 0;
  
    void producer() {
        while(TRUE) {
            int item = produce_item();
            down(&empty); // 要先down(empty)再加锁, 否则加锁后发现empty为0进入睡眠了, consumer也不能进来
            down(&mutex);
            insert_item(item);
            up(&mutex);
            up(&full);
        }
    }
  
    void consumer() {
        while(TRUE) {
            down(&full);  // 要先down(fill)再加锁, 否则加锁后发现full为0进入睡眠了, producer也不能进来
            down(&mutex);
            int item = remove_item();
            consume_item(item);
            up(&mutex);
            up(&empty);
        }
    }
  

  P(), V() (即down(),up())的实现方式如下
  value 如果小于0，说明有对应数量的process在queue中等待
  value 如果大于0, 说明没有等待的process, 可用的token为value的数量
  V()操作之后value仍然<=0, 则需要wake up process

  
  class Semaphore
  {
    int value;  /* counter */
    List queue; /* list of processes sleeping in this semaphore */
    void P();   /* down(), wait() */
    void V();   /* up(), signal () */
  }
  
  
  void P() // or wait() or down()
  {
      value = value – 1; 
      if (value < 0)
      {
          add the calling process to this semaphore’s list;
          sleep(); 
      }
  }
  
  void V() // or signal() or up() 
  {
      value = value + 1;
      if (value <= 0)
      {
        remove a process from this semaphore’s list;
        wake up the sleeping process;
      } 
  }
  
  

线程有哪几种状态？

在 Java虚拟机 中，线程从最初的创建到最终的消亡，要经历若干个状态：创建(new)、就绪(runnable/start)、运行(running)、阻塞(blocked)、等待(waiting)、时间等待(time waiting) 和 消亡(dead/terminated)。在给定的时间点上，一个线程只能处于一种状态，各状态的含义如下图所示：

什么是死锁？死锁产生的条件？

• 1 死锁的概念

  在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲，就是两个或多个进程无限期的阻塞、相互等待的一种状态。

• 2 死锁产生的四个必要条件

  互斥：至少有一个资源必须属于非共享模式，即一次只能被一个进程使用；若其他申请使用该资源，那么申请进程必须等到该资源被释放为止；

  占有并等待：一个进程必须占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有；

  非抢占：进程不能被抢占，即资源只能被进程在完成任务后自愿释放

  循环等待：若干进程之间形成一种头尾相接的环形等待资源关系

• 3 死锁的处理基本策略和常用方法

  解决死锁的基本方法主要有 预防死锁、避免死锁、检测死锁、解除死锁、鸵鸟策略 等。

  • (1) 死锁预防

    死锁预防的基本思想是 只要确保死锁发生的四个必要条件中至少有一个不成立，就能预防死锁的发生，具体方法包括：

    打破互斥条件: 允许进程同时访问某些资源。但是，有些资源是不能被多个进程所共享的，这是由资源本身属性所决定的，因此，这种办法通常并无实用价值。

    打破占有并等待条件：所有进程在开始执行前请求所需要的全部资源, 或者只允许进程在没有占用资源时才可以申请资源。但是这种策略也存在一些缺点：在很多情况下，无法预知一个进程执行前所需的全部资源，因为进程是动态执行的，不可预知的；同时，会降低资源利用率，导致降低了进程的并发性。

    打破非抢占条件：允许进程强行从占有者那里夺取某些资源。也就是说，如果一个进程占有了一部分资源，在其申请新的资源且得不到满足时，它必须释放所有占有的资源以便让其它线程使用。这种预防死锁的方式实现起来困难，会降低系统性能。

    打破循环等待条件：实行资源有序分配策略。对所有资源排序编号，所有进程对资源的请求必须严格按资源序号递增的顺序提出，即只有占用了小号资源才能申请大号资源，这样就不会产生环路，预防死锁的发生。

  • (2) 死锁避免

    • 安全状态
      定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

      

    • 银行家算法
      如果当前资源能满足某个进程, 将资源分配给它, 然后进程终止, 资源释放(变多), 再给下一个, 直到所有进程终止, 说明此状态为安全状态。
      如果一个状态不是安全的，需要拒绝进入这个状态。

  • (3) 死锁检测

    死锁检测主要是检测有向图中的环, 可用方法有dfs(搜到遍历过的节点即存在环), 拓扑排序(从入度为0的节点开始删除, 如果最后剩下还有节点, 则存在环)

  • (4) 死锁解除

    死锁解除的常用多种方法: 资源抢占, 进程终止, 回滚 所谓进程终止是指简单地终止一个或多个进程以打破循环等待，包括两种方式：终止所有死锁进程和一次只终止一个进程直到取消死锁循环为止；
    所谓资源抢占是指从一个或多个死锁进程那里抢占一个或多个资源;
    回滚是指回滚到安全状态;

  • (5) 鸵鸟策略

    把头埋在沙子里，假装根本没发生问题。

    因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

    当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

    大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

内存管理中的page和segment的区别

• segment

  段式存储管理是一种符合用户视角的内存分配管理方案。在段式存储管理中，将程序的地址空间划分为若干段（segment），如代码段，数据段，堆栈段；这样每个进程有一个二维地址空间，相互独立，互不干扰。段式管理的优点是：没有内碎片（因为段大小可变，改变段大小来消除内碎片）。但段换入换出时，会产生外碎片（比如4k的段换5k的段，会产生1k的外碎片）

• page

  页式存储管理方案是一种用户视角内存与物理内存相分离的内存分配管理方案。在页式存储管理中，将程序的逻辑地址划分为固定大小的页（page），而物理内存划分为同样大小的帧，程序加载时，可以将任意一页放入内存中任意一个帧，这些帧不必连续，从而实现了离散分离。页式存储管理的优点是：没有外碎片（因为页的大小固定），但会产生内碎片（一个页可能填充不满）。

• 不同点

  (1) 目的不同：分page是由于系统管理的需要而不是用户的需要，它是信息的物理单位；分segment的目的是为了能更好地满足用户的需要，它是信息的逻辑单位，它含有一组其意义相对完整的信息；

  (2) 大小不同：page的大小固定且由系统决定，而segment的长度却不固定，由其所完成的功能决定；

  (3) 地址空间不同：segment向用户提供二维地址空间；page向用户提供的是一维地址空间；

  (4) 信息共享：segment是信息的逻辑单位，便于存储保护和信息的共享，page的保护和共享受到限制；

  (5) 内存碎片：page式存储管理的优点是没有外碎片（因为page的大小固定），但会产生内碎片（一个page可能填充不满）；而segment式管理的优点是没有内碎片（因为segment大小可变，改变段大小来消除内碎片）。但segment换入换出时，会产生外碎片（比如4k的segment插入5k的内存片段，会产生1k的外碎片）。

操作系统中进程调度策略有哪几种？

• FCFS
  first come, first served

• LCFS
  last come, first served

• SRTF
  根据process的remainTime, 先执行remainTime最小的process

• RR (RoundRobin)
  在FCFS的基础上加上quantum参数, process的每次的CPU执行时间不超过quantum, 超过则转PREEMPT状态

• PRIO (PriorityScheduler)
  设置一个activeQ, 一个expiredQ, queue的每一层都是RoundRobin(实际中每层的quantum递增1,2,4,8), process每被PREEMPT一次, prio减1, 当prio变为-1时, 将process的prio重置为static prio
  放入时, 放到dynamic prio对应的队列中, 如果prio变为-1, 加入expiredQ;
  取出时, 从activeQ中取dynamic prio最高的process, 如果activeQ空了, 交换expiredQ和activeQ

• PREemptive PRIO (PREPRIO)
  和PRIO相同, 不同的是prio高的process可以有PREEMPT当前正在运行的process

虚拟内存(virtual memory)和paging

• 虚拟内存:
  virtual memory对应于main memory (physical memory), 是secondary memory中的一部分, 用来存储process.

  process通过pageTable把每个page和main memory中的frame对应起来, 即logic adress (page number + instruction offset) -> phsical adress (frame number + instruction offset)

  需要操作某个page时, 将logic adress中的page number取出来，通过pageTable转换为frame number, 加上instruction offset, 得到physical adress.

  如果某个page不在frame中, 即触发page Fault。如果frame已满, 则需要进行page replacement.

  

• 页面置换算法(page replacement)

  • FIFO:
    从main memory中从上到下依次选取frame进行置换, 每个frame机会均等

  • Random:
    随机选取

  • Clock:
    每次需要置换时, 选取第一个reference bit为0的frame, 并将遍历过的frame的reference bit置为0，表示从下一周期重新计算

  • NRU(Not recently used):
    frames被划分成4个等级, 应该选取等级最低的:
    3 referenced, modified
    2 referenced, not modified
    1 not referenced, modified
    0 not referenced, not modified
    遍历main memory, 随机选取等级最低的集合中的1个
    同时, 操作系统会在固定的时间间隔后清空所有的(frame中page的)referenced bit, 从下一周期开始重新计算

  • Aging:
    给每个frame赋予一个age, 每次置换时更新所有frame的age, reference 0/1加到最左边一位, 并选取age最小的frame换出去
    同时清空所有的referenced bit, 从下一周期开始重新计算
    if a page has referenced bits 1,0,0,1,1,0 in the past 6 clock ticks, its referenced counter will look like this: 10000000, 01000000, 00100000, 10010000, 11001000, 01100100.

  • WorkingSet:
    找到reference bit 为0, 且上一次被map的时间(tau)距离当前时间>delta的frame, 如果没有大于delta的, 选择tau最小(时间最早)frame, 扫描过程中重置ref=1为0并更新tau为当前时间。

• 虚拟内存的应用与优点

  虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时，可以把CPU交给另一个进程使用。虚拟内存的使用可以带来以下好处：

  • 1 在内存中可以保留多个进程，系统并发度提高

  • 2 解除了用户与内存之间的紧密约束，进程可以比内存的全部空间还大

颠簸

颠簸本质上是指频繁的页调度行为，具体来讲，进程发生page fault，这时，必须置换某一页。然而，其他所有的页都在使用，它置换一个页，但又立刻再次需要这个页。因此，会不断产生缺页中断，导致整个系统的效率急剧下降，这种现象称为颠簸（抖动）。

内存颠簸的解决策略包括：

• 1 如果是因为页面替换策略失误，可以修改替换算法来解决这个问题；

• 2 如果是因为运行的程序太多，造成程序无法同时将所有频繁访问的页面调入内存，则要降低多道程序的数量；

• 否则，还剩下两个办法：终止该进程或增加物理内存容量。

磁盘调度算法

• (1) FCFS (FIFO)
  从 IO_queue 的头部取

• (2) Shortest Seek Time First (SSTF)
  选和head最近的IO track

• (3) LOOK (Scan go to the end)
  选和head同方向最近的, 如果没有则掉头

• (4) CLOOK (C-Scan go to the end)
  选和head同方向最近的, 如果没有则回到track最低的IO

• (5) FLOOK
  选和head同方向最近的, 如果没有则掉头
  特别的: 拿IO是active_queue中拿的, 任何进来的IO都先被放进IO_queue中, active_queue空了才交换他们

User-level/Kernel-level threads

• Kernel-level Threads

  1:1, 1 user thread == 1 kernel thread

  advantages:

  • (1) kernel 可以主动schedule不同的线程到不同的processor
  • (2) 如果一个线程block了, kernel可以schedule另外一个线程

  disadvantages:

  • (1) 线程的切换需要转到kernel mode

• User-level Threads

  m:1, m user thread == 1 kernel thread

  advantages:

  • (1) 线程切换不需要转到kernel mode
  • (2) 可以在任何操作系统上运行

  disadvantages:

  • (1) 一个线程的 sys call可以bloack整个进程
  • (2) Page fault 可以block整个进程

User mode and Kernel mode

Kernel mode: 可以运行任何CPU指令, 能直接访问硬件, 能访问用户存储空间+系统存储空间, 崩溃是灾难性的

User mode: 只能通过system APIs去访问硬件和系统内存, 不能直接进行访问，其对内存的访问范围也局限于用户空间, 崩溃可以恢复

用户态切换到内核态的途径——>陷入(trap, syscall)/中断(打印机完成打印)/异常(Page fault)

内核态切换到用户态的途径——>设置程序状态字