操作系统复习笔记

admin管理员组

文章数量:1026989

使用书籍为《操作系统——精髓与设计原理（第八版）》

第一章 计算机系统概述

基本概念

基本构成：处理器、内存、输入/输出模块、系统总线

处理器中各寄存器的作用

处理器分为执行单元、控制单元、寄存器（用户可见寄存器、控制和状态寄存器）

用户可见寄存器

• 数据寄存器DR
• 地址寄存器AR

控制和状态寄存器

• 存储器地址寄存器MAR：制定下一次要读写的存储器地址
• 存储器缓冲寄存器MBR：包含要写入存储器的数据或者从存储器读取的数据
• I/O地址寄存器I/O AR
• I/O缓冲寄存器I/O BR
• 程序计数器PC：包含将取指令的地址
• 指令寄存器IR：包含最近取的指令内容
• 程序状态字PSW：条件码、中断允许位禁止位、管理程序/用户模式位

指令的执行过程

中断

中断是指CPU对系统中发生的异步事件的响应
发生中断时正在执行的程序的暂停点叫做中断断点
处理器暂停当前程序转而处理中断的过程称为中断响应
中断处理结束之后恢复原来程序的执行被称为中断返回
一个计算机系统提供的中断源的有序集合一般被称为中断字，这是一个逻辑结构，在不同的处理器有着很不相同的实现方式。

• 程序中断：因指令的执行结果而产生，如算术溢出、被零除等
• 时钟中断：由处理器内部的计时器而产生。通常在分时系统中每个进程分配了一个时间片，当进程用完时间片后就会发生一个时钟中断，系统将处理器分配给另一个进程使用
• I/O中断：由I/O控制器产生，通常在I/O操作正常完成或错误时发出信号提示处理器响应中断，是最常见的中断类型
• 硬件失效中断：因硬件故障而产生

中断处理

• 设备给处理器发出中断请求信号
• 处理器结束当前指令的执行
• 处理器发出中断应答信号以响应中断
• 保存当前程序的断点信息（PSW和PC压入控制栈）
• 转向中断处理例程入口（加载新的PC值）
• 执行中断处理例程（软件实现）

多个中断
方法一：正在处理一个中断时，禁止再发生中断
缺点：没有考虑中断的相对优先级T和时间限制要求
方法二：定义中断优先级，允许高优先级的中断打断低优先级的中断处理器的运行

存储器的层次结构

从上往下

• 每bit价格递减
• 容量递增
• 存取时间递增
• 处理器访问存储器的频率递减

局部性原理： 处理器“成簇”地访问指令和数据

Cache

置换算法-最近最少使用（LRU）算法
写策略：当块的内容被修改时，确定何时写回主存储器

• 直写：每次块内容被修改时都写回主存
• 回写：只有当块被替换时才写回主存（减少了存储器写操作的次数、导致数据不一致性）

I/O通信技术

• 程序控制I/O
• 中断驱动I/O
• 直接存储器读取（DMA）

程序控制I/O和中断驱动I/O存在两方面固有缺陷：

• I/O传送速度受限于处理器测试设备和提供服务的速度
• 处理器需要承担与I/O设备进行数据传送的工作

DMA模块解决上述问题
DMA模块完成I/O与主存之间的数据交换
DMA模块占用总线以完成数据交换（“总线窃取”）

第二章 操作系统概述

操作系统的定义、目标和功能

定义：操作系统是控制应用程序执行的程序，在应用程序和计算机硬件之间提供接口。

设计目标

• 方便(Convenience)： 使计算机更易于使用
• 有效 (Efficiency)：使计算机系统资源得到最大化利用
• 扩展的能力(Ability to evolve)：有效地开发、测试和引进新的系统功能

4个功能模块：文件系统、设备管理、存储器管理、处理器（进程）管理

操作系统的发展

简单批处理系统：

目标：为了解决人工操作（无操作系统）严重降低了计算机资源利用率的问题，即解决CPU等待人工操作和高速CPU与低速I/O间矛盾等问题。

脱机输入输出技术：该技术利用一台外围机，脱离主机先将低速输入设备（如纸带机）的数据，输入到较高速大容量的输入设备（如磁带）上。

使用监控程序

多道批处理系统：
它是在计算机内存同时存放几道相互独立的程序，这几道程序都处于运行过程中，它们先后开始了各自的运行，但都未运行完毕。多道程序在宏观上并行执行，而在微观上多道程序在某个部件上（如CPU、I/O）是串行的，即多道程序轮流地使用部件，交替执行。调度算法

分时系统：交互性、响应时间、时间片轮转（依次给队列中的每个进程分配一定的时间）

实时系统：实时、可靠、快速响应、

多道程序设计的概念：（宏观并行，微观即单设备串行）

现代操作系统的特征和主要成就

进程：包含三个部分：

• 一段可执行的程序
• 程序所需的相关数据
• 程序执行的上下文环境（操作系统用于管理和控制进程所需的所有数据（如PC, 数据寄存器内容, 进程优先级,进程状态等））

一个进程可分为多个并发的线程

内存管理
虚存

• 程序员使用虚地址访问内存，通过地址映射机制（通常由硬件实现）将虚地址动态映射为主存中的实地址
• 一个进程被分成若干个块（分页和分段），每一块都可以放置在主存中用户空间的任何地方
• 进程执行时，只需要一部分块在内存中即可。当访问的块不在内存中时，产生缺页中断，将所要访问的块从磁盘调入内存

安全性

• 可用性：确保系统正常可用
• 保密性：确保用户不能访问未授权的数据
• 数据完整性：保护数据不被未授权修改
• 认证：用户身份的认证、数据的合法性

调度

• 公平性（Fairness ）：平等、公平地访问资源
• 有差别的响应性（Differential responsiveness ）：根据进程的不同优先级差别对待
• 有效性（Efficiency ）：最大化吞吐量、最小化响应时间、尽可能容纳更多的用户

第三章 进程描述和控制

基本概念

进程(Process)定义：“可并发执行的程序在一个数据集合上的运行过程”。

• 一段可执行的程序
• 计算机中正在运行的程序的一个实例
• 可以分配给处理器并由处理器执行的一个实体
• 由一个顺序的执行线程、一个当前的状态以及一组相关的系统资源所描述的活动单元

从结构上，进程实体由程序段、数据段和进程控制块三部分组成。

进程的状态以及各状态间的转换条件（重点）

五状态模型

• 运行（Running）：占有CPU
• 就绪（Ready ）：除了CPU，其它所需资源都已占有，一旦得到处理机即可运行，则称此进程处于就绪状态
• 阻塞（Blocked ）：等待某些事件
• 新建（New ）: 已经创建了PCB并保存在主存中，但程序代码和相关数据还没有读入主存
• 退出（Exit ）

挂起（Suspended）进程

会出现内存中所有进程都被处理器执行了一遍, 都在等待I/O事件(即都是”阻塞”状态), 此时处理器空闲了, 却不能处理未进入内存的待执行程序.

可以通过不断增加内存大小来解决， 内存价格与大小是指数相关的, 不能一味增加大小. 因此操作系统引入了挂起(交换)的概念, 即内存已满时, 操作系统会将内存中等待I/O的进程(即”阻塞”状态)移动到硬盘中, 并从硬盘中调入新的"就绪"进程. 换出的进程被放置在挂起队列中, 由此引申出了七状态模型。

进程的描述

操作系统利用表结构来管理四种不同类型的表：存储表、I/O设备表、文件表和进程表。

