操作系统复习

修改自 https://blog.csdn.net/spicy_chicken123/article/details/131431719

感谢明月出天山大佬和编写飞书文档的各位大佬！！

此文章主要针对于考试的简答题，想看计算题可以移步到这篇文章：
blog.csdn.net/spicy_chicken123/article/details/131431782

# 操作系统引论

1. OS 的定义、目标、作用

   1. OS 定义：操作系统是位于硬件层 (HAL) 之上，所有其它系统软件层之下的一个系统软件，使得管理系统中的各种软件和硬件资源得以充分利用，方便用户使用计算机系统。**
   2. OS 目标：方便性，有效性，可扩展性，开放性 **
   3. OS 作用：作为用户与计算机硬件系统之间的接口，作为资源管理者，作为扩展机器

2. 三种基本操作系统的基本原理和异同（批处理操作系统，分时操作系统，实时操作系统）

   1. 单道批处理操作系统：
      • 自动性、顺序性、单道性
      • 系统对作业的处理都是成批进行的，且在内存中始终仅存一道作业运行，运行结束或出错，才自动调另一道作业运行。
      • 优点：减少人工操作，解决了作业的自动接续
      • 缺点：平均周转时间长，没有交互能力
   2. 多道批处理操作系统
      • 多道性、无序性、调度性（进程调度和作业调度）
      • 在内存中存放多道作业运行，运行结束或出错，自动调度内存中的另一道作业运行。
      • 多道批处理的主要优点：提高了资源利用率和吞吐能力。
      • 多道批处理的主要缺点：平均周转时间长，没有交互能力。
   3. 分时操作系统 (time-sharing system)
      • 多路性：一个主机与多个终端相连；
      • 独立性：彼此独立操作，互不干扰；
      • 及时性：系统能在很短的时间得到回答；
      • 交互性：能实现人机对话（区别于批处理系统）；
   4. 实时操作系统 (real time system)
      • 多路性：能对多个对象进行控制。
      • 独立性：独立运行，不混淆，不破坏。
      • 交互性：仅限于访问系统中某些特定的专用服务程序。
      • 可靠性：高可靠性，应具有多级容错防护能力。
      • 及时性：不同的系统要求不一样，控制对象必须在
        截止时间内完成。

3. OS 的特征（期中考）

   现代 OS 的四个基本特征：并发性（最重要的特征），共享性，虚拟性，异步性，并发是最重要的特征，其它特征都以并发为前提

   • 并发性：两个或多个事件在同一时间间隔内发生
   • 共享性：系统中的资源可供内存中多个并发执行的进程同时使用（分为互斥共享和同时访问）
   • 虚拟性：通过某种技术把一个物理实体变为若干个逻辑上的对应物的功能（时分复用技术【虚拟处理机和虚拟设备】，空分复用技术）
   • 异步性：进程是以人们不可预知的速度向前推进的

4. OS 的功能 **

   1. 处理机管理：进程控制，进程同步和互斥，进程通信，进程调度
   2. 存储器管理：内存分配，内存保护，地址映射，内存扩充
   3. 设备管理：缓冲管理，设备分配，设备处理
   4. 文件管理：文件存储空间管理，目录管理，文件的读 / 写管理和保护
   5. 向用户提供 “操作系统与用户的接口”

# 处理机管理

1. 进程和线程的概念

   在引入线程的操作系统中，线程是系统独立调度和分配的基本单位 ，进程是拥有资源和独立运行的基本单位

   在未引入线程的操作系统中，进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的基本单位

2. 进程的基本状态及状态转换的原因

   1. 进程五种状态

      • 就绪：准备执行
      • 执行：占用处理机（单处理机环境中，某一时刻仅一个进程占用处理机）
      • 阻塞：等待某事件发生才能执行，如等待 I/O 完成等
      • 新建：进程已经创建，但未被 OS 接纳为可执行进程，并且程序还在辅存，PCB 在内存
      • 终止：因停止或取消，被 OS 从执行状态释放

   2. 进程转换模型

      ① 空 → 新状态：新创建的进程首先处于新状态。

      ② 新状态 → 就绪状态：当系统允许增加就绪进程时，操作系统接纳新建状态进程，将它变为就绪状态，插入就绪队列中。

      ③ 就绪状态 → 执行状态：当处理机空闲时，将从就绪队列中选择一个进程执行，该选择过程称为进程调度，或将处理机分派给一个进程，该进程状态从就绪转变为执行。

      ④ 执行状态 → 终止状态：执行状态的进程执行完毕，或出现诸如访问地址越界、非法指令等错误，而被异常结束，则进程从执行状态转换为终止状态。

      ⑤ 执行状态 → 就绪状态：分时系统中，时间片用完，或优先级高的进程到来，将中断较低优先级进程的执行。进程从执行状态转变为就绪状态，等待下一次调度。

      ⑥ ** 执行状态 → 阻塞状态：** 执行进程需要等待某事件发生。通常，会因为进程需要的系统调用不能立即完成，如读文件、共享虚拟内存、等待 I/O 操作、等待另一进程与之通信等事件而阻塞。

      ⑦ 阻塞状态 → 就绪状态：当阻塞进程等待的事件发生，就转换为就绪状态。进入就绪队列排队，等待被调度执行。

3. PCB 的概念、作用、包含信息、组织方式

   1. 为使程序（含数据）能独立运行，应为之配置一进程控制块，即 PCB (Process Control Block)

   2. 而由程序段、相关的数据段和 PCB 三部分便构成了进程实体。

   3. 进程控制块的作用：

      1） 作为独立运行基本单位的标志；
      2） 能实现间断性运行方式；
      3） 提供进程管理所需要的信息；
      4） 提供进程调度所需要的信息；
      5） 实现与其他进程的同步与通信。

   4. 进程控制块中的信息：进程标识符，处理机状态，进程调度信息，进程控制信息

   5. PCB 的组织方式：线性方式，链接方式，索引方式

4. 进程控制的原语操作

   常见的进程控制原语：进程创建原语，进程终止原语，进程阻塞原语，进程唤醒原语，进程挂起原语，进程激活原语，wait，signal

5. 进程互斥、临界区、进程同步的基本概念、同步准则

   1. 进程同步的主要任务：是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。
   2. 进程同步是进程之间的直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系
   3. 进程互斥是进程之间的间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。**
   4. 临界资源：一段时间内只允许一个进程访问的资源 **
   5. 临界区：在每个进程中访问临界资源的那段程序
   6. 同步准则
      • 空闲让进：如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入
      • 忙则等待：任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待
      • 有限等待：进入临界区的进程要在有限的时间内退出，以便其它进程能及时进入自己的临界区
      • 让权等待：如果进程不能进入自己的临界区，则应该让出 CPU，避免进程出现 “忙等” 的现象

