操作系统: 期末复习

Posted on Edited on In , Word count in article: 5.5k Reading time ≈ 20 mins.

操作系统复习

概述

计算机启动(Boot)

  • 分为四个阶段，第一阶段为BIOS(Basic Input/Output System)
    • 硬件自检(Power-On Self-Test，即POST)
    • BIOS将控制权交给下一个启动程序，启动的顺序被存储在外存中
  • 第二阶段：主引导记录(Master Boot Record，即MBR)，是某个硬盘第零柱面的第一扇区
    • 将控制权转让，即BIOS读取MBR并将其放入内存，并通过MBR得知操作系统的具体分区
    • 如果此时拥有控制权的设备不能用于启动(在MBR中有特殊标注)，则按顺序继续转让控制权，继续读取下一个设备的MBR
    • 当计算机有启动管理器这个程序时，计算机在转让控制权时会由用户决定
  • 第三阶段：硬盘启动
    • 当找到可以用于启动的硬盘时，也就知道了操作系统的具体分区，计算机会读取这个分区的卷引导记录(Volumn Boot Record，即VBR)，即这个分区的第一个扇区 计算机就可以精确地找到操作系统的位置并加载
  • 第四阶段：操作系统
    • 系统内核先被加载，然后运行init进程，直到运行login进程让用户登录

OS的目的和发展

  • 在最初没有OS，输入、输出完全由手工操作时，每个任务由操作人员准备和放入，效率低下 OS出现的目的是提高系统资源利用率，增加系统吞吐量，以至于到后来提供方便性(对用户方便)、可扩充性(对扩充新模块方便)、开放性(对不同计算机的程序的移植方便)
  • 单道批处理：用户事先放入多个同类作业，由监控程序整理为一批作业串行执行 但当作业无法继续运行时，它不会放弃CPU，导致仍存在系统资源的浪费
  • 中断和通道技术的出现(进入集成电路时代)，推动了现代意义上操作系统的出现 发展为多道程序批处理系统，主存中可同时存在多个作业，CPU在其中切换 实现了一定程度的并发，即不同进程交替占用CPU运行，实现了微观上串行、宏观上并行的效果 但人机脱离，没有交互性
  • 分时操作系统：相比多道程序批处理系统，分时操作系统是联机的、多用户的、交互的操作系统，具有交互性、多用户同时性、独立性、及时性 Unix是典型的分时系统
  • 实时操作系统：强调可靠性和实时性，通用性差，专用于有实时控制需求的场景 分为硬实时和软实时，硬实时保证在限定的时间内完成任务，软实时并不保证这一点但也不允许过多地超过规定时间

操作系统服务

  • 用户接口：CLI、GUI等
  • 进程管理：对进程进行调度
  • 存储管理：针对内存进行存储分配、存储共享、存储保护(越界发生中断)、存储扩张(虚存)
  • 设备管理：管理I/O设备
  • 文件管理：文件存储管理、目录管理、文件操作管理、文件保护
  • 通信服务：同一机器上不同进程的IPC和不同计算机上的IPC
  • 资源分配
  • 错误检测
  • 统计
  • 保护和安全

操作系统的结构

系统调用

  • 操作系统分为两种模式：内核模式和用户模式，通过CPU状态位帮助OS判断现在CPU处于管态(内核态)或目态(用户态)，目态相比于管态，无法执行一些特定的指令 若发生中断或错误，系统会自动切换到管态来执行中断处理程序
  • 系统调用是内核暴露给用户的原始接口，用户可通过系统调用申请内核的服务，内核调用的实现是通过软中断或syscall指令使用户态切换到内核态执行内核态的特殊指令和内核函数，执行完毕后再切换回用户态
  • API是应用程序接口，也即在内核之上的库例程，是用高级语言编写的更高级的封装接口，可能完全在用户空间运行，也可能封装了系统调用 用户通常用API编写程序，因为API类似一个中间件，使程序具有更强的可移植性、更直观
  • 系统调用的传参方式：寄存器传参(限制参数个数)、内存块传参、堆栈传参

POSIX API

  • POSIX全称Portable Operating System Interface of UNIX，即针对所有类UNIX系统的可移植操作系统接口，它是一套标准
  • pid_t fork()：头文件unistd.h，用于创建一个子进程
    • fork()执行一次，创建一个子进程，向父进程和子进程均返回pid_t值
    • 对父进程的返回值一定不等于零，若小于零说明创建失败，若大于零则是子进程的pid
    • 对子进程的返回值一定等于零，子进程会采用写时拷贝的方式复制父进程的堆栈和数据段，只共享代码段且PC均指向fork()的下一条指令
    • 在不使用wait()的情况下，父进程和子进程的执行顺序是未定的，如果父进程提前结束，子进程将挂靠在父进程的父进程上
  • pid_t wait(int* stat_loc)：头文件sys/types.h和sys/wait.h，使父进程阻塞，直至所有子进程执行完毕后唤醒
    • stat_loc若不为空指针，wait()会将子进程的结束状态赋给stat_loc指向的整型变量 一般用法不关心子进程的结束状态，会使用wait(NULL)
  • void exit(int status)：头文件stdlib.h，用于以状态码status结束当前进程

