操作系统

概述

1. 并发
   a. 并发是指宏观上在一段时间内能同时运行多个程序
   b. 并行指同一时刻能运行多个指令
   c. 并发：一个处理器轮换执行多个任务；并行：多个处理器执行多个任务
   d. 操作系统引入进程和线程，使得程序可以并发运行

2. 共享
   a. 指系统中的资源可以被多个并发进程共同使用
   b. 有两种共享方式：互斥共享和同时共享

3. 虚拟
   a. 虚拟技术把一个物理实体转换为多个逻辑实体
   b. 主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术
   c. 多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换
   d. 虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中

进程和线程

1. 进程
   a. 资源分配的基本单位
   b. 进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作

2. 线程
   a. 独立调度的基本单位
   b. 一个进程中可以有多个线程，它们共享进程资源

3. 区别
   a. 拥有资源

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

   b. 调度

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

   c. 系统开销

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

   d. 通信方面

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

4. 进程状态的切换
   a. 就绪状态（ready）：等待被调度
   b. 运行状态（running）
   c. 阻塞状态（waiting）：等待资源
   d. 就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度

5. 进程调度算法
   a. 批处理系统

    i. 先来先服务 first-come first-serverd（FCFS）
    ii. 短作业优先 shortest job first（SJF）
    iii. 最短剩余时间优先 shortest remaining time next（SRTN）
   

   b. 交互式系统

    i. 时间片轮转
    ii. 优先级调度
    iii. 多级反馈队列
   

   c. 实时系统

6. 进程通信
   进程同步：控制多个进程按一定顺序执行；
   进程通信：进程间传输信息。
   a.管道
   b.FIFO
   c.消息队列
   d.信号量
   e.共享存储

死锁

1. 必要条件
   a. 互斥：每个资源要么已经分配给了一个进程，要么就是可用的
   b. 占有和等待：已经得到了某个资源的进程可以再请求新的资源
   c. 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放
   d. 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源

2. 处理方法
   a. 鸵鸟策略
   b. 死锁检测与死锁恢复
   c. 死锁预防
   d. 死锁避免

3. 鸵鸟策略
   a. 当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略
   b. 因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能

4. 死锁检测与恢复
   a. 每种类型一个资源的死锁检测：死锁成环
   b. 每种类型多个资源的死锁检测：利用银行家算法，进行检测
   c. 死锁恢复：

    i. 利用抢占恢复
    ii. 利用回滚恢复
    iii. 通过杀死进程恢复
   

5. 死锁预防：破坏必要条件中的一个或多个
   a. 破坏互斥条件
   b. 破坏占有和等待：进程在开始执行前请求所需要的所有资源
   c. 破坏不可抢占
   d. 破坏环路等待：给资源统一编号，按照编号请求资源

6. 死锁避免
   a.安全状态
   i.指系统能按某种顺序（P1，P2，。Pn）来为每个进程分配所需的资源，直至最大需求，使得每个进程都可以顺序完成。若不存在这样一个安全序列，则成系统处于不安全状态
   b. 银行家算法

内存管理

1. 虚拟内存
   a. 目的：为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存
   b. 内容：为更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割为很多块，每一个块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令
   c. 总结：虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能

2. 分页系统地址映射
   a. 内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表
   b. 一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

3. 页面置换算法
   a.要访问的页面不再内存，且内存已无空闲空间，则需要从内存中调出一个页面放在磁盘中。追求页面置换频率最低
   b.最佳

    i. 理论算法（类似于预知哪个页面使用频率最低）
    ii. 将访问时间间隔最长的进行置换
   

   c.最近最久未使用

    i. 使用定长的链表，装入访问的页面。当一个页面被访问，将此页面移到表头。则表尾就是最近最久未使用的页面
    ii. 但是每次都更新链表，代价很高
   

   d. 最近未使用

    i. 使用状态位：R（被访问设置为1）和M（被修改设置为1）
    ii. 优先换出已经修改的页面（R=0，M=1），不是经常使用的干净页面（R=1，M=0）
   

   e. 先进先出

    i. 和队列一致，换出最先进入的
    ii. 缺页率很高
   

   f. 第二次机会算法

    i. 使用状态位R（被访问置为1）和定长链表
    ii. 每次替换，检查表尾最老的R位。
    iii. 如果R为0，意味着这个页面又老又没用，则置换。
    iv. 如果是1，就清0，放在链表头部，假装刚刚进入。从尾部继续搜索
   

   g. 时钟

    i. 对于上一步的改进：反复遍历链表降低效率，时钟将链表连成环，再使用指针指向最老页面
   

4. 分段
   a. 把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长

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

6. 分页与分段的比较
   a. 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
   b. 地址空间的维度：分页是一维地址空间，分段是二维的。
   c. 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
   d. 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

将源文件转换为目标文件

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

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

2. 静态链接
   a. 静态链接器以一组可重定位目标文件为输入，生成一个完全链接的可执行目标文件作为输出。链接器主要完成以下两个任务：
   b.符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。
   c.重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的引用，使得它们指向这个内存位置。

3. 目标文件
   a. 可执行目标文件：可以直接在内存中执行；
   b. 可重定位目标文件：可与其它可重定位目标文件在链接阶段合并，创建一个可执行目标文件；
   c.共享目标文件：这是一种特殊的可重定位目标文件，可以在运行时被动态加载进内存并链接；

4. 动态链接
   a.静态库有以下两个问题：

    i. 当静态库更新时那么整个程序都要重新进行链接；
    ii. 对于 printf 这种标准函数库，如果每个程序都要有代码，这会极大浪费资源。
   

   b. 共享库是为了解决静态库的这两个问题而设计的，在 Linux 系统中通常用 .so 后缀来表示，Windows 系统上它们被称为 DLL。它具有以下特点：

    i. 在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中；
    ii. 在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。
   

参考链接