6. 四种信号量机制：整型信号量，记录型信号量，AND 型信号量，信号量集

   记录型信号量：

   在信号量机制中，除了需要一个用于代表资源数目的整型变量 value 外，还应增加一个进程链表指针 L，用于链接上述的所有等待进程。

   记录型信号量是由于它采用了记录型的数据结构而得名的。

   	typedef struct {
   	int value;
   	struct process_control_block *list;
   	} semaphore;
   	// 等待操作
   	void wait(semaphore *S) {
   	S->value --;
   	if (S->value < 0) {
   	// 将当前进程加入等待队列
   	block(S->L);
   	}
   	}
   	// 信号操作
   	void signal(semaphore *S) {
   	S->value ++;
   	if (S->value <= 0) {
   	// 唤醒等待队列中的进程
   	wakeup(S->L);
   	}
   	}

7. 信号量的应用

   用信号量实现进程互斥

   利用信号量实现前趋关系

8. 经典进程同步问题：生产者与消费者问题，哲学家进餐问题，读者 - 写者问题 ***

   考察伪代码

   生产者与消费者问题：

   	#define BUFFER_SIZE n
   	item buffer[BUFFER_SIZE]; // 缓冲区数组
   	int in = 0; // 生产者向缓冲区中添加数据的位置
   	int out = 0; // 消费者从缓冲区中取出数据的位置
   	// 生产者进程
   	void producer() {
   	while (true) {
   	produce_item(); // 生产一个数据项
   	// 等待缓冲区中有空的位置
   	P(empty);
   	// 获取对缓冲区的访问权
   	P(mutex);
   	// 将数据项添加到缓冲区
   	buffer[in] = item;
   	in = (in + 1) % BUFFER_SIZE;
   	// 释放对缓冲区的访问权
   	V(mutex);
   	// 增加 full 计数
   	V(full);
   	}
   	}
   	// 消费者进程
   	void consumer() {
   	while (true) {
   	// 等待缓冲区中有数据
   	P(full);
   	// 获取对缓冲区的访问权
   	P(mutex);
   	// 从缓冲区中取出一个数据项
   	item = buffer[out];
   	out = (out + 1) % BUFFER_SIZE;
   	// 释放对缓冲区的访问权
   	V(mutex);
   	// 增加 empty 计数
   	V(empty);
   	consume_item(item); // 消费数据项
   	}
   	}

9. 进程间通信的原理和实现方法

   4 种：共享存储器系统，管道通信系统，消息传递系统，客户机 - 服务器系统 **

   消息传递系统分为直接消息传递系统和信箱通信

   系统为信箱通信提供了若干条原语，分别用于信箱的创建、撤消和消息的发送、接收等。

   优点：在读 / 写时间上的随机性

   写进程 -> 信箱（中间实体）-> 读进程原语

   消息的发送和接收

   Send (mailbox, message)

   Receive (mailbox, message)

   信箱分为以下三类：

   （1）私用信箱

   （2）公用信箱

   （3）共享信箱

   在利用信箱通信时，在发送进程和接收进程之间，存在以下四种关系：

   （1）一对一关系。

   （2）多对一关系，客户 / 服务器交互。

   （3）一对多关系， 广播方式。

   （4）多对多关系。

10. 处理机调度的基本概念和种类（期中考）

    1. 高级调度

       ▪调度对象：作业

       ▪又称作业调度、长程调度、接纳调度

       ▪实现：作业管理程序

       ▪将外存作业调入内存，创建 PCB 等，插入就绪队列。

       ▪用于批处理系统，分 / 实时系统一般直接入内存，无此环节。

       ▪频度：最低，分钟级

    2. 低级调度

       ▪又称进程调度或短程调度

       ▪对象：就绪进程（或内核线程）

       ▪功能：决定就绪队列中的那个进程应获得处理机，并将处理机分配给选中的进程。

       ▪实现者 ：分派程序（dispatcher)

       ▪应用范围：都有

       ▪频度：最频繁，毫秒级

    3. 中级调度

       ▪又称内存调度、中程调度

       ▪对象：挂起的进程

       ▪功能：把外存上那些已经具备运行条件的就绪进程重新载入内存。从静止就绪到活动就绪。

       ▪实现：内存管理中的对换进程

       ▪应用范围：具有对换功能的操作系统

       ▪频度：中等

11. 选择调度算法的准则，周转时间，带权周转时间，响应时间

    1. 周转时间：接纳等待时间、执行等待时间、执行时间、I/O 时间。
    2. 带权周转时间：作业的周转时间 T 与系统为它提供服务的时间 Ts 之比。 W = T/Ts
    3. 响应时间：等待时间与要求服务时间之和

