操作系统总结

08 August 2021 - 4 mins read time
Tags: 基础知识学习

1 概述

1.1 操作系统的基本特征

• 并发：宏观上在一段时间内能运行多个程序

  并行指的是同一时刻能运行多个指令。并行需要硬件支持，如多流水线、多核处理器或分布式计算系统。

  操作系统通过进入进程和线程，使得程序能够并发运行。

• 共享：系统中的资源可以被多个并发进程共同使用。

  共享方式：互斥共享、同时共享。

  互斥共享的资源称为临界资源，例如打印机等，同一时刻只允许一个进程访问，需要使用同步机制来实现互斥访问。

• 虚拟：把一个物理实体转换为多个逻辑实体

  虚拟技术：时分复用技术和空分复用技术

  • 多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。

  • 虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将页置换到内存中。

• 异步：进程不是一次性执行完毕，而是走走停停，以不可预知的速度向前推进。

1.2 基本功能

• 进程管理

  • 进程同步、进程控制、进程通信、死锁处理、处理机调度等。

• 内存管理

  • 内存分配、内存映射、内存保护与共享、虚拟内存等。

• 文件管理

  • 文件存储空间的管理、目录管理、文件读写管理和保护等。

• 设备管理

  • 完成用户的I/O请求，方便用户使用各种设备，并提高设备的利用率。主要包括缓冲管理、设备分配、设备处理、虚拟设备等。

1.3 系统调用

如果一个进程在用户态需要使用内核态的功能，就进行系统调用而陷入内核，由操作系统代为完成。

1.4 宏内核与微内核

宏内核

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

微内核

定义：由于操作系统不断复杂，将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。

微内核架构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。

缺点：由于需要频繁地在用户态和内核态间进行切换，会有一定的性能损失。

1.5 中断分类

• 外中断

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

• 异常

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

• 陷入

  在用户程序中使用系统调用。

2 进程管理

2.1 进程与线程

进程

定义：资源分配的基本单位。

进程控制块(PCB, Program Control Block)用于描述进程的基本信息和运行状态。

线程

定义：独立调度的基本单位。

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

区别

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

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

• 系统开销：创建或撤销进程的开销远大于线程的开销。进程切换需要分配或回收资源，如内存空间、I/O设备等；线程切换只需要保存和设置少量寄存器内容，开销很小。

• 通信方式：线程间可以通过直接读写同一进程中的数据进行通信，而进程间通信需要借助IPC。

2.2 进程状态的切换

• 就绪状态(ready)：等待被调度

• 运行状态(running)：正在运行

• 阻塞状态(waiting)：等待资源

需要注意的是：

• 只有就绪状态和运行状态可以相互转换，其它状态都是单独转换。就绪状态的进程通过调度算法从而获得CPU时间，转为运行状态；而运行状态的进程，在分配给它的CPU时间片用完后就会转为就绪状态，等待下一次调度。

• 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括CPU运行时间。

2.3 进程调度算法

2.3.1 批处理系统

批处理系统中没有太多用户操作，其目标是保证吞吐量和周转时间。

• 先来先服务 FCFS, First-Come First-Served 按照请求的顺序进行调度。有利于长作业，不利于短作业。
• 短作业优先 SJF, Shortest Job First 按照估计运行时间最短的顺序进行调度。长作业有可能被饿死。
• 最短剩余时间优先 SRTN, Shortest Remaining Time Next 抢占式调度算法，按照作业的剩余运行时间进行调度。

2.3.2 交互式系统

交互式系统中有大量的用户交互操作，其目标是快速地对任务进行响应。

• 时间片轮转 所有就绪的进程按照FCFS原则排成一个队列，每次调度时把一个CPU时间片分配给队首进程。当时间片用完时，计时器发出时钟中断，调度程序停止该程序的运行，并将该任务送至就绪队列的末尾，同时将时间片分给队首的进程。 时间片过短：进程频繁切换，花费额外时间； 时间片过长：实时性无法得到保证

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

• 多级反馈队列 时间片轮转+优先级调度的结合：

2.3.3 实时系统

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

## 2.4 进程同步

• 临界区：访问临界资源的代码。

• 同步与互斥
  • 同步：多个进程因为合作而产生的直接制约关系，使得进程有一定的先后执行关系。
  • 互斥：多个进程在同一时刻只有一个进程能进入临界区。
• 信号量：一种整型变量，可以对其执行P、V操作。

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

 void P2(){
   down(&mutex);
   // 临界区
   up(&mutex);
 }

• 管程：将控制代码独立出来。

生产者-消费者问题的管程解法： 核心：引入条件变量及wait(), signal()来实现同步操作。

monitor ProducerComsumer
  condition full, empty;
  integer count := 0;
  condition c;

  procedure insert(item: integer):
  begin
    if count = N then wait(full);
    insert_item(item);
    count := count + 1;
    if count = 1 then signal(empty);
  end;

  procedure remove: integer:
  begin
    if count = 0 then wait(empty);
    remove = remove_item;
    count := count - 1;
    if count = N - 1 then signal(full);
  end

end monitor;

//生产者客户端
procedure producer
begin
  while true do
  begin
    item = produce_item;
    ProducerConsumer.insert(item);
  end
end

//消费者客户端
procedure consumer
begin
  while true do
  begin
    item = ProducerConsumer.remove;
    consume_item(item);
  end
end

2.5 经典同步问题

• 哲学家进餐问题

• 读者-写者问题

2.6 进程通信

用于进程间传输信息

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

进程通信是手段，进程同步是目的。

进程通信的方法：

• 管道：用于父子进程或兄弟进程

