2021计算机考研408操作系统个人笔记

2024-01-25 16:28:34

目录

本笔记为博主2021计算机专业考研408科目的操作系统个人笔记，融合了一些计算机组成原理的知识点，也将一些知识点划给了计算机组成原理笔记，仅供参考。

操作系统概述

操作系统的特征（并发、共享、虚拟、异步）

  • 并发 ※：同一时间间隔内，多个事件发生；与并行有区别。
  • 共享 ※：分为互斥共享方式，同时访问方式（实际上是并发访问）
  • 虚拟：分为时分复用技术（如处理器分时共享），空分复用技术（如虚拟存储器）
  • 异步：多个程序并发执行，以不可预知的速度向前推进，使得运行在一种随机环境下。

操作系统目标和功能：

  • 处理机管理、存储器管理、文件管理、设备管理
  • 作为用户与计算机硬件系统之间的接口：
    • 命令接口：分为联机命令接口（交互式命令接口，适用于分时或实时系统接口），脱机命令接口（批处理命令接口，适用于批处理系统）
    • 程序接口：由一组系统调用（广义指令）组成，让用户通过在程序中使用这些系统调用来请求操作系统为其提供服务。
  • 用作扩充机器

操作系统类型

单道批处理系统

作业成批处理，但是内存中始终只有一道作业。发出I/O请求后必须让CPU等待I/O完成。

多道批处理系统

作业成批处理，内存中允许有多个程序同时进入且在CPU中交替运行。发出I/O请求后，可暂停程序转去运行另一道程序，让系统各个组成部分都尽量去忙。

  • 优点：资源利用率高（多道程序共享资源），系统吞吐量大（尽可能让CPU和其他资源保持“忙”）
  • 缺点：用户响应时间较长，不能提供人机交互能力

分时操作系统

处理器运行时间分成很短的时间片，按时间片轮流把处理器分配给各联机作业使用

  • 优点：交互性、及时性，解决人机交互问题；独立性，各用户可同时独立使用计算机

实时操作系统

硬实时系统：某个动作必须绝对地在规定的时刻（或规定的时间范围）发生，如飞行器的飞行自动控制系统

软实时系统：接受偶尔违反时间规定且不会引起任何永久性损害，如飞机订票系统

  • 优点：及时性、可靠性，可及时处理外部信号，在严格时限内处理完接收事件

操作系统的运行机制

  • 时钟管理：时钟是最关键的设备，其功能有计时（提供标准系统时间）。通过对时钟中断的管理，可以实现进程切换，因此系统管理无不依赖于时钟。

  • 中断机制：现代操作系统是靠中断驱动的软件。只有一小部分功能属于内核，它们负责保护和恢复终端现场信息，转移控制权到相关处理程序。

  • 原语：若干条机器指令构成的用以完成特定功能的一段公共程序，如设备驱动、CPU切换、进程通信等功能中的部分操作都可定义为原语，它们属于内核。

    1. 处于操作系统最底层，最接近硬件的部分。
    2. 运行具有原子性，其操作不可分割（从系统安全性和便于管理考虑）。
    3. 运行时间都较短，且调用频繁。

    定义原语的直接方法：关闭中断，让其所有动作不可分割地完成后再打开中断。

  • 系统控制的数据结构及处理：如作业控制快、进程控制块（PCB）、各种消息队列等...

用户态、核心态

  • 操作系统内核程序：管理应用程序，要执行一些特权指令。
  • 核心态（管态、内核态） ：CPU状态为核心态时，才可运行内核程序。
  • 用户自编程序（应用程序）：出于安全考虑不可执行特权指令。
  • 用户态（目态）：CPU状态为用户态时，可运行用户自编程序。

用户态转换核心态的例子：

  • 用户程序要求操作系统服务（即系统调用）
  • 发生一次中断
  • 用户程序中产生了一个错误状态
  • 用户程序企图执行一条特权指令

处理任何中断（内、外中断）时，通过硬件中断机制修改CPU状态从用户态进入核心态，同时把CPU的使用权主动交给操作系统内核程序（中断处理程序）。操作系统内核程序（中断处理程序）对系统调用请求做出相应处理后，又会恢复CPU状态从核心态进入用户态，同时把CPU使用权还给用户。

某个进程的用户态、核心态之间的切换，不仅需要CPU里的状态切换（程序状态字），还需要切换用户堆栈、系统堆栈，且这个系统堆栈也属于该进程。

特权指令

计算机中不允许用户态直接使用的指令；用户态程序如果运行特权指令将发生异常，并切换到管态由操作系统接管CPU，即属于访管中断。

  • 包括了 系统调用 和 一些针对时钟、中断和原语的操作指令（如I/O指令，置中断指令，修改时钟（不包含读时钟），存取用于内存保护的寄存器、送程序状态字到程序状态字寄存器等的指令）。
  • 中断返回指令：从核心态转回用户态，是特权指令。

访管指令、陷入指令（trap指令）

  • 访管指令：是用户程序自愿进管的指令，强调的是用户程序可以执行特权指令；该指令本身属于非特权指令，可在用户态调用，在核心态执行。

  • 陷入指令（trap指令）：本质上和访管指令一样，但陷入指令强调的是用户进程放弃CPU，交还给操作系统程序；该指令本身属于非特权指令，可在用户态调用，在核心态执行。

系统调用（广义指令）

系统调用本质上是一个子程序（子功能）。当用户程序不能执行特权指令，需要借助操作系统来完成特定操作时，必须通过系统调用完成。

比如c语言的系统调用write()，这条广义指令在汇编层面包括：初始化相关参数和寄存器，执行陷入（中断）指令，跳转到中断服务程序，中断返回。

2021计算机考研408操作系统个人笔记

系统调用和函数调用的区别：

  • 系统调用本质上是一种函数调用，只是调用该函数是通过中断方式，INT 指令，进入核心态才能运行。
  • 函数调用通过CALL指令来进行，指令跳转的同时要保存函数调用前下条指令的地址，以保证函数调用完能返回当前指令接着运行。
  • 而系统调用是通过中断方式，即软件中断/陷入指令INT，执行后通过硬件关中断 保存断点和程序状态字，形成中断服务程序入口地址，之后执行中断服务程序。看起来很像是函数调用，只是系统调用会进入核心态，执行操作系统的代码。

