操作系统

操作系统知识模块主要分为：操作系统概述、进程管理、内存管理、文件管理、输入/输出(I/O)管理。

1.操作系统概述

操作系统（Operating System，OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源分配，以提供给用户和其他软件方便的接口和环境的程序集合。
操作系统的基本特征包括：并发、共享、虚拟和异步。

• 并发是指两个或多个事件在同一时间间隔内发生。

• 虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。操作系统的虚拟技术可归纳为：时分复用技术，如处理器的分时共享；空分复用技术，如虚拟存储器。

• 异步是指在多道程序环境下，允许多个程序并发执行，但由于自由有限，进程的执行不是一贯到底，而是走走停停，以不可知的速度向前推进，这就是进程的异步性。

2.进程管理

进程：

目的：更好地描述和控制程序并发执行；

定义：进程是进程实体的一次运行，是系统进行资源分配和调度的一个独立单位；

组成：

• PCB：保存进程运行期间相关的数据，是进程存在的唯一标志
• 程序段：能被进程调度程序调度到CPU运行的程序代码段
• 数据段：存储程序运行期间的相关数据，可以是原始数据也可以是相关结果

进程状态：

• 状态种类：

  • 运行状态：进程正在处理机上运行
  • 就绪状态：进程已获得除处理机之外的一切所需资源
  • 阻塞状态：进程正在等待某一事件而暂停运行
  • 创建状态：进程正在被创建，尚未转到就绪状态
    • 创建完成后转到就绪状态
  • 结束状态：进程正从系统中消失，分为正常结束和异常退出

• 状态变化：

  • 就绪->运行：经过处理机调度，就绪进程得到处理机资源
  • 运行->就绪：时间片用完或在可剥夺系统中有更高优先级进程进入
  • 运行->阻塞：进行需要的某一资源还没准备好
  • 阻塞->就绪：进程需要的资源已准备好

进程控制：

• 创建：终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等；
• 终止：正常结束、发生异常、外界干预
• 阻塞：等待资源
• 唤醒：资源到达
• 切换：时间片用完、主动放弃处理机、被更高优先级的进程剥夺处理机

进程通信：

• 共享存储：
  • 低级方式：基于数据结构的共享
  • 高级方式：基于存储区的共享
• 消息传递：
  • 直接通信方式：直接把消息挂到接收进程的消息队列
  • 间接通信方式：挂到某个中间实体，接收进程找实体接收消息，类似电子邮件
• 管道通信：利用一种特殊的pipe文件连接两个进程

代价：

• 时间代价：进行进程间的切换、同步及通信等所付出的时间开销
• 空间代价：进程控制块及协调各运行机构所占用的内存空间开销

线程：

• 引入目的：为了更好的使多道程序并发执行，以提高资源利用率和系统吞吐量，增加并发程序
• 特点：是程序执行的最小单元，基本不拥有任何系统资源
• 实现方式：用户级线程、系统线程

调度：

调度层次：

• 作业调度（高级调度）：选择处于后备状态的作业分配资源，发送频率低
• 内存调度（中级调度）：选择暂时不能允许的进程调出内存，发送频率中等
• 进程调度（低级调度）：选择就绪队列中合适的进程分配处理机，发生频率高

进程调度原因：合理的处理计算机软硬件资源

进程调度方式：

• 剥夺式：有更为重要或紧迫的进程需要使用处理机，立即分配
• 非剥夺式：有更为重要或紧迫的进程需要使用处理机，仍让当前进程继续执行

典型调度算法：

• 先来先服务：选择最先进入队列的
  • 不可剥夺
• 短作业优先：选择完成时间最短的
• 优先级调度：选择优先级最高的
• 高响应比优先：选择响应比最高的
  • 响应比Rp = (等待时间+要求服务时间) / 要求服务时间
• 时间片轮转：总数选择就绪队列中的第一个进程，但仅能运行一个时间片
  • 绝对可抢占
• 多级反馈队列：时间片轮转调度算法和优先级调度算法的综合和发展

进程同步：

引入原因：协调进程之间的相互制约关系

制约关系：

• 同步：需要在某些位置上协调进程之间的工作次序而等待、传递信息所产生的制约关系
• 互斥：当一个进程进入临界区使用临界资源时，其他要求进入临界区的进程必须等待

