操作系统

期末复习版

操作系统（OS)

第一章 OS

• 概念：操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。
• 定义：OS是一组能有效地组织和管理计算机硬件和软件资源，合理地对各类作业进行调度，方便用户使用的程序的集合。
• 目标：方便性，有效性，可扩充性，开放性
• 作用：①OS作为用户与计算机硬件系统之间的接口。②OS作为计算机资源的管理者。③OS实现了对计算机资源的抽象

多道批处理系统

• 特征：作业调度、资源分配、并行处理
• 优点：资源利用率高，系统吞吐量大
• 缺点：平均周转时间长，无交互能力

分时系统

• 在一台主机上连接了多个配有显示器和键盘的终端并由此所组成的系统，该系统允许多个用户同时通过自己的终端，以交互的方式使用计算机，共享主机中的资源。
• 特征：多路性，独立柱，及时性，交互性

操作系统的基本特性

• 并发：指两个或多个事件在同一时间间隔内发生
  • 并行性是同一时刻
• 共享：资源复用，方式有互斥共享方式和同时访问方式
  • 并发和共享是互为存在的条件
• 虚拟：通过某种技术将一个物理实体变为若干个逻辑上的对应物。
  • 虚拟技术有时分复用技术和空分复用技术。
• 异步：允许多个任务或进程以非阻塞的方式运行，不需要等待某个任务完成后再执行下一个任务
  • 进程是以人们不可预知的速度向前推进的，可看出进程没有顺序性

微内核

基于客户/服务器模式，应用“机制与策略分离”原理，面对对象，实现OS最核心功能的足够小的内核

第二章 进程

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

• 进程实体：程序段、相关数据段和PCB（进程控制块）构成

• 特征：动态性、并发性、独立性、异步性

• 进程三态：就绪、执行、阻塞状态

  阻塞状态

• 程序和进程的区别

  • 进程是动态的，程序是静态的
  • 进程是暂时的，程序是永久存在的
  • 一个程序对应多个进程
  • 程序是进程的组成部分

进程同步

• 两种形式的制约关系：间接和直接相互制约
• 临界资源：多个进程或线程可能需要共享使用，但在某一时刻只能由一个进程或线程访问的资源。
  • 各进程采取互斥方式实现共享的资源称作临界资源
• 临界区：每个进程中访问临界资源的代码
• 信号量机制
  • 整型信号量：定义为一个用于表示资源数目的整型量S,
    • 两个标准原子操作：wait(S)和signal(S)，也称为P，V操作
  • 记录型信号量：采用记录型数据结构
  • AND信号量：基本思想是将进程在整个运行过程中所需要的所有资源一次性地全部分配给进程，待进程使用完后一起释放
• 进程同步问题：生产者-消费者问题 P65

线程

• 定义：是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位
• 作用：能提高计算机系统的资源利用率，使OS具有更好的并发性
• 线程和进程的关系
  • 进程：资源分配的单位，一个进程可以产生多个线程
    线程：调度和分派的单位
  • 一个进程可以有多个线程，但至少有一个线程；而一个线程只能在一个进程的地址空间内活动。
  • 资源分配给进程，同一个进程的所有线程共享该进程所有资源。
  • CPU分配给线程，即真正在处理器运行的是线程。
  • 线程在执行过程中需要协作同步，不同进程的线程间要利用消息通信的办法实现同步。
• 线程与进程的比较
  • 调度的基本单位：传统的OS中是进程，引入线程的OS把线程作为调度和分派的基本单位，是能独立运行的基本单位。线程切换时，切换代价远小于进程。不同进程中的线程切换必然会引起进程的切换。
  • 并发性：进程之间可以并发，一个进程中的多个线程可以并发执行
  • 拥有资源：进程可以拥有资源，作为系统中拥有资源的一个基本单位，线程不拥有资源，仅有一点必不可少的、能保证独立运行的资源。
  • 独立性：同一进程中的线程中的独立性要比不同进程之间的独立性低
  • 系统开销：进程创建和撤销的系统开销大于线程
  • 支持多处理机系统：线程支持多处理器系统

第三章、处理机调度和死锁

• 吞吐量：单位时间内系统所完成的作业数。（总工作量）
  响应时间：从提交请求到显示出处理结果为止的一段时间间隔。（第一次响应-到达时间）
  周转时间：作业被提交给系统开始到作业完成的时间间隔。（完成时间-到达时间）
  平均周转时间：衡量不同调度算法对相同作业流的调度性能。
  带权周转时间：反映长短作业的差别。周转时间/执行时间（服务时长）（>=1）
  平均带权周转时间：比较某种算法对不同作业流调度性能。
• 批处理系统的目标：平均周转时间短，系统吞吐量高，处理机利用率高
• 分时系统的目标：响应时间快，均衡性

作业调度算法 P96

主要任务：检查系统中的资源能否满足作业的作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存。

• 先来先服务（FCFS）
• 短作业优先（SJF）
• 优先级调度算法（PSA）
• 高相应比优先调度算法（HRRN）

