操作系统

基本特征

• 共享-互斥共享和同时共享
• 并发与并行
• 虚拟-时（时间）分复用技术和空（空间）分复用技术
• 异步

  基本功能

  进程管理

  进程与线程

• 进程是资源分配的基本单位。进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。
• 线程是独立调度的基本单位。
• 区别：
  1. 线程不占有资源
  2. 同一进程中的线程切换不会导致进程切换
  3. 线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。
  4. 由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

     切换

     
     就绪态，运行态，阻塞态

     进程调度算法

     批处理系统

     批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1. 先来先服务 first-come first-serverd（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

2. 先来先服务 first-come first-serverd（FCFS）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

3. 先来先服务 first-come first-serverd（FCFS）

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

交互式系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1. 时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。时间片轮转算法的效率和时间片的大小有很大关系。

2. 优先度调度

为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

3. 多级反馈队列

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同。进程在第一个队列没执行完，就会被移到下一个队列。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以看成是时间片轮转调度算法和优先级调度算法的结合。

实时系统

实时系统要求一个请求在一个确定时间内得到响应。分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

同步互斥

• 对临界资源进行访问的那段代码称为临界区。

• 管程

• 同步互斥

  进程通信

  管道

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

  unistd.h 
  int pipe(int fd[2]);

• 半双工通信。

• 只能在父子进程和兄弟进程中使用。

  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 用作汇聚点，在客户进程和服务器进程之间传递数据。

消息队列

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

  信号量

  共享存储

  套接字

  共享存储

  死锁

  必要条件

  资源互斥 占有和等待 不可抢占 死循环

  处理方法

  鸵鸟策略

  死锁检测

  不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

1. 每种类型一个资源的死锁检测

从一个节点开始深度优先遍历，查找是否存在有向环。

2. 每种类型多个资源的死锁检测
   
   上图中，有三个进程四个资源，每个数据代表的含义如下：

• E 向量：资源总量
• A 向量：资源剩余量
• C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
• R 矩阵：每个进程请求的资源数量

递归，直到所有进程均被访问，若存在未被访问进程，则产生死锁。

死锁恢复

• 利用抢占恢复
• 利用回滚恢复
• 通过杀死进程恢复

  死锁预防

  破坏4个必要条件

1. 要求进程一次性的请求所有需要的资源，并且阻塞这个进程直到所有请求都同时满足。
2. 要求进程一次性的请求所有需要的资源，并且阻塞这个进程直到所有请求都同时满足。
3. 资源编号，顺序请求。

   死锁避免

• 进程启动拒绝：如果一个进程的请求会导致死锁，则不启动该进程
• 资源分配拒绝：如果一个进程增加的资源请求会导致死锁，则不允许此分配 银行家算法

安全状态

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

  银行家算法

• 单个资源的银行家算法
• 多资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。
算法：
按照分配矩阵进行分配，寻找小于等于可用资源的行，如果不存在则状态不安全。存在则释放该行继续迭代。
状态不安全。

内存管理

虚拟内存

虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存.

• 内存碎片 内外碎片

内存分配策略

1. 首次适配

• 第一个合适的块。

2. 最佳适配

• 遍历全部空间，差值最小。

3. 最差适配

• 差值最大。

  碎片整理

1. 压缩式
2. 交换式

   虚拟内存

分页系统映射

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

• 虚拟地址=页号+偏移量
  
  页表项最后一位表示是否存在于内存中，1 表示存在.0不存在,则需要进行页面替换.

  页面置换算法

1. 全局置换算法

• 工作集 一个进程当前正在使用的逻辑页面集合。
• 常驻集 指在当前时刻，进程实际驻留在内存当中的页面集合；工作集是进程在运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法；
• 当进程常驻集的大小达到某个数目后，再给它分配更多的物理页面，缺页率也不会明显下降

缺页率页面置换算法

• 常驻集大小可变。例如，每个进程在刚开始运行的时候，先根据程序的大小给它分配一定数目的物理页面，然后在运行过程中，再动态的调整常驻集的大小。
• 可采用全局页面置换的方式，当发生一个缺页中断时，被置换的页面可以是在其他进程当中，各个并发进程竞争地使用物理页面。
• 缺页率表示“缺页次数/内存访问次数”（比率）或“缺页的平均时间间隔的倒数”

抖动问题：

如果分配给一个进程的物理页面很少，不能包含整个的工作集，那常驻集含于工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存到外存之间替换页面，从而使进程的运行速度变得很慢，我们把这种状态称为“抖动”。

原因: 如果分配给一个进程的物理页面很少，不能包含整个的工作集，那常驻集含于工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存到外存之间替换页面，从而使进程的运行速度变得很慢，我们把这种状态称为“抖动”。

2. 局部置换算法

   OPT Optimal replacement algorithm

   选择被在此访问时间最长的那一页。是一种理想算法，实际无法实现。
   

   FIFO First in First out

   FIFO 会产生Belady异常（当所分配的物理块数增大而页故障数不减反增的异常现象）
