计算机系统概述

基本概念

定义

操作系统（Operating System，OS）是指控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为其他用户和软件提供方便接口与环境的程序集合。计算机操作系统是随着计算机研究和应用的发展逐步发展形成并发展起来的，它是计算机系统中最基本的系统软件。

功能

1. 处理机管理
2. 存储器管理
3. 文件管理
4. 设备管理

特征

1. 并发（Concurrence）
2. 共享（Sharing）
3. 虚拟（Virtual）
4. 异步（Asynchronism）

并发和共享是操作系统最基本的两个特征，互为存在条件。没有并发和共享，就谈不上虚拟和异步。

并发是指两个或多个时间在同一时间间隔内发生，并行是在同一时刻发生。

多核CPU同一时刻可以有多个程序并行执行，但并发依然必不可少。

异步性是指，由于资源有限，多个程序以不可预知的速度向前推进。

接口

命令接口供用户使用，联机命令接口相当于雇主说一句话工人做一件事，脱机命令接口相当于雇主把要做的事写在清单上，工人逐条完成。

程序接口供程序使用，程序接口由一组系统调用命令组成，用户通过在程序中使用这些系统命令来请求系统为其提供服务（不是申请系统资源）。

发展与分类

手工操作阶段

缺点：人机速度矛盾

批处理阶段

单道批处理系统

（引入脱机输入输出技术）

优点：缓解人机速度矛盾

缺点：资源利用率很低，不提供人机交互

多道批处理系统

（操作系统开始出现）

优点：多道程序并发执行，资源利用率高

缺点：不提供人机交互功能

分时操作系统

优点：提供人机交互功能

缺点：不能优先处理紧急任务

实时操作系统

硬实时系统：必须在绝对严格的规定时间内完成处理

软实时系统：能接受偶尔违反时间规定

优点：能优先处理紧急任务，及时、可靠

网络操作系统

分布式操作系统

个人计算机操作系统

运行环境

运行机制

CPU状态分为用户态（目态）和核心态（管态）

CPU处于用户态时，只能执行非特权指令（用户自编程序）

CPU处于核心态时，可以执行特权指令（I/O指令、有关访问程序状态的指令、存取特殊寄存器的指令）

时钟的功能是即使和实现进程的切换。

原语的特点：处于操作系统的最底层，最接近硬件；具有原子性；执行时间短，调用频繁。

中断和异常

广义的中断分为内中断和外中断，外中断是狭义的中断。

内中断又称为异常、例外、陷入，信号来自CPU内部，与当前执行的指令有关。

内中断分为自愿中断（指令中断，如访管指令）和强迫中断（硬件中断（缺页）、软件中断（除0））

外中断信号来自CPU外部，与当前执行的指令无关。

内中断的响应不在指令执行结束后，而是再指令执行过程中，因为内中断要立即处理。

中断调用子程序要保存断点（PC）和程序状态寄存器（PSW）的内容，这两者由中断隐指令自动保存，而通用寄存器内容由操作系统保存。

中断处理中，最重要的两个寄存器是PC和PSWR。

中断是操作系统必须提供的功能，计算机中的各种错误都需要中断处理。CPU用户态到核心态的切换也需要中断处理。

中断的处理过程：

1. 每条指令执行结束后，CPU检查是否有外部中断信号
2. 若有外部中断信号，则需要保护被中断进程的CPU环境
3. 根据中断信号类型转入相应的中断处理程序
4. 恢复原进程的CPU环境并退出中断，返回原进程继续往下执行

系统调用

系统调用会使CPU中用户态进入核心态。

用户态到核心态是通过中断实现的，并且中断是唯一途径。（硬件中断机制 不等于 中断处理程序）

凡是与资源有关的操作（存储分配、进行I/O传输、管理文件等），都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

中断发生后，进入中断程序的只能是操作系统程序，因为应用程序不能实现核心态的功能。

有些寄存器清零不需要再核心态下运行，例如运算时自己可以操作的寄存器。

广义指令是系统调用命令，必定工作在核心态。

输入输出需要中断操作，在核心态下进行。

指定系统调用的步骤：

1. 传递系统调用参数
2. 执行陷入指令（trap）
3. 执行相应的服务程序
4. 返回用户态

体系结构

大内核

