操作系统复习参考

背就完了

操作系统引论
进程的描述与控制
处理机调度和死锁
存储器管理
输入输出系统
文件系统
大题

操作系统引论

定义

操作系统是一组控制和管理计算机软硬件资源、合理地对各类作业进行调度以及方便用户使用的程序集合。操作系统是一组控制和管理计算机软硬件资源、合理地对各类作业进行调度以及方便用户使用的程序集合。

操作系统目标

有效性
方便性
可扩充性
开放性

作为计算机系统资源的管理者

处理机管理：分配和控制处理机
存储器管理：分配及回收内存
I/O(Input/Outpcut)设备管理：I/O 分配与操作
文件管理：文件存取、共享和保护

操作系统分类

未配置操作系统的计算机系统
单道批处理系统

自动性
顺序性
单道性

资源利用率仍不高：CPU、内存
平均周转时间长
没有交互能力
多道批处理系统
优点
提高 CPU 利用率
提高内存和 I/O 设备利用率
提高了系统吞吐量
资源利用率高
系统吞吐量大
CPU 和其他资源保持“忙碌”状态
仅当作业完成或者进行不下去时才切换，系统开销小
缺点
平均周转时间长
无交互能力
分时系统
定义

指一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户共享主机中的资源，各个用户都可通过自己的终端以交互方式使用计算机）

分类
单道分时系统
具有前、后台的分时系统（仅当前台无作业或在调进、出时，才运行后台批处理作业）
多道分时系统（不需要调入、出开销）
特性
多路性：多终端分时共享，提高资源利用率，降低费用。
独立性：每个用户在各自的终端上进行操作，彼此之间互不干扰，感觉就像独占主机。
及时性：及时响应请求，通常为 1-3 秒。
交互性：指用户可通过终端与系统进行广泛的人机对话。
典型系统：
Multics (MIT)
UNIX
实时系统
定义

系统能及时响应外部事件的请求，在规定的时间内完成对事件的处理，并控制所有实时任务协调一致地运行

特性（和分时系统相比）
多路性：相同
独立性：相同
及时性：实时系统要求更高
交互性：分时系统交互性更强
可靠性：实时系统要求更高
通用操作系统
单用户单任务操作系统
CP/M
MS-DOS
单用户多任务操作系统
Windows 系列（不会 Server 版）
多用户多任务操作系统
Unix
Solaris
Linux

操作系统基本特征

并发性
共享性
时分复用虚拟处理机技术，虚拟设备技术
空分复用虚拟存储
虚拟性
异步性

操作系统的功能

处理机管理
存储器管理
设备管理
文件管理
友好的用户接口

操作系统的结构设计

无结构
模块式
层次式
微内核

特征

足够小的内核
采用 C/S 模式
应用“机制与策略分离”原则
采用面向对象技术

优点问题

提高了可扩展性
增强了可靠性
可移植性强
提供了对分布式系统的支持
融入了面向对象技术
性能代价

进程的描述与控制

执行的特征：

顺序执行：

顺序性
封闭性（程序运行时独占全机资源，程序一旦开始执行，其执行结果不受外界因素影响）
可再现性

并发执行：

间断性
失去封闭性
不可再现性

进程的定义与特征

定义：
程序的一次执行
一个程序及其数据在处理机上顺序执行时所发生的活动
具有独立功能的程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。
进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
特征：动态性，并发性，独立性，异步性
结构：数据段、程序段、PCB（加起来等于进程映像）
PCB：
进程标志符（内部标识符【PID】、外部标识符）
处理器状态信息
通用寄存器
PC
PSW
SP
进程调度信息
进程状态
进程优先级
进程调度所需的其他信息（进程已等待 CPU 的时间总和、进程已执行的时间总和）
事件（阻塞原因）
进程控制信息
程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址；
进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等；
资源清单，列出了除 CPU 以外的、进程所需的全部资源及已经分配到该进程的资源的清单；
链接指针，它给出了本进程(PCB)所在队列中的下一个进程的 PCB 的首地址。

进程的状态转换

挂起使执行的进程暂停执行,静止下来,使就绪状态的进程暂不接受调度；当一个进程正常终止时（直接调用 exit 函数，或从 main 函数返回），则所有带未写缓冲数据的标准 I/O 都会被冲洗，所有打开的标准 I/O 流都会被关闭。

进程控制

进程同步

同步：并发进程在执行次序上的协调，以达到有效的资源共享和相互合作，使程序执行有可再现性。
原则
空闲让进：如果临界区空闲，则只要有进程申请就立即让其进入，以有效利用资源。
忙则等待：每次仅允许一个进程处于临界区，保证对临界资源的“互斥”访问。
有限等待：进程只能在临界区内逗留有限时间，不得使其他进程在临界区外陷入“死等”。
让权等待：进程不能进入临界区时，应立即释放处理机，以免陷入“忙等”状态
信号量
整型信号量
资源型信号量（记录型信号量）
注意
若干进程在临界段上互斥，并不是说某个进程处于该临界段时，就不能被其他进程打断。比如一个进程在临界区执行时，另一相关进程由进程调度可以剥夺其 CPU 的占有权。临界区进程

进程通信

低级通信：进程之间交换控制信息的过程
高级通信：进程之间交换批量信息的过程

线程

进程是资源分配的最小单位，线程是系统调度的最小单位。

每个线程都有一个独立的栈和独立的线程控制块 TCB，包含寄存器值、优先级、堆栈。线程运行状态、线程专有存储器、信号屏蔽等状态参数。

状态
运行状态
就绪状态
阻塞状态（系统调用时进入核心态时，若线程阻塞则其所在进程也会被阻塞）
状态变换
派生（Spawn)：当产生一个新进程时，同时也为该进程派生了一个“初始化线程”，随后，可以在同一个进程中派生另一个线程，新线程被放置在就绪队列中。
阻塞（Block)：当线程需要等待一个事件时，它将阻塞，此时处理器转而执行另一个就绪线程。
解除阻塞（Unblock）：当阻塞一个线程的事件发生时，该线程被转移到就绪队列中。
结束（Finish）：当一个线程完成时，其寄存器的信息和栈都被释放。
由于线程不是资源的拥有单位，挂起状态对线程是没有意义的，如果一个进程挂起后被对换出主存，则它的所有线程因共享了进程的地址空间，也必须全部对换出去。可见由挂起操作引起的状态是进程级状态，不作为线程级状态。类似地，进程的终止会导致进程中所有线程的终止。
分类
多对一：纯用户线程模式
一对一：内核线程模式，轻量级进程模式
多对多：组合模式

处理机调度和死锁

处理机调度：

分类：
高级调度（作业调度，长程调度）把外存后备队列中作业调入内存，用于批处理系统，分/实时系统一般直接入内存，无此环节。频率为分钟级。
低级调度（进程调度，短程调度）分派程序（dispatcher)，毫秒级。
中级调度（内存调度，中程调度）Swapping 把外存上那些已经具备运行条件的就绪进程重新载入内存。从静止就绪到活动就绪。由内存管理中的对换进程实现。
引起进程调度的原因：
正在执行的进程执行完毕，或因发生某事件而不能再继续执行（包括：当前执行进程被中断、时间片用完了、挂起自己、退出、I/O 请求）
PV 操作原语、Block、Wakeup
目标：
资源利用率
公平性
平衡性
策略强制执行
批处理系统的目标：
平均周转时间短（从被提交到完成 = 接纳等待、执行等待、执行时间、I/O 时间之和）

$$
带权周转时间=\frac{周转时间}{服务时间}
$$

系统吞吐量高（尽量多地选择短作业运行）
处理机利用率高（尽量选择计算量大的作业）矛盾
分时系统目标：
响应时间快
均衡性（指系统响应时间的长短应与用户所请求服务的复杂性相适应）
实时系统目标：
截止时间的保证
可预测性