进程控制块PCB的作用――进程存在的唯一实体
进程控制块中记录进程存在和特性信息，它与进程同生死。创建一个进程就是为其建立一个PCB，当进程被撤消时，系统就回收它的PCB；OS对进程的控制是根据PCB来进行，对进程管理也通过对PCB管理来实现，所以进程控制块是进程存在的唯一实体。

PCB的信息

• 进程标识信息：它用于唯一地标识一个进程。它有外部标识符（由字母组成，供用户使用）和内部标识符（由整数组成，为方便系统管理而设置）二种。
• 处理器状态信息：它由处理器各种寄存器（通用寄存器、指令计数器、程序状态字PSW、用户栈指针等）的内容所组成，该类信息使进程被中断后重新执行时能恢复现场从断点处继续运行。
• 进程控制信息 ：它包括进程状态（running、ready、blocked）、队列（就绪、阻塞队列）、队列指针，调度参数：进程优先级、进程已执行时间和已等待时间、进程间通信的信号系统、进程所分配的内存空间指针等。

进程控制

模式切换
用户模式（目态）：通常在该模式下执行用户程序、权限较低
系统模式、控制模式或内核模式（管态）：在该模式下执行操作系统内核、
可执行特权指令，权限更高

用户调用操作系统服务（系统调用）或发生中断时，执行模式从用户模式切换到内核模式
当系统服务返回或中断返回到用户进程时，执行模式从内核模式切换到用户模式

进程切换
进程切换可以在操作系统从当前正在运行的进程中获得控制权的任何时刻发生。

进程切换和模式切换的区别：
模式切换是系统执行模式的改变，发生模式切换可以不改变正处于运行态的进程状态。

进程切换时，操作系统必须使其运行环境发生改变。进程切换必然会存在模式切换（只有在内核模式下才能实现进程调度），但模式切换不一定会发生进程切换。

进程切换比模式切换更复杂。

创建进程
给进程分配一个唯一的进程标识号

给进程分配空间(进程要执行的程序代码和数据)

初始化进程控制块（如PC初始化为程序入口地址；进程状态初始化为就绪或就绪/挂起；进程优先级初始化为最低优先级等）

将进程控制块加入到正确的队列中（如加入到就绪队列中）

创建或扩充操作系统所需的其他数据结构（如审计文件）

第四章 线程

基本概念：线程定义为进程内一个执行单元或一个可调度实体。
线程只拥有一点在运行中必不可省的资源（程序计数器、一组寄存器和栈），但它可与同属一个进程的其它线程共享进程拥有的全部资源。

线程和进程的区别：进程是操作系统资源分配的基本单位，而线程是任务调度和执行的基本单位

线程三个基本的状态：运行Running, 就绪Ready 和阻塞Blocked。挂起状态对线程是没有意义的。

因为进程内的所有线程共享相同的地址空间，因此，挂起一个进程则该进程内的所有线程都将挂起。进程终止了，则该进程内的所有线程也将终止。

用户及线程和内核级线程
用户级线程

• 线程管理的所有工作都由应用程序来完成，内核并不知道线程的存在。应用程序使用线程库来实现多线程，线程库是个程序包，其中包括创建或删除线程，在线程间传递消息和数据，调度线程执行以及保存和恢复线程上下文等代码
  优点：
  不依赖于OS内核，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程，可以在任何操作系统中运行

调度由应用软件内部进行，通常采用非抢先式或更简单的规则，无需用户态/核心态切换，所以速度特别快，用户线程调度算法可针对应用优化

同一进程内各线程的切换不需要内核参与，减少了模式切换的开销

缺点：
当一个线程因系统调用而被阻塞时，该进程内的所有线程都被阻塞（为什么？）
答：系统调用使得模式从用户模式切换到内核模式，操作系统只知道进程，故操作系统将进程置为阻塞状态，从而使得该进程内的所有线程都被阻塞
内核一次只把一个进程分配给一个处理器，因此一次进程中只有一个线程可以执行，使多线程技术不能得到应用

内核级线程：
有关线程管理的所有工作都由内核来完成
应用程序只调用内核级线程的API
操作系统基于线程进行调度

优点：
内核可以同时把同一个进程中的多个线程调度到多个处理器中，从而更好地利用多道程序设计技术

如果一个进程内的线程阻塞，内核可以调度同一进程内的其他线程运行，不会导致整个进程被阻塞

内核例程自身也可以使用多线程

缺点：
同一个进程内两个线程的切换需要内核模式的切换

第五章 并发性：互斥和同步

与并发相关的概念

• 互斥（ mutual exclusion )指多个进程不能同时使用同一个资源
• 死锁（ deadlock )指多个进程互不相让，都得不到足够的资源
• 饥饿（ starvation )指一个进程一直得不到资源（其他进程可能轮流占用资源）
• 活锁：多个进程为响应其他进程中的变化而持续改变自己的状态而不能有用的工作的情形
• 临界区：一段代码，在这段代码中进程将访问共享资源，当另一个进程已在这段代码中运行时，这个进程就不能在这段代码中运行

互斥：软件和硬件的方法

软件方法

硬件实现方法

• 特殊的机器指令
• 在单个指令周期内执行，是原子性的指令（不能被中断）
• 在该指令执行时，任何需要访问内存的其他指令都将被阻塞
• 两种常见的指令：Testset和exchange指令

优点

• 适用于在单处理器或共享内存的多处理器上任何数目的进程
• 非常简单且易于证明
• 可用于支持多个临界区

缺点

• 忙等待
• 可能饥饿：多个进程等待进入临界区，选择哪个进程是随机的
• 可能死锁：考虑优先级情况

信号量(Semaphores)机制（重点）
基本原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一个位置停止，直到它接收到一个特定的信号。

信号量的定义：特殊的变量，称为信号量，用于发送信号
一个进程为了通过信号量s发送信号,它需要执行原语semSignal(s)/V(s)
一个进程通过信号量s接收信号, 它需要执行原语semWait(s) /P(s)
如果相应的信号没有接收到，该进程将被挂起，直到它所需的信号发送为止

一个具有整型数值的变量：被初始化为非负数 (nonnegative number).

semWait/P操作使信号量值减1。如果信号量值变为负数，则执行该操作的进程被阻塞。

semSignal/V 操作使信号量值增1。如果值小于或等于零，表示之前有进程在等该信号，则需要在该信号量的阻塞队列中唤醒一个进程。

同步也可以理解为：先做动作的进程C在动作完成后对同步信号量施加signal操作，代表发送消息；后做动作的进程P在动作前对同步信号量施加wait操作，代表测试消息是否到达。

生产者/消费者问题

读者/写者问题

信号量的物理含义：

• S>0表示有S个资源可用
• S=0表示无资源可用
• S<0则| S |表示S等待队列中的进程个数
• 信号量的初值应该大于等于0
• wait(s)（P(S)）:表示申请(等待)一个资源
• signal(s)（V(S)）:表示释放一个资源

第六章 并发：死锁和饥饿

死锁的原理

所谓死锁是指计算机系统和进程所处的一种状态。

在系统中，两个或多个进程无限期地等待永远不会发生的条件，此时称系统处于死锁状态。

一组进程因竞争系统资源或相互通信所造成的永久性阻塞

竞争资源引起死锁：在多道程序系统，多个进程共享系统的资源。对于可重用的资源，当系统把这类资源分配给某进程后，不能强行收回，只能在进程用完后自动释放。当多个进程竞争这类资源时就可能引起死锁。

进程推进顺序不当引起死锁：有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成了死锁。

死锁有四个条件

