操作系统

计算机操作系统

1 操作系统

1.1 定义

操作系统是一个大型的程序系统，它负责计算机的全部软硬件资源的分配、调度工作，控制并协调并发活动，实现信息的存取和保护。它提供用户接口，使用户获得良好的工作环境。操作系统使整个计算机系统实现了高效率和高度自动化。

1.2 目标*

1）有效性：A.提高系统资源利用率（利用CPU和I/O设备的空闲时间） B.提高系统吞吐量（通过调整工作流程，缩短程序运行周期）

2）方便性：方便用户使用，不必使用机器语言编写程序，可以使用高级语言。

3）可拓充性：便于增加新的功能和模块，修改老的功能和模块（微内核，客户/服务器模式）。

4）开放性：遵循世界标准规范。

1.3 作用/主要功能*

1）作为用户与计算机硬件系统之间的接口：A.命令方式；B.系统调用方式；C.图形窗口方式

2）作为计算机系统资源的管理者：A.处理机管理（进程管理、处理机调度）；B.存储器管理；C.I/O设备管理；D.文件管理

3）实现了对计算机资源的抽象：用户通过OS抽象接口，直接高效使用计算机，不用关心实际物理接口和O/I设备。

1.4 基本特性

1）并发性：多道，并行与并发。

2）共享性：互斥共享；同时访问。

3）虚拟性：时分复用；空分复用。

4）异步性：进程是以人们不可预知的速度向前推进，多个进程并发执行，但获得所需的资源后才能执行。

1.5 发展过程

无操作系统的计算机系统 =>单道批处理系统（1950s）=> 多道批处理系统（1960s）（开始成为真正的操作系统）=>

分时系统（也叫交互系统）=> 实时系统；

从理论角度，可以将现在的操作系统划分为3类：多道批处理系统、分时系统和实时系统

但实际的操作系统，往往是混合的，不存在纯粹的一类系统。

1.6 推动OS发展的主要动力

1）推动操作系统发展的主要动力

2）方便用户

3）器件的不断更新换代

4）计算机体系结构的不断发展

5）新的应用需求

2 进程管理

2.1 概念

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

为什么需要线程？

1）多道程序环境下，程序的执行属于并发执行

2）操作系统管理上的方便性。更好的管理内存中运行的各个程序

PCB有什么作用？

为使程序(含数据)能独立运行，应为之配置进程控制块，即PCB；

为了能有效管理多道环境下的应用程序，需要相关的管理信息（PCB）。

进程 == 程序+PCB；进程实体 == 程序+PCB+相关的数据段。

2.2 特征

1）结构特征：程序 + PCB == 进程；程序 + PCB + 数据段 == 进程实体。

2）动态性：相比程序，进程实体有一定的生命期。

3）并发性：多个进程实体同存于内存中，且能在一段时间内同时运行。

4）独立性：能独立运行、独立分配资源和独立接受调度的基本单位。

5）异步性：进程按各自独立的、 不可预知的速度向前推进。

2.3 状态

进程包括如下三种基本状态：

在不少系统中进程只有上述三种状态，但在另一些系统中，又增加了一些新状态，最重要的是挂起状态。

阻塞和挂起的区别？

阻塞是进程本身引起的，而挂起的原因都是外部的，不是程序本身的原因。

将挂起称为静止，将未被挂起称为活动，可以得到如下5种状态：

2.4 信号量机制

什么是信号量机制？

信号量是一个用于表示资源数目的整型量S。

为使多个进程能互斥地访问某临界资源，对这个信号量的操作，必须通过原子操作来进行。

使用信号量可以实现前趋图中的PV关系。

由上述前趋图看，得到的伪代码如下：

此处P表示请求信号量，V表示释放信号量；a-g信号量的初始值为0。

AND信号量被用于解决多个信号量的死锁问题：

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。

Swait(S1，S2，…，Sn)
　　if Si>=1 and … and Sn>=1 then
　　　for i:=1 to n do
　　　  Si:=Si-1；
　　　endfor
　　else
　　 place the process in the waiting queue associated with the first Si found with Si<1，and set the program count of this process to the beginning of Swait operation 
　　endif

Ssignal(S1，S2，…，Sn)
  for i:=1 to n do
    Si:=Si+1；
    Remove all the process waiting in the queue associated with Si into the ready queue.
  endfor； 