作业调度算法（决定接纳多少个作业、接纳哪些作业）

FCFS（作业调度、进程调度）
SJF （short job first)，抢占则为 SRT。
PSA（priority-scheduling algorithm）抢占式用于常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中
HRRN（Highest Response Ratio Next）：

$$
R_p=\frac{等待时间+要求服务时间 = 响应时间} {要求服务时间}
$$

-轮转调度 RR（Round Robin）：FCFS 策略 + 时钟中断 + 时间片原则分时系统，事务处理系统

多级队列调度算法
多级反馈队列调度算法（Multileveled Feedback Queue）：队列优先级依次降低，执行时间片依次翻倍。新进程首先进入最高优先级的队列。每个队列采用 FCFS 算法。队列中的进程运行一个时间片后未结束则降级排到下一个队列的末尾。最低优先权队列中的进程则按 RR 方式运行。

实时调度算法

非抢占轮转调度
基于时钟中断抢占的优先权抢占调度
非抢占优先权调度
立即抢占的优先权调度
EDF（Earliest Deadline First）非抢占（非周期实时任务）抢占（周期实时任务）
LLF（Least Laxity 松弛度 First）

$$
松弛度=完成截止时间–剩余运行时间–当前时间
$$

t=0s 时，A1 的松弛度=20ms-10ms-0ms=15ms，B1 的松弛度=50ms-25ms-0=25ms，先执行 A1；
A1 执行完后，t = 10ms ,B1 的松弛度=50ms-25ms-10ms=15ms，A2 的松弛度=40ms-10ms-10ms=20ms，执行 B1；
B1 执行 20ms 后，t = 30ms, B1 的松弛度=50ms-5ms-30ms=15ms，A2 的松弛度=40ms-10ms-30ms=0ms，继续执行 A2；
A2 执行 10ms 后，t = 40ms,A3 的松弛度= 60-10-40 = 10，B1 = 50-5-40 = 5ms ，所以执行 B1

松弛度为 0 了就要抢占。

优先级倒置

存在高中低三个优先级的进程，高和低共享同一个临界资源，低优先级进程先进入临界区，阻止高优先级进程进入临界区，中优先级进程抢占低优先级进程的 CPU，使得低优先级进程无法从临界区退出，从而间接阻止更高优先级进程运行。
临界区不允许抢占。
优先级继承。

死锁

原因
竞争资源。
进程间推进顺序非法。
必要条件：
互斥
请求与保持
不剥夺
环路等待
预防：银行家算法

它表示系统可提供给进程继续运行所需的各类资源数目，初始值 Work：＝Available

存储器管理

存储系统的结构

寄存器（存储管理）
主存（存储管理）
高速缓存
主存
磁盘缓存
辅存（设备管理和文件系统）
磁盘（可移动存储介质）

链接

由链接程序(Linker)将编译后形成的一组目标模块（程序段），以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)）

静态链接
修改相对地址：即将除第一个模块外的相对地址修改成装入模块中的相应的相对地址。
变换外部调用符号：即将每个模块中所用的外部调用符号，都变换为新的相对地址。

缺点：

不便于对目标模块的修改和更新（若要更新其中一个模块，需要打开装入模块）
无法实现对目标模块的共享
装入时动态链接
定义

用户源程序是主目标模块，装入内存时再链接需要的其他模块。即在装入目标模块时，若发现一个外部模块调用，则由装入程序找出相应的外部目标模块，并将其装入内存。

优点
便于软件版本的修改和更新。只需修改各个目标模块，不必将装入模块拆开，非常方便。
便于实现目标模块共享。即可以将一个目标模块链接到几个应用模块中，从而实现多个应用程序对该模块的共享。
缺点
进程（程序）在整个执行期间，装入模块是不改变的；
每次运行时的装入所有涉及的模块，但许多模块并不是每次运行都需要的，占用内存。
运行时动态链接

装入

定义：由装入程序(Loader)将装入模块装入物理内存

绝对装入
可重定位装入
静态重定位
地址变换是在装入内存时一次完成的，且以后不能移动。
一般情况下,物理地址=相对地址 + 内存中的起始地址
适用于多道程序环境，可以将装入模块装入到内存中任何允许的位置。
优点：不需硬件支持，可以装入有限多道程序。
缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动，不易实现共享。
动态运行时装入（动态重定位）

对换

换出
先换出阻塞状态的，后换出就绪状态
尽量选择优先级低的
考虑内存驻留时间长短
换出进程:
只能换出非共享的程序和数据段，共享段有其他进程使用时不能换出。
先申请对换空间，然后启动磁盘将要换出的内容写出，最后才回收内存空间并修改进程控制块和内存分配表等数据结构。
换入
系统定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程并将其中换出时间最久的进程作为换入进程；

连续分配

基本概念：
内零头：分配给作业但作业并不需要的部分
外零头：太小无法分配给任何作业的块。

单一连续分配

分区式分配

固定分区（有 n 个分区（大小相等不相等均可），则可同时装入 n 个作业/任务）
简单，只存在有碎片（内零头）
动态分区（可变式分区）
顺序分配算法（空闲分区按照地址或者大小组织为链表）
首次适应算法 FF 有外零头
循环首次适应算法
最佳适应算法
最坏适应算法
分区分配

快速适应算法
对于每一类相同容量的空闲分区单独设立一个空闲分区链表；设置管理索引表，每个表项对应一种空闲分区类型，并记录该类空闲分区链表表头指针。
优点：
查找效率高
不会对任何分区产生分割，能保留大的分区，也不会产生碎片
缺点：
分区归还主存时算法复杂，系统开销较大。
内零头
伙伴系统

优点
分配和回收内存速度快
且不会产生很多小碎片
缺点
内存利用率不高，分配的内存大小为 2 的幂，假如只需要 65 个页面，也需要分配 128 个页面的块，从而浪费了 63 个页面，即产生内部碎片。

可重定位分区分配

通过作业移动将原来分散的小分区拼接成一个大分区。
作业的移动需重定位。是动态（因作业已经装入）

离散分配

分页（分页只有内零头）

页面和物理块
将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页。
相应地，也把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框。
在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。
由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”或称为“内零头” 。
页表
页表：每个进程对应 1 个页表，描述该进程的各页面内存中对应的物理块号
页表中包括页号、物理块号（还可有存取控制字段，对存储块中的内容进行保护）。
全部页表集中存放在主存的系统专用区中，只有系统有权访问页表，保证安全。
作业表：整个系统 1 张，记录作业的页表情况，包含进程号、页表长度、页表始址等信息。
空闲块表：整个系统 1 张，记录主存当前空闲块。

地址转换
在系统中只设置一个页表寄存器 PTR (Page-Table Register)，在其中存放当前运行的进程的页表在内存中的起始地址，和此进程的页表长度。
当进程真正投入运行时，从进程控制块 PCB 中读出其页表起始地址，并用它设置页表寄存器，以后地址转换时直接从 PTR 中获得页表的起始地址。

快表
为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为快表、TLB(Translation Lookaside Buffer)，或联想存储器（Associative Memory）专门保存当前进程最近访问过的一组页表项。

多级页表
反置页表
反置页表为每一个物理块设置一个页表项，并将它们按物理块的编号排序，其中的内容则是页号和其所属进程的标志符。整个系统只有一个页表
根据进程标志符和页号检索反置页表，如果找到则页表项中的序号就是该页所在的物理块号。如果检索未找到则失败或者必须请求调页。
评价
较小的页面有利于减少内零头，从而有利于提高内存的利用率。然而，较小的页面也将导致页表过大，从而降低处理机访问页表时的命中率(Hit Rate)。
块越大，内/外存之间的数据交换效率越高。因此，对于支持交换技术的系统，较大的页面有利于提高页面换进/换出内存的效率
分页操作由系统自动进行,一个页面不能实现某种逻辑功能。
用户看到的逻辑地址是一维的，无法调试执行其中的某个子程序或子函数。
采用分页技术不易于实现存储共享，也不便于程序的动态链接。