操作系统的体系结构（大内核、微内核）

大内核

将操作系统主要功能模块都作为一个紧密联系的整体运行在核心态。

  • 优点：操作系统执行开销小，具有性能优势。
  • 缺点：交互关系复杂，维护困难。

微内核

将内核中最基本功能（如进程管理等）保留在内核，而将那些不需要再核心态执行的功能移到用户态执行，根据分层原则模块互相独立。

  • 优点：有效分离了内核与服务、服务与服务，降低内核设计复杂性，保证可靠性。
  • 缺点：需要频繁在核心态和用户态之间进行切换，操作系统执行开销偏大。

还有一种叫 库操作系统 的体系结构：将系统服务作为运行库链接到用户程序，可减少切换开销。

进程管理

进程

具有独立功能的程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。

进程的状态与转换

  • 运行态：正在处理机上运行
  • 就绪态：只缺少处理机资源，一旦得到处理机就可以立即运行。就绪态进程可能有很多个，用一个就绪队列排队。
  • 阻塞态（等待态）：等待其它资源（除处理机外）或某一事件。

2021计算机考研408操作系统个人笔记

进程控制

  • 进程的创建：
    1. 为新进程分配一个唯一进程标识号，并申请一个空白的PCB
    2. 为进程分配资源，为新进程的程序和数据及用户栈分配必要的内存空间（在PCB中体现）

注意，若资源（如内存资源）不足，不是创建失败而是处于阻塞态（等待态），等待资源。

  1. 初始化PCB（包括初始化标志信息、处理机状态信息和控制信息、进程的优先级等）
  2. 若进程就绪队列能过够接纳新进程，则新进程插入就绪队列，等待被调度运行

允许父进程创建子进程：子进程可继承父进程所拥有资源；子进程撤销，从父进程获得资源归还给父进程；父进程撤销，同时子进程也随之撤销。

  • 进程的终止：若正常结束，即完成任务。

    • 异常结束：发生某种异常事件（如存储区越接、保护错、非法指令、算术错误、I/O故障等），使程序无法继续运行
    • 外界干预：进程应外界请求而终止运行（如操作员/操作系统干预、父进程请求和父进程终止）

  • 进程的阻塞：运行态的进程期待的事件未发生（如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作可做等）

    • 进程自我阻塞，调用 阻塞原语（Block），由运行态变为阻塞态

  • 进程的唤醒：当被阻塞进程所期待的事件出现时（如它所启动的I/O操作已完成或其所期待的数据已到达）

    • 进程主动唤醒其它进程，调用 唤醒原语（Wakeup） ，将等待该事件的进程 由阻塞态唤醒为就绪态

进程阻塞是进程的自主调用行为，进程唤醒则是由别的进程调用

  • 进程的切换：
    1. 保存处理机上下文（包括PC和其它寄存器）
    2. 更新PCB信息，并把进程的PCB移入相应的队列（如就绪队列、某事件的阻塞队列）
    3. 选择另一个进程更新其PCB，并执行
    4. 更新内存管理的数据结构
    5. 恢复处理机上下文

调度/切换时机

不能进程切换的情形：

  • 处理中断过程中
  • 进程在操作系统内核程序临界区

不能进程调度/切换的情形：

  • 需要完全屏蔽中断的原子操作过程

进程调度的情形：

  • 发生引起调度条件且当前进程无法继续运行下去（阻塞态）时（若只支持这种情况的调度，则为非剥夺调度）
  • 中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，可马上进行进程调度与切换。（若支持该情况，则为剥夺调度）

进程切换：

  • 调度完成后立刻发生
  • 要求保存原进程当前切换点的现场信息，恢复被调度进程的现场信息。
  • 现场切换时，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。
  • 内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。

进程切换 和 处理机模式切换 是不同的：

  • 处理机模式切换时，处理机逻辑上可能还在同一进程中运行。若进程因中断或异常进入核心态运行，执行完后又回到用户态刚被中断的程序运行，则操作系统只需恢复进程进入内核时所保存的CPU现场，而无需改变当前进程的环境信息。
  • 进程切换时，则当前进程的环境信息也需要改变。

进程的组织

  • 进程控制块（PCB）：描述进程基本情况和运行状态，进而控制和管理程序；PCB是进程存在的唯一标志。
    进程描述信息 进程控制和管理信息 资源分配清单 处理机相关信息
    进程标识符（PID） 进程当前状态 代码段指针 通用寄存器值
    用户标识符（UID） 进程优先级 数据段指针 地址寄存器值
    代码运行入口 堆栈段指针 控制寄存器值
    程序的外存地址 文件描述符 状态寄存器值
    进入内存时间 键盘 状态字
    处理机占用时间 鼠标
    信号量使用
    • 链接方式：同一状态的PCB链接成一个队列，不同状态对应不同的队列。
    • 索引方式：同一状态的PCB指针组织在一个索引表中，不同状态对应不同的索引表。
  • 程序段：程序可被多个进程共享，即多个进程可以运行同一个程序。
  • 数据段

进程映像（进程实体）= 程序段 + 相关数据段 + PCB

进程的通信

  • 共享存储：通信进程之间有一块共享空间，通过对共享空间进行读/写操作实现信息交换，需要使用同步互斥工具（P/V操作）
  • 消息传递：数据交换以格式化的消息为单位，通过系统提供的 发送消息 和 接收消息 两个原语进行交换。
    • 直接通信方式：直接发送消息，并将它挂在接收进程的消息缓冲队列中，接收进程从该队列取得消息。
    • 间接通信方式（信箱通信方式）：消息发送到某个中间实体（信箱），接收进程从中间实体取得消息。
  • 管道通信：“管道”（pipe文件）即用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件。发送程序以字符流形式将大量数据写入管道，接受程序则从管道读出数据。
    • 管道读数据是一次性操作，一旦读取，数据就从管道中被抛弃
    • 管道采用半双工通信：某一时刻只能单向传输，要实现父子进程双方互动通信，需要定义两个管道