12. 算法：（抢占 / 非抢占、调度时机）

    • 先来先服务 FCFS

      既可用于 作业调度 ，也可用于 进程调度

      作业调度时，优先选择后备作业中最先进入队列的作业

      进程调度时，每次调度从就绪队列中选择一个最先进入该队列的进程。

      有利于长作业（长进程 ），而不利于短作业（短进程 ）

      缺陷：对待短作业（进程）不公平，如果他们排在队列后面，则其等待时间远大于其执行时间。

    • 短作业 (进程) 优先 SJF/SPF

      短作业 / 进程优先调度算法 SJ§F 是指对短作业或短进程优先调度的算法 。 它们可以分别用于作业调度和进程调度 。

      短作业优先的调度算法 是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行 。

      短进程优先调度算法 则是从就绪队列中选出一估计运行时间最短的进程，处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度 。

      缺点：

      • 该算法对长作业不利，如作业 C 的周转时间由 10 增至 16 其带权周转时间由 2 增至 3.1 。甚至长作业长期得不到执行
      • 不能保证紧迫性作业 进程 会被及时处理。
      • 由于作业 进程 的长短只是根据用户所提供的估计执行时间而定的，而用户不一定对执行时间估计那么准确，致使该算法不一定能真正做到短作业优先调度。

    • 时间片轮转 RR

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

      • 当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的未尾：然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片

      • 这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。即系统能在给定的时间内，响应所有用户的请求

      • 时间片的设置

        • 进程切换将会增加系统的额外开销。

          时间片设定得太短，进程切换会非常频繁，从而降低处理机的效率；时间片设定得太长，将无法满足交互式用户对响应时间的要求。

          因此，时间片大小的确定应综合考虑系统的最大用户数、响应时间、系统效率等多种因素。

    • 基于优先权 PSA

      • 外部赋予作业（进程）相应的优先级，例如以作业的紧迫程度作为优先级。
      • 选择优先级高 的作业（进程）投入 运行。
      • 即可用于作业调度算法，也可用于进程调度。

    • 高响应比优先 HRRN

      • 既考虑作业的等待时间，又考虑作业的运行时间

      • 赋予作业动态优先级，优先级随作业等待时间延长而增加，从而使长作业的优先级在等待期间不断增加

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

      等待时间 + 要求服务时间 = 响应时间

      故优先级相当于响应比 R_p

      • 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。

      • 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。

      • 对于长作业，作业的优先级可以随等待时间的增加而提高，从而也可获得处理机。

      简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序 ，避免长作业长期得不到服务。

    • 多级反馈队列 MLFQ/FB

      • 多级反馈队列调度算法设置多个就绪队列，并为每个队列赋予不同的优先级。
      • 第一个队列的优先级最高，其余队列的优先级逐个降低。不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中其时间片就愈小。
      • 接着每个队列都采用 FCFS 算法，当新进程进入内存后先将它放入第一等待队列的末尾进行调度。如果该进程能在该时间片内完成便可撤离，否则调度程序将其转入第二队列的末尾等待调度。当进程最后被降到第 n 队列后，在第 n 队列中按 RR 调度算法运行。
      • 如果 A 的优先级 > B 的优先级，运行 A；
      • 如果 A 的优先级 = B 的优先级，轮转运行 A 和 B；
      • 工作进入系统时，放在最上层队列。
      • 一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次），就移入低一级队列；
      • 经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。

    • 实时调度（了解）

      • 基本条件

        • 提供必要的信息

        • 系统处理能力强

        • 采用抢占式调度机制

        • 具有快速切换机制

      • 实时调度算法

        • 非抢占式调度算法

          ​ 调度程序每次选择队列中的第一个任务投入运行。该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行，而调度程序再 选择下一个 (队首) 任务运行。

          非抢占优先权调度算法

          ​ 如果在实时系统中存在着要求较为严格 (响应时间为数百毫秒) 的任务，则可采用非抢占式优先调度算法为这些任务赋予较高的优先级。 当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。

          抢占式调度算法

          基于时钟中断的抢占式优先权调度算法

          立即抢占的优先权调度算法

          最早截止时间优先级 EDF（Earliest Deadline First）算法

          优先级确定：根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。

          实时任务就绪队列：按各任务截止时间的早晚排序；具有最早截止时间的任务排在队列的最前面。

          调度顺序：总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。

          适用范围：既可用于抢占式调度，也可用于非抢占式调度方式中。

        • 最低松弛度优先即 LLF (Least Laxity First) 算法

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

          该算法按松弛度排序实时任务的就绪队列，松弛度值最小的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。

          该算法主要用于可抢占调度方式中。

13. 常见的两种实时调度算法

    最早截止时间优先算法 (EDF)，最低松弛度优先算法（LLF）

14. 死锁概念，处理死锁的基本方法、死锁产生的原因，四个必要条件

    1. 如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。

    2. 产生死锁的原因可归结为如下两点：
       （1）竞争资源：可重用资源的竞争，可消耗资源的竞争，不可抢占资源的竞争
       （2）进程间推进顺序非法

    3. 四个必要条件：

       （1）互斥条件
       （2）请求和保持条件
       （3）不剥夺条件
       （4）环路等待条件

15. 死锁的预防

    1. 破坏请求与保持：系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。从而进程在整个运行期间，便不会再提出资源要求，从而摒弃了请求和保持条件，由此可以避免发生死锁。
       ▪优点：简单、易于实现且很安全。
       ▪缺点：资源被严重浪费，使进程延迟运行。
    2. 破坏不剥夺：当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源。待以后需要时再重新申请。从而摒弃了 “不剥夺” 条件。
       ▪缺点：实现起来比较复杂且要付出很大代价
    3. 破坏环路等待：系统将所有资源按类型进行线性排队，并赋予不同的序号。 所有进程对资源的请求必须严格按照资源序号递增的次序提出

16. 死锁的检测与解除

    死锁的检测 —— 资源分配图，死锁定理

    1. 死锁定理：如果资源分配图中不存在环路，则系统中不存在死锁；反之，如果资源分配图中存在环路，则系统中可能存在死锁，也可能不存在死锁。
    2. 若能消去资源分配图中所有结点的连接边，使全部结点都成为孤立结点，则称该图是可完全简化图；若不能使该图完全简化，则称该图是不可完全化简图。可以证明：当且仅当系统某状态 S 所对应的资源分配图是不可完全化简的，则 S 是死锁状态。该充分条件称为死锁定理

    死锁的解除 —— 当发现有进程死锁时，常采用的两种方法是解除死锁：
    （1）剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。
    （2）撤消进程。最简单的撤消进程的方法，是使全部死锁进程都夭折掉；或者按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。

# 存储器管理

1. 存储器管理的基本任务

   1. 主存储器的分配和管理

      ：按用户要求把适当的存储空间分配给相应的作业。一个有效的存储分配机制，应在用户请求时能作出快速的响应，分配相应的存储空间；在用户不再使用它时，应立即回收，以供其他用户使用。为此，这个存储分配机制应具有如下功能：

      • 记住每个存储区域的状态：哪些是已分配的，哪些是可以用作分配的。
      • 实施分配：在系统程序或用户提出申请时，按所需的量给予分配；修改相应的分配记录表。
      • 接受系统或用户释放的存储区域：并相应地修改分配记录表。

   2. 提高主存储器的利用率：使多道程序能动态地共享主存，最好能共享主存中的信息。

   3. “扩充” 主存容量：这是借助于提供虚拟存储器或其它自动覆盖技术来达到的。即为用户提供比主存的存储空间还大的地址空间。

   4. 存储保护：确保各道用户作业都在所分配的存储区内操作，互不干扰。即要防止一道作业由于发生错误而损害其它作业，特别需要防止破坏其中的系统程序。这个问题不能用特权指令来加以解决，而必须由硬件提供保护功能，并由软件配合实现。