分段（分段只有外零头）

原因
方便编程根据编程人员的需要将程序分成代码段、数据段等独立信息段。
信息共享根据编程人员的需要对这些段进行更有效的信息共享和保护。
信息保护分段管理方式能更有效和方便地实现信息保护功能。
动态增长分段存储管理方式却能较好地解决数据段增长。
动态链接程序运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段调入内存并进行链接。
原理
分段：
作业地址空间按逻辑信息的完整性被划分为若干个段；
每段有段名（或段号），每段从 0 开始编址；
段内的地址空间是连续的
许多编译程序支持分段方式，自动根据源程序的情况产生若干个段
段表

地址变换机构

快表

信息共享
分页系统实现程序段的共享较为困难(每个进程都要写很多)
分段易于实现段的共享和段的保护
定义
为了实现分段共享，可在系统中配置一张共享段表，所有共享段都在共享段表中占有一个表项。

分配与回收
在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把 count 置为 1；
之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段表中，填上调用进程的进程名、存取控制等，再执行 count＝count＋1 操作，以表明有两个进程共享该段。
当共享此段的某进程不再需要该段时，应将该段释放，包括撤消该进程段表中共享段所对应的表项，以及执行 count=count-1 操作。
若 count 结果为 0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减 1 结果不为 0)，则只是取消调用者进程在共享段表中的有关记录。
分段保护
越界检查
存取控制检查
环保护机构
一个程序可以访问驻留在相同环或较低特权环中的数据；
一个程序可以调用驻留在相同环或较高特权环中的服务。

段页式

定义
先将用户程序分段，每段内再划分成若干页，每段有段名（段号），每段内部的页有一连续的页号。

比较

页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。段则是信息的逻辑单位，它含有一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。段则是信息的逻辑单位，它含有一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
页的大小固定且由系统决定，因而在系统中只能有一种大小的页面，而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

虚拟存储器

原理

时间局限性

如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。由于在程序中存在着大量的循环操作。

空间局限性

一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问; 程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

定义

是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
当进程运行时，先将当前要运行的部分程序装入内存，其他部分暂留外存；
当要执行的指令不在内存时，处理器发生中断，通知操作系统将所缺部分从外存调入内存，保证程序继续执行；
当内存不足时，允许程序部分换入、换出。

特征

多次性一个作业被分成多次调入内存运行。
对换性作业的运行过程中进行换进、换出，换进和换出能有效地提高内存利用率。
虚拟性能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

实现方法

分类

请求分页存储管理方式

硬件支持
请求分页的页表机制上增加若干项，作为请求分页的数据结构；

页号
物理块号
存在位
状态位（标志该页是否驻留内存）
访问位 A
修改位 M（供置换算法参考）
外存地址

缺页中断机构（在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求 OS 将所缺之页调入内存。地址转换时，检查页面的页表项中的存在位，如果为 0，则产生一个缺页中断）
操作系统接收到进程产生的缺页中断信号，启动中断处理例程，保留处理机现场；
操作系统通知处理机从外存读取指定的页面；
处理机激活 I/O 设备；
检查内存有无足够的空闲空间装入该页面？若有，转（6），否则，执行（5）；
利用页面置换算法，选择内存中的某个页面，换出内存；
将指定页面从外存装入内存；
更新该进程的页表；
更新快表；
计算物理地址。
地址变换机构
软件支持
实现请求调页的软件
实现页面置换的软件

请求分段系统

硬件支持
请求分段的段表机制上增加若干项，作为请求分段的数据结构；

段名
段长
段的基值
存取方式
访问位 A
存在位 P
修改位 M（供置换算法参考）
增补位
外存始址

缺段中断机构

地址变换机构

软件支持
实现请求调页的软件
实现页面置换的软件

段页式虚拟存储系统

内存分配策略和算法

最小物理块数的确定
物理块的分配策略
固定分配局部置换：为每个进程分配一定数目的物理块，在整个运行期间都不再改变。
可变分配全局置换（常用：先为系统中的每个进程分配一定数目的物理块，而 OS 自身也保持一个空闲物理块队列。用完后再调出。
可变分配局部置换：为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。
物理块分配算法
平均分配算法
按比例分配算法
考虑优先权的分配算法

调页策略

系统应当在何时把一个页面装入内存？

预调页
当进程创建时，预先为进程装入多个页面。
缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。
请求调页

从何处调入
系统拥有足够的对换区空间

进程运行前需将全部有关文件从文件区（离散分配）拷贝到对换区（连续分配）。
这时可以全部从对换区调入所需页面，以提高调页的速度

系统缺少足够的对换区空间

这时凡是未被修改的文件，都直接从文件区调入；而当换出这些页面时，若未被修改则直接丢弃，以后再调入时，仍从文件区调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入

UNIX

由于与进程有关的文件都放在文件区，应从文件区调入。凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。允许页面共享。

页面调入过程

每当程序所要访问的页面未在内存时，便向 CPU 发出一缺页中断。
中断处理程序首先保留 CPU 环境，分析中断原因后，转入缺页中断处理程序
如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出
如果此页已被修改，则必须将它写回磁盘。
然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为 “1”，并将此页表项写入快表中。
形成所要访问数据的物理地址，再去访问内存数据

页面置换算法
最佳(优)置换算法
先进先出（FIFO）页面置换算法
最近最久未使用（LRU）置换算法
寄存器：当进程访问某物理块时，要将相应寄存器的最高位 Rn-1 位置成 1。系统每隔一定时间（例如 100 ms）将寄存器右移一位。如果我们把 n 位寄存器的数看作是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。
栈：可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。
Clock 置换算法

当采用简单 clock 算法时，为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置 1。
置换程序从上次停止位置开始检查页面的访问位。如果是 0，就选择该页换出；若为 1，则重新将它置 0，暂不换出，而给该页第二次驻留内存的机会。置换时是将未使用过的页面换出去，故又把该算法称为最近未用算法 NRU。

改进型 Clock 置换算法

由访问位 A 和修改位 M 可以组合成下面四种类型的页面
A=0，M=0：表示该页最近既未被访问，又未被修改，是最佳淘汰页。
A=0，M=1：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
A=1，M=0：最近已被访问，但未被修改：该页有可能再被访问。
A=1，M=1：最近已被访问且被修改，该页可能再被访问。

从指针所指示的当前位置开始，扫描循环队列，寻找 A=0 且 M=0 的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。
如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找 A=0 且 M=1 的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置 0。
如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复 0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。
其它置换算法
最少使用
页面缓冲

访问内存的有效时间

从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间，成为内存的有效访问时间（EAT）
无快表时：

$$
EAT = 2t \space\space t 为单次内存访问需要的时间
$$

有快表时：命中率，指使用快表并在其中成功找到所需页面的表项的概率

$$
EAT=a \lambda+ ( t + \lambda )(1-a) + t = (2-a)t + \lambda
$$

具有快表机制的请求分页管理方式中,内存访问操作可以分为三种情况:

被访问页在内存中,且对应的页表项在快表中:

$$
{\it EAT}=\lambda+t
$$

被访问页在内存，单对应的页表项不在快表中

$$
{\it EAT} =2(\lambda+t)
$$

被访问页面不在内存

$$
{\it EAT}=2(\lambda+t)+\varepsilon
$$