线程

  • 属性：
    1. 有一个唯一标识符和一个线程控制块（记录线程执行的寄存器和栈等现场状态）。
    2. 同一个服务程序被不同用户调用时，操作系统把它们创建成不同线程。
    3. 同一进程各个线程共享该进程所拥有资源、地址空间。
    4. 多CPU计算机系统中，多个线程可占据不同的CPU，提高进程处理速度。
    5. 线程和进程一样，也会经理阻塞态、就绪态和运行态等变化。
  • 调度：线程是独立调度（处理机）的基本单元，进程则是拥有资源的基本单元。
  • 拥有资源：线程不拥有系统资源，但线程可访问其隶属进程的系统资源。
  • 系统开销：线程切换只需保存和设置少量寄存器内容，开销小，提高操作系统的并发性能；进程切换设计CPU环境的保存和新调度进程CPU环境的设置，开销较大。

多线程实现与模型

多线程实现：

  • 用户级线程：线程管理的所有工作由应用程序完成，效率较高，并发程度低
  • 内核级线程：线程管理的所有工作由内核完成，效率较低，并发程度高

多线程模型：

  • 多对一模型：多个用户级线程映射到一个内核级线程
    • 并发程度低（一个线程在使用内核服务时被阻塞，整个进程都会被阻塞；多个线程不能并行地运行在多处理机上）
  • 一对一模型：每个用户级线程映射到一个内核级线程
    • 并发程度高（当一个线程被阻塞后，允许另一个线程继续执行）
  • 多对多模型：将n个用户级线程映射到m个内核级线程上，m<=n
    • 并发程度较高，又不失效率

处理机调度

调度层次

  • 作业调度（高级调度）：按某种策略从外存上处于后备状态的作业挑选作业，给它们分配内存、I/O设备等必要资源，并建立相应进程。执行频率较低。

  • 中级调度（内存调度）：将外存上具备运行条件的程序重新调入内存（修改为就绪态）；提高内存利用率、系统吞吐量，执行频率一般。

  • 进程调度（低级调度）：按某种策略从就绪队列中选取一个进程，将处理机分配给它；最基本的，不可或缺，执行频率最频繁。

调度算法

  • 非剥夺调度方式（非抢占方式）：实现简单、系统开销小（适用批处理系统）
  • 剥夺调度方式（抢占方式）：提高系统吞吐率、响应效率（适用分时系统、实时系统）

  • 先来先服务（FCFS）调度算法：

    • 算法简单，但效率低；对长作业比较有利，但对短作业不利（有利于CPU繁忙型作业，不利于I/O繁忙型作业）
    • 适合批处理系统

  • 短作业优先（SJF）调度算法：

    • 对长作业不利（可能导致长作业长期不被调用，即“饥饿”现象）；不保证紧迫性作业及时处理；需估计执行时间。
    • 平均等待时间、平均周转时间最少（特殊性质）
    • 适合批处理系统

  • 优先级调度算法：

    • 进程优先级可分为：静态优先级（依据进程类型、资源要求、用户要求）、动态优先级（依据进程占CPU时间长短、就绪程序等待CPU时间长短）
    • 进程优先级设置：
      1. 系统进程 > 用户进程
      2. 交互型进程 > 非交互型进程（或前台进程 > 后台进程）
      3. I/O型进程 > 计算型计算
    • 适合实时操作系统

  • 高响应比优先调度算法：

    • \(响应比 = \frac{等待时间+要求服务时间}{要求服务时间}\)
    • 要求服务时间越短，响应比越高，有利于短作业。
    • 适合分时操作系统

  • 时间片轮转调度算法：

    • 时间片过大：退化成先来先服务调度算法
    • 时间片过小：切换频繁，处理机开销增大
    • 适合分时操作系统

  • 多级反馈队列调度算法：

    • 当某级队列为空时才调度下一级队列
    • 短作业优先、中等作业周转时间较短、长作业不会长期得不到处理
    • 适合分时操作系统

进程同步

  • 临界资源：一次仅允许一个进程使用的资源称为临界资源（如打印机）。
    • 进入区：检查是否可进入临界区，若能进入则设置正在访问临界区的标志，防止别的进程进入。
    • 临界区（临界段）：进程中访问临界资源的那段代码。
    • 退出区：将正在访问临界区的标志清除。
    • 剩余区：代码其余部分
  • 同步（直接制约关系）：共同完成某种任务建立的多个进程，需要在位置上协调它们的工作次序。
  • 互斥（间接制约关系）：一个进程进入临界区使用临时资源，另一个进程必须等待，占用临界资源的进程退出临界区后，另一进程才可访问此临界资源。

为防止两个进程同时进入临界区，需遵循：空闲让进、忙则等待、有限等待、让权等待

临界区互斥基本方法（软件实现方法）

  • 单标志法：使用单个标志位flag，两个进程交替进入临界区。
    • 缺点：若某个进程不再进入临界区，则另一个进程也无法进入临界区（违背“空闲让进”）
    while(turn!=0); //进入区
//临界区...
turn = 1;       //退出区
//剩余区...

    while(turn!=1); //进入区
//临界区...
turn = 0;       //退出区
//剩余区...
  • 双标志法先检查：先检查对方标志，再设置自己标志。
    • 缺点：可能会同时进入临界区（违背“忙则等待”）
    while(flag[j]); //进入区
flag[i] = true; //进入区
//临界区...
flag[i] = false;//退出区
//剩余区...

    while(flag[i]); //进入区
flag[j] = true; //进入区
//临界区...
flag[j] = false;//退出区
//剩余区...
  • 双标志法后检查：先设置自己标志，再检查对方标志。
    • 缺点：可能双方互相谦让，谁也进不了临界区，造成“饥饿”现象。
    flag[i] = true; //进入区
while(flag[j]); //进入区
//临界区...
flag[i] = false;//退出区
//剩余区...

    flag[j] = true; //进入区
while(flag[i]); //进入区
//临界区...
flag[j] = false;//退出区
//剩余区...
  • Peterson's Alogrithm：
    • 优点：利用turn解决“饥饿”现象；利用flag解决临界资源的互斥访问问题。
    flag[i] = true;turn = j;//进入区