轮转调度算法 RR P100

• 进程调度算法
• 时间片：时间片是分时操作系统分配给每个正在运行的进程微观上的一段CPU时间（在抢占内核中是：从进程开始运行直到被抢占的时间）
• 时间片的选择：应略大于一次典型的交互需要的时间。
  • 三个因素：系统对相应时间的要求、就绪队列中进程的数目和系统的处理能力。
  • 小：有利于短作业，响应时间短，吞吐量下降

死锁

• 定义：一组进程中的每一个进程都在等待仅由改组进程中的其他进程引发的事件，改组进程是死锁的
• 原因：竞争资源，进程间推进顺序不当
• 产生条件（同时具备）：互斥条件，请求和保持条件，不可抢占条件，循环等待条件
• 处理死锁的方法：预防死锁，避免死锁，检测死锁，解锁死锁、

银行家算法 P120

第四章、存储器管理

• 程序的装入
  • 绝对装入方式：绝对装入只适用于计算机系统很小，且仅运行单道程序。在编译时就知道程序将放入内存中的那个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。
  • 可重定位装入方式：根据内存的具体情况将装入模块装入到适当位置。把在装入时对目标程序中指令和数据地址的修改过程称为重定位。（p133提到的是静态重定位，动态重定位见p143）
  • 动态运行时的装入方式：装入程序把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换成物理地址，而是把这种地址转换推迟到程序真正要执行时猜进行。
• 连续分配存储管理方式 P135 思想 优缺
  • 单一连续分配
  • 固定分区分配
  • 动态分区分配（可变分区分配）
• 基于顺序搜索的动态分区分配算法 P140
  • 首次适应算法FF
  • 循环首次适应算法NF
  • 最佳适应算法BF
  • 最欢适应算法WF
• 对换
  • 对换是指把内存中暂时不能运行的进程或者暂时不用的程序和数据换到外存上，以便腾出足够的内存空间，再具把备运行条件的进程和进程所需要的程序及数据换入内存。
  • 是改善内存利用率的有效措施，提高处理机的利用率和系统的吞吐量

分页存储管理 P148-149

• 分段存储管理 P155
  • 分段：用户把自己的作业按逻辑关系划分为若干个段，每个段都从0开始编址，并且都有自己的名字和长度。逻辑地址就是由段名（段号）和段内偏移量（段内地址）来决定的。
  • 优点：方便编程、信息共享、信息保护、动态增长、动态链接
• 信息共享 P159 图4-21

第五章、虚拟存储器

• 虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种储存器系统
  • 特征：多次性，对换性，虚拟性
• 缺页率：访问失败/(访问成功+访问失败)
• 抖动：被调出的页面立刻被调入形成的频繁更换页面现象，以致一个进程在运行中把大部分时间都花费在页面置换工作上
  • 产生抖动的原因：在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将缺之页调入内存。
• 分段的共享与保护 P187

页面置换算法 P174

• 最佳置换算法 Optimal
• 先进先出页面置换算法 FIFO
• 最近最久未使用 LRU
• 最少使用置换算法 LFU

第六章 输入输出系统

• I/O系统的基本功能：①隐藏物理设备的细节。②与设备的无关性。③提高处理机与I/O设备的利用率。④对I/O设备进行控制。⑤确保对设备的正确共享。⑥错误处理。
• I/O通道：是一种特殊的处理机，具有执行I/O指令和通过执行通道I/O程序来控制I/O操作的能力
  • 不同于一般处理机的是：①指令类型单一，主要局限于I/O操作。②通道没有自己的内存，与CPU共享。
  • 目的：建立独立的I/O操作，使一些由原来由CPU处理的I/O任务转由通道来承担
  • 通道类型：①字节多路通道。②数组选择通道。③数组多路通道。
• 设施驱动程序的功能：
  • 接收由与设备无关的软件发来的命令和参数，并将命令中的抽象要求转换为与设备相关的低层操作序列
  • 检查用户I/O请求的合法性，了解I/O设备的工作状态，传递与I/O设备操作有关的参数，设置设备的工作方式。
  • 发出I/O命令，如设备空闲则立即启动完成I/O操作，忙碌则将请求块挂在设备队列上等待。
  • 及时响应由设备控制器发来的中断请求，根据中断类型调用相应的中断处理程序处理。

与设备无关软件

• 早期OS应用程序使用物理设备名使用设备，当设备忙碌时系统无法分配给其他相同功能的设备，致使进程请求I/O失败而阻塞
• 逻辑设备是抽象的设备名。仅当所请求的一类设备全部分配完毕时进程会阻塞。
• 逻辑设备名到物理设备名的转换
  • 为了实现与设备的无关性，应用程序请求使用I/O设备时应当用逻辑设备名，但系统只识别物理设备名
  • 在系统中配置一张逻辑设备表，包括逻辑设备名，物理设备名，设备驱动程序的入口地址

假脱机系统