将操作系统的主要功能模块都作为系统内核，运行在核心态。

优点：高性能

缺点：内核代码庞大，结构混乱，难以维护，不稳定

微内核

只把最基本的功能保留在内核。

优点：内核功能少，结构清晰，方便维护，稳定可靠

缺点：需要频繁的在核心态与用户态之间切换，性能差

大内核与微内核的区别类似CISC和RISC的区别。

进程管理

进程与线程

程序概念

程序是静态的，是存放在磁盘里的可执行文件，是一系列的指令集合。

提高单机资源利用率的关键技术是多道程序设计及技术。

并发性（多道程序技术）的实现需要需要中断功能的支持。

进程的概念与特征

进程是程序的一次执行过程。

程序段、数据段、进程控制块（PCB）构成进程映像。

同一程序的多个进程，程序段相同，PCB、数据段不同。

PCB中的信息：进程标识符、处理机状态、进程调度信息、进程控制信息

进程状态

1. 创建态
2. 就绪态
3. 运行态
4. 结束态（终止态）
5. 阻塞态

单核CPU最多只会有一个进程处于运行态。

运行态到阻塞态是主动行为，阻塞态到就绪态是被动行为。

当有多个进程等待同一个资源时，资源被释放后，仅唤醒等待队列中的第一个进程

时间片用完会进入就绪状态，因为并不等该其他资源。

磁盘速度很慢，只要读/写磁盘，就要等待I/O操作，进程会阻塞。

进程控制

进程控制用的程序段是原语，原语执行期间不允许中断（原子性），这个性质是通过关中断实现的。关中断指令不允许普通程序使用。

进程的通信

共享存储

需要使用互斥工具（PV）

消息传递

直接通信方式

间接通信方式（电子邮件就是间接通信方式）

管道通信

管道的本质是存于内存中的文件，通常容量为内存上的一页。

从管道中读数据时一次性操作，数据一旦读出，它就从管道中被抛弃。

读进程只能有一个，写进程可以有多个。如果又多个读进程，数据可能会被其他进程读出。

管道只能采用半双工方式，及某一时刻只能单向传输。

管道满时，写会阻塞；管道空时，读会阻塞。

线程概念

切换进程需要保存/恢复进程运行环境，还需要切换内存地址空间（更新快表、更新缓存），开销很大，所以要引入线程。

线程本身不具有任何资源，线程共享进程的资源。

同一进程切换线程开销很小。

同一进程的线程通信不需要操作系统的干涉。

进程是资源分配的单位，线程是处理器调度和分派的单位。

线程可分为用户级线程、内核级线程。

用户级线程的优先是开销小、效率高，缺点是不能处理阻塞，只能在一个CPU上运行。用户级线程中，如果一个线程被阻塞，其他线程也会被阻塞。

内核级线程的优先是并发能力强，能处理阻塞，缺点是线程的切换需要在核心态完成，开销大。

多对一模型相当于用户级线程。

多对多模型中，所有内核级线程都被阻塞时，进程才会阻塞。

同一个系统的进程（或线程），可以由系统调用的方法被不同进程（或线程）使用。

线程间栈指针不能共享。

作业概念

作业是存放在外存中还没有投入运行的程序。

作业由用户提交，一用户任务为单位；进程由系统生成，是操作系统的资源分配和独立运行的基本单位。

处理机调度

调度的层次

作业调度（高级调度）：为进程活动做准备，频率低

内存调度（中级调度）：将暂时不能运行的进程挂起，处于作业调度和进程调度之间，频率略高

进程调度（低级调度）：使进程正常活动起来，频率最高

资源分配策略或算法不公平会导致饥饿。

调度方式

非剥夺调度方式（非抢占方式）：当前正在执行的进程完成或阻塞后，才把处理机分配给更重要的进程

剥夺调度方式（抢占方式）：将处理机分配给更重要的进程

调度算法

先来先服务调度算法（FCFS）

简单但效率低。

有利于CPU繁忙型作业，不利于I/O繁忙型作业。

（CPU繁忙型作业类似长作业，I/O繁忙型作业类似短作业）

短作业优先调度算法（SJF）

优先级调度算法

有剥夺式优先级调度算法和非剥夺式优先级调度算法。

优先级：

系统进程>用户进程

交互性进程>非交互型进程