3. 改进的FIFO算法 第二次机会算法

根据FIFO维护一只链表，尾插法，设置标志位R,页面被使用时，R=0。从头开始查找R=1的页面，如果存在说明该页最久未使用，进行置换。如果R=1，则将R=0，将该页面放在尾部。

LRU, Least Recently Used

实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。该方法代价较高。

LRU需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法。

NRU, Not Recently Used（clock算法）

1. 简单clock算法

维护一个标志位R(read),将内存中所有页面都通过链接指针链接成一个循环队列。换页时，按照FIFO的算法检查将R=O的页面置换。

2. 改进的clock算法

每个页面设置两个标志位，R(read)和M(modify)。被读时，R=1.被修改时，M=1，R=0。

• 最近未被访问，也未被修改(R=0, M=0)。
• 最近被访问，但未被修改(R=1, M=0)。
• 最近未被访问，但被修改(R=0, M=1)。
• 最近被访问，被修改(R=1, M=1)。

  deque<map<int,int>> *que;
  auto deque_point = que.begin();
  while(true){
  while(deque_point){
      if(R=0,M=0)
          return;
      ++deque_point;
  }
  while(deque_point){
      if(R=0,M=1)
          return;
      *deque_point->M = 0;
      ++deque_point;
  }
  deque_point = que.begin();
  }

优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0).

分段

1. 虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。

• 段表 操作系统进行初始化，操作者可以进行后续设置。
• 段页式—程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。
  
  

2. 分页与分段

• 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。

• 地址空间的维度：分页是一维地址空间，分段是二维的。

• 大 小是否可以改变：页的大小不可变，段的大小可以动态改变。

• 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

  文件管理

  设备管理

  磁盘结构

• 盘面（Platter）：一个磁盘有多个盘面；

• 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；

• 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；

• 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；

• 制动手臂（Actuator arm）：用于在磁道之间移动磁头；

• 主轴（Spindle）：使整个盘面转动。
  

  磁盘调度算法

  读写一个磁盘块的时间的影响因素有：

• 旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）

• 寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）

• 实际的数据传输时间
  其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

1. FCFS frist come frist served
2. SSTF shortest seek time frist

优先调度与当前磁头所在磁道距离最近的磁道。容易产生饥饿现象。远端请求长时间无法响应。

3. SCAN

电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。单向访问距离最近的磁道。直到该方向上没有未完成的磁盘请求，然后改变方向。

4. CSCAN

保持最大磁道挨着最小磁道和SCAN相似，但是到达内部之后立即调整到最外层，继续往内。或者相反。

系统调用

Linux 系统调用

|task|command|
| —- | —-|
|进程控制|fork();exit();wait()|
|进程通信| pipe(); shmget(); mmap()|
|文件操作| open(); read();write()|
|设备操作| ioctl();read();write()|
|信息维护| getpid(); alarm(); sleep()|
|安全| chmod();umask();chown()|

内核

大内核

大内核是将操作系统功能作为一个紧密结合的整体放到内核。由于各模块共享信息，因此有很高的性能。

微内核

由于操作系统不断复杂，因此将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。
在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。

中断

外中断

由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。

异常

由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。

陷入

用户系统调用

链接装载

• 预处理阶段：处理以 # 开头的预处理命令；
• 编译阶段：翻译成汇编文件；
• 汇编阶段：将汇编文件翻译成可重定位目标文件；
• 链接阶段：将可重定位目标文件和 printf.o 等单独预编译好的目标文件进行合并，得到最终的可执行目标文件。

  静态链接

1. 符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。
2. 重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的引用，使得它们指向这个内存位置。
3. 在可执行文件中产生一份拷贝。

   目标文件

• 可执行目标文件：可以直接在内存中执行；

• 可重定位目标文件：可与其它可重定位目标文件在链接阶段合并，创建一个可执行目标文件；

• 共享目标文件：这是一种特殊的可重定位目标文件，可以在运行时被动态加载进内存并链接；

  动态链接

  在内存中一般只保留该编译单元的一份拷贝。

• 装载时动态链接(Load-time Dynamic Linking)：这种用法的前提是在编译之前已经明确知道要调用DLL中的哪几个函数，编译时在目标文件中只保留必要的链接信息，而不含DLL函数的代码；当程序执行时，调用函数的时候利用链接信息加载DLL函数代码并在内存中将其链接入调用程序的执行空间中(全部函数加载进内存），其主要目的是便于代码共享。（动态加载程序，处在加载阶段，主要为了共享代码，共享代码内存）

• 运行时动态链接(Run-time Dynamic Linking)：这种方式是指在编译之前并不知道将会调用哪些DLL函数，完全是在运行过程中根据需要决定应调用哪个函数，将其加载到内存中（只加载调用的函数进内存），并标识内存地址，其他程序也可以使用该程序，并用LoadLibrary和GetProcAddress动态获得DLL函数的入口地址。（dll在内存中只存在一份，处在运行阶段）