2. 重定位的基本概念，为什么引入，动态重定位的概念、实现方式，什么情况下需要重定位

   装入内存时，相对地址（数据、指令地址）要作出相应的修改以得到正确的物理地址，这个修改的过程称为重定位。

   源程序经过编译产生的目标模块一般总是从 0 开始编址的，其中的地址都是相对于起始地址的相对地址。在将目标模块经过链接装入内存时，其分配到的内存空间的起始地址通常不为 0，因此指令和数据的实际物理地址和装入模块内的相对地址是不同的，为了使程序能够正确执行，必须将相对地址转换成物理地址，即进行重定位。

   静态重定位：地址变换是在装入内存时一次完成的，且以后不能移动。

   动态重定位：装入程序将装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序执行时进行。在硬件地址变换机构的支持下，随着对每条指令或数据的访问自动进行地址变换，故称为动态重定位。

   在内存分配过程中，不免出现许多不可利用的小的空闲空间以至于造成了内存的利用率不高。如果让已经存在的程序紧凑起来，那么，那些不可利用的小的空闲空间也就连成了更大的空闲空间以供利用，移动已经在内存中的程序就是动态重定位。

   实现方式：要在不影响指令执行速度的同时实现地址变换，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。

3. 比较连续分配和离散分配，连续分配的三种方式

   （1）连续分配是指为一个用户程序分配一个连续的地址空间，包括单一连续分配方式，分区式分配方式（固定分区和动态分区），动态重定位分区（引入了紧凑）三种分配方式。单一方式将内存分为系统区和用户区，最简单，只用于单用户单任务操作系统；分区方式分固定和动态分区。
   （2）离散分配方式分为分页、分段和段页式存储管理。分页式存储管理旨在提高内存利用率，分段式存储管理旨在满足用户（程序员）的需要，段页式存储管理则将两者结合起来，具有分段系统便于实现、可共享、易于保护和动态链接等优点，又能像分页系统很好解决外部碎片及为各段可离散分配内存等问题，是比较有效的存储管理方式。

   连续分配方式不需要额外的硬件支持，且实现算法相对简单。但是在很多情况下会造成内存利用率低，系统吞吐量小和 CPU 利用率低等情况，虽然可以通过紧凑等方式有所调节，但是紧凑也会造成很大的系统开销。

   离散分配方式需要额外的硬件支持，且实现的算法相对比较复杂，但是出于用户或操作系统的角度，离散分配方式在系统性能上或实现功能上明显比连续分配更灵活。比如信息的保护和共享等等方面，离散比连续更加容易实现。

4. 动态分区分配方式：分配、回收算法

   首次适应算法，最佳适应算法，最差适应算法，下次适应算法

5. 动态可重定位分区分配

   动态重定位：改变程序驻留位置后的地址重定位问题解决方法

   紧凑：将内存中的所有作业进行移动，使它们全都相邻接，这样，可把原来分散的多个小分区合成一个大分区。这种技术称为存储器的 “紧凑”。（减少由于外零头造成的浪费）

   在动态运行时转入的方式中，作业装入内存后的所有地址仍然都是相对逻辑地址。而将相对地址转换为绝对（物理）地址的工作被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。
   地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位。当系统对内存进行了 “紧凑”，而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址去置换原来的起始地址即可。

6. 基本分页存储管理方式：为什么引入；地址变换机构和过程（含具有快表的情况）

   分页的优点：彻底消除了外零头，仅存在很少的内零头，提高了内存利用率。

7. 基本分段存储管理方式：为什么引入；地址变换机构和过程（含具有快表的情况）；信息的共享和保护

   分段引入原因：方便编程，信息共享，信息保护，动态增长，非常适合动态链接

   分段易于实现段的共享和段的保护。

8. 虚拟存储器的基本概念：为什么要引入；特征；实现虚拟存储的关键技术

   1. 虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
   2. 虚拟存储器的特征：
      • 多次性：是指一个作业被分成多次调入内存运行。
      • 对换性：是指作业的运行过程中进行换进、换出。换进和换出能有效地提高内存利用率。
      • 虚拟性：是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
   3. 虚拟存储器的实现方法：
      • 分页请求系统：在纯分页系统的基础上增加了请求调页、页面置换两大功能所形成的页式虚拟存储系统。
        • 为了实现请求调页、页面置换两大功能，系统必须提供如下的硬件支持：1. 请求分页的页表机制。2. 缺页中断机构。3. 地址变换机构。
        • 此外，实现请求调页、页面置换两大功能还需得到 OS 的支持。①实现请求调页的软件②实现页面置换的软件
      • 请求分段系统：它是在纯分段系统的基础上增加了请求调段、分段置换两大功能所形成的段式虚拟存储系统。
        • 为了实现请求调段、分段置换两大功能，系统必须提供如下的硬件支持：1. 请求分段的段表机制。2. 缺段中断机构。3. 地址变换机构。
        • 此外，实现请求调段、分段置换两大功能还需得到 OS 的支持。

9. 请求分页系统的基本原理：页表机制；地址变换过程；页面置换算法

   1. 工作原理：作业运行时，只将当前的一部分装入内存其余的放在辅存，一旦发现访问的页不在主存中，则发出缺页中断，由 OS 将其从辅存调入主存，如果内存无空块，则根据某种算法选择一个页淘汰以便装入新的页面。

   2. 请求页表机构：

      页号	页框号（物理块号）	状态位 P	访问字段 A	修改位 M	外存地址

      • 状态位 (存在位) P：用于说明该页是否已调入内存，供程序访问时参考；D=0，该页不在内存。 D=1，该页在内存
      • 访问位 A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。A=0，该页未被访问。A=1，该页被访问
      • 修改位 M：用于表示该页在调入内存后是否被修改过，也是提供给置换算法在换出页面时是否将该页面写回外存作参考。M=0，该页在内存中未被修改。M=1，该页在内存中已经被修改
      • 外存地址：用于指出该页在外存上的地址，供调入该页时使用。

   3. 地址变换过程。

   4. 5 种页面置换算法

10. 访问内存的有效时间

    1. 假设使用了快表，则 CPU 访问内存时有以下三种情况：设内存读写周期为 t，查找快表时间为 λ，缺页中断处理时间为ɛ
    2. 页面在内存且页表项在快表中：只需一次访问内存 ：EAT= λ + t
    3. 页面在内存但页表项不在快表中：需两次访问内存，一次读取页表，一次读取数据，另外还需更新快表：EAT= λ + t + t + λ=2 (λ + t)
    4. 页面不在内存：考虑查找快表时间、查找页表时间、缺页中断处理时间、更新快表时间、访问实际物理地址时间：EAT= λ + t +ɛ + λ + t = ɛ + 2 (λ + t)
    5. 引入快表命中率为 α，缺页中断率为 f，则有效访问内存时间为：EAT= λ + α t + (1- α)[t + f (t +ɛ +λ) + (1-f)(t +λ)]