I/O型进程>计算型进程（有利于让I/O设备尽早开始工作，进而提高系统的整体效率）

高响应比优先调度算法

相应比R_P=(等待时间+要求服务时间)/要求服务时间

作业的响应比可以随着等待时间的增加而提高。

时间片轮转调度算法

适用于分时系统，人机交互（保证每个作业能在一定时间内轮到）

先来先服务，仅能运行一个时间片，用完时间片后被释放，进入就绪状态。

多级反馈队列调度算法

结合了时间片轮转和优先级调度。

实现思想：

1. 多个就绪队列。
2. 高优先级队列中，每个进程运行的时间片小。
3. 未完成则进入下一队列的末尾。
4. 高优先级队列为空时，才调度低优先级队列中的进程运行。

长作业不会出现长时间得不到处理的情况。

进程同步

基本概念

临界资源是一次只允许一个进程使用的资源。

临界区是并发进程访问共享变量段的代码程序。

临界资源的访问过程可以分为四个部分：

1. 进入区
2. 临界区
3. 退出区
4. 剩余区

同步机制要遵循的原则：

1. 空闲让进
2. 忙则等待
3. 有限等待
4. 让权等待

实现临界资源互斥的方法

软件实现方法

1. 单标志法：只能轮流访问临界区，违反“空闲让进”
2. 双标志法先检查：可能同时进入临界区，违反“忙则等待”
3. 双标志法后检查：可能相互谦让，违反“空闲让进”和“有限等待”
4. Peterson’s Algorithm：后“谦让”的进程失去优先权，但不能进入临界区的进程仍会占用CPU，违反“让权等待”（问题不大）

硬件实现方法

1. 中断屏蔽技术：简单高效，只适用于内核进程，不适用于用户进程，不适用于多处理机
2. 硬件指令方法：有TestAndSet(Lock)（TLS）指令、Swap指令，简单，可适用于多处理机，但违反“让权等待”

实现进程同步的方法

信号量

信号量用来解决互斥与同步问题，它只能被两个原语wait(S)和single(S)访问，也可以记为P操作和V操作。（P是荷兰语中的proberen 尝试，V是荷兰语中的verhogen 提高）

1. 整形信号量，不满足“让权等待”
2. 记录型信号量，可以在wait(S)方法中主动阻塞，在signal(S)方法中唤醒阻塞的进程
3. 利用信号量实现同步，如果期望的消息不存在，信号量初始值为0，如果期望的消息存在，初始值不为0
4. 利用信号量实现互斥，信号量初始值为1，对不同资源要设置不同信号量

管程

管程解决了信号量机制编程麻烦、易出错的问题，类似面向对象编程思想中的封装。

管程可以实现进程的同步和异步。

基本特征：

1. 局部于管程的数据只能被局部于管程内的过程访问（类似用Javabean中用private修饰的成员变量）
2. 一个进程只有通过调用管程内的过程才能进入管程访问的共享数据（类似Javabean中用public修饰的方法）
3. 每次只允许一个进程在管程内执行某个内部过程（Java中可以用关键字synchronized修饰方法，同一时间段内只能被一个线程调用）

组成部分：

1. 局部管程的共享结构数据说明
2. 对该数据结构进行操作的一组过程
3. 对局部于管程的共享数据设置初始值的语句

管程中的signal操作的作用与信号量机制中的V操作不同，新海的基质中的V操作一定会改变信号量的值S=S+1，而管程中的signal操作是针对某个条件变量的，若不存在因该条件而阻塞的进程，则signal不会产生任何影响，若错在因该条件而阻塞的进程，则signal会唤醒阻塞队列队首进程。

若进程A执行x.wait()操作，则该进程会阻塞，并挂到条件变量x对应的阻塞队列上。

这两段还不太懂，是结合94页29题和47题得到的。

经典同步问题

#### 单生产者-单消费者问题

当缓冲区空时，消费者阻塞，生产者生产一个产品后，唤醒消费者

当缓冲区满时，生产者阻塞，消费者消费一个产品后，唤醒生产者

缓冲区是临界资源，各进程要互斥访问

实现互斥操作一行要在实现同步的P操作之后，否则会发生死锁。（要确定缓冲区能操作后再加锁，而且临界区要尽可能短）