考虑快表命中率为 a，访问缺页率为 f，则有效访问时间为

$$
{\it EAT}=查找快表时间+a * 根据物理地址访存时间\+（1-a） * [查找页表时间+f * (处理缺页时间+查找快表时间+根据物理地址访存时间)\+（1-f）* (修改快表时间+根据物理地址访存时间)]
$$

抖动与工作集

抖动
定义：如果运行进程的大部分时间都用于页面的换入/换出，而几乎不能完成任何有效的工作，则称此进程处于抖动状态。抖动又称为颠簸。
分类
局部抖动
全局抖动
原因
进程分配的物理块太少
置换算法选择不当
全局置换使抖动传播
工作集模型
定义：进程 Pi 工作集合 WSi = 在最近的时间内访问的页面集合，其中 为工作集窗口
工作集模型就用来计算一个局部的宽度(帧数)

输入输出系统

I/O 系统简介

任务
完成用户提出的 I/O 请求
提高 I/O 速率以及改善 I/O 设备的利用率
功能
设备分配
设备映射
设备驱动
I/O 缓冲区的管理（借用内存）
分层模型

10.用户层软件

11.设备独立性软件

12.设备驱动软件

13.中断处理程序

14.设备硬件

在 I/O 系统中，除了需要直接用于 I/O 和存储信息的设备外，还需要有相应的设备控制器和高速总线。
在有的大、中型计算机系统中，还配置了 I/O 通道或 I/O 处理机。
设备控制器:

设备控制器是 CPU 与 I/O 设备之间的接口，它接收从 CPU 发来的命令，并去控制 I/O 设备工作，以使处理机从繁杂的设备控制事务中解脱出来。
设备控制器主要职责是控制一个或多个 I/O 设备，以实现 I/O 设备和计算机之间的数据交换。
若控制器可连接多个设备时，则应含有多个设备地址，并使每一个设备地址对应一个设备。
通常，设备并不是直接与 CPU 进行通信，而是与设备控制器通信，因此，在设备与设备控制器之间应有一如下所示接口。

I/O 通道：一种特殊的执行 I/O 指令的处理机

I/O 通道设备的引入目的是使一些原来由 CPU 处理的 I/O 任务转由通道来承担，从而把 CPU 从繁杂的 I/O 任务中解脱出来。
DMA（直接存储器存取）方式显著地减少了 CPU 的干预。
只需向 I/O 通道发送一条 I/O 指令，即可完成一组相关的读（或写）操作及有关控制。
可实现 CPU、通道和 I/O 设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

中断机构和中断处理程序

中断简介
中断

中断源：引起中断发生的事件
中断请求：中断源（字符设备、块设备、通信设备）向 CPU 发出的请求中断处理信号
中断响应：CPU 收到中断请求后转到相应的事件处理程序的过程
关中断/开中断：CPU 内部的 PSW 的中断允许位被清除/被设置，不允许/允许 CPU 响应中断。用于保证某段程序执行的原子性
中断屏蔽：在中断请求产生后，系统有选择地封锁一部分中断而允许另一部分仍能得到响应。有些具有最高优先级的中断不允许被屏蔽。

陷入，通常把由 CPU 内部事件引起的中断称为内中断或陷入（trap）所引起的中断。例如进程在运算中发生了上溢或下溢，又如程序出错，如非法指令、地址越界，以及电源故障等。与中断一样，若系统发现了有陷入事件，CPU 也将暂停正在执行的程序，转去执行该陷入事件的处理程序。
中断向量表和中断优先级
对多中断源的处理方式

屏蔽（禁止）中断
嵌套中断

中断处理程序

测定是否有未响应的中断信号
保护被中断进程的 CPU 环境
转入相应的设备处理程序
中断处理
恢复 CPU 的现场并退出中断
是屏蔽中断，返回被中断的进程。
中断嵌套，如果没有优先级最高的中断请求 I/O 返回，否则处理该请求。
将保存在中断栈中的被中断进程的现场信息取出，并装入到相应的寄存器中，其中包括该程序下一次要执行的指令的地址 N+1、处理机状态字 PSW，以及各通用寄存器和段寄存器的内容。这样，当处理机再执行本程序时，便从 N+1 处开始，最终返回到被中断的程序。

设备驱动程序

概述
功能
接受与设备无关的软件发来的命令与参数，并将命令中的抽象要求转换为与设备相关的低层操作序列
检查用户 I/O 请求的合法性，了解 I/O 设备的工作状态，传递与 I/O 设备操作有关的参数、设置设备的工作方式
发出 I/O 命令，启动 I/O 设备若设备空闲，完成指定的 I/O 操作。将请求者的请求块挂在设备队列上等待
及时响应设备控制器发来的中断请求，根据中断类型，调用相应的中断处理程序进行处理
特点
驱动程序是实现在与设备无关的软件和设备控制器之间通信和转换的程序，具体说，它将抽象的 IO 请求转换成具体的 IO 操作后传送给控制器。又把控制器中所记录的设备状态和 IO 操作完成情况，及时地反映给请求 IO 的进程。
驱动程序与设备控制器以及 I/O 设备的硬件特性紧密相关，对于不同类型的设备，应配置不同的驱动程序。但可以为相同的多个终端设置一个终端驱动程序。
驱动程序与 I/O 设备所采用的 I/O 控制方式紧密相关，常用的 I/O 控制方式是中断驱动和 DMA 方式。
由于驱动程序与硬件紧密相关，因而其中的部分必须用汇编语言书写。目前有很多驱动程序的基本部分已经固化在 ROM 中。
驱动程序应允许可重入。一个正在运行的驱动程序常会在一次调用完成前被再次调用。
对 I/O 设备的控制方式

轮询的可编程 I/O 方式
程序 I/O（Programmed I/O）方式，或称为忙 – 等待方式。处理机向控制器发出一条 I/O 指令启动输入设备输入数据时，同时把 busy 置为 1，再不断循环测试 busy。
Busy=0，完成输入，处理机读取数据，送入指定单元，完成一次 I/O。
对状态寄存器中的忙/闲标志 busy 的检查实现控制。
使用中断的可编程 I/O 方式（以字节为单位，1000 字节要中断 1000 次）
当某进程要启动某个 I/O 设备工作时，便由 CPU 向相应的设备控制器发出一条 I/O 命令，然后立即返回继续执行原来的任务。设备控制器于是按照该命令的要求去控制指定 I/O 设备。此时，CPU 与 IO 设备并行操作。例如，在输入时，当设备控制器收到 CPU 发来的读命令后，便去控制相应的输入设备读数据。一旦数据进入数据寄存器，控制器便通过控制线向 CPU 发送一中断信号，由 CPU 检查输入过程中是否出错，若无错，便向控制器发送取走数据的信号，然后再通过控制器及数据线，将数据写入内存指定单元中。图 6-13(b)示出了中断驱动方式的流程。
直接存储器访问方式
数据传输的基本单位是数据块，即在 CPU 与 I/O 设备之间，每次传送至少一个数据块。
所传送的数据是从设备直接送入内存的，或者相反。
仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预，整块数据的传送是在控制器的控制下完成的。可见，DMA 方式较之中断驱动方式又进一步提高了 CPU 与 IO 设备的并行操作程度。
当 CPU 要从磁盘读入一数据块时，便向磁盘控制器发送一条读命令。该命令被送入命令寄存器 CR 中。同时，需要将本次要读入数据在内存的起始目标地址送入内存地址寄存器 MAR 中。将要读数据的字(节)数送入数据计数器 DC 中。还须将磁盘中的源地址直接送至 DMA 控制器的 IO 控制逻辑上。然后，启动 DMA 控制器进行数据传送。以后，CPU 便可去处理其它任务，整个数据传送过程由 DMA 控制器进行控制。当 DMA 控制器已从磁盘中读入一个字(节)的数据，并送入数据寄存器 DR 后，再挪用一个存储器周期，将该字(节)传送到 MAR 所指示的内存单元中。然后便对 MAR 内容加 1，将 DC 内容减 1，若减 1 后 DC 内容不为 0，表示传送未完，便继续传送下一个字(节);否则，由 DMA 控制器发出中断请求。图 6-15 是 DMA 方式的工作流程。