临界资源：多个进程可以共享系统中的资源，一次仅允许一个进程使用的资源叫临界资源；

临界区互斥：访问临界资源的那段代码称为临界区

• 原则：空闲让进、忙则等待、有限等待、让权等待
• 基本方法：
  • 软件实现：
    • 单标志法：违背”空闲让进“原则
    • 双标志法先检查：违背”忙则等待“原则
    • 双标志法后检查：会导致”饥饿“现象
    • 皮特森算法：单标志法和双标志法后检查的结合
  • 硬件实现：
    • 中断屏蔽法：进区关中断，出区开中断
    • 硬件指令法：设立原子操作指令
  • 信号量：利用PV操作实现互斥
    • P操作即wait(S)
    • V操作即signal(S)

管程：

• 定义：由一组数据以及定义在这组数据上的对这组数据的操作组成的软件模块
• 组成：
  • 局部于管程的共享结构数据（变量）说明
  • 对该数据结构进行操作的一组过程
  • 对局部于管程的共享数据设置初始值的语句，此外还需要为管程赋予一个名字
• 引入管程的目的：解决临界区分散所带来的管理和控制问题。在没有管程之前，对临界区的访问分散在各个进程之中，不易发现和纠正分散在用户程序中的不正地使用P、V操作等问题。管程将这些分散在各进程中的临界区集中起来，并加以控制和管理，管程一次只允许一个进程进入管程，从而便于系统管理共享资源，又能保证互斥。

死锁：

产生原因：非剥夺资源的竞争和进程的不恰当推进顺序

定义：多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进

解决方案：

• 预防死锁：

  • 破坏互斥条件：
  • 破坏不可剥夺条件：
  • 破坏请求和保持条件：
  • 破坏循环等待条件：

• 避免死锁：

  • 安全状态：能找到一个分配资源的序列能让所有进程都顺利完成
  • 银行家算法：采用预分配策略检查分配完成时系统是否处于安全状态

• 检测死锁：利用死锁定理化简资源分配图以检测死锁的存在

  • 资源分配图：
    • 圆圈代表进程；
    • 框中的一个点代表一类资源中的一个资源；
    • 进程到资源的有向边叫请求边；

    • 资源到进程的边叫分配边；

      
      
      资源分配图.png

• 解除死锁：

  • 资源剥夺法：挂起某些死锁进程并抢夺它的资源，以便让其他进程继续推进
  • 撤销进程法：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源
  • 进程回退法：让进程回退到足以回避死锁的地步

算法：

• 银行家算法为死锁避免算法；
• 死锁检查算法和资源分配图化简法为死锁检测；
• 资源有序分配算法为死锁预防策略；

所谓CPU繁忙型的作业，是指该类作业需要大量的CPU时间进行计算，而很少请求I/O操作。I/O繁忙型的作业是指CPU处理时，需频繁的请求I/O操作。

周转时间 = 作业完成时间 - 作业提交时间；

平均周转时间 = （作业1的周转时间 + ... + 作业n的周转时间）/ n ；

带权周转时间 = 作业周转时间 / 作业实际运行时间；

平均带权周转时间 = （作业1的带权周转时间 + ... + 作业n的带权周转时间）/ n；

响应比Rp = (等待时间 + 要求服务时间) /要求服务时间；

3.内存管理

内存管理：

引入目的：更好的支持多道程序并发执行，提升系统性能

程序的编译：由编译程序将用户源代码编译成若干个目标模块；

程序的链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块；

• 静态链接：在程序运行之前链接
• 装入时动态链接：在装入内存时，采用边装入边链接的链接方式
• 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接

程序的装入：由装入程序将装入模块装入内存运行；

• 绝对装入：适合单道程序环境

• 静态重定位：适合装入之后不再移动的情况

• 动态重定位：适合装入之后还会移动的情况

地址空间：

• 逻辑地址空间：是指一个源程序在编译或者链接装配后指令和数据所用的所有相对地址的空间；
• 物理地址空间：内存中物理单元的集合；

地址重定位：通过地址转换将逻辑地址转换为物理地址。

内存保护：

• 上、下限寄存器：分别与上、下限寄存器比较
• 基址、限长寄存器：与限长寄存器比较，与基址寄存器相加