while(flag[j] && turn==j); //进入区
//临界区...
flag[i] = false;//退出区
//剩余区...

    flag[j] = true;turn = i;//进入区
while(flag[i] && turn==i); //进入区
//临界区...
flag[j] = false;//退出区
//剩余区...

临界区互斥基本方法（硬件实现方法/低级方法/元方法）

  • 中断屏蔽方法：限制处理机交替执行程序的能力（切换进程需要中断处理），执行效率降低。而且不应该将开关中断权力交给用户。
    关中断;
//临界区...
开中断;
  • 硬件指令方法：适用任意数目的进程，而不管是单处理机还是多处理机；简单、容易验证其正确性；支持多个临界区；只需为每个临界区设立一个布尔变量；
    • TestAndSet 原子操作指令：读出指定标志后把该标志设置为真。
      while TestAndSet(&lock);
//临界区...
lock = flase;
//剩余区...
    • Swap 原子操作指令：交换两个字的内容
      flag = true;
while(flag) Swap(&flag,&lock);
//临界区...
lock = false;
//剩余区...

信号量

wait（P操作）、signal（V操作）均为原语操作，由软件通过中断屏蔽方法实现。

  • 整型信号量：表示资源数目的整型量S；其wait操作通过while不断测试S是否小于等于0，通过则S-1；其signal操作让S+1

  • 记录型信号量:除了表示资源数量value还增加一个进程链表L；其wait操作让S-1，且将进程放置在L队尾；其signal操作让S+1，且取L队首进程唤醒。

管程

代表共享资源的数据结构，以及对该共享数据结构的操作所组成的资源管理程序。每次仅允许一个进程进入管程，从而实现进程互斥（即多个进程同时调用管程的操作方法实际会串行运行）。

  • 条件变量：管程里记录因某种条件原因而阻塞的一个队列，且管程通常设有多个条件变量。

条件变量的wait/signal操作也可实现进程的阻塞/唤醒。不同的是信号量值反映了剩余资源数，而在管程中，条件变量只记录阻塞队列，而剩余资源数用共享数据结构记录

同步问题和互斥问题

  • 利用信号量实现前驱关系：

    2021计算机考研408操作系统个人笔记

      semaphore e12=e13=e24=e25=e36=e46=e56=0;
  S1(){V(e12); V(e13);}
  S2(){P(e12);V(e24); V(e25);}
  S3(){P(e13);V(e36);}
  S4(){P(e24);V(e46);}
  S5(){P(e25);V(e56);}
  S6(){P(e36);P(e46);P(e56);}

  • 生产者-消费者问题：

    • 生产者-消费者
    semaphore empty=n,full=0,mutex=1;
Producer(){
  while(1){
    //生产数据
    P(empty);
    P(mutex);
    //将数据放入缓冲区
    V(mutex);
    V(full);
  }
}
Consumer(){
  while(1){
    P(full);
    P(mutex);
    //从缓冲区取出数据
    V(mutex);
    V(empty);
    //消费数据
  }
}
    • 父母放水果-儿女吃水果
    semaphore A=0,B=0,plateEmtpy=1;
ProducerA(){
  while(1){
    //生产A数据
    P(plateEmpty);
    //将A数据放入缓冲区
    V(A);
  }
}
ConsumerA(){
  while(1){
    P(A);
    //从缓冲区取出A数据
    V(plateEmpty);
    //消费A数据
  }
}
ProducerB(){
  while(1){
    //生产B数据
    P(plateEmpty);
    //将B数据放入缓冲区
    V(B);
  }
}
ConsumerB(){
  while(1){
    P(B);
    //从缓冲区取出B数据
    V(plateEmpty);
    //消费B数据
  }
}

  • 读者-写者问题：

    • 读进程优先
    semaphore rw=1,mutex=1;count=0;
Reader(){
  while(1){
    P(mutex);
    if(count==0){P(rw);}  //队列里第一个读进程进入，则*rw锁
    count++;
    V(mutex);
    //读...
    P(mutex);
    count--;
    if(count==0){V(rw);}  //队列里最后一个读进程退出，则解锁rw锁
    V(mutex);
  }
  
}
Writer(){
  while(1){
    P(rw);
    //写...
    V(rw);
  }
}
    • 写进程优先
    semaphore rw=1,w=1,mutex=1;count=0;
Reader(){
  while(1){
    P(w);         //写进程进入后，防止新的读进程进入
    P(mutex);
    if(count==0){P(rw);}
    count++;
    V(mutex);
    V(w);         //允许写进程进入
    //读...
    P(mutex);
    count--;
    if(count==0){V(rw);}
    V(mutex);
  }
}
Writer(){
  while(1){
    P(w);          //表示写进程进入
    P(rw);
    //写...
    V(rw);
    V(w);          //表示写进程退出
  }
}

  • 哲学家进餐问题：

    • 左右两边筷子都可用时才允许抓起筷子
    semaphore chops[5]={1,1,1,1,1},mutex=1;
P1(int i){
  while(1){
    P(mutex);
    P(chops[i]);
    p(chops[(i+1)%5]);
    V(mutex);
    //吃饭
    V(chops[i]);
    V(chops[(i+1)%5]);
    //思考
  }
}

  • 吸烟者问题：

    semaphore offer1 = offer2 = offer3 = 0;
semaphore finish = 2;
P1(){
  while(1){
  P(finish);
  random = rand()%3;
  if(random == 0){V(offer1);}
  else if(random == 1){V(offer2);}
  else if(random == 2){V(offer3);}
  }
}

P2(){
  while(1){
  P(offer1);
  //抽烟...
  V(finish);
  }
}
P3(){
  while(1){
  P(offer2);
  //抽烟...
  V(finish);
  }
}
P4(){
  while(1){
  P(offer3);
  //抽烟...
  V(finish);
  }
}

死锁

  • 死锁：多个进程因争夺资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进；且死锁进程至少2个。
  • 死锁产生的原因：系统资源的竞争、进程推进顺序非法。
  • 饥饿：长时间没有得到资源分配（例如排队请求一直被插队）导致长时间等待。