2.5 生产者-消费者

2.6 哲学家进餐

放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。

信号量伪代码：

虽然上述解法可保证不会有两个相邻的哲学家同时进餐，但有可能引起死锁。

假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0； 当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。

对于这样的死锁问题，可采取以下几种解决方法：

　　(1) 至多只允许有四位哲学家同时去拿左边的筷子。

　　(2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。即AND信号量。

　　(3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，最后总会有一位哲学家能获得两只筷子而进餐。

AND信号量（正解）：

2.7 读者-写者

多个读者进程可以共存，一个写进程和其他读/写进程不能共存。

2-8 理发师

一个理发师和一把理发椅子，另有N把椅子供顾客休息等待。

没有顾客时，理发师休息，等待顾客；

每个顾客来时，先看是否有椅子空位，有空位，则坐下等待，否则不等待直接走。

2-9 进程通信

1）共享存储器系统

​ 在这种通信方式中，要求诸进程公用某些数据结构（例如，有界缓冲区），借以实现诸进程间的信息交换。

​ 公用数据结构的设置及对进程间同步的处理，都是程序员的职责。这无疑增加了程序员的负担，而操作系统却只须提供共享存储器。程序员的工作比较复杂。

2）消息传递系统

​ 消息传递系统是当前应用最为广泛的一种进程间的通信机制。程序员直接利用操作系统提供的一组通信命令，不仅能实现大量数据的传递，而且还隐藏了通信的实现细节，使通信过程对用户是透明的，从而大大减化了通信程序编制的复杂性。

​ A.直接通信方法：发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)：

Send(Receiver，message)；//发送一个消息给接收进程
Receive(Sender，message)；//接收Sender发来的消息；Sender也可以不指定。 

​ B.间接通信方法：间接通信方式指进程之间的通信需要通过作为共享数据结构的实体。该实体用来暂存发送进程发送给目标进程的消息；接收进程则从该实体中取出对方发送给自己的消息。通常把这种中间实体称为信箱。

3）管道通信

​ 所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)，以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。

2.10 线程

在多线程OS中，通常是在一个进程中包括多个线程，每个线程都是作为利用CPU的基本单位，是花费最小开销的实体。

使OS具有更好的并发性，在进程内并发有如下优点：

​ 1）并发更加细化；2）方便平行计算（并发）软件的开发。

进程和线程的区别？

A.进程是作为拥有系统资源的基本单位，包含多个线程并为它们提供资源

B.一个进程都含有一个或多个相对独立的线程。

C.进程不再是一个可执行的实体。在多线程OS中，是把线程作为独立运行的基本单位。

3 处理机调度与死锁

3.1 分类

操作系统处理机调度分为（高级、低级、中级）三种

1）高级调度（作业调度，接纳调度）：

​ 作业是一个比程序更为广泛的概念，不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。

2）低级调度（进程调度，短程调度）：

​ 进程调度用于决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程的具体操作。这是操作系统真正实现多道并发的关键。

​ 进程调度可采用“抢占/非抢占”两种调度方式。非抢占调度指的是：一旦把处理机分配给某进程后，都一直让它运行下去，直至该进程完成；抢占调度允许调度程序根据某种原则去暂停某个正在执行的进程，将处理机重新分配给另一进程。

3）中级调度（中程调度）：

​ 中级调度将暂时不能运行的进程不再占用宝贵的内存资源，调至外存上去等待；当这些进程重又具备运行条件且内存又稍有空闲时，再重新调入内存等待运行。引入中级调度的主要目的是为了提高内存利用率。 >早期计算机中普遍采用，目前广泛采用虚拟内存技术，中级调度已不再使用。

3.2 调度队列模型

1）仅有进程调度的调度队列模型

2）具有高级和低级调度的调度队列模型

区别：A.就绪队列的形式和进程来源， 采用高优先权优先调度算法。B.设置多个阻塞队列。

3）同时具有三级调度的调度队列模型

区别：引入中级调度，把就绪状态分为内存就绪和外存就绪。类似地，也可把阻塞状态进一步分成内存阻塞和外存阻塞。

3.3 调度准则

1）面向用户的准则：

​ A.周转时间短（常用于批处理系统）；B.响应时间快（常用于分时系统）；

​ C.截止时间的保证（常见于实时系统）。D.优先权准则（含义：让某些紧急的作业能得到及时处理）