多生产者-多消费者问题

生产者1生成产品1，生产者2生产产品2，消费者1消费产品1，消费者2消费产品2，缓冲区容量为1

缓冲区没有产品1时，消费者1阻塞

缓冲区没有产品2时，消费者2阻塞

缓冲区满时，生产者阻塞，产品被消费后，唤醒生产者

#### 读者-写者问题

一些写，多个读，读写互斥，但可以多个进程同时读，只有一个读者加锁，最后一个读者解锁，读者加锁和解锁的代码块要互斥。

死锁

概念

死锁：相互等待对方手里的资源，各进程都阻塞，无法推进。如果发生死锁，至少有两个进程死锁。

饥饿：长期得不到满足的资源（如处理机）而无法推进。发生饥饿的进程可能只有一个，饥饿的进程状态时阻塞或就绪。

死循环：进程一致跳不出循环，可能是错误，也可能是程序员故意设计的。

必要条件

以下四个必要条件缺一不可：

1. 互斥条件（哲学家的筷子、打印机是互斥的，内存、扬声器不是互斥的）
2. 不剥夺条件：资源只能主动释放
3. 请求和保持条件：进程至少保持了一个资源，同时又请求新的资源。
4. 循环等待条件：存在一种进程资源的循环等待链。

死锁的处理策略

预防：破坏死锁产生的条件，从根本上防止死锁的发生

避免：存在死锁产生的条件，通过调度避免死锁的发生

预防死锁

破坏死锁产生的四个必要条件之一：

1. 破坏互斥条件，这种方式可以认为是无法实现的。
2. 破坏不剥夺条件：剥夺资源。增加系统开销，降低吞吐量。
3. 破坏请求并保持条件：一次性分配进程所需的全部资源，或主动释放资源。严重浪费系统资源，还可能导致饥饿（一直从某个进程取出资源，该进程一直得不到满足）
4. 破坏循环等待条件：采用顺序资源分配法。浪费系统资源，并造成编程不便。

避免死锁

银行家算法：进行资源分配前，先计算此次资源分配的安全性，如果导致系统进入不安全状态，就不分配资源。

不安全状态是发生死锁的必要不充分条件。

预防死锁，使死锁在任何条件下都不可能发生。

避免死锁，在可能发生死锁的情况下避免死锁发生。

死锁的检测

资源分配图中，圆形表示进程，矩形内表示资源，矩形内的小圆表示该资源的数量。

简化资源分配图时，从及不阻塞又不孤点的进程开始。

发生死锁的充要条件是资源分配图不能完全简化。

简化后还连着边的进程是死进程。

死锁的解除

1. 资源剥夺法：挂起死锁进程，并抢占资源。
2. 撤销进程法：撤销部分死锁进程并剥夺全部资源。
3. 进程回退法：要保持进程的历史信息，设置还原点。

内存管理

内存管理的概念

基本原理和要求

在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是链接。

对主存储器的访问以字或字节为单位，例如在页式管理中，不仅要知道块号，还要知道页内偏移量。

逻辑地址的分配是按页为单位分配的，主存的分配即物理地址的分配是以内存（物理）块为单位分配的。

C语言中，二进制代码和常量存放在正文段，动态分配的存储区存放在数据堆段，临时使用的变量存放在数据栈段。

装入方式

1. 绝对装入：编译时产生绝对地址
2. 静态重定位（可重定位装入）：在装入时完成地址变换，将相对地址变为绝对地址。必须分配进程要求的全部内存空间，作业不能在内存中移动，也不能再申请内存空间。只适用于连续分配的固定分区方式。
3. 动态重定位（动态运行时装入）：装入内存后的所有地址均为相对地址。需要设置一个重定位寄存器。可以动态申请内存，适用于。

整个系统重定位寄存器只需要一个，因为系统处理器在同一时刻只能执行一条指令或访问数据，只需在切换程序执行时重置寄存器内容即可。而且寄存器是很昂贵的硬件。

内存保护

1. 使用一对上、下限寄存器。
2. 使用重定位寄存器（或基地址寄存器）和界地址寄存器（又称限长寄存器）。重定位寄存器存放最小的物理地址，界地址寄存器存放最大的逻辑地址。

覆盖与交换（用于扩充内存/节省主存空间）

覆盖

