操作系统原理 | 小张的博客

# 操作系统原理

# 一、绪论（特征、特点）

特征：
- 并发
  
  宏观上同时发生，微观上交替发生。通过分时技术实现。
  
  区分并行：同时两种以上操作，需要硬件操作
- 共享（与并发互为存在条件）
  - 互斥共享：不能同时访问的资源
  - 同时共享：能同时访问的资源（注意，这里的同时也是宏观同时，微观不同时的）
- 虚拟（与并发互为存在条件）
  
  把一个物理上的实体变成若干个逻辑上的对应物，逻辑上的才是用户能感受到的。
  - 空分复用技术
  - 时分复用技术
- 异步（与并发互为存在条件）
  
  开多了程序之后，cpu的时间片分不过来，那程序的运行就走走停停，不可预知。这就是异步性。
目标和功能
- 进程管理，见二
- 存储器管理（内存）
- 设备管理IO
- 文件管理
发展：批处理操作系统--分时操作系统--实时操作系统、网络和分布式操作系统
运行机制
- 中断和异常
- 系统调用（系统API)
体系结构
- 大内核
- 微内核

用户可以直接调用系统api

# 二、进程（处理机、cpu）计算题

进程
- 状态：创建、**运行、就绪、阻塞、**结束
- 控制：创建、终止、阻塞和唤醒、切换
- 通信：管道通信
线程
- 与进程的比较：更微小的控制。
- 线程的实现
磁盘调度算法
- SCAN算法（电梯算法）
- FIFO算法（先来先服务）
- SSTF算法（最短循道时间）
处理机调度（cpu）
- 概念：三级调度
  
  高级调度（作业调度）：从后背队列中选一个作业来创建进程。
  
  中级调度（内存调度）：将进程的部分数据调出外存，等内存空闲再调入内存。暂时被调出外存等待的进程状态为挂起状态。
  
  低级调度（进程调度）:从就绪队列中选取一个进程，将处理机分配给进程。
- 调度准则：
  
  cpu利用率：忙碌的时间/总时间
  
  吞吐量：完成的作业道数/总时间
  
  周转时间：作业完成时间-作业提交时间
  
  平均周转时间：各个作业的周转时间之和/作业的数量
  
  带权周转时间：作业完成时间-作业提交时间/作业实际运行时间
  
  平均带权周转时间：各作业带权周转时间之和/作业数
  
  等待时间：周转时间-运行时间-I/O时间
  
  作业的等待时间：被高级调度之前的等待时间加上被低级调度等待的时间，不算阻塞态时间；
  
  进程等待时间：被低级调度等待的时间，不算阻塞态时间。
  
  响应时间：用户从提出请求到首次被响应所用的时间
- 算法：
  
  FCFS（先来先服务）：先来先调度，其实考虑等待时间，越久就越优先得到服务，不存在饥饿。
  
  优点：要求等待时间长的优先
  
  短作业优先SJF：
  
  抢占式
  
  非抢占式（默认）
  
  优点：服务时间短的优先
  
  高响应比优先算法HRRN（非抢占式）
  
  响应比=（等待时间+要求服务时间）/要求服务时间
  
  优点：等待时间长和服务时间短的优先，避免长作业饥饿
  
  时间片轮转RR（抢占式）：每个进程运行一段时间。
  
  要求：时间片不能太大也不能太小。
  
  优点：公平、响应快；缺点：开销较大。
  
  优先级调度算法：设置一个优先数，优先级越高优先调度。
  
  抢占式
  
  非抢占式
  
  优先级设置：有静态优先级（一直不变）和动态优先级（动态改变），I/O型优先。
  
  多级反馈队列：对以上算法进行折中平衡。抢占式。
进程同步
- 临界资源、同步、互斥
- 信号量：整型、记录型
死锁（简答题）
- 定义：
- 原因：系统资源竞争、进程推进排序非法
- 四个必要条件：互斥（对互斥的争抢）、不剥夺、请求和保持、循环等待
- 策略：预防死锁、死锁的检测与解除（银行家算法）

# 三、内存（计算题）

程序执行过程
扩充内存
- 覆盖技术：用来解决**“程序大小超过物理内存综合”**的问题。
  
  将程序分为多个段，分为**“固定区”和若干个覆盖区**。常住的段放在固定区，调入后就不再调出，不常用的就放在覆盖区，需要用时调入，否则调出。（不能同时使用的函数就放在一个覆盖区）
  
  缺点：必须由程序员声明覆盖，对用户不透明。
- 交换技术（处理机中级调度）
  
  内存紧张时，将某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存。优先换出阻塞态内存，或者换出优先级较低内存（考虑驻留时间）。注意：PCB一直都在内存
  
  挂起态：暂时被换出外村等待的进程状态为挂起状态，分为就绪挂起态和阻塞挂起态。
  
  外存即磁盘，分为对换区（主要用于交换后的进程数据）和文件区（主要用于存储文件），前者追求速度，所以采用连续分配方式；后者追求空间利用率，所以采用离散分配方式。