1. 互斥 (Mutual exclusion)：一次只有一个进程可以使用一个资源
2. 占有且等待 (Hold-and-wait)：当一个进程在等待分配得到其他资源时，将继续占有已分配到的资源
3. 非剥夺 (No preemption )：不能强行抢占进程已占有的资源，以上三个还不能确定发生死锁
4. 循环等待 (Circular wait)：存在一个封闭的进程-资源链，每个进程至少占有一个该链中下一个进程所需要的资源

死锁的防范：理解哪个方法破坏了哪个条件

死锁的预防（Prevention）

• 间接死锁预防（预防前三个）
• 直接死锁预防（预防循环等待）

死锁的避免 (Deadlock Avoidance)

银行家算法：允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁。

死锁检测算法

哲学家就餐问题

第七章 内存管理

逻辑地址 (Logical)：

• 程序员访问的地址，与当前数据在内存中的实际位置无关
• 在进行内存访问时，必须将其转换成物理地址

相对地址 (Relative)

• 逻辑地址的特例
• 相对于某些已知点（通常的程序开始处）的存储单元

物理地址(Physical)

• 也称为绝对地址
• 是数据在主存中的实际位置

地址重定位，也称地址映射（map），它将相对地址转换成内存中的绝对地址。按照重定位的时机，可分为静态重定位和动态重定位。

内存管理技术

动态分区分配算法

(1)最佳适应算法BF（Best Fit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。

(2)首次适应算法FF（First Fit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。

(3)循环首次适应算法/邻近算法NF(Next Fit)：该算法是首次适应算法的变种，它把空闲分区表（空闲区链）中的空闲分区按地址递增构成一个循环链。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得比较均匀。

(4)最坏适应法：从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业；空闲分区按大小由大到小排序。该算法使小的空闲区减少，但造成大的空闲区不够大

逻辑地址到物理地址的转换

在进行地址变换时，系统将逻辑地址截成页号和页内地址二部分，将页号与页表长度进行比较，如果页号大于等于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，查页表得到该页的物理块号，将物理块号与逻辑地址中页内地址二者拼接成物理地址，这样便完成了从逻辑地址到物理地址的变换。

第八章 虚拟内存

基本概念

缺页中断：当处理器需要访问一个不在主存中的块时，系统将产生一个内存访问故障中断

局部性原理：程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。

抖动现象（thrashing）：即处理器大部分时间都用于交换块，而不是执行指令。

为了提高地址变换的速度，增设了一个具有按内容查找、并行查询功能的特殊的高速缓冲存储器，称为 “快表”，或称为“关联存储器(TLB, 转换后备缓冲器)”，用以存放当前访问的那些页表项，每个页表项包括页号和相应的块号（页号不能省略）。
引入快表之后的存储访问修改如下：
处理器首先将逻辑地址中的页号与TLB中的各页表项的页号进行比较
如果有相同的 (TLB命中)， 则直接从TLB的输出寄存器输出相应的块号
如果没有找到(TLB不命中) ，则访问内存从该进程的页表中查找
检查该页是否在内存中(检查P位)
如果不在，则发生缺页中断
页访问之后，同时要将该页的页表项读入TLB

请求分页

扩充的页表机制和缺页中断机构。

请求分段

在简单分段系统的基础上实现的虚拟存储器，是以分段为单位进行换入、换出的。
在程序运行之前只要先调入若干个分段（不必调入所有的分段），便可启动运行。
当所访问的段不在内存时可请求OS将所缺的段调入内存。
为实现请求分段存储管理方式，同样需要一定的硬件支持和相应的软件，有段表机制、缺段中断机构以及地址变换机构。

段页式系统

它以分页的方式管理内存，具有分页系统能有效地提高内存利用率的优点；又以分段的方式管理用户的逻辑地址空间，具有分段系统能很好地满足用户需要的长处

在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中必需同时配置段表和页表。由于将段中的页进行离散地分配，段表中的内容不再是段的内存始址和段长，而是页表始址和页表长度。

固定的分配会产生内部碎片，比如分页式、段页式、固定分区管理
分段式存储管理会产生外部碎片

替换策略

缺页率：页面置换算法的性能指标：缺页率（ page fault rate ）=“缺页次数 / 内存访问次数” (比率)

• 最佳 (Optimal policy,OPT)：选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去
• 先进先出（FIFO）置换算法：选择在内存中驻留时间最久的页面予以淘汰。
• 最近最久未使用置换算法（Least Recently Used，LRU）：选择最近最久未使用的页面予以淘汰
• Clock置换算法 可以看下面这个链接的解释
  Clock置换算法

具体例子
补充：Clock算法中*表示相应的使用位为1

第九章 单处理器调度

长程调度：
决定加入到待执行的进程池中，决定哪一个程序可以进入到系统中被处理；

加入的进程越多，每个进程可以执行的时间百分比越小，因此控制多道程序设计的度；

一个进程终止时可以执行该调度，选择某个程序加入到就绪队列或就绪/挂起队列中，供短程调度或中程调度处理；

可基于简单的先来先服务或优先级进行调度

中程调度：分配内存，对换
为了充分发挥内存的效能，需将那些暂时不能运行的进程从内存调到外存盘交换区去等待，而将那些在盘交换区的等待事件已经发生急需调度运行的进程从盘交换区调入内存。

有时内存中进程数目过多也需将处于就绪态的进程从内存调到盘交换区，当然在盘交换区等待时间过长的就绪态的进程也要调入内存。

在UNIX系统中,中程调度就是存储管理中的对换，即进程在磁盘的交换区和内存间的对换。

采用虚拟存储技术的分时系统往往设立中程调度。

短程调度：分配处理器

通常称为分派程序，执行得最频繁

决定将处理器分配给哪个就绪进程

是最基本的调度，任何操作系统都有短程调度/进程调度

可由以下事件激发：

• 时钟中断
• I/O 中断
• 操作系统调用
• 信号

周转时间(Turnaround Time)短：
它是评价批处理系统的重要性能指标。作业周转时间Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。周转时间Ti = 完成时间－到达(提交)时间

响应时间(Response Time)快：
响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。

系统吞吐量(throughput)大：
这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度具有密切关系。