死锁产生的必要条件

  • 互斥条件：资源具有排他性
  • 不剥夺条件：持有资源不能被强行夺走（只可以自己主动释放资源）
  • 请求并保持条件：允许同时持有资源并请求新的资源
  • 循环等待条件：存在一种进程资源的循环等待链（资源分配图含圈）

资源分配图含有圈但无死锁的原因是同类资源数大于一个；但若同类资源只有一个时，资源分配图含圈<=>系统出现死锁。

死锁预防

  • 破坏互斥条件：允许某些资源共享使用。
  • 破坏不剥夺条件：请求新资源得不到满足时，必须释放保持的所有资源。
    • 重复释放申请，增加系统开销，降低系统吞吐量。
    • 常用于易于保存和恢复的资源，如CPU寄存器及内存资源。
  • 破坏请求并保持条件：采用预先静态分配法，一次申请所有需要的资源。
    • 系统资源严重浪费。
    • 可能导致“饥饿”现象，某些资源长期被其他进程占用，导致另一些资源迟迟不能开始运行。
  • 破坏循环等待条件：采用顺序资源分类法，给系统资源编号，规定进程按编号递增的顺序请求资源，同类资源一次申请完。
    • 造成资源浪费，限制新设备的添加，经常发生使用资源的顺序和系统规定顺序不同。

死锁避免

  • 安全性算法：系统在进行资源分配之前，先计算这次分配的安全性。若这次分配会导致系统进入不安全状态，则让进程等待，否则允许分配。

    • 大题规范（见P134）：
    1. 资源分配表含有各进程的最大需求矩阵、分配矩阵和空闲资源矩阵。
    2. 比较空闲资源量和各进程需求量，如满足需求量，则回收该进程已占资源并记录进安全序列。
    3. 重复上一步，若所有进程都可进入安全序列，则本次分配为安全状态，否则为不安全状态。

  • 银行家算法：进程发来资源请求向量，先进行检查，得到更新后的分配矩阵，再用安全性算法检验分配安全性。

    • 大题规范（见P135）：
    1. 进程发来资源请求向量，先进行检查：检查需求量是否小于等于最大需求量、是否小于等于系统空闲资源量
    2. 更新分配矩阵，并用最大需求矩阵、分配矩阵、空闲资源矩阵进行安全性算法检查是否安全。
    3. 若安全得到安全序列并写出安全序列分析表。

死锁检测与解除

  1. 资源分配图：圆圈代表一个进程，方框代表一类资源，进程到资源的有向边表示请求边，资源到进程的有向边表示分配边。
    • 2021计算机考研408操作系统个人笔记
  2. 简化资源分配图（死锁定理：系统为死锁的条件是资源分配图是不可完全简化的）
    1. 找出资源分配图中既不阻塞又不孤点的进程\(P_i\)（即找出它所有的申请边，且每个边对应资源申请数量<=空闲资源数量），消去它所有请求边和分配边。
    2. 释放资源后可以唤醒等待这些资源而阻塞的其他进程，从而重复消去图中的边。
  3. 死锁解除
    • 资源剥夺法：挂起某些死锁进程，抢占它的资源，分配给其他死锁进程。
    • 撤销进程法：强制撤销部分甚至全部死锁进程并剥夺这些进程资源。
    • 进程回退法：让一或多个进程回退到足以回避死锁，进程回退时进程主动释放资源而非被剥夺；但要求系统保持进程的历史信息，设置还原点。
资源分配策略 各种可能模式 主要优点 主要缺点
死锁预防 保守，并发程度低，宁可资源闲置 一次请求所有资源/资源剥夺/顺序资源分配法（按一定顺序申请资源） 适用于突发式处理的进程，不必进行剥夺 效率低，进程初始化时间延长；剥夺次数过多，不变灵活申请新资源
死锁避免 折中，运行时判断是否可能死锁 寻找可能的安全分配序列 不必进行剥夺 必须知道将来的资源需求，进程不能被长时间阻塞
死锁检测 宽松，并发程度高，只要允许就分配资源 定期检查死锁是否已经发生 不延长进程初始化时间，允许对死锁进行现场处理 通过剥夺解除死锁，造成损失

内存管理

程序装入和链接

  1. 程序 =编译程序=> 目标模块
  2. 目标模块 =链接程序=> 装入模块
  3. 装入模块 =装入程序=> 装入内存运行

链接

  • 静态链接：将各目标模块及所需库函数链接成一个可执行程序
  • 装入时动态链接：各目标模块装入内存时，边装入边链接
  • 运行时动态链接：运行时需要某个模块时才链接该目标模块

装入（装入内存）

  • 绝对装入：地址均为绝对地址
  • 可重定位装入（静态重定位）：地址一开始是相对于各模块的地址的起始地址，装入内存时才对各目标模块里的相对地址修改为绝对地址（重定位）
    • 作业装入内存时，必须分配它要求的全部内存空间
    • 运行期间不可移动其内存【不支持页式管理】，也不能申请内存空间
  • 动态运行时装入（动态重定位）：地址是相对于各模块的初始地址，等到程序真正要执行时采用地址转换机制（重定位寄存器）
    • 作业装入内存时，装入部分代码即可运行
    • 运行期间根据需要动态申请分配内存，支持程序在内存中发生移动
    • 可将程序分配在不连续的存储区【支持页式管理】，也便于程序段的共享
    • 可以向用户提供一个比存储空间大得多的地址空间

逻辑地址空间、物理地址空间

  • 逻辑地址（相对地址）：编译后每个目标模块从0开始
  • 物理地址：地址转换的最终地址
  • 地址重定位：将逻辑地址转换为物理地址

内存保护、紧凑技术

内存保护

  • 采用上、下限寄存器：存放用户作业在主存的上、下限地址，每当CPU访问某个地址，与两寄存器值相比，判断有无越界。
  • 采用重定位寄存器（或基址寄存器）和界地址寄存器（限长寄存器）：重定位寄存器含最小物理地址值，界地址寄存器含逻辑地址最大值。将逻辑地址与界址寄存器比较。

紧凑

  • 紧凑：操作系统不时地对进程在内存中的位置进行移动和整理。

连续内存分配（单一连续、固定分区、动态分区）

单一连续分配