I/O 通道控制方式
I/O 通道方式是 DMA 方式的发展，它可进一步减少 CPU 的干预，即把对一个数据块的读（或写）为单位的干预，减少为对一组数据块的读（或写）及有关的控制和管理为单位的干预。
可实现 CPU、通道和 I/O 设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

与设备无关的 I/O 软件

功能
执行所有设备的公有操作。
对独立设备的分配与回收；
将逻辑设备名映射为物理设备名，进一步可以找到相应物理设备的驱动程序；
对设备进行保护，禁止用户直接访问设备；
缓冲管理
差错控制
提供独立于设备的逻辑块
向用户层(或文件层)软件提供统一接口

磁盘系统及磁盘调度

磁盘系统
数据的组织和格式
存储面(surface)
磁道(track)
柱面
扇区(sectors)
磁盘访问时间
寻道时间 s：启动磁臂的时间 n：磁头移动 n 条磁道 m：移动每一条磁道所花费的时间

$$
T_s=m\times n+s
$$

旋转延迟时间 Tτ

硬盘旋转速度为 15 000 r/min，每转需时 4 ms，平均旋转延迟时间 Tτ 为 2 ms；

传输时间 Tt，b 为字节数，r 为磁盘每秒钟的转数，N 为一条磁道上的字节数

$$
T_t=\frac{b}{rN}
$$

磁盘调度
先来先服务 FCFS
最短寻道时间优先 SSTF（可能发生“饥饿”现象）
扫描（SCAN）算法

该算法优先考虑的是磁头当前的移动方向。例如，磁头自里向外移动, 并同时自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向自外向里移动。（又常称之为电梯调度算法）

循环扫描（CSCAN）算法

CSCAN 算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。

文件系统

文件系统基本概念

文件的概念

文件是存储和管理数据的容器
文件是指由创建者所定义的、具有文件名的一组相关元素的集合。
若文件中的数据有格式，可能是如下的结构

在有结构的文件中，文件由若干个相关记录组成；
而无结构文件则被看成是一个字符流。
文件在文件系统中是一个基本的管理单元，这个管理单元必然有一组属性。

文件的属性

文件类型
按照用途分类

系统文件
用户文件
库文件

按照数据形式分类

源文件
目标文件
可执行文件

按存取控制属性分类

只执行文件
只读文件
读写文件

按组织形式和处理方式分类

普通文件
目录文件
特殊文件

文件长度
文件物理位置
文件建立时间

文件系统

概念
操作系统中的各类文件、管理文件的软件，以及管理文件所涉及到的数据结构等信息的集合。
功能
有效地管理文件的存储空间；
管理文件目录；
完成文件的读/写操作；
实现文件共享与保护；
为用户提供交互式命令接口和程序调用接口。
模型

用户（程序）
文件系统接口

命令接口
程序接口（系统调用）

对对象操纵和管理的软件集合

对文件存储空间的管理
对文件目录的管理
用于将文件的逻辑地址转换为物理地址的机制
对文件读和写的管理
以及对文件的共享与保护等功能。

对象及其属性

文件：它作为文件管理的直接对象。
目录：为了方便用户对文件的存取和检索，在文件系统中必须配置目录。对目录的组织和管理是方便用户和提高对文件存取速度的关键。
磁盘(磁带)存储空间：文件和目录必定占用存储空间，对这部分空间的有效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。

文件的逻辑组织与访问

逻辑结构
有结构文件
顺序文件
串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录，依此类推。
顺序结构，指文件中的所有记录按关键字(词)排列。是最常用的文件组织方式，可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。
索引文件
为变长记录文件建立一张索引表，对主文件中的每个记录，在索引表中设有一个相应的表项，用于记录该记录的长度 L 及指向该记录的指针(指向该记录在逻辑地址空间的首址)。
索引顺序文件
它将顺序文件中的所有记录分为若干个组(例如，50 个记录为一个组)；
为顺序文件建立一张索引表.
在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。
直接（哈希）文件
对于直接文件，则可根据给定的记录键值，直接获得指定记录的物理地址。
换言之，记录键值本身就决定了记录的物理地址。
物理结构

文件的基本操作

文件操作概述

创建文件、删除文件。读文件、写文件、截断文件和设置文件的读／写位置、对文件属性的操作、改变文件名、改变文件的拥有者、查询文件的状态等
文件的“打开”和“关闭”操作：所谓“打开”，是指系统将指名文件的属性（包括该文件在外存上的物理位置）从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（或称为索引）返回给用户。利用“关闭”（close）系统调用来关闭此文件，OS 将会把该文件从打开文件表中的表目上删除掉。

文件系统目录管理

文件目录的管理要求
实现“按名存取”
提高对目录的检索速度
文件共享
允许文件重名。
文件控制块和索引节点

文件控制块（FCB）：用于描述和控制文件的数据结构
基本信息：文件名、文件类型等；
地址信息：卷（存储文件的设备）、起始地址（起始物理地址）、文件长度（以字节、字或块为单位）等。
访问控制信息：文件所有者、访问信息（用户名和口令等）、合法操作等；
使用信息：创建时间、创建者身份、当前状态、最近修改时间、最近访问时间等。
文件目录：文件控制块的有序集合。
通常，一个文件目录也被看做是一个文件，称为目录文件

FCB 存储全部目录内容
存储部分目录信息，如文件名、索引节点指针等，其余部分保存在索引节点（i 节点）。打开文件时将索引节点从磁盘读到内存中。索引节点：文件描述信息单独形成一个数据结构。文件名与索引节点分开。文件目录保存：文件名和对应的文件索引节点。每个文件都在磁盘上保存一个磁盘索引节点，当文件被打开时，文件的索引节点从磁盘读入内存，称为内存索引节点。

单级目录结构
查找速度慢
不允许重名
不便于实现文件共享
两级目录结构（主文件目录 MFD、用户文件目录 UFD）
树形目录结构
树叶是数据文件
树的节点是目录，或称为子目录。

创建目录：在用户要创建一个新文件时，只需查看在自己的 UFD 及其子目录中，有无与新建文件相同的文件名。若无，便可在 UFD 或其某个子目录中增加一个新目录项。
目录删除采用下述两种方法处理：（1）不删除非空目录。（2）可删除非空目录。
改变目录：改变工作目录 ▪ 移动目录：将子目录或者文件移动到其他目录下。
链接操作：通过链接让同一个文件具有多个父目录
查找：在目录中查找某个文件或者子目录。
线性检索
Hash 方法

文件系统外存管理

有关问题

从物理组织的角度看，文件由若干数据块组成
操作系统或文件管理系统负责为文件分配和管理数据块
如何划分磁盘空间？
如何为一个新建文件分配空间？
如何为一个已存在的文件增加存储空间？
用什么数据结构记载文件已分配到的数据块和空闲数据块？

组织方式概述