• 命名管道 FIFO：常见于客户端-服务器应用程序，FIFO用作汇聚点，在服务器和客户进程间传递数据。

• 消息队列：相较于FIFO，消息队列可以：独立于读写进程存在，从而避免了同步管道打开及关闭时可能产生的困难；避免同步阻塞的问题；有选择地接收消息，而FIFO只能默认接收。

• 信号量：用于为多个进程提供数据对象的访问。

• 共享存储：允许多个进程共享一个给定的存储区。

• 套接字：用于不同机器间的进程通信。

3 死锁

概念：一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件。

3.1 必要条件：

• 互斥：每个资源要么已经分配给了一个进程，要么就是可用的；

• 占有及等待：已经得到了某个资源的进程可以再请求新的资源；

• 不可抢占：已经分配给一个进程的资源不能被强制性地抢占，它只能被占有它的进程显式地释放；

• 环路等待：有两个或两个以上的进程组成环路，每个进程都在等待下一个进程所占有的资源。

3.2 处理方法

• 鸵鸟策略

• 死锁检测及恢复

• 死锁预防

• 死锁避免

3.2.1 鸵鸟策略

直接忽视死锁，什么也不做。

3.2.2 死锁检测与死锁恢复

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

死锁检测方法：检测环路

死锁恢复方法：

• 利用抢占恢复

• 利用回滚恢复

• 通过杀死进程恢复

3.2.3 死锁预防

在死锁发生前预防发生死锁。

• 破坏互斥条件：例如假脱机打印技术，允许多个进程同时输出，但真正物理打印的是打印机守护进程。

• 破坏占有和等待条件：规定所有进程在开始执行前请求需要的全部资源。

• 破坏不可抢占条件：规定进程拥有的资源可以抢占。

• 破坏环路条件：给资源统一编号，进程只能按顺序请求资源。

3.2.4 死锁避免

在程序运行时避免发生死锁。

案例：银行家算法。

4 内存管理

4.1 虚拟内存

将物理内存扩充为更大的逻辑内存，从而让程序有更多的可用内存。

4.2 分页系统地址映射

内存管理单元(MMU)负责程序地址空间和物理内存的转换，MMU中的页表(Page Table)存储着页(程序地址空间)和页框间(物理内存空间)的映射。

4.3 页面置换算法

程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断而将该页调入内存。如果此时内存已满，则系统从内存中调出一个页面到磁盘对换区以腾出空间。

• 最佳

所选择的页面是最长时间内未被访问的页面。然而，实际使用中无法知道一个页面多长时间不再被访问。

• 最近最久未使用 LRU, Least Recently Used

维护一个链表，当页面被访问时，将页面移动至链表表头，这样就能保证链表表尾的页面是最近最久未使用的。

• 最近未使用 NRU, Not Recently Used

每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：

- R=0，M=0
- R=0，M=1
- R=1，M=0
- R=1，M=1

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。

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

• FIFO

选择换出的页面是最先进入的页面，会导致常被访问的页面被换出，导致缺页率升高。

• 第二次机会算法

  在FIFO的基础上增加R位。页面被访问或修改后R=1,替换时check:

  (R == 1) ? 0 : out

• 时钟

第二次机会算法采用链表移动页面，降低了效率。时钟使用环形链表连接页面，再使用一个指针指向最老的页面。

4.4 分段

分页技术的问题：随着内存空间的动态增长，不同页表的地址空间会相互覆盖。

解决方法：把每个表分成端，一个段构成一个独立的地址空间。

4.5 段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

4.6 分页与分段对比

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

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

• 大小是否可以改变：页的大小不可变，段的大小可变；

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

5 地址管理

5.1 磁盘结构

• 盘面：一个磁盘有多个盘面；
• 磁道：盘面上的圆形带状区域；
• 扇区：磁道上的一个弧段，是最小的物理存储单位；
• 磁头：负责磁场与电信号间的相互转换；
• 制动手臂：在磁道间移动磁头；
• 主轴：使整个盘面转动；

5.2 磁盘调度算法

影响磁盘块的读写效率因素有：

• 旋转时间(盘面->扇区)
• 寻道时间(扇区->磁道)
• 实际的数据传输时间

5.2.1 先来先服务 FCFS, First Come First Served

按照磁盘请求的顺序进行调度。

优点：公平、简单；

缺点：平均寻道时间可能较长；

5.2.2 最短寻道时间优先 SSTF, Shortest Seek Time First

优先调度与当前磁头所在磁道距离最近的磁道。

优点：平均寻道时间较短；

缺点：不公平，可能出现饥饿现象；

5.2.3 电梯算法 SCAN

按一个方向进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。解决了饥饿问题。

6 链接

6.1 编译系统

• 预处理阶段：处理以#开头的预处理命令；

• 编译阶段：翻译成汇编文件；

• 汇编阶段：将汇编文件翻译成可重定位目标文件；

• 链接阶段：将可重定位目标文件和printf.o等单独预编译好的目标文件进行合并，得到最终的可执行目标文件。

6.2 静态链接

输入：一组可重定位目标文件 输出：完全链接的可执行目标文件

过程：

• 符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。
• 重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的引用，使得它们指向这个内存位置。

6.3 目标文件

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

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

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

6.4 动态链接

静态库的问题：

• 静态库更新时整个程序都要重新进行链接；

• 对于标准函数库，如果每个程序都要有代码，会造成空间浪费；

共享库：

• windows: .dll
• linux: .so

共享库的特点：

• 一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件；

• 在内存中，一个共享库的.text节(已编译程序的机器代码)的一个副本可以被不同的正在运行的进程共享。