FCFS (First-Come-First-Served）：先来先服务

RR（Round-Robin）：时间片轮转
分时系统采用的主要调度算法
总是选择就绪队列中第一个进程，允许其占有处理机一个时间片的时间。当执行的时间片用完时，调度程序便停止该进程的执行，并将它送到就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。
采用基于时间片的抢占模式
周期性地发生时钟中断，使操作系统获得控制权
每次就绪进程的选择都基于FCFS策略

SPN（Shortest Process Next）：最短进程优先
在就绪队列中选择所需服务时间最短的进程

SRT（Shortest Remaining Time）：最短剩余时间优先
在就绪队列中选择运行所需剩余时间最短的进程

HRRN（Highest Response Ratio Next）：最高响应比优先
在就绪队列中选择响应比最高的进程来调度
非抢占模式
选择函数max®=max(1+w/s)
折中策略，综合考虑服务时间和等待时间

feedback反馈
原则：处罚运行时间较长的作业
基于抢占原则（按时间片）并使用动态优先级机制
新进程进入RQ0，每当它被抢占，则降到下一个优先级队列中
优先级最低队列采用轮转法，其他队列采用FCFS机制

第十一章 I|O管理和磁盘调度

I|O功能的组织：

程序控制I|O：
处理器给I/O模块发送I/O命令，进程进入忙等待，直到I/O操作完成才可以继续执行

中断驱动I|O：
处理器发送I/O命令，然后继续执行后续指令，当I/O模块完成后，给处理器发送中断

DMA：
由DMA模块控制主存和I/O模块之间的数据交换

I/O系统的目标—设备独立性

为了提高操作系统的可适应性和可扩展性，目前几乎所有的操作系统都实现了设备的独立性（Device Independence）（也称为设备无关性）。

用户程序的设备独立性是：用户程序不直接使用物理设备名（或设备的物理地址），而只使用逻辑设备名；而系统在实际执行时，将逻辑设备名转换为某个具体的物理设备名，实施I/O操作。

I/O软件的设备独立性是：除了直接与设备打交道的低层软件之外，其他部分的软件并不依赖于硬件。I/O软件独立于设备，就可以提高设备管理软件的设计效率。

设备独立性的好处：
（1）设备分配时的灵活性
当进程以逻辑设备名请求某类设备时，如果一台设备已经分配给其它进程或正在检修，此时系统可以将其它几台相同的空闲设备中的任一台分配给该进程。
（2）易于实现I/O重定向
所谓I/O重定向，指用于I/O操作的设备可以更换，应用程序的输入、输出可以重定向，不必修改应用程序

I|O缓冲区

单缓冲、双缓冲、循环缓冲

磁盘调度算法

寻道时间（ Seek time ）TS：
这是把磁头从当前位置移动到指定磁道上所经历的时间。该时间是启动磁盘的时间s与磁头移动n条磁道所花费的时间之和。即 TS＝m×n十s

旋转延迟时间（ Rotational delay or rotational latency ）Tr：
Tr 是指定扇区移动到磁头下所经历的时间。对于硬盘来说，典型的转速为3600RPM（目前硬盘的转速达到7200RPM），每转需时16.7ms，平均旋转延迟时间为8.3ms。对于软盘，其旋转速度为300或600RPM，平均Tr为50～100ms。

传输时间Tt：
Tt 是指把数据从磁盘读出，或向磁盘写入数据所经历的时间，它的大小与每次所读／写的字节数b及旋转速度r(/秒)有关：Tt =b/(r*N)(N为一条磁道上字节数)。

Ta= TS+ Tr+ Tt= TS + 1/2r+ b/rN

先来先服务FCFS算法：

先来先服务FCFS（First Come First Served）是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。

算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。

缺点是算法未对寻道进行优化，致使平均寻道时间可能较长（平均响应时间长）。

最短寻道时间优先SSTF算法：

该算法总是满足那些与当前磁头所在的磁道距离最近的请求,也就是执行寻道时间最短的那个I/O请求。

这种调度算法有较好的平均寻道时间。但它可能导致某些进程长时间的得不到服务（饥饿现象）。因为只要不断有新进程到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必被优先满足。

对中间磁道访问服务比内、外两侧磁道服务好，造成响应时间变化幅度大,在服务请求多时，内外边缘请求被无限期延迟，不可预期。

扫描（SCAN）算法：

即当磁头正在自里向外运动时，SCAN算法要选择的下一个访问对象是其欲访问的磁道在当前磁道之外，又是距离最近的。直至再无更外的磁道需要访问时，才将磁臂换向，自外向里运动。从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律象电梯的运行，所以又称为电梯调度算法。

克服SSTF服务集中中间磁道和响应时间变化较大缺点，两侧磁道的访问的频率低于中间磁道。

循环扫描 CSCAN算法：

CSCAN算法规定磁头只能单向运动（自里向外或自外向里），当磁头运动到最外面的被访问磁道时，磁头立即返回到最里面的欲访的磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。

磁盘Cache

如何将磁盘cache中的数据传送给请求的用户进程？
使用共享存储空间，将指向该共享空间的指针传递给进程即可，避免了数据直接传送的耗时。

如何替换cache中的数据块?
LRU和LFU算法

最不常用算法（Least Frequently Used, LFU）:
替换访问次数最少的块。
每个块关联一个计数器，由计数器来记录该块的访问次数。
块被读入时，计数器的值为1；每次访问到该块时，计数器的值+1。
替换时，选择计数器值最小的块。
存在一个问题：某些块可能在一段时间内被频繁地访问，使计数器值变得很大，但后面就不再访问到。因计数器值大，可能永远都不会被替换，虽然这块可能再也不会用到。

第十二章 文件管理

基本概念

文件是存储在某种介质上的（如磁盘、磁带等）并具有文件名的一组有序信息的集合

文件系统是操作系统中以文件方式管理计算机软件资源的软件和被管理的文件和数据结构（如目录和索引表等）的集合。

FAT文件系统（MS-DOS文件系统、msdos）
文件地址以FAT表结构存放，文件目录32B，文件名为8个基本名加上一个“.”和3个字符扩展名

文件的五种逻辑组织方式

• 堆 (Pile)
• 顺序文件 (sequential file)
• 索引顺序文件 (indexed sequential file)
• 索引文件 (indexed file)
• 直接或散列文件 (direct, or hashed, file)

文件目录和文件共享：“按名存取”

文件目录

为了实现“按名存取”，系统必须为每个文件设置用于描述和控制文件的数据结构，它至少要包括文件名和存放文件的盘物理地址，这个数据结构称为文件控制块FCB。

文件控制块的有序集合称为文件目录，即一个文件控制块FCB就是一个文件目录项。

三种记录组块方式

固定组块 (Fixed blocking)

• 记录长度固定
• 若干条完整的记录被保存在一个块中
• 存在内部碎片

可变长度跨越式组块 (Variable-length spanned blocking)

• 记录长度可变
• 紧缩在块中，解决了内部碎片问题
• 某些记录可能跨两个块，通过指针指向后继块

可变长度非跨越式组块 (Variable-length unspanned blocking)

• 记录长度可变
• 记录不跨块，存在内部碎片问题

固定组块是记录长度固定的顺序文件最常用的格式
可变长度跨越式组块存储效率高，但难于实现
可变长度非跨越式组块会导致空间的浪费，并且记录大小受块大小限制

三种文件分配方法（连续、链式、索引）

连续分配（Contiguous allocation）

创建文件时，给文件分配一组连续的块

预分配策略，分区大小可变

文件分配表FAT中每个文件只需要一个表项：起始块和文件长度

存在外部碎片，需定期执行压缩技术

读取文件中第i块需要访问几次磁盘？
A：1次，根据FAT中文件的起始块，访问所需要的块（假设起始块为b，要访问第i块，则其位置为b+i-1）

链式分配

基于单个块进行分配，链中每一块都包含指向下一块的指针

动态分配：按需进行块分配

FAT表中每个文件一个表项：起始块和文件长度

优点是盘存储空间利用率高，文件增删改记录方便，不存在外部碎片

局部性原理不再适用，可周期性地对文件进行合并

读取文件中第i块需要访问几次磁盘？
A：i次，根据FAT找到该文件的起始块，顺着链指针依次往下找，因此访问第i块，需要查找i次

索引分配

文件分配表FAT中对每个文件都包含一个一级索引

文件索引保存在单独块中，在FAT的表项里指向这一块的值

分配可基于固定大小的块，也可基于可变大小的分区：索引块中包括指向文件所有块的指针或指向分区起始块的指针

支持顺序访问文件和直接访问文件，是最普遍的一种文件分配形式

读取文件中第i块需要访问几次磁盘？
A：2次，第一次，根据FAT找到该文件的索引块；第二次，根据索引的指针找到所要访问的第i块

空闲空间管理（位示图）

磁盘分配表（Disk allocation table，DAT）用来记录磁盘上哪些块是可用的
三种常用技术:

位表（Bit tables）

链式空闲区（Chained free portions）

索引（Indexing）

下面的一些选择题是别的大佬整理的，可以看看
选择题

希望可以有所帮助！

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn/qq_43515163/article/details/112701397

使用书籍为《操作系统——精髓与设计原理（第八版）》

第一章 计算机系统概述

基本概念

基本构成：处理器、内存、输入/输出模块、系统总线

处理器中各寄存器的作用

处理器分为执行单元、控制单元、寄存器（用户可见寄存器、控制和状态寄存器）

用户可见寄存器

• 数据寄存器DR
• 地址寄存器AR

控制和状态寄存器

• 存储器地址寄存器MAR：制定下一次要读写的存储器地址
• 存储器缓冲寄存器MBR：包含要写入存储器的数据或者从存储器读取的数据
• I/O地址寄存器I/O AR
• I/O缓冲寄存器I/O BR
• 程序计数器PC：包含将取指令的地址
• 指令寄存器IR：包含最近取的指令内容
• 程序状态字PSW：条件码、中断允许位禁止位、管理程序/用户模式位

指令的执行过程

中断

中断是指CPU对系统中发生的异步事件的响应
发生中断时正在执行的程序的暂停点叫做中断断点
处理器暂停当前程序转而处理中断的过程称为中断响应
中断处理结束之后恢复原来程序的执行被称为中断返回
一个计算机系统提供的中断源的有序集合一般被称为中断字，这是一个逻辑结构，在不同的处理器有着很不相同的实现方式。

• 程序中断：因指令的执行结果而产生，如算术溢出、被零除等
• 时钟中断：由处理器内部的计时器而产生。通常在分时系统中每个进程分配了一个时间片，当进程用完时间片后就会发生一个时钟中断，系统将处理器分配给另一个进程使用
• I/O中断：由I/O控制器产生，通常在I/O操作正常完成或错误时发出信号提示处理器响应中断，是最常见的中断类型
• 硬件失效中断：因硬件故障而产生

中断处理

• 设备给处理器发出中断请求信号
• 处理器结束当前指令的执行
• 处理器发出中断应答信号以响应中断
• 保存当前程序的断点信息（PSW和PC压入控制栈）
• 转向中断处理例程入口（加载新的PC值）
• 执行中断处理例程（软件实现）

多个中断
方法一：正在处理一个中断时，禁止再发生中断
缺点：没有考虑中断的相对优先级T和时间限制要求
方法二：定义中断优先级，允许高优先级的中断打断低优先级的中断处理器的运行

存储器的层次结构

从上往下

• 每bit价格递减
• 容量递增
• 存取时间递增
• 处理器访问存储器的频率递减

局部性原理： 处理器“成簇”地访问指令和数据

Cache

置换算法-最近最少使用（LRU）算法
写策略：当块的内容被修改时，确定何时写回主存储器

• 直写：每次块内容被修改时都写回主存
• 回写：只有当块被替换时才写回主存（减少了存储器写操作的次数、导致数据不一致性）

I/O通信技术

• 程序控制I/O
• 中断驱动I/O
• 直接存储器读取（DMA）

程序控制I/O和中断驱动I/O存在两方面固有缺陷：

• I/O传送速度受限于处理器测试设备和提供服务的速度
• 处理器需要承担与I/O设备进行数据传送的工作

DMA模块解决上述问题
DMA模块完成I/O与主存之间的数据交换
DMA模块占用总线以完成数据交换（“总线窃取”）

第二章 操作系统概述

操作系统的定义、目标和功能

定义：操作系统是控制应用程序执行的程序，在应用程序和计算机硬件之间提供接口。

设计目标

• 方便(Convenience)： 使计算机更易于使用
• 有效 (Efficiency)：使计算机系统资源得到最大化利用
• 扩展的能力(Ability to evolve)：有效地开发、测试和引进新的系统功能

4个功能模块：文件系统、设备管理、存储器管理、处理器（进程）管理

操作系统的发展

简单批处理系统：

目标：为了解决人工操作（无操作系统）严重降低了计算机资源利用率的问题，即解决CPU等待人工操作和高速CPU与低速I/O间矛盾等问题。

脱机输入输出技术：该技术利用一台外围机，脱离主机先将低速输入设备（如纸带机）的数据，输入到较高速大容量的输入设备（如磁带）上。

使用监控程序

多道批处理系统：
它是在计算机内存同时存放几道相互独立的程序，这几道程序都处于运行过程中，它们先后开始了各自的运行，但都未运行完毕。多道程序在宏观上并行执行，而在微观上多道程序在某个部件上（如CPU、I/O）是串行的，即多道程序轮流地使用部件，交替执行。调度算法

分时系统：交互性、响应时间、时间片轮转（依次给队列中的每个进程分配一定的时间）

实时系统：实时、可靠、快速响应、

多道程序设计的概念：（宏观并行，微观即单设备串行）

现代操作系统的特征和主要成就

进程：包含三个部分：

• 一段可执行的程序
• 程序所需的相关数据
• 程序执行的上下文环境（操作系统用于管理和控制进程所需的所有数据（如PC, 数据寄存器内容, 进程优先级,进程状态等））

一个进程可分为多个并发的线程

内存管理
虚存

• 程序员使用虚地址访问内存，通过地址映射机制（通常由硬件实现）将虚地址动态映射为主存中的实地址
• 一个进程被分成若干个块（分页和分段），每一块都可以放置在主存中用户空间的任何地方
• 进程执行时，只需要一部分块在内存中即可。当访问的块不在内存中时，产生缺页中断，将所要访问的块从磁盘调入内存

安全性

• 可用性：确保系统正常可用
• 保密性：确保用户不能访问未授权的数据
• 数据完整性：保护数据不被未授权修改
• 认证：用户身份的认证、数据的合法性

调度

• 公平性（Fairness ）：平等、公平地访问资源
• 有差别的响应性（Differential responsiveness ）：根据进程的不同优先级差别对待
• 有效性（Efficiency ）：最大化吞吐量、最小化响应时间、尽可能容纳更多的用户

第三章 进程描述和控制

基本概念

进程(Process)定义：“可并发执行的程序在一个数据集合上的运行过程”。

• 一段可执行的程序
• 计算机中正在运行的程序的一个实例
• 可以分配给处理器并由处理器执行的一个实体
• 由一个顺序的执行线程、一个当前的状态以及一组相关的系统资源所描述的活动单元

从结构上，进程实体由程序段、数据段和进程控制块三部分组成。

进程的状态以及各状态间的转换条件（重点）

五状态模型

• 运行（Running）：占有CPU
• 就绪（Ready ）：除了CPU，其它所需资源都已占有，一旦得到处理机即可运行，则称此进程处于就绪状态
• 阻塞（Blocked ）：等待某些事件
• 新建（New ）: 已经创建了PCB并保存在主存中，但程序代码和相关数据还没有读入主存
• 退出（Exit ）

挂起（Suspended）进程

会出现内存中所有进程都被处理器执行了一遍, 都在等待I/O事件(即都是”阻塞”状态), 此时处理器空闲了, 却不能处理未进入内存的待执行程序.

可以通过不断增加内存大小来解决， 内存价格与大小是指数相关的, 不能一味增加大小. 因此操作系统引入了挂起(交换)的概念, 即内存已满时, 操作系统会将内存中等待I/O的进程(即”阻塞”状态)移动到硬盘中, 并从硬盘中调入新的"就绪"进程. 换出的进程被放置在挂起队列中, 由此引申出了七状态模型。

进程的描述

操作系统利用表结构来管理四种不同类型的表：存储表、I/O设备表、文件表和进程表。

进程控制块PCB的作用――进程存在的唯一实体
进程控制块中记录进程存在和特性信息，它与进程同生死。创建一个进程就是为其建立一个PCB，当进程被撤消时，系统就回收它的PCB；OS对进程的控制是根据PCB来进行，对进程管理也通过对PCB管理来实现，所以进程控制块是进程存在的唯一实体。

PCB的信息

• 进程标识信息：它用于唯一地标识一个进程。它有外部标识符（由字母组成，供用户使用）和内部标识符（由整数组成，为方便系统管理而设置）二种。
• 处理器状态信息：它由处理器各种寄存器（通用寄存器、指令计数器、程序状态字PSW、用户栈指针等）的内容所组成，该类信息使进程被中断后重新执行时能恢复现场从断点处继续运行。
• 进程控制信息 ：它包括进程状态（running、ready、blocked）、队列（就绪、阻塞队列）、队列指针，调度参数：进程优先级、进程已执行时间和已等待时间、进程间通信的信号系统、进程所分配的内存空间指针等。

进程控制

模式切换
用户模式（目态）：通常在该模式下执行用户程序、权限较低
系统模式、控制模式或内核模式（管态）：在该模式下执行操作系统内核、
可执行特权指令，权限更高

用户调用操作系统服务（系统调用）或发生中断时，执行模式从用户模式切换到内核模式
当系统服务返回或中断返回到用户进程时，执行模式从内核模式切换到用户模式

进程切换
进程切换可以在操作系统从当前正在运行的进程中获得控制权的任何时刻发生。

进程切换和模式切换的区别：
模式切换是系统执行模式的改变，发生模式切换可以不改变正处于运行态的进程状态。

进程切换时，操作系统必须使其运行环境发生改变。进程切换必然会存在模式切换（只有在内核模式下才能实现进程调度），但模式切换不一定会发生进程切换。

进程切换比模式切换更复杂。

创建进程
给进程分配一个唯一的进程标识号

给进程分配空间(进程要执行的程序代码和数据)

初始化进程控制块（如PC初始化为程序入口地址；进程状态初始化为就绪或就绪/挂起；进程优先级初始化为最低优先级等）

将进程控制块加入到正确的队列中（如加入到就绪队列中）

创建或扩充操作系统所需的其他数据结构（如审计文件）

第四章 线程

基本概念：线程定义为进程内一个执行单元或一个可调度实体。
线程只拥有一点在运行中必不可省的资源（程序计数器、一组寄存器和栈），但它可与同属一个进程的其它线程共享进程拥有的全部资源。

线程和进程的区别：进程是操作系统资源分配的基本单位，而线程是任务调度和执行的基本单位

线程三个基本的状态：运行Running, 就绪Ready 和阻塞Blocked。挂起状态对线程是没有意义的。

因为进程内的所有线程共享相同的地址空间，因此，挂起一个进程则该进程内的所有线程都将挂起。进程终止了，则该进程内的所有线程也将终止。

用户及线程和内核级线程
用户级线程

• 线程管理的所有工作都由应用程序来完成，内核并不知道线程的存在。应用程序使用线程库来实现多线程，线程库是个程序包，其中包括创建或删除线程，在线程间传递消息和数据，调度线程执行以及保存和恢复线程上下文等代码
  优点：
  不依赖于OS内核，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程，可以在任何操作系统中运行

调度由应用软件内部进行，通常采用非抢先式或更简单的规则，无需用户态/核心态切换，所以速度特别快，用户线程调度算法可针对应用优化

同一进程内各线程的切换不需要内核参与，减少了模式切换的开销

缺点：
当一个线程因系统调用而被阻塞时，该进程内的所有线程都被阻塞（为什么？）
答：系统调用使得模式从用户模式切换到内核模式，操作系统只知道进程，故操作系统将进程置为阻塞状态，从而使得该进程内的所有线程都被阻塞
内核一次只把一个进程分配给一个处理器，因此一次进程中只有一个线程可以执行，使多线程技术不能得到应用

内核级线程：
有关线程管理的所有工作都由内核来完成
应用程序只调用内核级线程的API
操作系统基于线程进行调度

优点：
内核可以同时把同一个进程中的多个线程调度到多个处理器中，从而更好地利用多道程序设计技术

如果一个进程内的线程阻塞，内核可以调度同一进程内的其他线程运行，不会导致整个进程被阻塞

内核例程自身也可以使用多线程

缺点：
同一个进程内两个线程的切换需要内核模式的切换

第五章 并发性：互斥和同步

与并发相关的概念

• 互斥（ mutual exclusion )指多个进程不能同时使用同一个资源
• 死锁（ deadlock )指多个进程互不相让，都得不到足够的资源
• 饥饿（ starvation )指一个进程一直得不到资源（其他进程可能轮流占用资源）
• 活锁：多个进程为响应其他进程中的变化而持续改变自己的状态而不能有用的工作的情形
• 临界区：一段代码，在这段代码中进程将访问共享资源，当另一个进程已在这段代码中运行时，这个进程就不能在这段代码中运行