# 设备管理

1. I/O 控制方式：四种 I/O 方式的基本原理；四种 I/O 方式由低效到高效的演变

   1. 使用轮询的可编程 I/O 方式：程序 I/O（Programmed I/O）方式，或称为忙 —— 等待方式。

      处理机向控制器发出一条 I/O 指令启动输入设备输入数据时，同时把 busy 置为 1，再不断循环测试 busy。busy=0，完成输入，处理机读取数据，送入指定单元，完成一次 I/O。对状态寄存器中的忙 / 闲标志 busy 的检查实现控制。

   2. 使用中断的可编程 I/O 方式：当某进程要启动某个 I/O 设备工作时，便由 CPU 向相应的设备控制器发出一条 I/O 命令，然后立即返回继续执行原来的任务。设备控制器于是按照该命令的要求去控制指定 I/O 设备。此时，CPU 与 I/O 设备并行操作。

   3. DMA 控制方式的特点：①数据传输的基本单位是数据块，即在 CPU 与 I/O 设备之间，每次传送至少一个数据块；②所传送的数据是从设备直接送入内存的，或者相反；③仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预，整块数据的传送是在控制器的控制下完成的。

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

2. 缓冲管理：缓冲的概念，为什么引入缓冲

   缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。

   引入缓冲区的目的：为了缓和 CPU 与 I/O 设备速度不匹配的矛盾；提高 CPU 和 I／O 设备的并行性； 减少对 CPU 的中断频率， 放宽对 CPU 中断响应时间的限制；解决数据粒度不匹配问题

3. 单缓冲如何提高 I/O 速度，它存在哪些不足，双缓冲、循环缓冲又如何提高 CPU 与 I/O 设备的并行性

   单缓冲：在设备和处理机之间设置一个缓冲。设备与处理机交换数据时，先把交换的数据写入缓冲区，然后需要数据的设备 / 处理机再从缓冲区中取走数据。

   ​ 通过允许 CPU 和 I/O 设备异步操作，单缓冲减少了因速度不匹配导致的等待时间，提高了整体的吞吐量。

   双缓冲：在设备输入时，先将数据送入第一缓冲区，装满后便转向第二缓冲区。此时操作系统可以从第一缓冲区中移出数据，并送入用户进程

   环形缓冲区方式 （1）多个缓冲区。 每个缓冲区的大小相同。 （2）缓冲区可分成三种类型：① 空缓冲区 Empty，用 E 表示，用于存放输入数据；② 已装满数据的缓冲区 Full，用 F 表示，其中的数据提供给计算进程使用；③ 现行工作缓冲区 Current，用 C 表示，这是计算进程正在使用的缓冲区。

   单缓冲
   工作原理：
   单缓冲技术涉及在CPU和I/O设备之间设立一个缓冲区。当I/O设备准备数据时，它会将数据写入缓冲区，随后CPU可以在不等待I/O操作完成的情况下继续执行其他任务。一旦数据准备好，CPU可以方便地从缓冲区读取数据，而I/O设备则可以开始下一次的数据传输，从而减少了直接CPU等待的时间。
   
   提高I/O速度：
   通过允许CPU和I/O设备异步操作，单缓冲减少了因速度不匹配导致的等待时间，提高了整体的吞吐量。
   
   不足：
   
   瓶颈问题：如果缓冲区的容量小或CPU处理数据的速度远快于数据填充缓冲区的速度，CPU仍需等待缓冲区填满或清空，这成为系统的瓶颈。
   数据粒度不匹配：单缓冲可能无法有效应对数据传输速率的大幅波动，尤其是当I/O设备传输数据的速率与CPU处理速率差异很大时。
   双缓冲
   工作原理：
   双缓冲使用两个缓冲区交替工作。当一个缓冲区正在被CPU处理时，另一个缓冲区可以由I/O设备填充数据。这样，CPU总能在一个缓冲区处理完后立即切换到另一个已填满的缓冲区，实现了连续的数据流处理。
   
   提高并行性：
   双缓冲显著提高了CPU与I/O设备的并行工作能力，因为CPU总有一个缓冲区可处理，同时I/O设备也在填充另一个缓冲区，减少了空闲等待时间。
   
   不足：
   
   额外资源消耗：相比单缓冲，双缓冲需要额外的内存空间。
   特定情况下的效率问题：如果CPU处理速度极快，且I/O操作频繁但每次数据量不大，可能会出现短暂的等待，尽管这种情况相对较少。
   循环缓冲（也称为环形缓冲）
   工作原理：
   循环缓冲是一个固定大小的缓冲区，被视为首尾相连的环。数据既可以顺序写入，也可以顺序读出，当达到缓冲区的末端时，会自动回到开头继续。这种设计使得缓冲区可以连续重复使用，适合连续的数据流处理。
   
   提高并行性：
   循环缓冲特别适用于连续的数据流处理，如音频或视频流，因为它可以连续不断地读写，无需等待缓冲区完全填满或清空，从而提高了数据处理的平滑性和并行性。
   
   不足：
   
   复杂性增加：管理和同步循环缓冲的读写指针比单缓冲或双缓冲更复杂。
   潜在的溢出问题：如果没有适当的流量控制，生产者（写入方）过快或消费者（读取方）过慢可能导致数据溢出。
   