目的
有效地利用外存空间
提高对文件的访问速度
提高磁盘系统的可靠性
连续组织
连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。
把逻辑文件中的数据顺序地存储到物理上邻接的各个数据块中，这样形成的物理文件可以进行顺序存取。
文件目录中为每个文件建立一个表项，其中记载文件的第数据块地址及文件长度。
对于顺序文件，连续读/写多个数据块内容时，性能较好。
优点
顺序访问容易
顺序访问速度快
缺点
要求有连续的存储空间
必须事先知道文件的长度
链接组织
连续组织一次分配的文件分区太大，不利于存储空间的有效利用。
如果在将一个逻辑文件存储到外存上时，可以考虑将文件装到多个离散的盘块中。
链接文件：采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。
分类
隐式链接
在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。
每个盘块中都含有一个指向下一个盘块的指针。
缺点: 如果要访问文件所在的第 i 个盘块，则必须先读出文件的第一个盘块……，就这样顺序地查找直至第 i 块。一个簇可包含 4 个盘块，在进行盘块分配时，是以簇为单位进行的。在链接文件中的每个元素也是以簇为单位的。减少查找时间和指针所占空间，但增大了内部碎片
显式链接
把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。
整个磁盘仅设置一张文件分配表（FAT）
优点
消除磁盘外部碎片，提高了利用率
对插入、删除和修改记录都非常容易；
能适应文件的动态增长，无需事先知道文件的大小
缺点
不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在 FAT 中顺序地查找许多盘块号。
FAT 需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在 FAT 中的，因而只有将整个 FAT 调入内存，才能保证在 FAT 中找到一个文件的所有盘块号。
索引组织
优点
索引组织方式支持直接访问。当要读文件的第 i 个盘块时，可以方便地直接从索引块中找到第 i 个盘块的磁盘块号；
基于数据块的分区能消除外部碎片
缺点
单级索引组织
为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。
在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。

二级索引
增量索引
直接寻址：10 个块号
一级索引，一次间址：一个索引块
二级索引，二次间址
三级索引，三次间址

磁盘空闲空间管理

文件存储空间管理的概念

存储空间的基本分配单位是磁盘块。
其分配方法与内存的分配有许多相似之处，即同样可采取连续分配方式或离散分配方式。
系统应为分配存储空间而设置相应的数据结构；其次，系统应提供对存储空间进行分配和回收的手段。

文件存储空间管理方法概述

空闲分区表
空闲表法属于连续分配方式，它为每个文件分配一块连续的存储空间，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。
适合于可变大小分区的连续分配方式。
为文件分配存储空间时，首先顺序查找空闲分区表中的各个表项，直至找到第一个大小适合的空闲分区。
可以采用首次适应分配算法、最佳适应分配算法等。 ▪
然后，将该分区分配给文件，同时修改空闲分区表，删除相应表项。
当删除文件释放出空间时，系统回收其存储空间，合并相邻空闲分区。
对交换分区一般都采用连续分配方式。
对于文件系统，当文件较小(1～4 个盘块)时，仍采用连续分配方式，为文件分配相邻接的几个盘块；
当文件较大时，便采用离散分配方式。
优点
实现简单。对于最佳适应分配算法，可以将各空闲分区按照（长度）从小到大的顺序进行排列，再利用有效的查找算法，能很快找到需要大小的空闲分区。
缺点
当存储空间中的空闲分区分布较分散且数量较多时，空闲分区表将会很大。需要很大的内存空间，会降低空闲分区表的检索速度。
空闲链表法
空闲盘块链
将磁盘上的所有空闲空间，以盘块为单位拉成一条链。
当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。
当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。
空闲盘区链
将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块) 拉成一条链。
在每个盘区上含有用于指示下一个空闲盘区的指针和能指明本盘区大小(盘块数)的信息。
分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。
在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。
为了提高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张链表。
每个分区结点内容：起始盘块号、盘块数、指向下一个空闲盘区的指针。
问题
一段时间以后，可能会使空闲分区链表中包含太多小分区，使文件分配到的存储空间过分离散。
删除一个由许多离散小分区组成的文件时，将回收的小分区链接到空闲分区链表中需要很长时间。
若一个文件申请连续存储空间，则需要花费较长的时间查找相邻的空闲分区。
因此，这种空闲空间组织方法适合于非连续存储文件。
位示图
利用二进制位 0、1 表示存储空间中存储块的使用状态。
空闲分区:0，已分配分区:1（或者相反）。
磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。
通常可用 m × n 个位数来构成位示图，并使 m × n 等于磁盘的总块数。
位示图也可描述为一个二维数组 map：
优点
可以容易地找到一个或一组连续的空闲分区。
例如，我们需要找到 4 个相邻接的空闲盘块，这只需在位示图中找出 4 个其值连续为“0”的位即可。
缺点
一个位示图需要占用的存储空间大小为：磁盘容量（字节数）/ （8 * 数据块大小）
对于容量较小的磁盘，位示图占用的空间会很小。
对于一个 16GB 的磁盘，若数据块大小为 512 字节，则位示图大小为 4MB，大约需要占用 8000 个磁盘块的存储空间。
很难一次性将该位示图全部装入内存。即使内存足够大，可以存放全部或绝大部分位示图数据，搜索一个很大的位示图将会降低文件系统的性能。
尤其当磁盘空间快用完，剩下的空闲磁盘块很少时，文件系统的性能将严重降低。
成组链接法
成组链接法仅适用于离散分配形式，无法用于连续分配
将磁盘空闲块分成若干组，如将 100 个盘块作为一组，用索引表表示，值得一提的是栈顶是下标最大的。
该组空闲块总数和各空闲块块号存入下一组的第一个空闲块中（从后往前分组），各组通过链接指针连在一起形成链表；
空闲盘号栈存的是空闲盘块的盘块号，
最后不满 100 块的那组空闲块总数和各空闲块块号计入磁盘区专用管理块（超级块）的空闲盘块号栈的 s_nfree 和 s_free[100]中，其数据结构如下页所示。

分配
未到栈底：出栈，将栈顶盘块分配给用户
已到栈底盘块：先将栈底盘块出栈，然后将该盘块数据读到内存空闲盘块号栈中，再将栈底盘块分配出去。
回收 ▪
栈未满：进栈，依次将回收盘块号压入栈中
栈已满：先将栈内数据写入将回收的磁盘块中，将栈清空，再将回收盘块号进栈。
优点
无需占用额外的磁盘空间
分配回收速度快
大小磁盘均可采用
缺点
不适用于连续分配

文件共享与保护

文件共享

同时存取
存取权限
无（None） — 用户不知道文件的存在。用户无法获知该文件的目录信息，当然更不会知道文件的内容。
探知（Knowledge） — 用户可以检测文件的存在和文件的文件主，还可以向文件主申请增加对该文件的存取权限。
执行（Execution） — 用户可以装载并执行程序，但不允许拷贝程序内容。
读（Reading）— 允许用户读文件内容，包括拷贝和执行文件。某些系统严格地将浏览文件内容和拷贝权限分开，可以控制文件只能被浏览（显示），不能被拷贝。
追加（Appending）— 允许用户向文件添加数据，通常只能将数据添加到文件尾。但是，不能修改或删除文件内容。例如，超市收银员只能将新结帐的数据添加到文件中，不允许其修改或删除已有的数据。
更新（Updating）— 允许用户修改、删除、增加文件内容。包括创建文件、重写文件的全部或部分内容、移动文件的全部或部分数据等操作。
更改权限 (Changing protection) — 一般只有文件主才能更改共享该文件的其他用户对该文件的存取权限。有的系统允许文件主将更改文件存取权限赋予其他某个用户，但必须限制授权用户更改的权限范围。
删除 (Deletion) — 允许用户删除文件
实现
链接目录项
文件目录项中设置一个链接指针，用于指向共享文件的目录项。
访问文件时，根据链接指针内容找到共享文件的目录项，读取该目录项中文件起始位置等信息，操作该文件。
每当有用户（进程）共享文件时，共享文件目录项中的 “共享计数”加 1；当用户不再共享该文件，撤消链接指针时，“共享计数”减 1。
只有当共享文件用户数为 1 时，才能删除共享文件
索引节点
文件的物理地址及其它的文件属性等信息，不再是放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。
由任何用户对文件进行 Append 操作或修改，所引起的相应结点内容的改变(例如，增加了新的盘块号和文件长度等)，都是其他用户可见的，从而也就能提供给其他用户来共享。
可以通过共享文件索引节点来共享文件，即当用户需要共享文件时，在自己的文件目录中新建一个目录项，为共享文件命名(也可用原名)，并将索引节点指针指向共享文件的索引节点。
在索引结点中还应有一个链接计数 count，用于表示链接到本索引结点(亦即文件)上的用户目录项的数目。
符号链
为使 B 能共享 C 的一个文件 F，可以由系统创建一个 LINK 类型的新文件，也取名为 F 并将 F 写入 B 的目录中，以实现 B 的目录与文件 F 的链接；在新文件中只包含被创文件 F 的路径名。这样的链接方法被称为符号链接.
新文件中的路径名，则只被看作是符号链。当 B 要访问被链接的文件 F 且正要读 LINK 类新文件时，将被 OS 截获， OS 根据新文件中的路径名去读该文件，于是就实现了用户 B 对文件 F 的共享。
URL