互斥：软件和硬件的方法

软件方法

硬件实现方法

• 特殊的机器指令
• 在单个指令周期内执行，是原子性的指令（不能被中断）
• 在该指令执行时，任何需要访问内存的其他指令都将被阻塞
• 两种常见的指令：Testset和exchange指令

优点

• 适用于在单处理器或共享内存的多处理器上任何数目的进程
• 非常简单且易于证明
• 可用于支持多个临界区

缺点

• 忙等待
• 可能饥饿：多个进程等待进入临界区，选择哪个进程是随机的
• 可能死锁：考虑优先级情况

信号量(Semaphores)机制（重点）
基本原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一个位置停止，直到它接收到一个特定的信号。

信号量的定义：特殊的变量，称为信号量，用于发送信号
一个进程为了通过信号量s发送信号,它需要执行原语semSignal(s)/V(s)
一个进程通过信号量s接收信号, 它需要执行原语semWait(s) /P(s)
如果相应的信号没有接收到，该进程将被挂起，直到它所需的信号发送为止

一个具有整型数值的变量：被初始化为非负数 (nonnegative number).

semWait/P操作使信号量值减1。如果信号量值变为负数，则执行该操作的进程被阻塞。

semSignal/V 操作使信号量值增1。如果值小于或等于零，表示之前有进程在等该信号，则需要在该信号量的阻塞队列中唤醒一个进程。

