操作系统

目录

1. OS

2. 进程、线程

3. 调度算法、死锁

4. 虚拟存储

5. I/O系统

6. 文件

1 OS

典型操作系统：多道批处理系统、分时系统、实时系统。

1.1 多道批处理系统

在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。

【特征】

1. 资源利用率高
2. 系统吞吐量大
3. 平均周转时间长
4. 无交互能力

1.2 分时系统

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

【特征】

1. 多路性
2. 独立性
3. 及时性
4. 交互性

1.3 实时系统

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

【特征】

1. 多路性
2. 独立性
3. 及时性
4. 交互性
5. 可靠性

1.4 OS的特征和功能

【特征】

1. 并发：同一段时间内多个程序执行(注意区别并发和并行，前者是同一时刻的多个事件，后者是统一时间段内的多个事件)
2. 共享：系统中的资源可以被内存中多个并发执行的进线程共同使用
3. 虚拟：通过时分复用（如分时系统）以及空分复用（如虚拟内存）技术实现把一个物理实体虚拟为多个
4. 异步：系统中的进程是以走走停停的方式执行的，且以一种不可预知的速度推进

【功能】

1. 资源管理器
   1. 处理器管理：处理机分配都是以进程为单位，所以处理器管理也被看做是进程管理。包括进程控制，进程同步，进程通信和进程调度
   2. 存储器管理：内存分配，内存保护，地址映射，内存扩充
   3. 设备管理：管理所有外围设备，包括完成用户的IO请求；为用户进程分配IO设备；提高IO设备利用率；提高IO速度；方便IO的使用
   4. 文件管理：管理用户文件和系统文件，方便使用同时保证安全性。包括：磁盘存储空间管理，目录管理，文件读写管理以及文件共享和保护
2. 用户接口
   1. 用户接口：联机用户接口，脱机用户接口和图形用户接口
   2. 程序接口：该接口是为用户程序在执行中访问系统资源而设置的，它是由一组系统调用组成。

2 进程和线程

2.1 进程

2.1.1 进程的概念

进程（Process） 是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。 在当代面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体（数据结构+算法+数据）。计算机中正在运行的程序实例。

线程（thread） 是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。

我们简单总结下：一句话：进程是资源分配的最小单位，线程是CPU调度的最小单位

进程：指在系统中正在运行的一个应用程序；程序一旦运行就是进程；进程——系统资源分配的最小单位。

线程：系统分配处理器时间资源的基本单元，或者说进程之内独立执行的一个单元执行流。线程——程序执行的最小单位。

并行和并发

　　并行处理（Parallel Processing）是计算机系统中能同时执行两个或更多个处理的一种计算方法。并行处理可同时工作于同一程序的不同方面。并行处理的主要目的是节省大型和复杂问题的解决时间。

　　并发处理(concurrency Processing)：指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机(CPU)上运行，但任一个时刻点上只有一个程序在处理机(CPU)上运行

同步和异步

在计算机领域，同步就是指一个进程在执行某个请求的时候，若该请求需要一段时间才能返回信息，那么这个进程将会一直等待下去，直到收到返回信息才继续执行下去；异步是指进程不需要一直等下去，而是继续执行下面的操作，不管其他进程的状态。当有消息返回时系统会通知进程进行处理，这样可以提高执行的效率。举个例子，打电话时就是同步通信，发短息时就是异步通信。

2.1.2 进程和程序区别

　　进程（Process） 是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。

　　程序是指令、数据及其组织形式的描述，进程是程序的实体。

1. 进程是一个动态概念，强调执行的过程，每个进程中包含了程序段和数据段两个部分，以及进程控制块PCB；而程序是一个静态概念，程序是指令的有序集合，无执行含义；
2. 进程具有并行特征（独立性，异步性），程序则没有；
3. 一个进程可以执行多个程序（如Linux中通过exec调用），同一程序的多次执行将产生多个不同的进程。同一个程序的一次执行也可产生多个进程（如在程序中多次调用linux中的fork）。

2.1.3 进程和作业的区别

　　进程是一个程序对某个数据集的执行过程，是对已提交完毕的程序所执行过程的描述，是向系统申请分配资源的基本单位。

​ 作业是用户需要计算机完成某项任务，而要求计算机所做工作的集合；一个作业的完成要经过作业提交、作业收容、作业执行和作业完成四个阶段。

其主要区别如下：

1. 作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行； 进程则是完成用户任务的执行实体。任一进程，只要它被创建，总有相应的部分存在于内存中；
2. 一个作业可由多个进程组成。且必须至少由一个进程组成，但反过来不成立；
3. 作业的概念主要用在批处理系统中，像UNIX这样的分时系统中，则没有作业的概念；而进程的概念则用在几乎所有的多道程序系统中。