将经常活跃的部分放在固定区，其余部分按调用关系分段。

固定区不会被覆盖。

对用户不透明，增加了用户编程的负担，仅用于早期OS。

可用于单一连续分配和固定分区分配。

交换

通过内存调度（中级调度）实现，将阻塞、在内存中驻留时间较长的进程换到磁盘的对换区。

磁盘分为文件区和对换区，对换区是连续的，速度较快。

PCB常驻内存，不会被换出。

正在进行I/O操作的进程不能换出主存，否则进程的I/O数据区将被新换入的进程占用。

虚拟内存

见下一节。

连续分配管理方式

使用分区的方式，操作系统实现起来代价小，不需要额外硬件和特定数据结构的支持。

单一连续分配

只有一道程序，占整个内存空间。

无外部碎片，有内部碎片。

内部碎片：分配给某进程的内存区域中，存在没有备用上的部分。

外部碎片：内存中的某些空闲分区由于太小而难以利用。

固定分区分配

将内存空间划分为固定大小的区域，每个进程只装入一道作业，一道作业只属于一个分区。

分区大小可以相等，也可以不等。

有内部碎片，无外部碎片。

很少用于现代操作系统。

可采用静态重定位。

动态分区分配

不预先划分内存，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。

需要使用空闲分区表或空闲分区链来记录内存的使用情况。

要用紧凑技术解决外部碎片（把进程移到一起，得到一个更大的连续空闲空间）。

无内部碎片，有外部碎片。

动态分区分配策略算法有：首次适应、最佳适应、最坏适应、邻近适应。

非连续分配管理方式

基本分页存储管理方式

基本概念

把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。

进程中的块称为页（Page）或页面，内存中的块称为页框，又称页帧、内存块、物理块。

地址结构为：页号P-页内偏移量W。

每个进程拥有一张页表，页表记录每个进程所对应的物理块，一般放在内存中。

存取一个数据或指令需要访存两次，第一次时访问页表，确定所取数据或指令的物理地址，第二次是根据该物理地址存取数据或指令。

没有外部碎片，内部碎片很小。

页的大小的设计，要考虑进程的平均大小、页表占用长度等，一旦确定，所有的页面就是等长的，与内存外存大小、CPU地址结构无关。

缺点：不方便按照逻辑地址模块实现信息的保护和共享。

这里涉及很多计算，比较简单，但难以描述。

具有快表的地址变换机构

快表是一种访问速度比内存快很多的高速缓冲存储器（Cache），用来存放当前访问的若干页表项。

若未命中，则要在读出页表项后将其存入快表。

快表根据时间和空间的局部性来设计，在计算机组成原理中已经学过。

两级页表

两级页表是为了解决单级页表过长，不能存储在一个块（页框）中，需要存储在连续内存空间的问题。

添加的一级页表称为页目录表。

如果两级不够，还可以采用多级，各级页表的大小不能超过一个块（页帧）的大小。

俄罗斯套娃

导致的问题是访存次数增加。

基本分段存储管理方式

按照用户进程中的自然段划分逻辑空间。

优点：很方便按照逻辑模块实现信息的保护和共享。

缺点：如果段过长，为其分配很大的连续地址空间会很不方便。另外，会产生外部碎片（与动态分为类似，不过小一些）。

地址结构为为：段号-段内地址。

每个段的长度是不一致的，需要检查是否越界。

不能被修改的代码称为可重入代码或纯代码，不属于临界资源，这样的代码和不能修改的数据可以共享。

无内部碎片，有外部碎片。

也可以用快表。

可重入程序就是通过共享来使用同一块存储空间的，或通过动态链接的方式将所需的程序映射到相关程序中去，其最大的优点是减少了对程序段的调入/调出，因此减少了对换数量。

共享程序段可能同时被多个程序使用，所以必须可重入编码，否则无法实现共享功能。

书上是这样写的，不知道啥意思。

段页式管理方式

引入是为了满足：方便编程、分段共享、分段保护、动态增长、动态链接。（没有方便操作）

能有效提高内存利用率。

地址结构为：段号S-页号P-页内偏移量W

有内部碎片。

每个进程一张段表，每个段一张页表。

也可以用快表。

虚拟存储技术

基本概念