同步也可以理解为：先做动作的进程C在动作完成后对同步信号量施加signal操作，代表发送消息；后做动作的进程P在动作前对同步信号量施加wait操作，代表测试消息是否到达。

生产者/消费者问题

读者/写者问题

信号量的物理含义：

• S>0表示有S个资源可用
• S=0表示无资源可用
• S<0则| S |表示S等待队列中的进程个数
• 信号量的初值应该大于等于0
• wait(s)（P(S)）:表示申请(等待)一个资源
• signal(s)（V(S)）:表示释放一个资源

第六章 并发：死锁和饥饿

死锁的原理

所谓死锁是指计算机系统和进程所处的一种状态。

在系统中，两个或多个进程无限期地等待永远不会发生的条件，此时称系统处于死锁状态。

一组进程因竞争系统资源或相互通信所造成的永久性阻塞

竞争资源引起死锁：在多道程序系统，多个进程共享系统的资源。对于可重用的资源，当系统把这类资源分配给某进程后，不能强行收回，只能在进程用完后自动释放。当多个进程竞争这类资源时就可能引起死锁。

进程推进顺序不当引起死锁：有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成了死锁。

死锁有四个条件

1. 互斥 (Mutual exclusion)：一次只有一个进程可以使用一个资源
2. 占有且等待 (Hold-and-wait)：当一个进程在等待分配得到其他资源时，将继续占有已分配到的资源
3. 非剥夺 (No preemption )：不能强行抢占进程已占有的资源，以上三个还不能确定发生死锁
4. 循环等待 (Circular wait)：存在一个封闭的进程-资源链，每个进程至少占有一个该链中下一个进程所需要的资源