4. 缓冲池是为了解决什么问题而引入，引入缓冲池后系统将如何处理 I/O 设备和 CPU 间的数据输送

   上述三种缓冲区的组织形式仅适用于某种特定的 I/O 进程和计算进程，属于专用缓冲。当系统中的设备很多时，将会有许多这样的循环缓冲区，消耗大量的内存空间，而且其利用率也不高。为了提高缓冲区的利用率，可以采用公共缓冲池技术，其中的缓冲区可为多个设备和进程服务。

   缓冲池是为了解决以下几个关键问题而引入的：

   1. CPU 与 I/O 设备速度不匹配：缓冲池通过在内存中预留一部分区域作为缓冲区集合，帮助协调 CPU 高速处理能力和 I/O 设备较慢的传输速率之间的差异。这样，即使 I/O 设备速度较慢，CPU 也可以继续执行其他任务，而不是等待数据传输完成。
   2. 减少中断频率：没有缓冲池时，每次 I/O 操作完成或需要数据时都会触发中断，CPU 需要频繁响应这些中断，降低了效率。缓冲池可以累积一定量的数据后再通知 CPU，从而减少中断次数。
   3. 提高并行性：通过允许 CPU 与多个 I/O 操作并行进行，缓冲池提升了系统的并发处理能力。例如，当一个缓冲区正在被 CPU 处理时，其他缓冲区可以用于新的 I/O 操作，保持数据流动。
   4. 资源复用和管理：缓冲池将多个缓冲区统一管理起来，可以根据需要动态分配给不同的 I/O 操作，提高了内存资源的利用率。

   引入缓冲池后，系统处理 I/O 设备和 CPU 间的数据输送的方式如下：

   • 数据输入：当数据从 I/O 设备传入时，系统首先将数据写入缓冲池中的一个空闲缓冲区。如果 CPU 需要这些数据，它可以快速地从缓冲池中读取，而不需要直接等待 I/O 设备。数据完全写入缓冲区后，I/O 设备可以继续其操作，同时 CPU 收到通知（如通过中断）来处理缓冲区中的数据。
   • 数据输出：当 CPU 需要将数据发送到 I/O 设备时，数据先被写入缓冲池。一旦缓冲区填满或达到特定条件，系统会调度数据从缓冲区传输到 I/O 设备，同时 CPU 可以继续执行其他任务。这减少了 CPU 等待 I/O 设备完成传输的时间。
   • 缓冲区管理：系统需要维护一个机制来跟踪缓冲区的状态（空闲、正在填充、正在提取数据等），以及高效地分配和回收缓冲区。缓冲池通常采用队列或其他数据结构来组织和管理这些缓冲区。

5. 缓冲池的工作方式及 Getbuf 和 Putbuf 过程

   缓冲池的四种工作方式：

   1. 收容输入
   2. 提取输入
   3. 收容输出
   4. 提取输出

   缓冲池（Buffer Pool）是一种内存区域，主要用于存储从慢速存储设备（如磁盘）读取的数据或等待写回慢速存储设备的数据。其目的是利用内存的高速访问特性，减少对慢速存储的直接访问，提高系统性能。以下是缓冲池的一般工作方式及 Getbuf 和 Putbuf 过程的概述：

   # 缓冲池的工作方式：

   1. 数据读取：
      • 当系统需要读取数据时，首先检查所需数据是否已经在缓冲池中。如果是，则直接从缓冲池读取，这称为 “缓存命中”。
      • 如果数据不在缓冲池中（缓存未命中），系统会从磁盘读取数据到缓冲池的一个空闲缓冲区中，并记录此缓冲区的状态。之后，CPU 可以直接从缓冲池中获取数据。
      • 在缓冲池空间有限的情况下，可能需要根据某种替换策略（如 LRU，Least Recently Used）选择一个缓冲区，将其内容写回磁盘以腾出空间给新数据。
   2. 数据写入：
      • 写操作通常也是先写入缓冲池，而不是直接写入磁盘。这称为 “延迟写” 策略。
      • 数据在缓冲池中被标记为 “脏” 的，表示它已被修改且尚未持久化到磁盘。
      • 当缓冲区被标记为脏或者按照一定策略（如定时、缓冲区满）需要刷新时，数据会被写回磁盘。

   # Getbuf 和 Putbuf 过程：

   这两个过程常用于描述多进程环境下对缓冲池中缓冲区的分配和回收操作，以确保资源的安全共享和避免冲突。这些过程通常涉及信号量机制以实现互斥和同步。

   • Getbuf 过程： 当进程需要从缓冲池中获取一个缓冲区来读取或写入数据时，执行 Getbuf 过程：
     1. 检查资源：进程首先尝试减少资源信号量 RS (type)，以确认是否有可用的缓冲区。
     2. 互斥访问：如果资源可用，减少互斥信号量 MS (type) 以获得对缓冲池的独占访问权。
     3. 分配缓冲区：从缓冲池中选择一个合适的缓冲区并标记其状态。
     4. 释放互斥：完成后，增加 MS (type) 信号量，允许其他进程访问缓冲池。
   • Putbuf 过程： 当进程完成对缓冲区的使用后，执行 Putbuf 过程归还缓冲区：
     1. 更新状态：将缓冲区状态更新为可用或脏（如果数据被修改）。
     2. 释放资源：增加资源信号量 RS (type)，表明有一个缓冲区已经可用给其他进程使用。

6. 设备独立性：什么是设备独立性，如何实现设备独立性，设备驱动程序（了解）

   1. 设备独立性的概念：设备独立性的概念为了提高 OS 的可适应性和可扩展性，在现代 OS 中都毫无例外地实现了设备独立性 (Device Independence)，也称为设备无关性。其基本含义是: 应用程序独立于具体使用的物理设备。
   2. 设备独立性软件的主要功能可分为以下两个方面：(1) 执行所有设备的公有操作。(2) 向用户层 (或文件层) 软件提供统一接口

7. 虚拟设备：什么是虚拟设备，实现虚拟设备的关键技术（了解）

   （1）设备的固有属性

   ​ 独占性。独占设备是不能同时共用的设备，即在一段时间内，该设备只允许一个进程独占。临界资源

   ​ 共享性。允许多个进程同时共享

   ​ 可虚拟性。虚拟设备是利用某种技术把独占设备改造成可由多个进程共享的设备

   （2）设备分配算法

   ​ 先来先服务

   ​ 优先级高者优先

8. 设备驱动程序与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动 I/O 设备工作的驱动程序。

9. SPOOLing 技术，SPOOLing 技术的组成，如何利用 SPOOLing 技术实现共享打印机（了解）

   在主机的直接控制下，实现脱机输入、输出功能。此时的外围操作与 CPU 对数据的处理同时进行，我们把这种在联机情况下实现的同时外围操作称为 SPOOLing（Simultaneaus Periphernal Operating On Line），或称为假脱机操作。

   其工作原理为：①在磁盘中开辟若干区域，形成 “共享设备”，当某作业或进程请求分配独占设备时，系统就分配给它共享设备中的某一部分，使其与独占设备相关联。②在用户申请独占设备时，用户实际得到的是磁盘上的一块区域。③采用 “预输入” 和 “缓输出” 策略，以提高低速、独占设备的利用率。

10. 磁盘调度的目标，磁盘访问时间的计算，FCFS、SSTF、SCAN、CSCAN 等算法的应用；各算法的性能比较

# 文件管理