• 假脱机技术：在联机情况下实现的同时外围操作的技术
• 假脱机技术可将一台物理I/O设备虚拟为多台逻辑I/O设备，这样也就允许多个用户共享一台物理I/O设备，实现了设备的虚拟分配
• 特点：①提高了I/O的速度。②将独占设备改造为共享设备。③实现了虚拟设备功能。

缓冲区管理

• 是一个存储区域，由专门的硬件寄存器组成。一般情况下，更多是利用内存作为缓冲区。
• 几乎所有I/O设备与处理机交换数据时都使用了缓冲区
• 形式：单缓冲区，双缓冲区，环形缓冲区，循环缓冲区，公用缓冲池
• 引入缓冲区的原因
  • 缓和CPU与I/O设备间速度不匹配的矛盾
  • 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
  • 解决速度颗粒不匹配的问题
  • 提高CPU和I/O设备之间的并行性

早期的磁盘调度算法 P233

目标是使磁盘的平均寻道时间最少

• 先来先服务 FCFS：按先后次序
• 最短寻道时间优先 SSTF：局部最优，贪心算法

第七章 文件管理

• 数据项：是最低级的数据组织形式。
  • 基本数据项：用于描述一个对象的某种属性的字符集，也叫字段
  • 组合数据项：由若干个基本数据项组成，也叫组项
• 记录：是一组相关数据项的集合，用于描述在一个对象在某方面的属性
  • 关键字：唯一标识一个记录的数据项（主键/外键）
• 文件：是指由创建者所定义的、具有文件名的一组相关元素的集合
  • 有结构文件：文件由若干个相关记录组成
  • 无结构文件：被看作是一个字符流
  • 文件属性：包括文件类型，文件长度，文件的物理位置，文件的创立时间
• 文件的结构
  • 逻辑结构：文件是由一系列的逻辑记录组成的，又称为文件组织
  • 物理结构：文件的存储结构
• 文件控制块：为文件设置用于描述和控制文件的数据结构
  • 含有三类信息：基本信息，存取控制信息，使用信息
• 索引结点
  • 引入：将文件描述信息单独形成一个称为索引结点的数据结构
  • 磁盘索引结点：存放在磁盘上的，每个文件有唯一的一个磁盘索引结点
  • 内存索引结点：存放在内存中的，当文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中
• 单级文件目录：最简单的文件目录，整个文件系统中只建立一张目录表
  • 优点：简单
  • 缺点：只能实现按名存取这一最基本功能，查找速度慢，不允许重名，不便于文件共享

第八章、磁盘存储器的管理

外存的组织方式

• 连续组织方式：连续分配方式，为每一个文件分配一组相邻接的盘块。
  • 文件结构：顺序文件结构。物理文件：顺序文件
  • 优点：顺序访问容易，顺序访问速度快
  • 缺点：①要求为一个文件分配连续的存储空间。②必须事先知道文件的长度，不适用于动态增长的文件。③不能灵活地删除和插入记录。
• 链接组织方式：为文件分配多个不连续的盘块，再通过每个盘块上的链接指针，将属于一个文件的多个离散的盘块链接成一个链表。
  • 文件结构：链表。物理文件：链接文件
  • 链接方式
    • 隐式链接：文件目录的每个目录表上，都含有指向链接文件第一个盘块和最后一个盘块的指针。只适用于顺序访问
    • 显示链接：把用于链接文件个物理块的指针显示地存放在内存的一张链接表（文件分配表 FAT）中
  • 优点：①消除了磁盘的外部碎片，提高了外存的利用率。②对插入、删除和修改记录都非常容易。③能适应文件的动态增长，无需事先知道文件大小
  • 缺点：①不能支持高效的直接存取，对于较大的文件需要FAT中顺序查找许多盘块号。②FAT需占用较大的内存空间
• 索引组织方式
  • 单级索引组织方式
    • 优点：支持直接访问
    • 缺点：每建立一个索引文件都要分配一个索引块，对小文件来说利用率极低
  • 多级索引组织方式
    • 优点：大大加快对大型文件的查找速度
    • 缺点：访问一个盘块时需要启动的次数锁着索引级数的增加而增多
  • 增量式索引组织方式：全面照顾到小、中、大及特大型作业，采用多种组织方式来构成文件的物理结构

文件存储空间的管理

• 空闲表法：连续分配方式，为每个文件分配一块连续的存储空间，类似内存的连续分配
• 空闲链表法：将所有的空闲盘区拉成一条空闲空闲链。
  • 空闲盘块链：将磁盘上的所有空闲空间以盘块为单位拉成一条链，其中每个盘块都有指向后继盘块的指针
  • 空闲盘区链：将磁盘上的所有空闲盘区（每个盘区可包含若干盘块）拉成一条链。
• 位示图：由所有盘块所对应的位构成一个集合。
  • 通常用 m*n 个位数来构成位示图，并使 m*n 等于磁盘的总块数。
  • 盘块的分配和回收