非虚拟存储器中，作业必须全部装入内存，且在运行过程中也一直驻留内存

虚拟存储器中，作业不必装入内存，在运行过程中也不用一直驻留内存

虚拟存储技术用于扩充内存。

虚拟内存最大容量由计算机地址结构决定。

虚拟内存实际容量=min{内外存容量之和, CPU寻址范围}

请求分页管理方式

页表项地址结构：页号-物理块号-状态位P-访问字段A-修改位M-外存地址

状态位又称合法位。

访问字段A记录本页在一段时间内被访问的次数。

修改位M标识该页调入内存后是否被修改过。

访问内存时，先查快表，如果在快表中，就修改访问位和修改位，并直接形成物理地址；

如果不在快表中，但在内存中，就修改快表，修改访问位和修改位，再形成物理地址；

如果不在快表中，也不在内存中，就会发生缺页中断，进程阻塞（因为I/O操作比较慢），从外存找到所缺的页，换入主存，等待下一轮运行时从内存中读出。在换入主存时，如果主存满，就要从主存选择一页换出，如果换出的页被修改过，就要将该页写回外存（类似计算机组成原理Cache写策略中的写回法）。

页面置换算法

导致LRU算法实现起来耗费高的主要原因是需要对所有的页进行排序。

淘汰页面后，新的页面会使用被淘汰的页面的页框。

页面分配策略

驻留集大小（和策略）

驻留集：给一个进程分配的物理页框的几何就是这个进程的驻留集。

采用虚存，驻留集的大小一般小于进程的总大小。

驻留集过大，导致多道程序并发量下降，资源利用率降低。

驻留集过小，导致缺页率高。

固定分配：驻留集大小不可变

可变分配：驻留集大小可变

局部置换：只能选择进程自己的空闲物理块进行置换

全局置换：系可以选择操作系统保持的空闲物理块，或任何进程保持的物理块进行置换

不存在固定分配全局置换，因为两者的进程数是否可变存在矛盾。

固定分配局部置换：不灵活，难以确定为每个进程分配的物理块数。

可变分配全局置换：主要缺页就分配新的物理块，导致系统的并发能力下降，被选中的进程缺页率增加。

可变分配局部置换：要根据缺页频率动态增减该进程的物理块。

调入时机

预调页策略：一次调入若干相邻的页，可能效率高但可能大多数未被访问，主要用于进程的首次调入。

请求调页测率：每次调入一页，调入的页一定会被访问，需要较多的I/O开销，主要用于运行期间。

调入位置

系统拥有足够的对换区空间时，可以全部从对换区调入所需页面，以提高调页速度。

系统缺少足够的对换区空间时，不会修改的文件从文件区调入，不会被调出，可能被修改的换出到对换区。

UNIX方式：首次调入从文件区，再次调出调入从对换区。

抖动（颠簸）

频繁的页面调度行为称为抖动或颠簸，产生的主要原因是，某个进程频繁访问的页面数量高于可用的物理页帧数目（分配给该进程的物理块不够）。

页面置换算法不合理也是导致抖动的原因。

抖动的产生与磁盘交换区容量和速度无关，因此更换更好的硬盘无法解决抖动。

更换更快的CPU也不能解决抖动。

增大内存可以减少缺页率，从而解决抖动。

减少多道程序度数，可以减少主存中的进程，从而减少换入还出，从而解决抖动。

工作集

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

操作系统可以根据检测工作及的大小来决定驻留集的大小。

驻留集大小不能小于工作集大小。

地址翻译

这是与计算机组成原理结合的知识点，408考纲没有直接写出此考点。

磁盘管理

文件系统基础

外存被分为块。

文件的逻辑结构

逻辑文件的组织形式取决于用户，物理结构的选择取决于文件系统设计者针对硬件结构所采取的策略。

无结构文件（流式文件）

例如txt文件。

有结构文件（记录式文件）

例如数据库文件。

根据各条记录的长度是否相等，又可分为定长记录和可变长记录。

根据文件的记录形式，可以分为 顺序文件、索引文件、索引顺序文件、直接文件或散列文件。

目录结构

文件控制块FCB

FCB（File Control Block）包含的信息：

基本信息：文件名、物理位置、逻辑结构、物理结构。

存取控制信息：存取权限

使用信息：建立时间、修改时间