进程(线程+内存+文件/网络句柄)

我们通过图片进行进一步理解：

“内存”： 我们通常所理解的内存是我们所见到的(2G/4G/8G/16G)物理内存,它为什么会在进程之中呢？ 实际上，这里的内存是逻辑内存。指的是内存的寻址空间。每个进程的内存是相互独立的。 否则的话会出现一个问题：我们把指针的值改一改就指向其他进程的内存了，通过这样我们岂不是就可以看到其他进程中"微信"或者是"网上银行"的信息， 这样的话，那我们的微信聊天记录或者是银行账户的信息就都被别人找到了，这是一个很危险的信号！显然这样是不可能的。

“文件/网络句柄”： 它们是所有的进程所共有的，例如打开同一个文件，去抢同一个网络的端口这样的操作是被允许的。

“线程”： 是操作系统能够进行运算调度的最小单位。

2.1.4 进程由三部分组成：PCB（程序控制快）、程序段、数据段

为什么说PCB是进程存在的唯一标志？

​ 在调度到某进程后，要根据其PCB中所保存的CPU状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存地址，找到其程序和数据；进程在执行过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也都需要访问PCB：当进程由于某种原因而暂停执行时，又需将器断点的CPU环境保存在PCB中。可见，在进程的整个生命期中，系统总是通过PCB对进程进行控制的，亦即系统是根据进程的PCB而不是任何别的什么而感知到该进程的存在的。所以PCB是进程存在的唯一标志。

1. PCB

   为了描述和控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块PCB（Process Control Block）

   • 进程标识符：内部标识符，外部标识符
   • 处理机状态
   • 进程调度信息
   • 进程控制信息

   PCB的作用：

   1. PCB是系统只为每个进程定义的一个数据结构，是为了使程序（含数据）能独立运行，为之配置的一进程控制块（Process Control Block）；
   2. PCB、程序段和相关的数据段三部分构成了进程实体，创建进程，实质上是创建进程和实体中的PCB，而撤销进程，实质上是撤销进程的PCB；PCB是为了保证程序的并发执行；
   3. PCB使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。

2. 进程的基本状态和转换

   进程的描述与控制 进程的状态和转换 三态模型和五态模型

   进程的三种基本状态：就绪状态，执行状态，阻塞状态（另外两种：创建状态和终止状态）

临界资源：每次仅允许一个进程访问的资源。

2.1.5 进程间的两种相互制约关系：同步、互斥

进程同步（直接相互制约关系）：它主要源于进程合作，是进程间共同完成一项任务时直接发生相互作用的关系。为进程之间的直接制约关系，在多道环境下，这种进程间在执行次序上的协调是必不可少的。

进程互斥（间接相互制约关系）：它主要源于资源共享，是进程之间的间接制约关系。在多道系统中，每次只允许一个进程访问的资源称为临界资源，进程互斥就是保证每次只有一个进程使用临界资源。

2.1.6 什么是进程的(高级)通信，类型？

进程通信，是指进程之间的信息交换，其所交换的信息量少者是一个状态或数值，多者则是成千上万个字节。高级进程通信，是指用户可直接利用操作系统所提供的一组通信命令高效地传送大量数据的一种通信方式。