大题

装入和链接

绝对装入
编译时确定位置
静态重定位装入
编译时产生从 0 开始的目标模块。装入时重定位改代码
动态运行时装入方式
需要寄存器，不改代码

调度算法的对比

引起进程调度的因素可归结为：
正在执行的进程执行完毕，或因发生某事件而不能再继续执行（包括：当前执行进程被中断、时间片用完了、挂起自己、退出等）；
执行中的进程因提出 I／O 请求而暂停执行；
在进程通信或同步过程中执行了某种原语操作，如 P、V 操作原语，Block 原语， Wakeup 原语等。
就绪队列中新进入了进程。（如创建了新的进程，或者某个进程被唤醒、某个进程被激活）

银行家

PV 操作

某机场的入口有 1 条通道，该通道有 3 名证件查验员，再往里是一个安检室，内有 5 名安检员。安检室可容纳五人等待（另有五人正在被检查）。入场者可让任意一名证件查验员检查，在证件查验员核对正确并放行后进入安检室等待并被检验，安检员放行后进入机场。证件查验员无人时休息，来人时被来人唤醒，查验来人证件后，确认安检室有空位后让来人入安检室。安检员无人时休息，直到被来人唤醒，检查完来人后放行来人入机场。

semaphore card_checker = 3;
semaphore secure_checkeer = 5;
semaphore empty = 10;
semaphore safe_ok_i = 1;

void arriver()
{
    signal(need_card_check)
    wait(card_checker);
    被检查证件；
    wait(card_ok);
    signal(card_checker)
  
    wait(empty)
    进入安检室
    signal(need_secure_check);
    wait(secure_checker);
    被安全检查
    wait(safe_ok)
    signal(safe_checker);
    signal(empty);
    进入机场
}

void checkTheCard ()
{
    while(1)
    {
        wait(need_card_check);
        检查
        signal(card_ok)
    }
}

void checkSecruity()
{
    while(1)
    {
          wait(need_secure_check);
          wait(empty);
          signal(safe_oki);
    }
}

一家茶馆共有三名侍者，大厅有 10 个座位供客人坐下饮茶，还有一个收银员负责收银。客人来到茶馆时若没有座位则立即离开，如果有座位则进入并坐一个座位，然后叫侍者为其上茶，客人饮完茶后即叫收银员收银，在得到收银员同意后即离开茶馆。侍者没有事时休息等待呼叫，有人呼叫时则为客人上茶，完后继续休息等待；收银员无人呼叫时也休息，有人呼叫时则收钱，确认金额正确后通知客人离开，然后继续休息。

int count = 0;
semaphore mutex=1; empty=3; full = 0;
semaphore payment=0, receipt = 0;
void drinkTea()
{
    wait(mutex);
    if(count > 10)
    {
        signal(mutex);
        exit(0);
    }
    count++;
    signal(mutex);
  
    signal(full);
    wait(empty);
    等上好茶
    singal(empty);
    喝茶
  
    wait(mutex);
    count--;
    signal(mutex);
  
    signal(payment);
    付费；
    wait(receipt);
}
void waiter()
{
    while(1)
    {
        wait(full);
        上茶
    }
}

void pay()
{
   while(1)
   {
       wait(payment);
       收款
       signal(receipt);
   } 
}

IO（磁盘调度）

先来先服务 FCFS
最短寻道时间优先 SSTF
扫描（SCAN）算法
循环扫描（CSCAN）算法

Coding

pipe

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
    char buffer[100] = {0};
    int fd[2];
    pipe(fd); // fd[0] asdasdasfread fd[1] write
    pid_t pid = fork();
    if (pid) // father process
    {
        sleep(1);
    }
    else
    {
        close(fd[0]);
        const char *msg = "Child process 1 is sending a message!\n";
        write(fd[1], msg, strlen(msg));
        close(fd[1]);
        exit(0);
    }
    pid = fork();
    if (pid) // father process
    {
        sleep(1);
        close(fd[1]);
        read(fd[0], buffer, sizeof(buffer));
        printf("%s\n", buffer);
        close(fd[1]);
    }
    else
    {
        close(fd[0]);
        const char *msg = "Child process 2 is sending a message!";
        write(fd[1], msg, strlen(msg));
        close(fd[1]);
        exit(0);
    }
    return 0;
}

thread

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>

#define N 5
#define LEFT (i)
#define RIGHT ((i + 1) % N)

sem_t mutex[N];

void *eat(void *arg)
{
    int i = *((int *)arg);
    while (1)
    {
        if (i & 1)
        {
            printf("philo %d is thinking\n", i);
            sleep(1);
            sem_wait(&mutex[RIGHT]);
            sem_wait(&mutex[LEFT]);
            printf("philo %d is eating\n", i);
            sleep(1);
            sem_post(&mutex[LEFT]);
            sem_post(&mutex[RIGHT]);
        }
        else
        {
            printf("philo %d is thinking\n", i);
            sleep(1);
            sem_wait(&mutex[LEFT]);
            sem_wait(&mutex[RIGHT]);
            printf("philo %d is eating\n", i);
            sleep(1);
            sem_post(&mutex[RIGHT]);
            sem_post(&mutex[LEFT]);
        }
    }
}

int main()
{
    pthread_t philosophers[N];
    int id[N] = {0, 1, 2, 3, 4};
    for (int i = 0; i < N; i++)
    {
        sem_init(&mutex[i], 0, 1);
        pthread_create(&philosophers[i], NULL, eat, &id[i]);
    }
    for (int i = 0; i < N; i++)
        pthread_join(philosophers[i], NULL);
    return 0;
}

Shell

clear
echo"Input a existed file name of current directory:"
read fname *#shell可以这样定义变量*
if [ -f$fname ] *#-f 文件存在*
then
    echo"Current status of [$fname] is :" *#被双引号括起来的字符中，"$"代表引用变量的值*
    ls -l $fname
else
    echo"Can't find the file [$fname], exit"
    exit
fi
change_count=0
test_count=0
oldstatus=`ls -l $fname| awk '{print $5}'` *# 反引号代表引用命令，尽量使用 $(命令) 的方式来引用命令的输出，而不要使用反引号。*
while [ $change_count-ne 2 ] *#not equal*
do
    sleep 2
    newstatus=`ls -l $fname| awk '{print $5}'` *#$5表示将当前行按照分隔符分割后的第5列,不指定分隔符时,默认使用空格作为分隔符*
    if [ "$oldstatus"="$newstatus" ] *#Use the = operator with the test [ command*
    then
        ((test_count++))
        echo"Testing file's status ..."
        if [ $test_count-eq 10 ] *#equal*
        then
            echo"Test times has reached ten, exit"
            exit
        else
            continue
        fi
    else
        echo"File [$fname] size changed!"
        oldstatus="$newstatus"
        ((change_count++))
        test_count=0
    fi