内存分配
- 连续分配
  - 单一连续分配：内存分为系统区（较小）和用户区，用户区最多只能有一个用户程序。因此利用率较低，产生内部碎片，但是实现简单。
  - 固定分区分配：将用户区分成好几个块，这几个块可以是相等大小的，也可以是不相等大小的。
    
    分区说明表：记录表的区号、大小、起始地址和是否分配的状态。优点：实现简单。但是产生内部碎片。
  - 动态分区分配（可变分区分配）：不会预先分配内存分区，动态的建立分区。
    
    问题：1、数据结构：空闲分区表（类似分区说明表）或者空闲分区链（每一个节点都有两个指针，分别指向前一个空闲分区和后一个空闲分区。
    
    2、动态分区分配算法：如何选择可用分区分配？
    
    首次适应算法：按地址从小到大的顺序排。优点：开销小；
    
    最优适应算法：按空间从小到大排。优点：保留大的分区；缺点：容易形成小碎片；算法开销大
    
    最坏适应算法：按空间从大到小排。优点：减少难以利用的小碎片；缺点：大分区易被用完；算法开销大
    
    邻近匹配算法：按地址从小到大排，只不过每次都从上一次搜索结束的位置开始排。优点：开销小
    
    3、分配与回收：挨在一块就合并。
- 非连续分配（计算）
  - 页式
    
    进程分成多个页面；内存分为多个页框，二者数量对应相等；使用数据结构--页表进行页面号和内存块号（页框号）的对应。物理上：只需要存储块号，而不需要页号（从0开始）。
    
    注意对应关系：$1kb=1024b$
    
    地址转换：逻辑地址对应两个元素：页号和页内偏移量（通过这两个元素查询页表，找到其在内存中的起始位置）
  - 段式
    
    与分页区别：存储基础单位不同，每一段的长度不同。
    
    分段方式：按照逻辑，自身划分为若干个段，每个段都是从0开始编址。隔断之间在内存中并不一定相邻。优点：可操作性高，可读性高。
    
    段表：记载段号、段长、段基址。对于段表，每一项的存储大小都是相等的。
  - 段页式
    
    段页式兼具了段式和页式的优点，先按照逻辑进行分段，再在每个段中进行分页。段页式的逻辑地址在段式逻辑地址的基础上，将段内地址换成了页号和页内偏移量。段号决定了最多有多少段，页号决定了每个段内最多有多少页，页内偏移量决定了页面大小、内存块大小是多少（二者相等）
虚拟内存
- 来源：传统存储管理方式要求
  
  一次性：作业必须一次性装入内存后才能开始运行，会造成①作业很大时，不能全部装入内存②大量作业要求运行时，由于内存太小，不能容纳所有程序。
  
  驻留性：一旦作业被装入内存，就必须运行完才能走。
- 概念
  - 局部性原理
    
    ①时间局部性：执行了某条指令不久后，该条指令可能会再次进行；如果某个数据被访问过，不久之后可能会被再次访问。
    
    ②空间局部性：一旦成型访问量某个单元，不久之后其附近的存储单元也可能被访问。
  - 概念：在程序装入时，把很快要用到的部分装入内存，暂时用不到的就装在外存；当所访问信息不在内存时，系统负责将信息由外存调入内存；当内存不够时，操作系统负责将暂时用不到的信息调入到外存。
  - 特征：
    
    多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
    
    对换性：在作业运行中，可以将作业换入、换出
    
    虚拟性：从逻辑上扩充了内存容量·，是用户看到的容量远大于实际容量。
- 请求分页
  - 组成
    
    ①基本页式分配
    
    ②操作系统提供请求调页功能：将缺失页面从外存调入内存。
    
    ③页面置换功能：对应内存不够，要把不用的页面调出。
  - 请求调页
    
    在请求调页系统中，当访问的页面状态位为0，即不在内存中，那么就产生一个缺页中断，由操作系统的缺页中断处理程序处理中断。
    
    此时缺页的进程阻塞，放入阻塞队列，调页完成后再唤醒，放入就绪队列。
    
    如果存在空闲块：那就直接进入；如果不存在空闲块：那就挑选一个置换，优先换出访问次数更少的页面。
  - 页面置换算法
    - 最佳置换OPT（实际应用无法实现）
      
      每次选择淘汰的页面是以后永不使用或者最长时间内不再被访问的页面。
    - 先进先出FIFO（很差）
      
      Belady异常：当为进程分配的物理快数增大时，缺页次数不减反增。
    - 最近最久未使用LRU（性能好，但是开销大）
      
      在页表项在添加一个访问字段，用来记录自上次被访问以来所经历的时间。
    - 时钟算法CLOCK、最近未用算法NRU
      
      优先替换未被访问过的（为0）的，最多会进行两轮扫描。
    - 改进时钟算法
  - 页面分配策略：
    
    选择一个合适的驻留集：固定分配（驻留集大小不变）和可变分配（驻留集大小可变）。
    
    欲调页策略、请求调页策略
  - 抖动