死锁的防范：理解哪个方法破坏了哪个条件

死锁的预防（Prevention）

• 间接死锁预防（预防前三个）
• 直接死锁预防（预防循环等待）

死锁的避免 (Deadlock Avoidance)

银行家算法：允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁。

死锁检测算法

哲学家就餐问题

第七章 内存管理

逻辑地址 (Logical)：

• 程序员访问的地址，与当前数据在内存中的实际位置无关
• 在进行内存访问时，必须将其转换成物理地址

相对地址 (Relative)

• 逻辑地址的特例
• 相对于某些已知点（通常的程序开始处）的存储单元

物理地址(Physical)

• 也称为绝对地址
• 是数据在主存中的实际位置

地址重定位，也称地址映射（map），它将相对地址转换成内存中的绝对地址。按照重定位的时机，可分为静态重定位和动态重定位。

内存管理技术

动态分区分配算法

(1)最佳适应算法BF（Best Fit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。

(2)首次适应算法FF（First Fit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。

(3)循环首次适应算法/邻近算法NF(Next Fit)：该算法是首次适应算法的变种，它把空闲分区表（空闲区链）中的空闲分区按地址递增构成一个循环链。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得比较均匀。

(4)最坏适应法：从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业；空闲分区按大小由大到小排序。该算法使小的空闲区减少，但造成大的空闲区不够大

逻辑地址到物理地址的转换

在进行地址变换时，系统将逻辑地址截成页号和页内地址二部分，将页号与页表长度进行比较，如果页号大于等于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，查页表得到该页的物理块号，将物理块号与逻辑地址中页内地址二者拼接成物理地址，这样便完成了从逻辑地址到物理地址的变换。

第八章 虚拟内存

基本概念

缺页中断：当处理器需要访问一个不在主存中的块时，系统将产生一个内存访问故障中断

局部性原理：程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。

抖动现象（thrashing）：即处理器大部分时间都用于交换块，而不是执行指令。

为了提高地址变换的速度，增设了一个具有按内容查找、并行查询功能的特殊的高速缓冲存储器，称为 “快表”，或称为“关联存储器(TLB, 转换后备缓冲器)”，用以存放当前访问的那些页表项，每个页表项包括页号和相应的块号（页号不能省略）。
引入快表之后的存储访问修改如下：
处理器首先将逻辑地址中的页号与TLB中的各页表项的页号进行比较
如果有相同的 (TLB命中)， 则直接从TLB的输出寄存器输出相应的块号
如果没有找到(TLB不命中) ，则访问内存从该进程的页表中查找
检查该页是否在内存中(检查P位)
如果不在，则发生缺页中断
页访问之后，同时要将该页的页表项读入TLB

请求分页

扩充的页表机制和缺页中断机构。

请求分段

在简单分段系统的基础上实现的虚拟存储器，是以分段为单位进行换入、换出的。
在程序运行之前只要先调入若干个分段（不必调入所有的分段），便可启动运行。
当所访问的段不在内存时可请求OS将所缺的段调入内存。
为实现请求分段存储管理方式，同样需要一定的硬件支持和相应的软件，有段表机制、缺段中断机构以及地址变换机构。

段页式系统

它以分页的方式管理内存，具有分页系统能有效地提高内存利用率的优点；又以分段的方式管理用户的逻辑地址空间，具有分段系统能很好地满足用户需要的长处

在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中必需同时配置段表和页表。由于将段中的页进行离散地分配，段表中的内容不再是段的内存始址和段长，而是页表始址和页表长度。

固定的分配会产生内部碎片，比如分页式、段页式、固定分区管理
分段式存储管理会产生外部碎片

替换策略

缺页率：页面置换算法的性能指标：缺页率（ page fault rate ）=“缺页次数 / 内存访问次数” (比率)

• 最佳 (Optimal policy,OPT)：选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去
• 先进先出（FIFO）置换算法：选择在内存中驻留时间最久的页面予以淘汰。
• 最近最久未使用置换算法（Least Recently Used，LRU）：选择最近最久未使用的页面予以淘汰
• Clock置换算法 可以看下面这个链接的解释
  Clock置换算法

具体例子
补充：Clock算法中*表示相应的使用位为1

第九章 单处理器调度

长程调度：
决定加入到待执行的进程池中，决定哪一个程序可以进入到系统中被处理；

加入的进程越多，每个进程可以执行的时间百分比越小，因此控制多道程序设计的度；

一个进程终止时可以执行该调度，选择某个程序加入到就绪队列或就绪/挂起队列中，供短程调度或中程调度处理；

可基于简单的先来先服务或优先级进行调度

中程调度：分配内存，对换
为了充分发挥内存的效能，需将那些暂时不能运行的进程从内存调到外存盘交换区去等待，而将那些在盘交换区的等待事件已经发生急需调度运行的进程从盘交换区调入内存。

有时内存中进程数目过多也需将处于就绪态的进程从内存调到盘交换区，当然在盘交换区等待时间过长的就绪态的进程也要调入内存。

在UNIX系统中,中程调度就是存储管理中的对换，即进程在磁盘的交换区和内存间的对换。

采用虚拟存储技术的分时系统往往设立中程调度。

短程调度：分配处理器

通常称为分派程序，执行得最频繁

决定将处理器分配给哪个就绪进程

是最基本的调度，任何操作系统都有短程调度/进程调度

可由以下事件激发：

• 时钟中断
• I/O 中断
• 操作系统调用
• 信号

周转时间(Turnaround Time)短：
它是评价批处理系统的重要性能指标。作业周转时间Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。周转时间Ti = 完成时间－到达(提交)时间

响应时间(Response Time)快：
响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。

系统吞吐量(throughput)大：
这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度具有密切关系。