管理方式：

• 连续分配：产生内部碎片；用户进程（或作业）在主存中都是连续存放的
  • 单一连续分配：分配到内存固定区域，只适合单任务系统；
  • 固定分区分配：分配到内存中不同的固定区域，分区可以相等也可以不等；
    • 产生内部碎片
  • 动态分区分配：
    • 产生外部碎片
    • 基本概念：按照程序的需要进行动态的划分
    • 分配算法：
      • 首次适应：空闲区按地址从小到大为序，分配第一个符合条件的分区；
      • 最佳适应：空闲区按空间大小从小到大排序，分配第一个符合条件的分区；
      • 最坏适应：空闲区按空间从大到小排序，分配第一个符合条件的分区；
      • 邻近适应：空闲区按地址地址递增的次序排列，分配内存时从上次查找结束的位置开始继续查找；
• 非连续分配：允许一个程序分散地装入到不相邻的内存分区中，需要额外的空间去存储分散区域的索引
  • 基本分页：内存分为固定的块，按物理结构划分，会有内部碎片；
    • 主存、进程都划分为大小固定的块，进程在执行时，以块为单位申请主存中的块空间；
    • 进程中的块为页，内存中的块为页框。系统为每个进程建立一张页表，页表记录页面在内存中对应的物理块号，实现从页号到物理块号的地址映射；
    • 页式管理中地址空间是一维的；
  • 基本分段：内存块的大小不固定，按逻辑结构划分，会有外部碎片；
    • 段式管理方式按照用户进程中的自然段划分逻辑空间。段内要求连续，段间不要求连续。段号和段内偏移量必须由用户显示提供。
    • 方便编程、共享、保护、动态链接和增长。
  • 段页式：基本分段和基本分页的结合，会有内部碎片；
    • 作业的逻辑地址分为：段号、页号和页内偏移量；采用分段方法来分配和管理用户地址空间，采用分页方法来管理物理存储空间；开销大。
  • 请求分页存储管理：采用虚拟技术，开始运行时不必将作业全部一次性装入内存；
  • 多级页表：将页表的10页空间也进行地址映射，建立上一级页表，用于存储页表的映射关系；

多道程序下的内存扩充：

• 覆盖：预先设定覆盖段，覆盖掉暂时不用的内容，通常在同一个程序之中进行；
• 交换：把处于等待的程序暂时移到外存，通常在不同程序之间进行；
• 虚拟内存：只能基于非连续分配技术。
  • 引入原因：在逻辑上扩充内存
  • 时间局部性：程序中存在着大量的循环操作；
  • 空间局部性：程序在一段时间内所访问的地址，可能集中在一定的范围内；
  • 组成部分：
    • 页表机制：通过查表获取相关信息；
    • 中断机制：要访问页不在内存时产生缺页中断
    • 地址变换机构：把逻辑地址变换成物理地址
    • 内存和外存：需要一定容量的内存和外存支持
  • 置换算法：
    • 最佳置换算法（OPT）：选择以后不用的页面
    • 先进先出（FIFO）：选择最先装入的页面
    • 最近最久未使用（LRU）：选择最近最近未使用的页面
    • 时钟置换算法（最近未用算法）：选择最近未用的页面
    • 改进型CLOCK：考虑页面修改问题
  • 地址翻译：TLB->页表（TLB不命中）->Cache->主存->外存

页面分配策略：

• 固定分配局置换：每个进程分配一定数目的物理块，在整个运行期间不变，缺页时只在该进程在内存中的页面中进行置换；
• 可变分配全局置换：为每个进程分配一定数目的物理块，操作系统自身也保持一个空闲物理块队列；
• 可变分配局部置换：若进程在运行中频繁地缺页，系统再为该进程分配若干物理块；

抖动（颠簸）：

• 刚换出的页面马上又要换入内存；刚换入的页面马上就要换出内存；

工作集（驻留级）：

• 指在某段时间间隔内，进程要访问的页面集合。

虚拟内存空间大小：

• <=内存容量和外存容量之和
• <=计算机的地址位数能容纳的最大容量

虚拟存储的页表项：