1. 文件的逻辑结构：顺序文件、索引文件和索引顺序文件，原理和特征，组织方式、访问方法及各种文件形式的比较

   1. 顺序文件，指由一系列记录按某种顺序排列所形成的文件，其中的记录可以是定长记录或可变长记录。批量存取时效率高；但是单个记录查改性能差，长度限制，增加或删除困难
   2. 索引文件，指为可变长记录文件建立一张索引表，为每个记录设置一个表项，以加速对记录的检索速度。对单个文件的查找、插入和删除速度快，但索引增加了存储开销。
   3. 索引顺序文件，这是顺序文件和索引文件相结合的产物，这里，在为每个文件建立一张索引表时，并不是为每一个记录建立一个索引表项，而是为一组记录中的第一个记录建立一个索引表项。

2. (文件的物理结构) 外存分配方式：连续分配、链接分配和索引分配原理、优缺点（显示链接 FAT、增量式索引分配）

   1. 连续分配要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。把逻辑文件中的数据顺序地存储到物理上邻接的各个数据块中，这样形成的物理文件可以进行顺序存取。文件目录中为每个文件建立一个表项，其中记载文件的第一个数据块地址及文件长度。对于顺序文件，连续读 / 写多个数据块内容时，性能较好。

      • 连续分配的主要优点：（1）顺序访问容易。 能很快检索文件中的一个数据块。(2) 顺序访问速度快。磁头移动距离短，效率最高
      • 缺点：（1）要求有连续的存储空间。 该分配方案可能会导致磁盘碎片，严重降低外存空间的利用率。(2) 必须事先知道文件的长度。空间利用率不高；(3) 不能灵活的删除和插入数据 (4) 不利于文件尺寸的动态增长。

   2. 链接文件：采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。

      优点：消除了磁盘的外部碎片，提高了外存的利用率；对插入、删除和修改记录都非常容易；能适应文件的动态增长

      • 隐式链接：在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。每个盘块中都含有一个指向下一个盘块的指针。隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效的。
      • 显式链接：这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。整个磁盘仅设置一张文件分配表（FAT）。
        • 在该表中，凡是属于某一文件的第一个盘块号，均作为文件地址被填入相应文件的 FCB 的 “物理地址” 字段中。
        • 查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。
        • 由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表 FAT (File Allocation Table)。

   3. 索引分配

      1、利用专门的索引块存储索引信息
      2、一个数据块容纳不了一个文件的所有分区时，
      需要若干个索引结点进行存储，建立二级
      索引或多级索引。

   4. 单级索引分配：索引分配能解决连续分配和链接分配存在的诸多问题。原理：为每个文件分配一个索引块 (表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。

      • 优点：索引分配方式支持直接访问。基于数据块的分区能消除外部碎片
      • 缺点：索引块可能要花费较多的外存空间。每当建立一个文件时，便须为之分配一个专门的索引块，将分配给该文件的所有盘块号记录于其中。对于小文件如果采用这种方式，索引块的利用率将是极低的。大文件索引项较多，可能使一个数据块容纳不了一个文件的所有分区的索引。

   5. 多级索引分配，增量式索引分配

   6. 混合索引方式

3. 目录管理：目录管理的要求，文件控制块（FCB）索引结点，目录结构：单级、两级和多级

   目录管理的要求：

   • 实现 “按名存取”
   • 提高对目录的检索速度
   • 文件共享
   • 允许文件重名

   文件控制块（FCB）：用于描述和控制文件的数据结构

   文件目录：文件控制块的有序集合。

   索引节点：把文件名和文件描述信息分开，使文件描述信息单独形成一个成为索引节点的数据结构

   目前广泛采用的目录结构是树形目录结构，具体形式多样，但大多基于以下几种模型或其变体：

   • 单级目录结构：早期系统中使用，所有文件都在同一层次下，但现代系统已很少采用，因为它不满足易用性和可扩展性的需求。
   • 两级目录结构：将文件系统分为用户文件目录和系统文件目录，尽管有所改进，但仍然不能很好地支持大规模文件组织。
   • 树形目录结构（多级目录）：这是当前操作系统普遍采用的目录结构。每个目录可以包含文件和子目录，形成一个倒置的树状结构。根目录位于顶部，其他目录和文件作为分支和叶子节点。这种结构支持无限层级的嵌套，易于组织和查找文件，同时也便于实现权限控制和资源共享。

   树形目录结构的优点包括：

   • 灵活的文件组织：用户可以根据需要创建多级目录，便于分类和管理文件。
   • 高效的搜索和访问：通过路径名可以直接定位文件，且现代系统常采用缓存等技术加速目录查找。
   • 权限控制：可以为不同目录设置不同的访问权限，增强系统的安全性和隐私保护。
   • 易于维护和扩展：随着文件数量的增长，可以通过增加目录层级来管理，不会导致系统性能的线性下降。
   • 兼容性和标准化：大多数操作系统（如 Windows, Linux, macOS）都采用了类似的树形目录结构，便于跨平台操作和数据交换。

   在 Linux 中：

   UNIX 文件管理 (重点)
   Linux 中用 EXT2 文件系统结构
   在 EXT2 文件系统中，查找文件的过程:

   • 当访问一个文件时，通过文件名在 “目录表” 中查到其 “索引节点号 "
   • 通过 “索引节点号 "查" 索引节点表”。
   • 通过 “索引节点表” 得到其 “索引节点”。
   • 通过索引节点得到文件数据所在位置

   需要学会如何根据 Inode 信息，计算系统支持的最大文件大小

   • 6 种文件类型：普通文件、目录文件、特殊文件、命名管道、链接文件、符号链接

   • 文件分配单位：块

   • 分配方式：动态按需分配

   • 文件组成
     Linux 文件系统的一个文件由目录项、inode 和数据块组成

   • 目录项：包括文件名和 inode 节点号

   • Inode: 又称文件索引节点，是文件基本信息的存放地和数据块指针存放地

   • 数据块：文件的具体内容存放地

   Inode： 索引节点，包含操作系统所需的某个文件的关键信息，UNIX 系统中的文件分配表

   1. 目录文件内容：一系列目录项（dirent）的列表，每个目录项由两部分组成：所包含文件的文件名；文件名对应的索引节点（inode）号

   2. 文件在内核中的表现形式：文件描述符表，文件表，索引节点

   单级目录结构：所有用户的全部文件目录保存在一张目录表中，每个文件的目录项占用一个表项。

   • 单级目录的优点是简单且能实现目录管理的基本功能 —— 按名存取
   • 存在下述一些缺点： (1) 查找速度慢 (2) 不允许重名 (3) 不便于实现文件共享

   两级目录结构：主文件目录 MFD、用户文件目录 UFD

   • 提高了检索目录的速度

     ・由 n*m 提高到 n+m

      在不同的 UFD 中，可以使用相同的文件名
                     
     不同用户可以使用不同的文件名访问系统中的同一个共享文件
                     
      用户间的隔离使文件共享不方便
                     
     - 要让不同用户使用不同的文件名访问系统中的同一个共享文件，可以通过在MFD中设置一个特殊条目来指向共享文件的实际位置，然后在需要访问该共享文件的用户的UFD中创建一个链接或别名（可能是硬链接或符号链接的形式），这个链接指向MFD中共享文件的条目。这样，每个用户看到的是自己UFD中的文件名，但实际上指向的是同一个物理文件。
     

     • 用户间的隔离使文件共享不方便：虽然实现了基本的共享，但权限管理和访问控制较为简陋，难以精细化控制不同用户对共享文件的访问权限。
       • 文件如何共享？：改进方法包括引入权限系统，允许系统管理员或文件所有者设定共享文件的访问权限（读、写、执行等），并在 UFD 中通过链接明确标识出哪些文件是共享的，并附带相应的访问控制信息。随着技术发展，现代文件系统（如 NTFS、Ext4 等）采用了多级目录结构、访问控制列表（ACL）、用户组等高级功能，极大地丰富了文件共享和权限管理的能力。

   多级目录结构：

     （1）目录结构：多级目录结构又称为树型目录结构，主目录在这里被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点。
           
     （2）路径名：从树的根（即主目录）开始，把全部目录文件名与数据文件名，依次地用“/”连接起来，即构成该数据文件的路径名（path name）。系统中的每一个文件都有惟一的路径名。
           
     （3）当前目录：为每个进程设置一个“当前目录”，又称为“工作目录”进程对各文件的访问都相对于“当前目录”而进行。
   

4. 文件磁盘空间管理：空闲表法和空闲链法，位示图法：分配和回收的具体计算

   1. 空闲分区表：空闲表法属于连续分配方式，它为每个文件分配一块连续的存储空间，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。适合于可变大小分区的连续分配方式。

   2. 空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：空闲盘块链、空闲盘区链

      • 空闲盘块链：将磁盘上的所有空闲空间，以盘块为单位拉成一条链。当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。
      • 空闲盘区链：将磁盘上的所有空闲盘区 (每个盘区可包含若干个盘块) 拉成一条链。在每个盘区上含有用于指示下一个空闲盘区的指针和能指明本盘区大小 (盘块数) 的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。

   3. 位示图：利用二进制位 0、1 表示存储空间中存储块的使用状态。空闲分区：0，已分配分区：1（或者相反）。磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。通常可用 m × n 个位数来构成位示图，并使 m × n 等于磁盘的总块数。

      ü 顺序扫描位示图，从中找出一个值为 “0” 的二进制位（空闲位）

      ü 将所找到的空闲位号转换成与之相应的空闲块号： 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　b=n*(i-1)+j

      b 为对应的空闲块的块号

      n 为位示图中每行的位数

      i、j 分别为空闲位在位示图的行号、列号

      修改位示图：令 map [i,j]＝1

      ③盘块的回收

      ü 将回收盘块的盘块号转换成位示图中的行

      号和列号

      ​ i=(b-1)/ n + 1

      j=(b-1)% n + 1

      ü 修改位示图：令 map [i,j]＝0

# Unix/Linux 入门

# 什么是 SHELL

• Shell 是系统的用户界面，提供了用户与内核进行交互操作的一种接口。它接收用户输入的命令并把它送入内核去执行。

• Shell 是一个命令解释器，它解释由用户输入的命令并且把它们送到内核。

• Shell 是一个解释型的程序设计语言。

# 简单命令

# 输入 / 输出重定向 ：grep

command > filename command >> filename

command < filename command << filename

# 管道 command1 | command2

◦例如：$ ps –e | grep student2

shell 环境变量 env

echo 命令的使用

系统变量: 系统变量只能引用不能修改！

单引号、双引号、反撇号和花括号

• 单引号禁止变量替换，元字符 $ 和 * 等保持其符号本身；而双引号允许元字符变量替换.
• 反撇号中的字符串作为命令名执行
• 花括号将变量名和后面的字符串区分开

#

shell 编程：功能性语句、结构性语句和说明性语句.

read, expr,test 等

#!/bin/sh
# Put  line  numbers  on  all  lines  of  a  file 
if [ $#  -ne  1 ]
then
       echo  "Usage: $0  filename "  >&2
       exit 1
fi
count=1                     # Initialize count
cat  $1  |  while  read  line   
# Input is coming from file on command line
do
    echo  $count  $line
    count=`expr $count + 1`
done  >  tmp$$           # Output is going to a temporary file
mv  tmp$$  $1

功能：给一个文本文件中的每一行前面加上行号。

注意：while 循环体的标准输入，被重定向为从管道中读。

while 循环体的标准输出，被重定向到了 tmp$$ 文件中，这里的 $$ 就是当前进程的进程号，因为进程号的唯一性，所以多个用户同时运行该程序时，不会相互覆盖！

当前进程的ID号 $# 命令行上的参数个数 ## **文件操作与权限管理** 目录文件内容：一系列目录项（dirent）的列表，每个目录项由两部分组成：所包含文件的文件名；文件名对应的索引节点（inode）号 Linux内核通过一个被称为进程描述符的task_struct结构体来管理进程，这个结构体包含了一个进程所需的所有信息。 文件的打开和关闭都是资源的一种操作，Linux中的task_struct中有两个结构体存储这两个信息。 Sruct fs_struct *fs：进程的可执行映象所在的文件系统，有两个索引点，称为root和pwd，分别指向对应的根目录和当前目录。 Struct files_struct *files：进程打开的文件, 指向files_struct结构体, 称为文件描述符表 已打开的文件在Linux内核中用file结构体表示,文件描述符表中的指针fd[ ]指向一个已打开文件的file结构体 在file结构体中比较重要的成员包括File Status Flag(f_flags)和当前读写位置(f_pos )还有f_count,表示引用计数(Reference Count), 每个file 结构体都指向一个file_operations 结构体,这个结构体的成员都是函数指针,指向实现各种文件操作的内核函数。  每个进程在PCB中有一个文件描述符表，每个描述符表项指向一个文件表 内核为每一个被该进程使用（打开）的文件维护一张文件表file 每个文件（或设备）都有一个索引节点，它包含了文件类型属性及文件数据