简单bash shell

  • chmod

进程和线程

进程的概念

  • 进程和程序的本质区别是动态性，进程相当于程序、PCB、数据的组合体 此外，进程还具有并发性、独立性、异步性

    • 并发性：多个进程在宏观上并行执行的现象
    • 独立性：进程是资源分配、调度的基本单位
    • 异步性：不同进程的执行通常不需要按相同的节奏推进

  • 具体来说，进程包含代码段、数据段、堆、栈、PC 其中，全局变量存放在数据段中，局部变量存放在栈中，动态分配内存的变量存放在堆中

  • 进程状态模型： 

    graph LR
Ready(就绪) -->|调度| Run(运行) -->|时间片结束或被抢占式调度算法中断| Ready
Run -->|处理I/O或等待事件发生| Wait(阻塞) -->|I/O完成或事件发生| Ready

    graph LR
Ready(就绪) -->|调度| Run(运行) -->|时间片结束或被抢占式调度算法中断| Ready
Run -->|处理I/O或等待事件发生| Wait(阻塞) -->|I/O完成或事件发生| Ready
Wait <--> SuspendWait(挂起阻塞)
Ready <--> SuspendReady(挂起就绪)
Run --> SuspendReady
SuspendWait --> SuspendReady

  • 进程上下文切换

    • 指CPU切换到另一个进程时，保存原来进程状态、并加载新进程的状态的过程
    • 涉及到用户级上下文(用户代码段、用户数据段、用户堆栈)、寄存器上下文(PSW程序状态寄存器、栈指针、通用寄存器)、系统级上下文(PCB、内存区表、内核栈)

  • CPU调度层次：

    • 长期调度、作业调度：选择作业载入内存的就绪队列
    • 中期调度、平衡负载调度：通过交换技术，将内存中的进程换出或将挂起的进程换入，缓解内存空间压力
    • 短期调度、进程调度：选择一个处于就绪队列的进程占有CPU执行

  • 引起进程阻塞的原因：

    • 请求系统服务
    • 无新工作可做(例如无工作可做的系统进程)

  • 调度是一个系统服务，其本质是执行一个系统调用schedule()，正如之前所说执行系统调用是通过软中断或syscall指令进行，执行系统调用相当于执行一个中断处理程序，所以进程执行系统调用和陷入内核态不属于进程的调度 而通常在实现上，从内核态返回用户态时，会发生一次调度，原因大概是为了减少上下文切换的开销，在执行完系统调用后返回用户态前顺便进行一次schedule()，能减少因“返回用户态后立刻因为时间片结束或新进程到达导致再次被中断进行调度”造成的开销

IPC

  • IPC：Inter-Process Communication，进程间通信
  • 低级通信：用于传递控制消息，用互斥锁、信号量实现
  • 高级通信：用于传输数据，用管道、消息队列、共享内存实现

线程概念

  • 为了减少因进程调度产生的上下文切换开销，将调度的基本单位设置为进程内的若干执行序列，并将其称为线程
  • 线程和进程的区别：
    • 在引入线程后，进程仍是资源分配的基本单位，线程是系统调度的基本单位
    • 同一进程下的不同线程共享代码段、数据段，每个线程有自己的堆栈、PC、寄存器集
    • 线程切换的开销小于进程切换的开销
    • 线程间共享比进程间共享更简单
    • 线程的引入提高了并发性，使得一个进程的不同计算任务也可以并发推进
  • 用户级线程：操作系统内核不支持线程，进程通过线程库来实现多线程编程的情况
    • 若进程的一个线程进入阻塞，则所有其它对等线程也进入阻塞
    • 同一进程的不同线程的切换不需要经过内核，切换时间短
    • 一个进程含有多个线程不会增加整个进程的执行时间
  • 内核级线程：操作系统内核支持线程
    • 一个线程的阻塞不会影响其它线程的状态
    • 线程切换时需要中断并执行系统调用，切换开销大
    • 多线程编程下，一个进程的执行时间更长
  • 多线程模型：
    • 多对一：多个用户级线程映射到一个内核级线程
    • 一对一：每个用户级线程都对应一个内核级线程
    • 多对多：多个用户级线程对应相同个或更少的内核级线程
    • 二级模型：允许多对多和一对一映射