2）面向系统的准则：

​ A.系统吞吐量高（用于批处理系统）；B.各类资源的平衡利用（保持系统中各类资源都处于忙碌状态）；

​ C.处理机利用率好

3.4 调度算法

3.5 死锁产生原因和条件

1）原因：

​ A.竞争资源：系统中供多个进程共享的资源的数目不足以满足诸进程的需要。

​ B.进程间推进顺序不当：进程在运行过程中，请求和释放资源的顺序不合理。

2）条件： A.互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用（临界资源）。

​ B.请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

​ C.不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

​ D.环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链。

3.6 预防死锁

预防死锁指的是：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的至少一个，来预防发生死锁。

预防死锁是一种较易实现的方法，以降低系统资源利用率和系统吞吐量为代价，已被广泛使用。

1）摒弃“请求和保持”条件

​ 系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。

​ 缺点：进程是一次性地获得其整个运行过程所需的全部资源的，且独占资源，其中可能有些资源很少使用，甚至在整个运行期间都未使用，这就严重地恶化了系统资源的利用率。此外，进程也延迟运行。仅当进程在获得了其所需的全部资源后，才能开始运行。

2）摒弃“不剥夺”条件

​ 缺点：一个资源在使用一段时间后，它的被迫释放可能会造成前段工作的失效。即使是采取了某些防范措施，也还会使进程前后两次运行的信息不连续。

3）摒弃“环路等待”条件

​ 所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路。这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量都有较明显的改善。

​ 缺点：系统中各类资源的序号必须相对稳定，这就限制了新类型设备的增加，也必然会限制用户简单、自主地编程。

3.7 银行家算法

https://www.bilibili.com/video/BV18M4m1f76s?vd_source=5f2b68719bbd3751e445c4e25eb9e7ae

3.8 死锁的检测与解除

资源分配图：e={pi，rj}是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e={rj，pi}是资源分配边，由资源rj指向进程pi，它表示把一个单位的资源rj分配给进程pi。

S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。

4 存储器管理

4.1 层次结构

1）寄存器：

​ 寄存器是真正完成运算的地方，访问速度最快，完全能与CPU协调工作，但价格却十分昂贵。

2）主存储器：

​ CPU的控制部件只能从主存储器中取得指令和数据。

​ 数据能够从主存储器读取并将它们装入到寄存器中，或者从寄存器存入到主存储器。

由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。

4.2 程序执行的步骤

在多道程序环境下，将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤：

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

​ 链接：由链接程序，将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成完整程序。

​ 装入：由装入程序，将装入模块装入内存。

4.3 程序链接

根据链接时间的不同，可以将程序链接分为3种：静态链接、

1）静态链接

在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块（可执行文件），以后不再拆开。

这种事先进行链接的方式称为静态链接方式。

2）装入时动态链接

将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。

优点：A.便于修改和更新；B.便于实现对目标模块的共享。

3）运行时动态链接

对某些目标模块的链接，是在程序执行中，需要该目标模块时，才进行链接。

运行时动态链接的原因？

在一些情况下，事先无法知道本次要运行哪些模块，故只能是将所有可能要运行到的模块都全部装入内存。但这种做法十分低效。所以，当发现一个被调用模块尚未装入内存时，应该立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。这种做法就是运行时动态链接。

4.4 程序装入

1）绝对装入方式

在编译时，如果知道程序将驻留在内存的什么位置，那么，编译程序将产生绝对地址的目标代码。最后，按照装入模块中的地址，将程序和数据装入内存。

早期DOS系统、单道批处理系统即采用这种方式

2）可重定向装入方式

在多道程序环境下，编译程序不可能预知所编译的目标模块应放在内存的何处，因此绝对装入方式只适用于单道程序环境。

可重定向装入方式下，由OS决定应用程序在内存中的位置。

3）动态运行时装入方式

可重定位装入方式方式并不允许程序运行时在内存中移动位置。

在运行过程中程序在内存中的位置可能经常要改变，此时就应采用动态运行时装入的方式。

4.5 内存分配

1）单一连续分配

这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。

把内存分为系统区和用户区两部分，系统区仅提供给OS使用，用户区仅提供给用户使用。

2）固定分区分配

将内存的用户空间划分为若干个固定大小（或不同大小）的分区。