• 页号
• 物理块号
• 状态位P：用于指示该页是否已调入内存，供程序访问参考；
• 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时参考；
• 修改位M：标识该页在调入内存后是否被修改过；
• 外存地址

Belady现象：进程的缺页次数随着分配给进程的页框个数的增加而增加，只有FIFO队列式页面置换算法才有。

页式地址变换.png

快表（联想寄存器TLB）：用来存放当前访问的若干页表项，以加速地址变换的过程，若所需访问页号在快表中则可减少一次内存访问。

4.文件管理：

文件控制块（FCB），类似进程管理的PCB，存放控制文件需要的各种信息的数据结构。

• 基本信息：包括文件物理位置
• 存取控制信息
• 使用信息
• 索引结点

一个文件对应一个FCB，而一个文件目录项就是一个FCB。

打开文件操作是讲该文件的FCB存入内存的活跃文件目录表，而不是将文件内容负责到主存，找到指定文件目录是打开文件之前的操作。

文件系统基础：

逻辑结构：

• 无结构文件（流式文件）：将数据按顺序组织成记录并积累保存，（流式文件）则被看成是一个字符流，以字节（Byte）为单位；
• 有结构文件：
  • 顺序文件：
    • 串结构：记录之间的顺序与关键字无关
    • 顺序结构：记录之间的顺序与关键字有关
  • 索引文件：为变长文件建立索引表，提高查找速度
  • 索引顺序文件：顺序文件和索引文件的结合，将顺序文件中的所有记录分为若干组，为顺序文件建立一张索引表，在索引中为每组的第一个记录建立一个索引项，其中含有该记录的关键字值和指向该记录的指针
  • 直接文件（查找文件）Hash File：通过哈希函数直接决定记录地址

目录结构：

• 单级：全部文件都放在一个目录下
• 两级：在目录下分出用户目录
• 多级：将两级结构加以推广，采用树形结构
• 无环图：在树形结构上加入一些有向边，便于共享

文件共享：

• 基于索引结点（硬链接）：共享文件指向同一个索引节点；链接计数count；
• 基于符号链（软链接）：有文件拥有者才拥有指向其索引结点的指针，共享该文件的其他用户则只有该文件的路径；

文件保护：

• 口令保护：通过口令访问文件
• 加密保护：对文件进行加密处理
• 访问控制：根据访问者的身份进行限制

文件系统实现：

目录实现：

• 线性列表：
  • 无序：查找文件较慢，新建文件较快
  • 有序：查找文件较快，新建文件较慢
• 哈希表：查找、新建文件都较快，要处理冲突

文件实现：

• 连续分配：在磁盘上连续存放文件

• 链接分配：

  • 隐式：采用类似链表的结构
  • 显示：把隐式文件中的指针单独抽离出来

• 索引分配：每个文件所有的盘块号都集中存放，建立索引表

存储空间管理：

• 空闲表：把所有空闲块组织成表
• 空闲链表法：把所有空闲块组织成链表
• 位示图：利用二进制的每位记录空闲块
• 成组链接：空闲表和空闲链表的结合，适合大的文件系统

磁盘管理：

磁盘地址结构：柱面号、盘面号、扇区号

读写时间：

• 寻道时间：将磁头移动到指定磁道所需要的时间
• 延迟时间：磁头定位到某一磁道的扇区所需要的时间
• 传输时间：从磁盘读出或向磁盘写入数据所经历的时间
• 启动时间（一般忽略）：控制器的启动时间

调度算法：

• 先来先服务（FCFS）：根据进程请求访问磁盘的先后顺序进行调度
• 最短寻找时间优先（SSTF）：选择当前磁头所在的磁道距离最近的磁道
• 扫描（SCAN）算法（电梯算法）：在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求
• 循环扫描（C-SCAN）：在扫描算法的基础上规定磁头单向移动来提供服务

磁盘管理：

• 初始化：对磁盘进行低级格式化和逻辑化
• 引导块：存放自举程序
• 坏块：对于损坏扇区的处理

5.I/O管理：

I/O管理概述：状态跟踪、设备存取、设备分配、设备控制

设备分类：

• 按传输速率分：
  • 低速：如磁盘、鼠标
  • 中速：如行式打印机、激光打印机
  • 高速：如磁带机、磁盘机、光盘机