只能用于单用户单任务的操作系统，内存永远只有一道程序，因此也无需内存保护。

  • 有内部碎片，但无外部碎片
  • 硬件支持：界地址寄存器、越界检查机构

固定分区分配

预先分为若干固定大小（固定但不一定相同）的分区：

  • 有内部碎片，但无外部碎片
  • 多进程不可共享一个主存区
  • 硬件支持：上下限寄存器、越界检察机构；重定位寄存器、长度寄存器、动态地址转换机构

动态分区分配

动态分配分为大小数目可变的分区。

  • 有外部碎片（解决方法：紧凑技术），但无内部碎片
  • 分配策略：
    • 首次适应：以地址递增的次序找到第一个满足大小的空闲区域。
    • 邻近适应（循环首次适应）：由首次适应演变，从上次查找结束的位置开始查找。
    • 最佳适应：以容量递增的次序找到第一个满足大小的空闲区域。
    • 最坏适应（最大适应）：以容量递减的次序找到第一个满足大小的空闲区域。
  • 硬件支持：上下限寄存器、越界检察机构；重定位寄存器、长度寄存器、动态地址转换机构

非连续内存分配（页式分配、段式分配、段页式分配）

页式分配

  • 优点：页面长度固定，不会产生外部碎片
  • 缺点：最后一页会产生内部碎片（页内碎片）

  1. 页表（慢表）【在主存中】

    页号 有效位 脏位（修改位） 引用位（使用位） 页地址
    数组索引（隐含） 表示对应页面是否存在于主存 表示对应页面是否被修改（虚存机制采用回写策略） 用来配合替换策略进行设置（例如是否实现FIFO或LRU策略等） 对应的主存块号或外存地址
    • 用于索引找到页号对应的主存地址（或硬盘地址）
    • 缺点：读取1个主存数据需2次访存

  2. 快表、相联存储器（TLB）【不在主存里】

    • 由高速缓冲器组成，用于加快查找页面（减少额外的访存），通常采用全相联、组相联方式。
  • 页表寄存器（PTR）：存放页表的初始地址和页表长度。进程未执行时，页表始址和长度放在进程控制块PCB；进程执行时，将该进程对应的页表始址和长度存入页表寄存器。

段式分配

  • 优点：段的分界具有逻辑独立性，易于编译、管理、修改、保护、共享。
  • 缺点：容易造成碎片（浪费内存）

  1. 段表 【在主存中】

    段号 段首址 装入位 段长
    数组索引（隐含） 首地址 表示该段是否已调入主存 长度
  • 段表寄存器：存放段表始址和段表长度。
  • 纯代码（可重入代码）：不能修改的代码（不属于临界资源）。
  • 段的共享与保护：两个作业的段表中相应表项指向被共享的段的同一个物理副本。不可修改的代码和数据可被共享，否则不能共享。

段页式分配

按逻辑结构分段，每段再划分为固定大小的页，兼具页式和段式虚拟存储器的优点

  • 缺点：地址转换过程需要两次查表，系统开销大

一个进程只能有一个段表，可能有多个页表。

虚拟内存管理（请求方式分配）

虚拟存储器的主要特征：

  • 多次性：无需在作业运行时一次性全部装入内存，而是允许分成多次调入内存运行。
  • 对换性：无需在作业运行时一直常驻内存，而允许作业运行过程中进行换入和换出。
  • 虚拟性：逻辑上扩充内存的容量，用户看到的内存用量大于实际的内存容量。

缺页（页面故障）中断：要访问的页面不在内存时，便会产生一个缺页中断。

  • 在指令执行期间而非一条指令执行完后产生和处理中断信号，属于内部中断。
  • 一条指令在执行期间可能产生多次缺页中断。

抖动（颠簸）

由于频繁发生缺页，导致处理机大部分时间都将用于交换块，系统效率大大降低。

  • 主要原因：某个进程频繁访问的页面数目高于可用的物理块数目。
  • 解决方法：使用更好的置换算法；扩大内存空间

驻留集、工作集

  • 驻留集：操作系统决定给某个进程分配几个物理块（物理页框）。
  • 工作集：在某段时间间隔内进程可能将要访问的页面集合，反映了接下来一段时间内很可能频繁访问的页面集合。

根据局部性原理，对最近访问过的若干个页面来确定工作集，并为其分配大于其工作集的驻留集物理块（若小于，可能频繁缺页，发生抖动）。

页面分配

页面分配（给进程分配多少物理块）策略：

  • 固定分配局部置换（运行期间不改变块数）：每个进程分配一定数目的物理块。
  • 可变分配全局置换（仅动态增加块数）：每个进程分配一定数目的物理块，操作系统自身也保持一个空闲物理块队列。某进程一旦发生缺页，系统从空闲物理块队列取出一个物理块分配给该进程并调入所需页装入其中。
    • 实现简单，比起固定分配更加灵活
    • 可能盲目的增加物理块，导致多道程序并发能力下降
  • 可变分配局部置换（动态增加/减少）：每个进程分配一定数目的物理块。某进程发频繁发生缺页时，系统重新为其分配更多的物理块；反之某些进程缺页率特别低时，系统会适当回收该进程物理块
    • 实现复杂一些
    • 保证进程不会过多调页的同时，保持系统多道程序并发能力

页面调入

  • 调入页面的时机：

    • 预调页策略：根据局部性原理，由程序员预先指出程序应先调入哪些页（运行前调入）。
    • 请求调页策略：进程在运行中需要访问的页面不在内存而提出请求，由系统将所需页面调入内存（运行时调入）。

  • 对换区、文件区：外存分为 用于存放对换页面的对换区 与 用于存放文件的文件区；对换区通常采用连续分配方式，文件区采用离散分配方式，因此对换区磁盘I/O速度比文件区的更快。

  • 从何处调入页面：

    1. 系统拥有足够的对换区空间：可以全部从对换区调入所需页面，提高调页速度。
    2. 系统缺少足够的对换区空间：凡不会被修改的文件直接从文件区调入；换出这些页面时由于未被修改因此可以直接抛弃。对那些可能被修改的部分，在将它们换出时必须调到对换区，以后需要时再从对换区调入（因为读的速度比写的速度快）
    3. UNIX方式：与进程有关的文件都放在文件区，未运行过的页面都应从文件区调入。曾运行过但又被患处的页面，由于存放在对换区，因此下次调入应从对换区调入。进程请求的共享页面若被其他进程调入内存，则无需从对换区调入。