FCB的有序几何称为文件目录。

索引节点

每个文件对应一个索引结点，索引结点只有文件名和结点指针。在检索目录时，只用到了文件名，文件的其他描述信息不会用到，也不需要调入内存。

目录结构

1. 单级目录结构：整个系统只有一张目录表，不允许文件重名
2. 两级目录结构：不同用户的文件文件可以重名，但不能对文件进行分类
3. 多级目录结构：不便于实现文件共享，Windows、Linux都是用的这种方式
4. 无环图目录结构：可以实现文件共享

文件共享

基于索引结点的共享方式（硬链接）

在索引结点中用到一个链接计数器count，用于表示链接到本索引结点（及文件）上用户目录项的数目。

只有当count=0时，表示没有用户使用该文件，系统才负责删除该文件。

利用符号链实现文件共享（软连接）

类似Windows系统中的快捷方式。

Link型文件记录了共享文件的存放路径。

即使软连接指向的共享文件已被删除，Link型文件依然存在。

速度较慢，需要I/O。

文件的打开和读取

文件被用户进程首次打开，即被执行open函数，会把该文件的FCB存入内存的活跃文件目录表，而不是直接把文件内容复制到主存，只有进程希望获取文件内容时才会读取文件内容。

open函数的参数包含文件的路径与文件名，返回文件描述符fd。

read函数的参数包含：①文件描述符fd②缓冲区首址buf③传送字节数n。

read函数的功能是试图从fd所指示的文件中读入n个字节的数据，并将它们送至指针buf所指示的缓冲区中。

Java中的open()方法和read()方法也是类似的。

文件系统的实现

文件系统层次结构

目录实现

文件实现

文件分配方式

文件分配表（FAT）每个磁盘对应一个。

索引表每个文件对应一个。

索引分配可能出现索引表大小超过一个磁盘块的问题，所以要采用链接方案、多层索引、混合索引来解决这个问题。

链接方案可能需要多次I/O操作，性能差；

多层索引类似多级页表，读磁盘操作较少，但对小文件，I/O次数与大文件一样多；

混合索引是前两种解决方案的结合。

文件存储空间管理

1. 空闲表法（与内存管理-动态分区分配类似）
2. 空闲链表法（又分为空闲盘块链和空闲盘区链）
3. 位示图法（注意从0开始还是从1开始）
4. 成组链接法（UNIX中使用，难但很少考）

磁盘的组织与管理

磁盘的结构

磁盘地址用 柱面号-盘面号-扇区号（或块号） 表示。

顺序不能更换，如果盘面号在前，会出现读取连续地址时磁头移动次数过多的问题。

每个扇区存放的数据量相同，内侧的数据密度大。

磁盘读写时间

磁盘的一次读写时间=寻找(寻道)时间+延迟时间+传输时间

延迟时间等于磁盘转半圈所需的时间。

磁盘调度算法影响寻找时间。

寻道（寻找）时间

如果没有额外说明，题目中的SCAN算法就是该表格中的LOOK算法，题目中的C-SCAN算法就是该表格中的C-LOOK算法。

延迟时间

对盘面进行交替编号，对盘片组中不同的盘面错位命名。

传输时间

扇区的数据处理时间影响传输时间。

磁盘的格式化

低级的格式化：对磁盘进行分区，确定磁区扇区校验码所占位数。

逻辑格式化：建立文件系统的根目录，将保存空闲磁盘块信息的数据结构初始化。

操作系统引导

整个磁盘只有一个主引导记录

每个分区有各自的引导块，没安装操作系统的分区引导块为空

1. 开机时，CPU会自动执行ROM（ROM集成在主板上）中存储的自举程序
2. 自举程序引导磁盘中的主引导记录读入RAM
3. 主引导记录中的 磁盘引导程序 引导主机读入安装了操作系统的分区 的分区引导块
4. CPU执行分区引导块中的 引导程序，把分区的根目录信息读入主存

简单来说就是：ROM->磁盘主引导记录->分区引导块->引导程序

如果安装了双系统，在开机时可以选择使用哪个分区中的操作系统

虚拟文件系统（VFS）

虚拟文件系统的特点：