• 信号 (sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

• 管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。

• 消息队列( messagequeue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

• 信号量(semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

• 共享内存(shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。

• 套接字(socket ) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。

信号量

信号量是Dijkstra提出的用于解决进程同步的有效工具。信号量是一个【数据结构+对自身的操作】。

除初始化外，仅能通过两个标准的原子操作wait(S)和 signal(S)来访问。两个语句在执行到一半的时候不能被中断。

P操作和V操作

(P、V操作的处理流程，以记录型信号量为例）

P（S）：wait(S)

每次wait操作，意味着进程请求一个单位的该类资源，使系统可供分配的该类资源数减少一个。

① 将信号量S的值减1，即S.value:=S.value-1；

② 当S.value<0时，表示该类资源分配完毕，进程调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表中。

V（S）：signal(S)

每次signal操作，表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个

① 将信号量S的值加1，即S.value:=S.value+1；

② 如果S.value<=0，表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将链表中的第一个等待进程唤醒。

用信号量和P、V操作机制实现互斥和同步的方法，信号量取值的含义

利用信号量和P V操作实现进程互斥时应该注意的是：

（1）每个程序中用户实现互斥的P,V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。

（2）P,V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。

（3）互斥信号量得初值一般为1

其中信号量S用于互斥，初值为1。

利用信号量和P V操作实现进程同步

2.2 线程

**线程（thread） 是操作系统能够进行运算调度的最小单位。**它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。

2.2.1 线程(栈+PC+TLS)

栈:

调用堆栈就是调用栈的意思。 那么我们的栈里面有什么呢？ 我们从主线程的入口main函数，会不断的进行函数调用， 每次调用的时候，会把所有的参数和返回地址压入到栈中。

PC：

Program Counter 程序计数器，操作系统真正运行的是一个个的线程， 而我们的进程只是它的一个容器。PC就是指向当前的指令，而这个指令是放在内存中。 每个线程都有一串自己的指针，去指向自己当前所在内存的指针。 计算机绝大部分是存储程序性的，说的就是我们的数据和程序是存储在同一片内存里的 这个内存中既有我们的数据变量又有我们的程序。所以我们的PC指针就是指向我们的内存的。

TLS:

全称：thread local storage 之前我们看到每个进程都有自己独立的内存，这时候我们想，我们的线程有没有一块独立的内存呢?答案是有的，就是TLS。 可以用来存储我们线程所独有的数据。 可以看到：线程才是我们操作系统所真正去运行的，而进程呢，则是像容器一样他把需要的一些东西放在了一起，而把不需要的东西做了一层隔离，进行隔离开来。

2.2.2 线程之间通信

1. 锁机制：包括互斥锁、条件变量、读写锁
   • 互斥锁提供了以排他方式防止数据结构被并发修改的方法。
   • 读写锁允许多个线程同时读共享数据，而对写操作是互斥的。
   • 条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
2. 信号量机制（semaphore）：包括无名线程信号量和命名线程信号量
3. 信号机制（Signal）：类似进程间的信号处理pv

线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

2.3 进程和线程的关系

2.3.1 进程和线程的宏观理解

要了解二者的区别与联系，首先你要知道什么是线程，什么是线程？

【进程】是并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概念。

进程至少有 5 种基本状态，它们是：初始态，执行态，等待状态，就绪状态，终止状态。

【线程】在网络或多用户环境下，一个服务器通常需要接收大量且不确定数量用户的并发请求，为每一个请求都创建一个进程显然是行不通的，无论是从系统资源开销方面或是响应用户请求的效率方面来看。因此，操作系统中引入了线程

线程是进程的一部分，一个没有线程的进程可以被看作是单线程的。线程有时又被称为轻权进程或轻量级进程，也是 CPU 调度的一个基本单位。

2.3.2 进程和线程的区别

1. 进程的执行过程是线状的，尽管中间会发生中断或暂停，但该进程所拥有的资源只为该线状执行过程服务。一旦发生进程上下文切换，这些资源都是要被保护起来的。这是进程宏观上的执行过程。

2. **进程又可有单线程进程与多线程进程两种；**我们知道，进程有 一个进程控制块PCB 、程序段 和相关数据块 三部分，单线程进程的执行过程在宏观上是线性的，微观上也只有单一的执行过程；而多线程进程在宏观上的执行过程同样为线性的，但微观上却可以有多个执行操作（线程），如不同代码片段以及相关的数据结构集。

   线程也有自己的线程控制表 TCB，所保存的线程状态信息则要比 PCB 表少得多，主要是相关指针用堆栈（系统栈和用户栈）、寄存器中的状态数据，线程的改变只代表了 CPU 执行过程的改变，而没有发生进程所拥有的资源变化。

3. 进程拥有一个完整的虚拟地址空间，不依赖于线程而独立存在；反之，线程是进程的一部分，没有自己的地址空间，与进程内的其他线程一起共享分配给该进程的所有资源。

线程可以有效地提高系统的执行效率，但并不是在所有计算机系统中都是适用的，如某些很少做进程调度和切换的实时系统。使用线程的好处是有多个任务需要处理机处理时，减少处理机的切换时间；而且，线程的创建和结束所需要的系统开销也比进程的创建和结束要小得多。最适合使用线程的系统是多处理机系统和网络系统或分布式系统。

3 基本调度算法

3.1 调度算法

1、FCFS先来先服务

【算法思想】当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪对垒中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

（非抢占式的调度算法）

2、短作业（进程）优先调度

【算法思想】短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先（SPF）调度算法则是从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

（非抢占式的调度算法）

3、 最短剩余时间优先算法

4、高响应比优先调度算法

为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然后寄回分配到处理机。该优先权的变化规律可描述为：

　　优先权=（等待时间+要求服务时间）/ 要求服务事件

5、基于时间片的轮转调度算法

系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。

时间片轮转法中，时间片取值的影响：

​ 如果选择很小的时间片将有利于短作业，因为它能较快地完成，但会频繁地发生中断、进程上下文的切换，从而增加系统的开销；反之，如果选择太长的时间片，使得每个进程都能在一个时间片内完成，时间片轮转算法便退化为FCFS算法，无法满足交互式用户的需求。

如何确定时间片的大小：

​ 时间片应略大于一次典型的交互需要的时间。这样可使大多数进程在一个时间片内完成。一般应考虑三个因素：系统对相应时间的要求、就绪队列中进程的数目和系统的处理能力。

3.2 死锁

如果一个进程集合中的每个进程都在等待只能由此集合中的 其他进程才能引发的事件，而无限期陷人僵持的局面称为死锁。

产生死锁的原因：可归结为（1）竞争资源；（2）进程间推进顺序非法。

产生死锁的必要条件：

1. 互斥条件：一个资源每次只能被一个线程使用。
2. 请求与保持条件：一个线程因请求资源而阻塞时，对已获得的资源保持不放。
3. 不剥夺条件：线程已获得的资源，在未使用完之前，不能强行剥夺。
4. 循环等待条件：若干线程之间形成一种头尾相接的循环等待资源关系。

如何避免死锁？

答：银行家算法

破坏四个必要条件中的任一个即可避免死锁，重要的一点：在并发程序中，避免了逻辑中出现多个线程互相持有对方线程所需要的独占锁的的情况，就可以避免死锁。

4 虚拟存储

4.1 逻辑地址和物理地址

逻辑地址（Logical Address）是指由程序产生的和段相关的偏移地址部分。只有在Intel实模式下，逻辑地址才和物理地址相等（因为实模式没有分段或分页机制,CPU不进行自动地址转换）；

物理地址（Physical Address）是指出现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果地址。（假如启用了分页机制，那么线性地址会使用页目录和页表中的项变换成物理地址。假如没有启用分页机制，那么线性地址就直接成为物理地址了）

4.2 地址重定位、静态地址重定位、动态地址重定位

​ 重定位就是把程序中相对地址变换为绝对地址。通常是把在装入时对目标程序中指令和数据的修改过程称为重定位。有静态重定位和动态重定位两种重定位技术。

​ 因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。

​ 在运行过程中程序在内存中的位置可能经常要改变，此时就应采用动态运行时装入的方式。动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一个重定位寄存器的支持。

4.3 虚拟存储器、引入的原因

​ 所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。

引入的原因：

① 有的作业很大，要求的内存空间超过了内存总容量，不能装入内存，至使该作业无法运行。
② 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们运行，而将其他大量的作业驻留在外存上等待。
③ 常规存储器管理方式：一次性；驻留性
④ 局部性原理的提出：时间局限性；空间局限性。
一个解决方式是从逻辑上扩充内存容量，这正是虚拟存储技术所要解决的主要问题。

虚拟存储器特征：对换性，多次性，虚拟性（最本质特征）

4.4 内存管理方式-段式页式和段页式

　　由于连续内存分配方式(单一连续分配，固定分区分配，动态分区分配，动态重定位分区分配)导致的内存利用率偏低以及内存碎片的问题，进而引出离散的内存分配方式。离散内存分配可以从OS的内存管理角度引出页式(离散分配的基本单位是页)管理，也可以从程序编制角度引出段式(离散分配的基本单位是段)管理。

4.4.1、基本分页存储管理

​ 基本分页存储管理中不具备页面置换功能(即没有实现虚拟内存的功能)，因此需要整个程序的所有页面都装入内存之后才可以运行。因为程序数据存储在不同的页面中，而页面又离散的分布在内存中，因此需要一个页表来记录逻辑地址和实际存储地址之间的映射关系，以实现从页号到物理块号的映射。由于页表也是存储在内存中的，因此和不适用分页管理的存储方式相比，访问分页系统中内存数据需要两次的内存访问(一次是从内存中访问页表，从中找到指定的物理块号，加上页内偏移得到实际物理地址；第二次就是根据第一次得到的物理地址访问内存取出数据)。

​ 为了减少两次访问内存导致的效率影响，分页管理中引入了快表(或者联想寄存器)机制，包含快表机制的内存管理中，当要访问内存数据的时候，首先将页号在快表中查询，如果查找到说明要访问的页表项在快表中，那么直接从快表中读取相应的物理块号；如果没有找到，那么访问内存中的页表，从页表中得到物理地址，同时将页表中的该映射表项添加到快表中(可能存在快表换出算法)。

​ 在某些计算机中如果内存的逻辑地址很大，将会导致程序的页表项会很多，而页表在内存中是连续存放的，所以相应的就需要较大的连续内存空间。为了解决这个问题，可以采用两级页表或者多级页表的方法，其中外层页表一次性调入内存且连续存放，内层页表离散存放。相应的访问内存页表的时候需要一次地址变换，访问逻辑地址对应的物理地址的时候也需要一次地址变换，而且一共需要访问内存3次才可以读取一次数据。

4.4.2、基本分段存储管理方式

　　分页是为了提高内存利用率，而分段是为了满足程序员在编写代码的时候的一些逻辑需求(比如数据共享，数据保护，动态链接等)。

　　分段内存管理当中，地址是二维的，一维是段号，一维是段内地址；其中每个段的长度是不一样的，而且每个段内部都是从0开始编址的。由于分段管理中，每个段内部是连续内存分配，但是段和段之间是离散分配的，因此也存在一个逻辑地址到物理地址的映射关系，相应的就是段表机制。段表中的每一个表项记录了该段在内存中的起始地址和该段的长度。段表可以放在内存中也可以放在寄存器中。

​ 访问内存的时候根据段号和段表项的长度计算当前访问段在段表中的位置，然后访问段表，得到该段的物理地址，根据该物理地址以及段内偏移量就可以得到需要访问的内存。由于也是两次内存访问，所以分段管理中同样引入了联想寄存器。

4.4.3、分段和分页的对比：

1. 页是信息的物理单位，是出于系统内存利用率的角度提出的离散分配机制；段是信息的逻辑单位，每个段含有一组意义完整的信息，是出于用户角度提出的内存管理机制
2. 页的大小是固定的，由系统决定；段的大小是不确定的，由用户决定
3. 页地址空间是一维的，段地址空间是二维的

4.4.4、段页式存储管理

　　先将用户程序分为若干个段，然后再把每个段分成若干个页，并且为每一个段赋予一个段名称。这样在段页式管理中，一个内存地址就由段号，段内页号以及页内地址三个部分组成。
　　段页式内存访问：系统中设置了一个段表寄存器，存放段表的起始地址和段表的长度。地址变换时，根据给定的段号（还需要将段号和寄存器中的段表长度进行比较防止越界）以及寄存器中的段表起始地址，就可以得到该段对应的段表项，从段表项中得到该段对应的页表的起始地址，然后利用逻辑地址中的段内页号从页表中找到页表项，从该页表项中的物理块地址以及逻辑地址中的页内地址拼接出物理地址，最后用这个物理地址访问得到所需数据。由于访问一个数据需要三次内存访问，所以段页式管理中也引入了高速缓冲寄存器。

4.4.5、虚拟内存及页面置换算法

　　如果存在一个程序，所需内存空间超过了计算机可以提供的实际内存，那么由于该程序无法装入内存所以也就无法运行。单纯的增加物理内存只能解决一部分问题，但是仍然会出现无法装入单个或者无法同时装入多个程序的问题。但是可以从逻辑的角度扩充内存容量，即可解决上述两种问题。

　　虚拟存储器就是具有请求调入功能和置换功能，可以从逻辑上对内存容量加以扩充的一种存储器系统。虚拟存储器都是建立在离散内存管理的基础上

虚拟存储器的特征：

1. 多次性：一个作业可以分多次被调入内存。多次性是虚拟存储特有的属性
2. 对换性：作业运行过程中存在换进换出的过程(换出暂时不用的数据换入需要的数据)
3. 虚拟性：虚拟性体现在其从逻辑上扩充了内存的容量(可以运行实际内存需求比物理内存大的应用程序)。虚拟性是虚拟存储器的最重要特征也是其最终目标。虚拟性建立在多次性和对换性的基础上行，多次性和对换性又建立在离散分配的基础上

4.4.6、页面置换算法

1. 最佳置换算法：只具有理论意义的算法，用来评价其他页面置换算法。置换策略是将当前页面中在未来最长时间内不会被访问的页置换出去。
2. 先进先出置换算法：简单粗暴的一种置换算法，没有考虑页面访问频率信息。每次淘汰最早调入的页面
3. 最近最久未使用算法LRU：算法赋予每个页面一个访问字段，用来记录上次页面被访问到现在所经历的时间t，每次置换的时候把t值最大的页面置换出去(实现方面可以采用寄存器或者栈的方式实现)
4. 最少使用算法LFU：设置寄存器记录页面被访问次数，每次置换的时候置换当前访问次数最少的。存在问题是该访问寄存器并不能真正反映当前页面访问次数，因为访问速度比较快，所以在更新寄存器的时间间隔内访问1次和访问100次都是一样的。另外，LFU和LRU是很类似的，支持硬件也是一样的，但是区分两者的关键在于一个以时间为标准，一个以次数为标准(例如对于寄存器 pa 001111 和pb 111000，两个页面，如果采用LRU，那么被淘汰的是pa，如果采用LFU那么被淘汰的是pb)。

4.5 静态链接-装入时动态链接-运行时动态链接

a.静态链接是指在程序运行之前，先将各自目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开的链接方式。

b.装入时动态链接是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的一种链接方式，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找相应的外部目标模块，把它装入内存中，并修改目标模块中的相对地址。

c.运行时动态链接是将对某些模块的链接推迟到程序执行时才进行链接，也就是，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。

5 I/O系统的组成

5.1 I/O设备

设备分类情况

• 按设备的使用特性分类：存储设备；输入/输出设备
• 按传输速率分类：低速设备；中速设备；高速设备
• 按信息交换的单位分类：块设备；字符设备
• 按设备的共享属性分类：独占设备；共享设备；虚拟设备

虚拟设备：通过虚拟技术将一台独占设备变换为若干台逻辑设备，供若干个用户（进程）同时使用。

引入虚拟设备的目的：将慢速的独占设备改造成多个用户可共享的同类设备，提高设备的利用率。

5.2 OS在设备管理中引入的相关技术

5.2.1 中断技术

组成：

　　CPU和I/O控制器

工作原理：

① CPU：向控制器发出I/O命令，然后继续执行计算任务；
② I/O控制器：执行I/O命令，控制外部设备完成指定的I/O操作，然后向CPU发送中断信号；
③ CPU：暂停正在执行的任务，处理I/O中断，完成后再返回，继续执行原来的任务。

5.2.2 DMA技术

组成：

　　CPU，内存，DMA控制器（主机与DMA控制器的接口；DMA控制器域块设备的接口；I/O控制逻辑；命令/状态寄存器CR；内存地址寄存器MAR；数据寄存器DR；数据计数器DC）

工作原理：

　　①当处理器需要读/写一整块数据时，给DMA控制单元发送一条命令，包含：一次读或写的指令、I/O设备的地址、开始读或写的主存地址、需要传送的数据长度等；
　　②处理器发送完命令后就可处理其它事情；
　　③DMA控制器自己独立管理整块数据的传送；
　　④当这个过程完成后，它会向处理器发一个中断请求。处理器只在一块数据开始传送和传送结束时关注一下I/O操作即可。

5.2.3 通道技术

组成：每条通道指令包含的信息是：操作码、内存地址、计数、程序结束位、记录结束位。

工作原理：把DMA方式中CPU以数据块为单位对读/写任务的干预，减少为以一次读/写任务及有关的控制和管理为单位的干预。 同时，又可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

5.2.4 缓冲技术

组成：单缓冲，双缓冲，循环缓冲，缓冲池

工作原理：在CPU与外设之间建立缓冲区，用于暂存CPU与外设间交换的数据，从而缓冲CPU与外设间速度不匹配的矛盾。

5.2.5 Spooling技术（虚拟设备技术）

组成：

• 在磁盘上开辟输入井和输出井；
• 在内存中开辟输入缓冲区和输出缓冲区；
• OS要有相关的管理进程：SPi，模拟脱机输入；SPo模拟脱机输出。
  工程原理：

　　脱机输入和脱机输出
　　在多道环境下，可以用OS的一道管理程序实现从I/O设备输入数据并存放到磁盘上，模拟脱机输入；用OS的另一道管理程序将磁盘上的数据输出到I/O设备上，模拟脱机输出；这种假脱机I/O操作称为Spooling技术。
　　Spooling是一种虚拟设备技术、一种资源转换技术。

设备分配的原则，什么是设备独立性(与设备无关性)

　　原则：要充分发挥设备的使用效率，尽可能地让设备处于工作状态，但又要避免由于不合理的分配方法造成进程死锁；

​ 设备独立性：即应用程序独立于具体使用的物理设备。为了实现设备独立性而引入了逻辑设备和物理设备这两个概念。在应用程序中， 使用逻辑设备名称来请求使用某类设备；而系统在实际执行时， 还必须使用物理设备名称。因此，系统须具有将逻辑设备名称转换为某物理设备名称的功能，这非常类似于存储器管理中所介绍的逻辑地址和物理地址的概念。

5.3 虚拟设备

为什么要引入设备独立性？如何实现设备独立性？

引入设备独立性，可使应用程序独立于具体的物理设备，是设备分配具有灵活性。另外容易实现I/O重定向。

为了实现设备独立性，必须在设备驱动程序之上设置一层设备独立性软件，用来执行所有I/O设备的公用操作，并向用户层软件提供统一接口。关键是系统中必须设置一张逻辑设备表LUT用来进行逻辑设备到物理设备的映射，其中每个表目中包含了逻辑设备名、物理设备名和设备驱动程序入口地址三项；当应用程序用逻辑设备名请求分配I/O设备时，系统必须为它分配相应的物理设备，并在LUT中建立一个表目，以后进程利用该逻辑设备名请求I/O操作时，便可从LUT中得到物理设备名和驱动程序入口地址。（OS实现设备独立性的方法：设置设备独立性软件(P164)、配置逻辑设备表，实现逻辑设备到物理设备的映射。）

什么是虚拟设备？其实现所依赖的关键技术有哪些？

虚拟设备是指通过虚拟技术，可将一台独占设备变换成若干台逻辑设备，供若干个用户（进程）同时使用。由于多台逻辑设备实际上并不存在，而只是给用户的一种感觉，因此被称为虚拟设备。其实现所依赖的关键技术是SPOOLing技术。

试说明SPOOLing系统的组成。

　　1）输入井和输出井；

　　2）输入缓冲区和输出缓冲区；

　　3）输入进程SPi和输出进程SPo。

5.4 磁盘调度

什么是磁盘调度，磁盘调度的目标，磁盘调度算法的原理、优先考虑的因素？

　　**磁盘调度：**就是当有多个进程同时要求访问磁盘时，安排对磁道访问请求的执行顺序。
　　**磁盘调度的目标：**使磁盘的平均寻道时间最少。

　　先来先服务FCFS：根据进程请求访问磁盘的先后次序进行调度。

　　最短寻道时间优先SSFT：要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。

　　扫描算法SCAN：不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。

​ **电梯调度算法：**模仿电梯

6 文件

6.1 文件的逻辑结构

这是用用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。

记录式文件的逻辑结构：
1、有结构文件：
记录的长度可分为定长和不定长两类：定长记录；变长记录
根据用户和系统管理上的需要，可采用多种方式来组织这些记录，形成下述的几种文件：顺序文件；索引文件；索引顺序文件。
2、无结构文件：
流式文件，其长度以字节为单位。

文件的物理结构:又称为文件的存储结构，是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。

外存的分配方式：

1、连续分配

实现方式：

　　为每个文件分配一组位置相邻接的盘块(物理地址连续的外存空间)，文件中的逻辑页被顺序地存放到相邻的物理盘块中。这保证了文件中的逻辑顺序与文件占用盘块顺序的一致性。这样物理结构的文件称为顺序文件。

　　每个文件都从分配给它的一个盘块的第一个字节开始存放。

记录文件地址：

　　在文件的目录中，存放该文件的第一个记录所在的盘块号和文件的长度(共占多少块)

2、链接分配

实现方式：

　　为每个文件分配一组位置离散的盘块，每个盘块中存放文件的一个逻辑页。通过在每个盘块上设置一个指针，将属于同一个文件的盘块顺序地链接在一起，链接的顺序和文件的逻辑顺序一致。这样物理结构的文件称为链接文件。

　　链接方式有隐式链接和显式链接两种。

　　记录文件地址：

显示链接：每个文件的第一个盘块的编号存放在文件目录中；文件的其他盘块的编号存放在FAT中；

隐式链接：目录和FAT一起记录了哪些盘块分给了这个文件以及这些盘块中内容的逻辑顺序。

3、索引分配

实现方式：

​ 为每个文件分配一组位置离散的盘块，为每个文件建立一个物理结构的索引表，记录分配给该文件的物理盘块，以及这些盘块和文件逻辑顺序的对应关系。建立一个文件时，要初始化它的索引表，并将索引表的地址放到文件的目录中。打开一个文件时，文件的索引表也被同时读入内存。
记录文件地址：

单级索引：每个文件一张索引表，这张索引表放在一个盘块中

多级索引：对于一个长文件的索引表(内容同上，但单个盘块放不下)，可以将它存放在若干个离散的盘块中。再为这些索引块建立一个索引表，存放在一个盘块中，这样就形成了一个文件的两级索引。

混合索引：文件系统混合使用多种分配方式。文件的目录中可以存放不同形式的地址信息：
　　　　直接地址，文件数据的盘块号；
　　　　一次间接地址，文件索引块的盘块号；
　　　　二次间接地址，文件二级索引块的盘块号。

6.2、单级、两级和多级(树型)目录结构的构成，逐步能实现的功能(特点)

6.2.1、单级目录结构：

构成：
为整个文件系统建立一张目录表，每个文件占一个目录项。
功能：
单级目录的优点是简单且能实现目录管理的基本功能—-按名存取。
缺点：(1)查找速度慢；(2)不允许重名；(3)不便于实现文件共享。

问题：采用单级目录能否满足对目录管理的主要要求？为什么？

　采用单级目录不能完全满足对目录管理的主要要求，只能实现目录管理最基本的功能即按名存取。由于单级目录结构采用的是在系统只配置一张目录表用来记录系统中所有文件的相关信息，因此此目录文件可能会非常大，在查找时速度慢，另外不允许用户文件有重名的现象，再者由于单级目录中要求所有用户须使用相同的名字来共享同一个文件，这样又会产生重名问题，因此不便于实现文件共享。

6.2.2、两级目录结构：

构成：
系统给每一个用户建立一张独立的用户目录表(UFD)，用来存放该用户所有文件的FCB， UFD的结构与单级目录表相似，它以一个目录文件的形式存在磁盘上；

整个文件系统有一张主目录表(MFD)，其中的每一个表目(一行)用来存放一个UFD文件的名字、大小、存放位置等信息(目录文件的FCB)。这样就形成了两级目录。

功能：
优点：解决了文件的重名问题和文件共享问题，提高搜索速度，查找时间降低
缺点：妨碍了用户间的文件共享，增加了系统开销

6.2.3、多级目录结构：

构成：
将两级目录的这种层次结构推广，就形成多级目录。

在多级目录结构中，MFD演变为文件系统的根目录，在根目录中可以存放一般文件的FCB，也可以存放目录文件的FCB；每一个目录文件对应一张目录表，其中既可以存放一般文件的FCB，也可以存放目录文件的FCB。
功能：
优点：
层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；提高文件检索速度；能进行存取权限的控制
缺点：
查找一个文件按路径名逐层检查，由于目录文件和普通文件都放在外存，多次访盘，影响速度。

6.3磁盘空间的组织管理方法

​ 空白文件目录、空闲链表、位示图、成组链--每种方法的数据结构，存储分配和回收的方法

6.3.1、空闲表法：

　　为每个文件分配一块连续的存储空间按，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。

6.3.2、空闲链表法：

1、空闲块链法：将磁盘上所有的空闲块拉成一条链，在链首设一个分配指针，在链尾设一个回收指针。空闲块的分配与回收分别在链的首尾进行。
2、空闲区链法：将磁盘上所有的空闲区拉成一条链，空闲区中要记录本区包含的空闲块数。存储空间的分配与回收与内存的动态分区分配类似。

6.3.3、位示图法：

空闲块的组织：在内存中划出连续若干个字，为每一个文件存储器建立一张位示图。磁盘的每一个物理块都有一个二进制位与之对应。该位值是“0”为空闲、“1”为已分配。

问题：空闲磁盘空间的管理常采用哪几种方式？UNIX系统采用的是何种方式？
　　（1）空闲表法，属于连续分配方式，它与内存管理中的动态分区分配方式相似。

　　（2）空闲链表法，将所有空闲盘区链接成一条空闲链。根据构成链的基本元素不同，可分为空闲盘块链和空闲盘区链。

　　（3）位示图法，利用二进制的一位来表示磁盘中每一个盘块的使用情况，磁盘上的所有盘块都有一个二进制位与之对应，从而由所有盘块所对应的位构成一个集合，即位示图。

　　（4）成组链接法，结合空闲表法和空闲链表法而形成。UNIX系统采用的是成组链接法。

6.4、存储空间的分配与回收

位示图需要多少个字，决定于盘块数。
申请物理块时，可以在位示图中顺序查找一个或一组其值为0的位，计算并返回每位对应的物理块号，分配物理块，并将位示图中对应的位置“1”；
回收物理块时，将回收的物理块号逆计算，得出块在位示图中的位置，并将对应的位置“0”。

成组链表法：

将系统的所有空白块每N个组成一组(例如N=100；这N个空白块位置不必连续)；
将所有的空白块组链接起来。链接的方法是：每一组的第一个空白块存放前一组的盘块总数和包含的每一个盘块号；

6.5、文件保护

文件的保护是指防止文件主或其他用户无意或有意破坏文件内容。也指防止系统出现异常、病毒或其他自然因素对文件内容的破坏。

文件保护采取的主要措施有：
　　(1) 通过存取控制机制，来防止人为因素所造成的文件不安全性；
　　(2) 通过磁盘容错技术，来防止磁盘部分故障造成的文件不安全性；
　　(3) 通过后备系统，来防止自然因素造成的整个文件存储器的不安全性。