高速缓冲存储器（映射方式、替换算法、写策略）

局部性原理

  • 时间局部性：如果某个数据被访问，那么在不久的将来它很可能再次被访问（例如循环体指令\重复访问同个数据）
  • 空间局部性：如果某个数据被访问，那么与它相邻的数据很可能也能被访问（例如数组数据）

命中率计算要注意给出的C程序代码中变量被访问的实际总次数。

Cache和主存的映射方式

Cache和主存的交换是以 块（行） 为单位的。

  1. 直接映射：访问地址取中间若干位，索引到对应Cache行标记。若有效位为 \(1\) 且标记一致，则命中，否则不命中。
    2021计算机考研408操作系统个人笔记
  2. 全相联映射：访问地址与所有Cache块（行）进行比较。
    2021计算机考研408操作系统个人笔记
  3. Q路组相联映射：CaChe分成若干个含Q块（行）的组，组间直接映射，组内全相联映射（当 \(Q=1\) 时变为直接映射，当 \(Q=总块数\) 时变为全相联映射）
    2021计算机考研408操作系统个人笔记

Cache写策略

  1. 全写法（直通法）：Cache和主存都写入
  2. 写回法：只写入Cache，被换出时Cache才写回内存

地址翻译

2021计算机考研408操作系统个人笔记

快表&页表查询计算（虚拟地址=>物理地址）

  1. 虚拟页号映射页框号（物理页号）
  2. 先查快表（TLB）、再查页表
  3. 若页号不存在，则发生缺页中断，调入页后重新从头开始访问

Cache查询计算（物理地址=>Cache地址）

  1. 主存地址映射为Cache地址（Cache块号+块内地址）：物理地址划分标记、组（行/块）号、块内地址并索引到Cache列表。
  2. 标记阵列：由Cache中每一行的标记项组成，每行标记项又包含：
    • 标记位：若干位
    • 有效位：1位，表示该Cache行是否存在对应主存块
    • LRU替换控制位：若干位，取决于一组多少路（若2路则1位，8路则3位），即用于LRU计数
    • 一致性位：1位，用于写回法的脏位
  3. 相联存储器：在用全相联或组相联时可能用到的一个中介表，每项包含主存块号到Cache行号的映射

置换算法（Cache、快表）

  • 最佳（OPT）置换算法：替换掉以后最长时间内不被访问的页面。
    • 保证获得最低缺页率，但不可能实现
  • 先进先出（FIFO）置换算法：替换掉最早进入内存的页面。
    • 可能会出现Belady异常：分配物理块数增大而页故障数不减反增的异常现象
  • 最近最久未使用（LRU）置换算法：替换掉最久没有使用过的页面。
  • 时钟（CLOCK）算法（最近未用算法）：每帧关联一个使用位（首次装入时、被访问时置为1）。
    1. 从指针处开始循环扫描（被扫过后置为0），选择遇到的第一个使用位为0的页面，同时指针指向下一帧。
  • 改进型CLOCK置换算法：每帧关联访问位、修改位（被访问时u=1，被修改时m=1）。
    1. 从指针处开始循环扫描（不做修改），选择遇到的第一个（u=0,m=0）的帧用于替换。
    2. 从指针处开始循环扫描（被扫过后u置为0），选择遇到的第一个（u=0,m=1）的帧用于替换。
    3. 若均失败，重复第一步、第二步（若第一步再次失败）

注意FIFO、LRU的画图顺序

文件管理

文件系统层次结构

2021计算机考研408操作系统个人笔记

  • 1层：用户调用结构：由新建、打开、读写、关闭、删除文件，建立、删除目录等程序模块组成，每个模块对应一条系统调用。

用户要查看文件F中的内容，于是通过用户调用接口对操作系统发出命令。

  • 2层： 文件目录系统：负责管理文件目录（管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织存储设备上的文件目录结构、调用下一级存取控制模块）

操作系统得到命令后，通过文件目录系统来查找目录以文件F的索引信息，可能是FCB，也可能是索引结点。

  • 3层：存取控制验证模块：实现文件保护（把用户访问要求和FCB中指示的访问控制权限进行比较）

通过目录找到文件FCB后，通过存取控制验证层把用户访问要求和FCB中指示的访问控制权限进行比较。用户通过验证后，就真正开始寻址了。

  • 4层：逻辑文件系统与文件信息缓冲区：根据文件逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号。

操作系统的寻址往往是先得到逻辑地址，再得到物理地址。于是在开始寻址的时候，操作系统经过了逻辑文件系统与文件信息缓冲区得到了相应文件的内容的逻辑地址；

  • 5层：物理文件系统：把逻辑记录所在的相对块号转换成实际物理地址。

把逻辑地址转换成物理地址，是在物理文件系统中完成的。

  • 6层：辅助分配模块：管理辅存空间，负责分配辅存空闲空间和回收辅存空间。
  • 6层：设备管理程序模块：分配设备、分配设备读写用缓冲区、硬盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等。

寻址完成以后，我们关心找到的这块空间应该如何管理。如果要释放这块空间，那么任务就交给辅助分配模块；如果要把这块空间分配给设备用于I/O，那么就把任务交给设备管理程序模块。

目录

  • 文件控制块（FCB）：存放控制文件所需的数据结构。
    • 基本信息：文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
    • 存取控制信息：文件存取权限等。
    • 使用信息：文件建立时间、修改时间等。
  • 文件目录：FCB的有序集合。
  • 索引结点：用于查找文件的数据结构（比起FCB简化了许多查找时不会用到的信息），存放在磁盘上则被称为磁盘索引结点。
    • 文件主标识符、文件类型、文件存取权限、文件物理地址、文件长度