有一用户程序要装入时，由内存分配程序从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序。

3）动态分区分配

动态分区分配是根据进程的实际需要，动态地为之分配内存空间。

A.首次适应算法（FF）(first fit)

​ 在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止； ​ 然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中； ​ 若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。

B.循环首次适应算法(next fit)

​ 该算法是由首次适应算法演变而成的。

​ 每次不再从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到能满足要求的空闲分区。

​ 使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区

C.最佳适应算法(best fit)

​ 每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业。

​ 会留下许多难以利用的小空闲区。

D.最坏适应算法(worst fit)

​ 每次为作业分配内存时，总是把能满足要求、又是最大的空闲分区分配给作业。

​ 查找效率高，但是会缺乏较大的空闲区。

E.快速适应算法(quick fit)

​ 该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。

​ 查找效率高， 但算法复杂，系统开销较大。

4）动态重定位分区分配

动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。

如果在系统中只有不相邻接的若干小分区，即使它们容量的总和大于要装入的程序，也无法把该程序装入内存。

这种通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为拼接或紧凑。

4.6 分页

分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页。

相应地，也把内存空间分成与页面相同大小的若干个存储块，称为物理块或页框。

在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。

页面大小由CPU决定（在设计CPU时已经确定），操作系统无法改变。

1）地址计算：

2）页表：

​ 系统又为每个进程建立了一张页面映像表，简称页表。在进程地址空间内的所有页，依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。页表的作用是实现从页号到物理块号的地址映射。

3）快表：

由于页表是存放在内存中的，这使CP在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表。第二次访问内存时，才是从第一次所得地址中获得所需数据。因此，采用这种方式将使计算机的处理速度降低近1/2。为了提高地址变换速度，可在地址变换机构中增设一个特殊高速缓冲寄存器，又称为“联想寄存器”，或称为“快表”

4）两级/多级页表：

现代的大多数计算机系统，都支持非常大的逻辑地址空间。在这样的环境下，页表就变得非常大。

对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，必须采用多级页表（三级页表），将外层页表再进行分页。

4.7 虚拟内存

1）常规存储器：

​ 一次性：常规的存储管理方式中，都要求将作业全部装入内存后方能运行。有些程序每次运行时，并非其全部程序和数据都要用到，这是一种对内存空间的浪费。

​ 驻留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束。进程会因阻塞而长时间等待，程序有些模块或数据用过一次可能就不再需要了，但它们都仍将继续占用宝贵的内存资源。

2）分页式虚拟存储系统

分页式虚拟存储系统是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的。

允许装入少数页面的程序(及数据)，便启动运行。以后再通过调页功能及页面置换功能，陆续地把随后运行所需的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。

3）缺页性能影响计算：

4.8 物理块的分配策略

1）固定分配局部置换

为每个进程分配固定数目的物理块，在整个运行期间都不再改变。

如果进程在运行中发现缺页，只能从进程在内存的n个页面中选出一页换出，然后再调入新页。

缺点：应为每个进程分配多少个物理块难以确定。若太少，会频繁地出现缺页中断，会大大降低性能；若太多，浪费，使内存中驻留的进程数目减少，可能造成CPU或其它资源空闲。

2）可变分配全局置换

先为系统中的每个进程分配一定数目的物理块，OS自身也保持一个空闲物理块队列。

当某进程发现缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程。

仅当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，可以是系统中任一进程的页（物理块）。

3）可变分配局部置换

在1）的基础上，增加如下策略：如果进程在运行中频繁地发生缺页中断，则系统为该进程追加若干数量的物理块，使进程的缺页率减少；反之，若进程在运行过程中的缺页率特别低，则可适当减少分配给该进程的物理块数，但以不引起其缺页率的明显增加为准。

4.9 页面置换算法

1）最佳置换算法

一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或者是在最长时间内不再被访问的页面。

目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的。

2）先进先出(FIFO)页面置换算法

最早出现的置换算法。总是淘汰最先进入内存的页面，选择在内存中驻留时间最久的页面予以淘汰。

优点：容易实现。

缺点：性能较差，因为页面调入的先后并不能反映页面的使用情况。

3）最近最久未使用(LRU)置换算法

LRU置换算法是选择最近最久未使用的页面予以淘汰。

5 设备管理

5.1 设备管理的任务