• 按信息交换单位分：
  • 块设备：如磁盘
  • 字符设备：如键盘、打印机

控制方式：

• 程序直接控制：程序直接对设备特环测试
• 中断驱动：引入中断机制，当设备准备完成时发生中断
• DMA：在I/O设备与主存之间开辟直接数据通路，彻底“解放”CPU。
  • 基本数据单位是块；
  • 传送的数据从设备直接送入内存（或相反）
  • 仅在传送一个或多个数据块的开始和结束时，才需要CPU干预，整块数据的传送是在DMA控制器的控制下完成的；
  • 包含的四类控制器：
    • 命令/状态寄存器（CR）
    • 内存地址寄存器（MAR）
    • 数据寄存器（DR）
    • 数据计数器（DC）
• 通道控制：引入专门的I/O处理机进行管理

I/O子系统层次：

• 用户层I/O软件：实现与用户交互的接口
• 设备独立性软件：实现用户程序与设备驱动器的统一接口、设备命令、设备保护以及设备分配与释放
• 设备驱动程序：与硬件直接相关，负责具体实现系统对设备发出的操作指令
• 中断处理程序：用于处理中断相关事项
• 硬件设备：包括一个机械部件（设备本身）和一个电子邮件（控制器）

I/O核心子系统：

I/O调度：确定一个好的顺序来执行这些I/O请求

磁盘高速缓存：指利用内存中的存储空间来暂存从磁盘上读出的一系列盘块中的信息；逻辑上属于磁盘，物理上属于内存；

• 1：在内存中开辟一个单独的存储空间作为磁盘高速缓存，大小固定
• 2：把未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘时I/O共享

缓冲区：位于内存区域

• 特点：当缓冲区的数据非空的时候，不能往缓冲区冲入数据，只能从缓冲区把数据传出；为空时，可以冲入数据，但必须充满遗憾才能再传出。

• 引入缓冲区的目的：

  • 缓和CPU与I/O设备间速度不匹配的矛盾
  • 减少对CPU的中断频率，放宽对CUP中断响应时间的限制
  • 解决基本数据单元大小不匹配的问题
  • 提高CPU和I/O设备之间的并行性

• 单缓冲

• 双缓冲

• 循环缓冲

• 缓冲池

设备的分配与回收：

• 分类：

  • 独点式使用设备：设备被使用时不再允许其他进程使用设备
  • 分时共享式使用设备：设备没有独占使用的要求时，可以通过分时共享使用
  • SPOOLing技术：将独占设备改造成共享设备,实现了虚拟设备的功能；以空间换时间，必须先有独占设备

• 设备分配的数据结构：

  • 设备控制表（DCT）：每个设备配置一张DCT，以记录本设备的情况；
  • 控制器控制表（COCT）：每个控制器有一张COCT；
  • 通道控制表（CHCT）：每个通道配置一张CHCT；
  • 系统设备表（SDT）整个系统只有一张SDT，记录已连接到系统中的所有物理设备的情况；
  • SDT中有一个DCT指针，DCT中有一个COCT指针，COCT中有一个CHCT指针，CHCT中有一个COCT指针。

• 分配原则：

  • 即要求充分发挥设备的使用效率，又要避免造成进程死锁，还要将用户程序和具体设备隔离开

• 分配方式：

  • 静态分配：在用户作业开始执行前，由系统一次性分配该作业所要求的全部设备
  • 动态分配：在进程执行过程中根据执行需要进行分配

• 设备分配的安全性：

  • 安全分配方式：每当进程发出I/O请求后便进入阻塞状态，直到其I/O操作完成时才被唤醒。
  • 不安全分配方式：进程发出多个I/O请求并继续运行，仅当进程所请求的设备已被另一进程占用时，才进入阻塞状态。

• 设备独立性是指应用程序独立于具体使用的物理设备

SPOOLing技术：主要包括输入井、输出井、输入缓冲区和输出缓冲区以及输入进程和输出进程。

• 输入井和输出井是在磁盘上开辟的两大存储空间；
  • 输入井是模拟脱机输入时的磁盘设备，用于暂存I/O设备输入的数据
  • 输出井是模拟脱机输出时的磁盘，用于暂存用户程序的输出数据