进程调度

  • 进程调度即短期调度，指从就绪队列中选择一个进程，将CPU控制权分配给它
  • 调度时机：
    • 进程从运行态到阻塞态 进程结束 均为非抢占的，进程自愿放弃CPU
    • 进程从运行态到就绪态 进程从阻塞态到就绪态 均为抢占的，进程被迫放弃CPU、进程根据先到先得的方式获得非CPU资源
  • 进程调度算法：
    • 先来先服务：优先考虑等待时间
    • 最短作业优先(SJF)：非抢占、存在饥饿
    • 最短剩余时间优先(SRTF)：抢占、存在饥饿
    • 最高响应比优先(HRF)：$\begin{align}R=\frac{W+T}{T}\end{align}$，周转时间(等待时间加运行时间)除以运行时间，同时考虑等待时间和运行时间
    • 轮转法(RR)
    • 最高优先级调度：静态优先级存在饥饿现象
    • 多级反馈轮转法：现代操作系统采用的方式，分为多个优先级的队列，每个队列内部采用轮转法

进程互斥与同步

  • 临界资源：多个进程共享但同一时间只允许一个进程访问的资源

  • 互斥：一组并发进程由于共享某些资源，导致它们的临界区不允许交替执行

  • 同步：一个进程的输出作为另一个进程的输入，导致它们有执行的先后顺序

  • 临界区三大要求：互斥、空闲让进、有限等待

  • 互斥软件解法(面包店算法)：进程先取号，在已经取号的进程里面，根据(取得的号，进程id)元组从小到大的顺序访问临界资源

  • 互斥硬件解法(原子操作TestAndSet())

  • 信号量的两种实现：

    • 自旋锁：进程会循环申请锁，出现忙等现象，这在多处理器环境或只需要短时间占有锁的情况下是有益的，不会导致频繁的切换上下文导致巨大开销
    • 非自旋锁：进程如果无法申请锁，则会进入对应的阻塞队列并阻塞，在单处理器情况下是常用的

  • 互斥信号量的P操作必须紧贴临界区，V操作无所谓

  • 读者写者问题：可同时读-读、不可同时读-写、写-写 定义读信号量S、写信号量X、共享变量r_cnt表示读者个数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    // 读者
    while (1) {
        P(S);
        ++r_cnt;
        if (r_cnt == 1) {	// 此前没有读者, 需要保证当前没有写者
            P(X);
        }
        V(S);
        /* 读取操作 */
        P(S);
        --r_cnt;
        if (r_cnt == 0) {	// 现在没有读者了, 释放写锁
            V(X);
        }
        V(S);
    }
    // 写者
    while (1) {
        P(X);
        /* 写操作 */
        V(X);
    }

    类似这种A类进程间有互斥关系、A和B类进程间有互斥关系、B类进程间没有互斥关系，需要用共享变量统计B类进程的个数并用信号量维护 同理，如果A类进程间也没有互斥关系，也要用一个共享变量和信号量统计并维护A类进程个数 然后用一个互斥信号量维护资源的个数

进程死锁

  • 四大方式：死锁预防、死锁避免、死锁检测、死锁恢复
  • 死锁的根本原因：资源不足
  • 死锁预防是预防发生死锁的四大必要条件：互斥、占有并等待、不可抢占、循环等待
    • 解决占有并等待：进程必须一次性获取所有资源才可分配，即静态资源分配
    • 解决不可抢占：如果进程申请资源失败，则要释放所有已占有的资源
    • 解决循环等待：对不同类资源进行编号，进程按照资源编号递增的顺序申请资源，即有序分配资源
  • 死锁避免：进程申请资源分配时，动态执行银行家算法判断分配后是否仍属于安全状态，若属于则允许分配
    • 进程需要事先说明最大所需资源数
  • 现代操作系统的做法是：允许进入死锁，及时进行死锁检测并恢复
    • 死锁检测：画出资源分配图看进程之间是否存在环，实际上就是执行银行家算法
    • 死锁恢复：终止引起死锁的进程或剥夺其占有的所有资源

内存管理

绑定内存地址时机

  • 重定位：将逻辑地址转化为物理地址的过程
  • 编译时期绑定：内存位置已知，可执行文件中存放的地址就是内存中的地址
  • 装入时期绑定：内存位置未知，可执行文件中存放的地址是逻辑地址，加载到内存时才进行重定位，转化为物理地址
  • 运行时期绑定(动态地址重定位)：内存位置未知，可执行文件中、装入内存后的地址均为逻辑地址，只在执行指令时通过基地址寄存器BR和程序虚拟地址寄存器VR(文件中存储的逻辑地址)算出