什么是设备管理？

5.2 I/O系统的组成

I/O系统包括：设备、控制器 和 总线（或 通道）

5.3 I/O设备

1）存储设备（外存，辅存）

是计算机系统用以存储信息的主要设备。该类设备存取速度较内存慢，但容量比内存大得多，相对价格也便宜。

2）输入/输出设备（包括输入设备、输出设备和交互式设备）

输入设备用来接收外部信息，如键盘、鼠标、扫描仪、视频摄像、各类传感器等。输出设备是用于将计算机加工处理后的信息送向外部的设备，如打印机、绘图仪、显示器、数字视频显示设备、音响输出设备等。交互式设备则是集成上述两类设备，利用输入设备接收用户命令信息，并通过输出设备(主要是显示器)同步显示用户命令以及命令执行的结果。如现在的显示屏（触摸屏） 。

5.4 I/O控制方式

1）程序I/O方式

处理机对I/O设备的控制采取程序I/O(Programmed I/O，忙-等待）方式。在处理机向控制器发出一条I/O指令启动输入设备输入数据时，要同时把状态寄存器中的忙/闲标志busy置为1，然后不断地循环测试busy。当busy=1时，表示输入机尚未输完一个字(符)，处理机应继续对该标志进行测试。直至busy=0，表明输入机已将输入数据送入控制器的数据寄存器中。然后处理机才能将数据寄存器中的数据取出，送入内存指定单元中，这样便完成了一个字(符)的I/O。

2）中断驱动I/O控制方式

即当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，CPU不等待I/O完成，CPU与I/O设备并行操作。以输入为例，设备控制器收到CPU发来的读命令后，便去控制相应的输入设备读数据。一旦数据进入数据寄存器，控制器便通过控制线向CPU发送一中断信号，由CPU检查输入过程中是否出错，若无错，便从控制器发送取走数据的信号。

优点：使CPU和I/O设备都处于忙碌状态，从而提高了整个系统的资源利用率及吞吐量。

3）直接存储器访问(DMA)I/O控制方式

引入：中断驱动I/O已经很有效，但它仍是以字（字节）为单位进行I/O的，每当完成一个字(节)的I/O时，控制器便要向CPU请求一次中断。对于块设备的I/O，显然是极其低效的。

DMA的特征：

A.CPU与I/O设备之间数据传输的基本单位是数据块；

B.数据从设备直接送入内存的，或者相反；

C.仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成的。

4）I/O通道控制方式

引入：DMA方式中，CPU每发出一条I/O指令，也只能去读(或写)一个连续的数据块。而当我们需要一次去读多个数据块且将它们分别传送到不同的内存区域，或者相反时，则须由CPU分别发出多条I/O指令及进行多次中断处理才能完成。

I/O通道方式是DMA方式的发展。当CPU只需向I/O通道发送一条I/O指令，以给出其所要执行的通道程序的首址和要访问的I/O设备，通道接到该指令后，通过执行通道程序便可完成指定I/O任务。

总结：

程序控制：CPU控制下完成整个I/O过程，I/O过程中CPU必须等待。

中断控制：CPU不干预I/O过程，完成后再由中断通知。注意，一次只能完成一个数的I/O。

DMA控制：控制器自主依次完成多个字节（数据块），每次执行一个I/O指令，控制器可以直接访问内存，有计数器。

I/O通道：通道本身是一个特殊的处理器，可以执行多个指令，完成多个数据块的I/O。

5.5 缓冲

目的：缓和CPU与I/O设备间速度不匹配的矛盾；减少对CPU中断处理的紧迫性；提高CPU和I/O设备之间的并行性。

原理： 1）单缓冲

每当用户进程发出一I/O请求时，操作系统便在主存中为之分配一缓冲区。

在块设备输入时，假定从磁盘把一块数据输入到缓冲区的时间为T，操作系统将该缓冲区中的数据传送到用户区的时间为M，而CPU对这一块数据处理(计算)的时间为C。由于T和C是可以并行的，处理时间表示为Max(C，T)+M。

2）双缓冲

为了加快输入和输出速度，提高设备利用率，人们又引入了双缓冲区机制。双缓冲通常能消除用户的等待时间，即用户在输入完第一行之后，在CPU执行第一行中的命令时，用户可继续向第二缓冲区输入下一行数据。

3）循环缓冲

输入循环缓冲，可使输入进程和计算进程并行执行。

5.6 设备分配

设备分配考虑因素：

A.设备的固有属性；B.设备分配算法；C.设备分配时的安全性；D.设备独立性。

设备独立性：

　　为了提高OS的可适应性和可扩展性，在现代OS中都毫无例外地实现了设备独立性，也称为设备无关性。

​ 基本含义是：应用程序独立于具体使用的物理设备。

​ 优点：A.设备分配时的灵活性（若进程能以逻辑设备名称来请求某类设备时，系统可立即将该类设备中的任一台分配给进程，仅当所有此类设备已全部分配完毕时，进程才会阻塞）B.易于实现I/O重定向（所谓I/O重定向，是指用于I/O操作的设备可以更换(即重定向)，而不必改变应用程序）

5.7 SPOOLing技术

SPOOLing技术包括如下三个部分：

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

2）输入缓冲区和输出缓冲区。为了缓和CPU和磁盘之间速度不匹配的矛盾，在内存中要开辟两个缓冲区：输入缓冲区和输出缓冲区。

3）输入进程SPi和输出进程SPo。用两个进程来模拟脱机I/O时的外围控制机。进程SPi模拟脱机输入的外围机，将用户要求的数据从输入机通过输入缓冲区再送到输入井；进程SPo模拟脱机输出的外围机，把用户要求输出的数据先从内存送到输出井。

6 文件管理

6.1 文件管理的任务

1）存储空间的管理（分配与回收）

2）目录管理（数据存取）

3）文件共享

4）文件安全性与保护

6.2 文件

目前实际的操作系统中，基本只使用两种类型的文件：

A.文本格式：（行格式，差别）

B.二进制流：一个简单的内存信息保存。操作系统不做任何格式处理，信息的解释（处理）完全由用户（应用程序）自定。

文本的属性包括：

A.类型：可以从不同的角度来规定文件的类型，如源文件、目标文件及可执行文件等。

B.长度：文件长度指文件的当前长度，长度的单位可以是字节、字或块。

C.物理位置：该项属性通常是用于指示文件在哪一个设备上及在该设备的哪个位置的指针。

D.时间信息：建立、修改时间、访问时间。

6.3 外存分配方式

1）连续分配

把逻辑文件中的记录顺序地存储到邻接的各物理盘块中。

随着文件建立时空间的分配和文件删除时空间的回收，较小的连续区已难于用来存储文件，此即外存碎片。同样，我们也可以利用紧凑的方法，将盘上所有的文件紧靠在一起。

优点：顺序访问容易，速度快。

缺点：A.要求有连续的存储空间。因此产生的大量碎片，严重地降低了外存空间的利用率；B.必须事先知道文件的长度；C.对于那些动态增长的文件，需要预分配空间，很低效。

2）隐式链接分配

在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针；在每个盘块中也都含有一个指向下一个盘块的指针。

缺点：它只适合于顺序访问，它对随机访问是极其低效的。

3）显式链接分配

把用于链接文件各物理块的指针，全部显式地（集中）存放在硬盘的一个特定的地方，也就是把链表指针集中存放。

由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。

4）索引分配

引入：链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了下述另外两个问题。

A.不能支持高效的直接存取（要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号）；

B.FAT本身需占用较大的内存空间；

事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个FAT调入内存。

为此，应将每个文件所对应的盘块号集中地放在一起。为每个文件分配一个索引块，再把分配给该文件的所有盘块号都记录在该索引块中。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。

6.4 目录管理

文件目录是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。

要求：

1）实现“按名存取”：用户只须向系统提供所需访问文件的名字，便能快速准确地找到指定文件在外存上的存储位置。这是目录管理中最基本的功能，也是文件系统向用户提供的最基本的服务。

2）提高对目录的检索速度：通过合理地组织目录结构的方法，可加快对目录的检索速度，从而提高对文件的存取速度。这是在设计一个大、中型文件系统时所追求的主要目标。

3）文件共享：在多用户系统中，应允许多个用户共享一个文件。这样就须在外存中只保留一份该文件的副本，供不同用户使用，以节省大量的存储空间，并方便用户和提高文件利用率。

4）允许文件重名：系统应允许不同用户对不同文件采用相同的名字，以便于用户按照自己的习惯给文件命名和使用文件。