FCFS (First-Come-First-Served）：先来先服务

RR（Round-Robin）：时间片轮转
分时系统采用的主要调度算法
总是选择就绪队列中第一个进程，允许其占有处理机一个时间片的时间。当执行的时间片用完时，调度程序便停止该进程的执行，并将它送到就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。
采用基于时间片的抢占模式
周期性地发生时钟中断，使操作系统获得控制权
每次就绪进程的选择都基于FCFS策略

SPN（Shortest Process Next）：最短进程优先
在就绪队列中选择所需服务时间最短的进程

SRT（Shortest Remaining Time）：最短剩余时间优先
在就绪队列中选择运行所需剩余时间最短的进程

HRRN（Highest Response Ratio Next）：最高响应比优先
在就绪队列中选择响应比最高的进程来调度
非抢占模式
选择函数max®=max(1+w/s)
折中策略，综合考虑服务时间和等待时间

feedback反馈
原则：处罚运行时间较长的作业
基于抢占原则（按时间片）并使用动态优先级机制
新进程进入RQ0，每当它被抢占，则降到下一个优先级队列中
优先级最低队列采用轮转法，其他队列采用FCFS机制

第十一章 I|O管理和磁盘调度

I|O功能的组织：

程序控制I|O：
处理器给I/O模块发送I/O命令，进程进入忙等待，直到I/O操作完成才可以继续执行

中断驱动I|O：
处理器发送I/O命令，然后继续执行后续指令，当I/O模块完成后，给处理器发送中断

DMA：
由DMA模块控制主存和I/O模块之间的数据交换

I/O系统的目标—设备独立性

为了提高操作系统的可适应性和可扩展性，目前几乎所有的操作系统都实现了设备的独立性（Device Independence）（也称为设备无关性）。

用户程序的设备独立性是：用户程序不直接使用物理设备名（或设备的物理地址），而只使用逻辑设备名；而系统在实际执行时，将逻辑设备名转换为某个具体的物理设备名，实施I/O操作。

I/O软件的设备独立性是：除了直接与设备打交道的低层软件之外，其他部分的软件并不依赖于硬件。I/O软件独立于设备，就可以提高设备管理软件的设计效率。

设备独立性的好处：
（1）设备分配时的灵活性
当进程以逻辑设备名请求某类设备时，如果一台设备已经分配给其它进程或正在检修，此时系统可以将其它几台相同的空闲设备中的任一台分配给该进程。
（2）易于实现I/O重定向
所谓I/O重定向，指用于I/O操作的设备可以更换，应用程序的输入、输出可以重定向，不必修改应用程序

I|O缓冲区

单缓冲、双缓冲、循环缓冲

磁盘调度算法

寻道时间（ Seek time ）TS：
这是把磁头从当前位置移动到指定磁道上所经历的时间。该时间是启动磁盘的时间s与磁头移动n条磁道所花费的时间之和。即 TS＝m×n十s

旋转延迟时间（ Rotational delay or rotational latency ）Tr：
Tr 是指定扇区移动到磁头下所经历的时间。对于硬盘来说，典型的转速为3600RPM（目前硬盘的转速达到7200RPM），每转需时16.7ms，平均旋转延迟时间为8.3ms。对于软盘，其旋转速度为300或600RPM，平均Tr为50～100ms。

传输时间Tt：
Tt 是指把数据从磁盘读出，或向磁盘写入数据所经历的时间，它的大小与每次所读／写的字节数b及旋转速度r(/秒)有关：Tt =b/(r*N)(N为一条磁道上字节数)。

Ta= TS+ Tr+ Tt= TS + 1/2r+ b/rN

先来先服务FCFS算法：

先来先服务FCFS（First Come First Served）是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。

算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。

缺点是算法未对寻道进行优化，致使平均寻道时间可能较长（平均响应时间长）。

最短寻道时间优先SSTF算法：

该算法总是满足那些与当前磁头所在的磁道距离最近的请求,也就是执行寻道时间最短的那个I/O请求。

这种调度算法有较好的平均寻道时间。但它可能导致某些进程长时间的得不到服务（饥饿现象）。因为只要不断有新进程到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必被优先满足。

对中间磁道访问服务比内、外两侧磁道服务好，造成响应时间变化幅度大,在服务请求多时，内外边缘请求被无限期延迟，不可预期。

扫描（SCAN）算法：

即当磁头正在自里向外运动时，SCAN算法要选择的下一个访问对象是其欲访问的磁道在当前磁道之外，又是距离最近的。直至再无更外的磁道需要访问时，才将磁臂换向，自外向里运动。从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律象电梯的运行，所以又称为电梯调度算法。

克服SSTF服务集中中间磁道和响应时间变化较大缺点，两侧磁道的访问的频率低于中间磁道。

循环扫描 CSCAN算法：

CSCAN算法规定磁头只能单向运动（自里向外或自外向里），当磁头运动到最外面的被访问磁道时，磁头立即返回到最里面的欲访的磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。

磁盘Cache

如何将磁盘cache中的数据传送给请求的用户进程？
使用共享存储空间，将指向该共享空间的指针传递给进程即可，避免了数据直接传送的耗时。

如何替换cache中的数据块?
LRU和LFU算法

最不常用算法（Least Frequently Used, LFU）:
替换访问次数最少的块。
每个块关联一个计数器，由计数器来记录该块的访问次数。
块被读入时，计数器的值为1；每次访问到该块时，计数器的值+1。
替换时，选择计数器值最小的块。
存在一个问题：某些块可能在一段时间内被频繁地访问，使计数器值变得很大，但后面就不再访问到。因计数器值大，可能永远都不会被替换，虽然这块可能再也不会用到。

第十二章 文件管理

基本概念

文件是存储在某种介质上的（如磁盘、磁带等）并具有文件名的一组有序信息的集合

文件系统是操作系统中以文件方式管理计算机软件资源的软件和被管理的文件和数据结构（如目录和索引表等）的集合。

FAT文件系统（MS-DOS文件系统、msdos）
文件地址以FAT表结构存放，文件目录32B，文件名为8个基本名加上一个“.”和3个字符扩展名

文件的五种逻辑组织方式

• 堆 (Pile)
• 顺序文件 (sequential file)
• 索引顺序文件 (indexed sequential file)
• 索引文件 (indexed file)
• 直接或散列文件 (direct, or hashed, file)

文件目录和文件共享：“按名存取”

文件目录

为了实现“按名存取”，系统必须为每个文件设置用于描述和控制文件的数据结构，它至少要包括文件名和存放文件的盘物理地址，这个数据结构称为文件控制块FCB。

文件控制块的有序集合称为文件目录，即一个文件控制块FCB就是一个文件目录项。

三种记录组块方式

固定组块 (Fixed blocking)

• 记录长度固定
• 若干条完整的记录被保存在一个块中
• 存在内部碎片

可变长度跨越式组块 (Variable-length spanned blocking)

• 记录长度可变
• 紧缩在块中，解决了内部碎片问题
• 某些记录可能跨两个块，通过指针指向后继块

可变长度非跨越式组块 (Variable-length unspanned blocking)

• 记录长度可变
• 记录不跨块，存在内部碎片问题

固定组块是记录长度固定的顺序文件最常用的格式
可变长度跨越式组块存储效率高，但难于实现
可变长度非跨越式组块会导致空间的浪费，并且记录大小受块大小限制

三种文件分配方法（连续、链式、索引）

连续分配（Contiguous allocation）

创建文件时，给文件分配一组连续的块

预分配策略，分区大小可变

文件分配表FAT中每个文件只需要一个表项：起始块和文件长度

存在外部碎片，需定期执行压缩技术

读取文件中第i块需要访问几次磁盘？
A：1次，根据FAT中文件的起始块，访问所需要的块（假设起始块为b，要访问第i块，则其位置为b+i-1）

链式分配

基于单个块进行分配，链中每一块都包含指向下一块的指针

动态分配：按需进行块分配

FAT表中每个文件一个表项：起始块和文件长度

优点是盘存储空间利用率高，文件增删改记录方便，不存在外部碎片

局部性原理不再适用，可周期性地对文件进行合并

读取文件中第i块需要访问几次磁盘？
A：i次，根据FAT找到该文件的起始块，顺着链指针依次往下找，因此访问第i块，需要查找i次

索引分配

文件分配表FAT中对每个文件都包含一个一级索引

文件索引保存在单独块中，在FAT的表项里指向这一块的值

分配可基于固定大小的块，也可基于可变大小的分区：索引块中包括指向文件所有块的指针或指向分区起始块的指针

支持顺序访问文件和直接访问文件，是最普遍的一种文件分配形式

读取文件中第i块需要访问几次磁盘？
A：2次，第一次，根据FAT找到该文件的索引块；第二次，根据索引的指针找到所要访问的第i块

空闲空间管理（位示图）

磁盘分配表（Disk allocation table，DAT）用来记录磁盘上哪些块是可用的
三种常用技术:

位表（Bit tables）

链式空闲区（Chained free portions）

索引（Indexing）

下面的一些选择题是别的大佬整理的，可以看看
选择题

希望可以有所帮助！

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn/qq_43515163/article/details/112701397

本文标签： 操作系统笔记