存储管理方案

  • 单一连续分配：出现在单道程序操作系统中，不需要考虑多个进程同时装入内存
  • 分区管理方案
    • 固定分区：存在内部碎片和外部碎片
    • 动态分区：存在内部碎片
  • 页式管理方案：将内存分帧、进程空间分页，页和帧大小一致且固定
    • 只在进程的最后一页可能存在内部碎片
    • 不利于进程共享代码
    • 对用户来说，进程的空间是一维线性空间，只需要提供一个逻辑地址就可以由硬件自动完成映射
    • 优化页表访问：TLB，即Translation Lookaside Buffer，地址转换后备缓冲
  • 段式管理方案：支持由用户观点划分程序段，相当于将大进程分为多个小进程进行动态分区管理
    • 存在外部碎片
    • 对用户来说，进程的空间是二维线性空间，用户需要同时提供段号、段内偏移
    • 优化段表访问：快表
  • 段页式管理方案：在段式的基础上，将段内偏移分为了页号、页内偏移 先通过段表地址寄存器访问段表，获取段号对应的页表位置；再访问页表获取页号对应的页面号；再加上页内偏移计算出物理地址

动态存储空间分配

  • 最先适配法：按可用空间的起始地址从小到大匹配
  • 最好适配法：按可用空间的大小从小到大匹配，容易出现极小的外部碎片，每次都要重新调整可用表
  • 最坏适配法：按可用空间的大小从大到小匹配，每次都要重新调整可用表

虚拟内存

  • 实现方式：按需调页和按需调段
  • 页表每个页添加有效位表示是否有对应的物理页面，访问无效页时，发生缺页中断
  • 访问无效页时的缺页中断处理时，如果在内存中不存在空闲的页面，则进行页面替换，页面替换算法有：
    • FIFO：淘汰最先进入内存的页 存在Belady现象，即内存页面数增加时反而导致缺页次数增加的现象
    • OPT：淘汰在未来，最久不会被使用的页 这个算法是最优的，但无法实现
    • LRU：最近最少使用，即淘汰内存中最久没被使用过的页，实现为每次命中时将页移至队尾，淘汰时替换掉队头的页 利用局部性原理，根据调用历史模拟OPT算法
    • LRU近似算法——二次机会算法(Clock)：所有页添加引用位(初始为1)，淘汰时循环检查队列，若引用位为1则忽略并置0(给予二次机会)
    • LRU近似算法——增强型二次机会算法(E-Clock)：添加脏位，循环检查队列，先找vis=0,dirt=0的页 若找不到，则找vis=0,dirt=1的页，将所有遇到的页vis置0 若仍找不到，则再找vis=0,dirt=0的页，由于第二部将vis置0，故一定能找到一页
  • 用户进程内存分配：
    • 固定分配(平均或比例分配)、优先级分配
    • 颠簸现象：进程没有足够的帧时，页可能会频繁地在内存、外存之间调度 解决方法：增加物理内存页面数，修改页面替换算法，降低多道程序数量
  • 内核进程内存分配：
    • Buddy系统：固定分区分配，分区大小一定为2的幂，最小分区是一页
    • Slab系统：以slab为最小单位

文件系统

文件系统层次

  • 用户接口
  • 目录系统
  • 虚拟文件系统(VFS)：统一的文件系统访问接口
  • 磁盘调度系统

文件概念

  • 文件系统功能：按名存取、文件共享
  • 逻辑结构：无结构文件(流式文件)、有结构文件(记录式文件)
  • 文件访问方法：顺序存取(磁带)、随机存取(磁盘)、按键存取(索引文件)

目录系统

  • 单级目录、双级目录(主文件目录、用户文件目录)、树状结构目录、无环图结构目录
  • 树状：支持文件分组、快速检索

空间分配方法(文件的物理结构)

  • 连续空间分配、链接式分配、索引分配(在链接式分配的基础上，将所有指针存放在一个物理块中，称为索引表)
  • 文件存储空间通过空闲文件目录或空闲块链或位示图管理

磁盘调度系统

  • FCFS
  • SSTF：最短寻道时间优先，类似OPT，最好但难以实现
  • SCAN：又称电梯算法，按固定方向扫描并处理沿途请求，到达另一端后反向扫描，以此循环
  • C-SCAN：按固定方向扫描并处理沿途请求，到达一端后立刻返回另一端(时间忽略不计)，继续沿原有方向扫描，等待时间更均匀
  • LOOK和C-LOOK：记录请求柱面号的最小值和最大值，与SCAN和C-SCAN的区别是不会移动到磁盘的尽头而是移动到最小值或最大值

I/O设备管理

中断分类

  • 硬中断：
    • 外部中断(中断)：DMA申请的中断、用户发起的中断等
    • 内部中断：
      • 陷阱：有意的中断，如系统调用
      • 故障：可恢复的错误引起的中断，如缺页中断
      • 终止：不可恢复的错误引起的中断，如除以零
  • 软中断