1. 操作系统向上层提供统一标准的调用接口，帮用户屏蔽了底层文件系统的差异
2. 如果文件系统想要在操作系统上支持，就必须满足该操作系统的VFS要求，提供操作系统规定的接口
3. 每打开一个文件，VFS就会在主存中新建一个vnode，用统一的数据结构表示文件，无论底层使用哪个文件系统

IO管理

I/O管理概述

I/O控制方式

通道就是弱化版的CPU，指令单一，没有自己的内存。

通道程序是放在主存当中的。

通道、设备控制器、设备三者关系层层递进，不能并行工作，控制次序也不能颠倒。

通道控制设备控制器，设备控制器控制设备。

通道控制器与设备控制器之间是一对多的关系，设备控制器与设备之间也是一对多的关系。

中断向量地址是例行程序的入口地址的地址。

DMA控制器的组成：

1. 主机-控制器接口
2. I/O控制逻辑
3. 块设备-控制器接口

DMA方式的详细工作过程：（初始化->传输->请求中断->结束）

在进行DMA传输时，主机首先向内存写入DMA命令块，向DMA控制器写入这个命令块的地址，启动I/O设备，完成上述操作后，CPU继续其他工作，DMA在DMA控制器的控制下，根据DMA控制信息设置要求进行I/O设备与内存之间的数据传输。当数据传输结束后，DMA控制器向CPU发送中断请求。CPU响应中断请求，结束DMA操作，释放总线。

I/O子系统的层次结构

1. 用户层I/O软件
2. 设备独立性软件（设备无关软件）
3. 设备驱动程序
4. 中断处理程序
5. 硬件

其中，库函数在1层。

34与硬件交互。

234属于设备管理软件，是操作系统内核部分，即I/O系统，又称I/O核心子系统。

I/O设备控制器

I/O设备控制器的组成：

1. CPU与控制器的接口
2. I/O逻辑（用于实现设备控制功能）
3. 控制器与设备的接口

I/O核心子系统

高速缓存与缓冲

缓冲区一般用内存实现。（用硬件也可以实现，但是成本高，如TLB）

缓冲区的作用是缓和CPU与I/O设备之间速度不匹配的矛盾。

缓冲区有一个特点：当缓冲区非空时，不能冲入数据；当缓冲区充满后，才能传输数据。

单缓冲：处理每块数据的用时为max{C, T} + M

双缓冲：处理每块数据的用时为max{C + M, T}

循环缓冲：多个大小相等的缓冲区链接成一个循环队列

缓冲池：有三个缓冲队列：空缓冲队列、装满输入数据的缓冲队列、转满输出数据的缓冲队列

在缓冲机制中，无论是单缓冲、多缓冲还是缓冲池，由于缓冲区是一种临界资源，所以在使用缓冲区时都有一个申请和释放（即互斥）的问题需要考虑

设备的分配

设备分配的方式：

1. 独占设备：只允许各个进程串行使用的设备，例如打印机。
2. 共享设备：允许多个进程“同时”使用的设备（在微观上是交替使用的），例如磁盘、扬声器。
3. 虚拟设备：把一个物理设备变换成多个对应的逻辑设备。

设备的分配策略：

静态分配：用于独占设备

动态分配：用于共享设备

设备分配的安全性：

安全分配：进程发出I/O请求后遍进入阻塞态，直到I/O完成后才被唤醒，不会发生死锁，因为破坏了“请求并保持”。

不安全分配：进程在发出I/O请求后继续运行，需要时还可以发出第二个、第三个I/O请求，仅当所请求的设备亦被另一进程占用时才阻塞，可能产生死锁，但可以用银行家算法避免。

设备的分配要考虑固有属性、设备独立性、设备安全性，一般不需要考虑及时性。

设备的独立性：用户在编程时使用的设备与实际设备无关。

SPOOLing技术（假脱机技术）

脱机输入/输出技术需要专门的外围控制机，SPOOLing技术（假脱机技术）不需要专门地外围机。

SPOOLing技术在外存（不一定是磁盘）上开辟输入井和输出井两个存储区域，模拟脱机输入/输出技术。

SPOOLing技术用空间换取时间。

SPOOLing技术将独占设备改造为共享设备，实现了虚拟设备的功能。

SPOOLing技术的主要目的是提高独占设备的利用率。

使用SPOOLing技术，进程不必等I/O操作完成就可以执行输出操作。