目录结构

  • 单级目录结构：每个文件占一个目录项。
  • 两级目录结构：主文件目录、用户文件目录；一个用户占一个主文件目录表项，一个文件占一个用户文件目录表项；解决不同用户的文件重名问题，但仍缺乏灵活性，不能对文件分类。
  • 多级目录结构（树形目录结构）：每次访问都是相对于当前目录进行的；层次结构清晰、方便实现文件分类，但不便于文件共享；但是多级访问增加磁盘访问次数，影响查询速度。
  • 无环图目录结构：在树状目录结构基础上允许指向同一共享结点，共享节点存放共享计数器（为0时才真正删除该节点）；方便实现文件共享，但管理更加复杂。

目录实现

  • 线性列表：使用存储文件名和数据块指针的线性表。

    • I/O操作多，效率低

  • 哈希表：根据文件名得到一个值，并返回一个指向线性列表中元素的指针。

    • 查找迅速，插入、删除简单，可能发生冲突

为减少目录查询的I/O操作，应当把当前使用的文件目录复制到内存，以后要使用该文件时，只需在内存中操作，降低磁盘操作次数，提高系统速度。

文件共享

硬链接（基于索引结点）

引用资源时计数+1，删除时计数-1

软连接（基于符号链）

通过路径（符号链）引用资源，不改变计数。
以后要访问源文件发现该文件计数为0时才移除本连接

逻辑文件结构

无结构文件（流式文件）：

  • 无结构文件（流式文件）：无结构，访问记录只能通过穷举搜索的方式
    • 适用于源程序文件、目标代码文件等。

有结构文件（记录式文件）：

  • 顺序文件（顺序查找）：记录按一定顺序排列（记录通常定长，且可顺序/链式存储），访问记录通过顺序搜索

    • 顺序读写一大批记录最为高效，但增删查改单条记录的效率比较低。

  • 索引文件（索引查找）：建立索引表（本身是定长记录的 顺序文件），所有表项按存放顺序存放各个记录的长度（实际上等同于每项指向一个记录地址）

    • 提高查找效率，但增加了存储空间。

  • 索引顺序文件（顺序索引查找）：建立索引表（本身是定长记录的 顺序文件），所有表项按关键字存放各个记录的逻辑地址（实际上等同于每项指向若干个已排序记录的首地址）

    • 提高查找效率，但增加了存储空间。

  • 直接文件（散列文件、哈希查找）：通过给定键值和散列函数直接决定记录的物理地址

    • 无顺序特性；有很高的存取速度，但可能有冲突。

物理文件结构

文件分配方式

  • 连续分配：连续分配方式，目录项记录起始盘块和长度。

2021计算机考研408操作系统个人笔记

  • 隐式链接分配：离散分配方式，每个盘块额外包含指向下一个盘块的指针。

2021计算机考研408操作系统个人笔记

  • 显式连接分配（FAT方法）：离散分配方式，将链接各物理块的指针显式地存放在内存中的一张链接表（文件分配表、FAT）中，在系统启动时便被读入内存，减少了磁盘访问次数。

2021计算机考研408操作系统个人笔记

  • 索引分配：把一个文件的所有盘块号集中放在位于某个硬盘块的索引块（索引表）

    可能文件过大，单个索引块不能容纳时：

    • 链接方案：多个索引块，每个索引块用指针链接起来。
    • 多级索引：第一层索引块指向第二层索引块...最后一层索引块指向文件快
    • 混合索引（高频考点）：多种索引分配方式结合，入既采取直接地址，又单级索引分配方式或两级索引分配方式。

2021计算机考研408操作系统个人笔记

通常打开文件后，将文件索引块读入内存缓冲区中，以加快文件访问速度。

打开文件表：使用open（参数为文件名）会首先在打开文件表中寻找是否存在已经打开的文件，否则把文件名传给文件系统搜索目录，让文件系统找到文件后把该文件FCB复制到打开文件表里。文件名不必是打开文件表的一部分（一旦完成对FCB在磁盘上的地位，就没必要使用文件名），而是用访问打开文件表的索引（UNIX->文件描述符，Windows->文件句柄）。

访问第N条记录 优点 缺点
连续分配 需访问1次硬盘 顺序存取速度快，有效支持直接访问、随机访问 要求连续存储空间，会产生外存碎片，不利于文件动态扩充
隐式链接分配 需访问N次硬盘 动态增长较方便，解决外存碎片 只能按指针链顺序访问，查找效率低；指针信息额外增加存储空间开销
显式链接分配（FAT） 需访问1次硬盘 动态增长较方便，解决外存碎片，有效支持直接访问 只能按指针链顺序访问，查找效率低；指针信息额外增加内存空间开销
索引分配 m级需访问m+1次硬盘 文件易于增删，解决外存碎片，有效支持直接访问、随机访问 索引表增加存储空间开销，索引表查找策略对文件系统影响效率较大

注意：文件的逻辑结构是用户可见的结构，即用户使用文件的结构。文件的物理结构是文件在存储器上的组织结构，它表示一个文件在辅存上安置、链接、编目的方法，与文件存取方法以及辅存系统设备特性有着密切联系。例如，逻辑结构是顺序结构，物理结构是隐式链接结构，即使理论上很快找出某条记录的地址，实际上找时仍需要在磁盘上一块一块地找。

文件存储空间管理

  • 空闲表法：建立一张空闲盘块表，与内存分配空闲表类似；同样可以用首次适应、循环首次适应等算法。
  • 空闲链表法：分为空闲盘块链、空闲盘区链；都用指针链接起来，前者以空闲块为单位，后者以若干个连续的空闲块为单位；通常采用首次适应算法。
  • 位示图法：用二进制的一位来表示磁盘的一个盘块使用情况，0为空闲，1为已分配。分配时，顺序扫描位示图，找到第一个为0的位置并置1，并根据位置得到盘块号。（注：行列号均从下标1开始）
  • 成组链接法：空闲扇区存储n个空闲扇区的地址和下一空闲扇区的地址。解决空闲表法、空闲链表法不适用大型文件系统的问题，其中UNIX系统采用成组链接法。

2021计算机考研408操作系统个人笔记

上一篇：从PRISM开始学WPF（九）交互（完结）


下一篇：2022考研王道计算机408（王道计算机组成原理+王道操作系统+王道计算机网络+王道数据结构）