done
echo"Change times has reached two, exit."

分页分段大题

主存储器容量为 8MB，虚存容量 2GB，虚地址和物理地址各为多少位?根据寻址方式计算出来的有效地址是虚拟地址还是物理地址?如果页面大小为 4kB，页表长度是多少?（6 分)

31 23 物理地址 2^31 / 2^12 = 2^19

2.（重量级）已知系统为 32 位实地址，采用 48 位虚拟地址，页面大小 4KB，页表项大小为 8B；每段最大为 4GB。

假设系统使用纯页式存储，则要采用多少级页表，页内偏移多少位？

页内偏移根据 4KB 显然为 12 位
页表长度为 4KB / 8B = 2 ^ 9
计数 = 虚页号 / 9 = （48-页内偏移）/ 9 = 4

假设系统采用一级页表，TLB 命中率为 98%，TLB 访问时间为 10ns，内存访问时间为 100ns，并假设当 TLB 访问失败后才访问内存，问平均页面访问时间是多少？

98%×（10+100）ns + 2%×（10+100+100）ns=112ns

如果是二级页表，页面平均访问时间是多少？

98%×（10+100）ns+2%×（10+100+100+100）ns=114ns

上题中，如果要满足访问时间 <=120ns，那么命中率需要至少多少？

p×（10+100）ns+（1-p）×（10+100+100+100）ns<=120ns，解得 p >= 95%

若系统采用段页式存储，则每用户最多可以有多少段？段内采用几级页表？

故段内地址为 32 位，段号为 48-32=16 位。每个用户最多可以有 2 ^ 16 个段。段内采用页式地址，与 1)中计算同理，(32-12)/9，取上整为 3，故段内应采用 3 级页表。

3.（进制转换）物理地址 0090 0000H 开始的连续主存空间中。页表从主存 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算该代码段对应的两个页表项的物理地址，这两个页表项中的页框号，以及代码页面 2 的起始物理地址

代码段长度 8KB=2 个页
逻辑地址 0000 8000H 转换为二进制 0000 0000 0000 0000 1000 0000 0000 0000B，由于采用的是（1）中的分页存储管理方式，故后 12 位是页内偏移量，则代码段对应的两个页号为 00008H,00009H
8 号页表项物理地址=0020 0000H +8*4=0020 0020H
9 号页表项物理地址=0020 0000H +9*4=0020 0024H
页框号代表真正的物理地址，而页框大小和页面大小是 4KB,12 位，逻辑地址和物理地址都是 32 位的
那么页框号就是 20 位的，已知页框号 1 的物理地址 0090 0000H，就有页框号 1=00900H，而连续存放这个条件
就能得到页框号 2=00901H
物理地址 3 指向的是代码页面 2 的起始位置，所以页内偏移量是没有的，直接补上 3 个 0
即物理地址 3=0090 1000H

1.（进制转换）

页面大小 1KB，则页内偏移 10 位
由于用户的编程空间为 32 位，故页号的位数为 6 位
主存空间为 16KB，则页框号的位数为 14 位，
0AC5 = 0000 1010 1100 0101 页号为 2，映射到物理块号 4，故物理地址 01 00 10 1100 0101
1AC5 = 0001 1010 1100 0101 页号为 6，在用户表里面没找到 6 号页，会缺页中断
3AC5 = 0011 1010 1100 0101 页号为 14，用户程序一共才 0~9 号页，14 号页超过了界限，会产生越界中断

位示图

页号块号
0 21
1 27
2 28
3 29
4 34
5 35
分页类似固定分区，但是分页过后的页面，其实已经很小了，但是也会存在内部碎片，也就是内零头；这里的内零头为 0.8KB，因为作业 5.2KB，占据了 6 个页面，但是最后一个面只存放了 0.2KB 的作业，剩下 0.8KB 是空着的；
内存容量为 64MB，页面大小为 4KB，则内存一共可以分为 16*2^10 个页面，位示图又是表示这些页面的，故位示图需要
2^14bit 来存储这些页面状态，（这里的页面也就是页框，也可以说是物理块，盘块，总之指的是物理意义的盘块）
就需要 2^11B=2KB

文件系统

存放在某个磁盘上的文件系统，采用混合索引分配方式，其 FCB 中共有 13 个地址项，第 0 一 9 个地址项为直接地址，第 10 个地址项为一次间接地址，第 11 个地址项为二次间接地址，第 12 个地址项为三次间接地址．如果每个盘块的大小为 512 字节，则每个索引块可记录 170 个盘块地址：
该文件系统允许文件的最大长度是多少

该文件系统的最大长度是(10+170+170170+170170*170)*512B。

将文件的字节偏移量 5000、15000、150000 转换为物理块号和块内偏移量。

5000/512 得到商为 9，余数为 392，即字节偏移量 5000 对应的逻辑块号为 9，块内偏移量为 392。由于 9<10，故可直接从该文件的 FCB 的第 9 个地址项处得到物理盘块号，块内偏移量为 392。
15000/512 得到商为 29，余数为 152，即字节偏移量 15000 对应的逻辑块号为 29，块内偏移量为 152。由于 10≤29<10+170，而 29-10=19，故可从 FCB 的第 10 个地址项，即一次间址项中得到一次间址的地址;并从一次间址块的第 19 项(即该块的第 57~59 这 3 个字节）中获得对应的物理盘块号，块内偏移量为 152。
150000/512 得到商为 292，余数为 496，即字节偏移量 150000 对应的逻辑块号为 292，块内偏移量为 496。由于 10+170≤292<10+170+170*170,而 292-(10+170)=112，112/170 得到商为 0，余数为 112，故可从 FCB 的第 11 个地址项，即二次间址项中得到二次间址块的地址，并从二次间址块的第 О 项中获得一个一次间址块的地址，再从该一次间址块的第 112 项中获得对应的物理盘块号，块内偏移量为 496。
(3）由于文件的 FCB 已在内存，为了访问文件中某个位置的内容，最少需要 1 次访问磁盘（即可通过直接地址直接读文件盘块)，最多需要 4 次访问磁盘(第一次是读三次间址块，第二次是读二次间址块，第三次是读一次间址块，第四次是读文件盘块)。

长度为 80K 的文件，需要占用多少个盘块；长度为 100K 的文件，需要占用多少个盘块长度为 200K 的文件，需要占用多少个盘块

长度为 80K 的文件，需占用文件块，80K/512=160 个．则只用到一级索引，因此是 160 个文件块加上 1 个索引块，共 161 个盘块。
长度为 100K 的文件，需要占用文件块 100K/512=200 个，则需用到二级索引，在二级索引中用到了第一层索引块 1 个，第二层索引块 1 个，因此 200 个文件块，1 个一级索引块，2 个二级索引块，共 203 个盘块。
长度为 200K 的文件，需要占用文件块 100K/512=400 个，则需用到二级索引，在二级索引中用到了第一层索引块 1 个，第二层索引块 2 个，因此 200 个文件块，1 个一级索引块，3 个二级索引块，共 204 个盘块。

假设某个文件的 FCB 已在内存，但其他信息均在外存，为了访问该文件中某个位置的内容，最少需要几次访问磁盘，最多需要几次访问磁盘

访问该文件中某个位置的内容，最少需要 1 次访盘，即此位置在直接地址中可以找到。最多需要 4 次访盘，即在三级索引中找到。