操作系统

操作系统基础

概述

什么是操作系统

​ 操作系统（Operating System， OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配；以提供给用户和其他软件方便的接口和环境；它是计算机系统中最基本的系统软件

操作系统提供的功能

• 处理机（CPU）管理
• 存储器管理
• 文件管理
• 设备管理

操作系统的目标

• 作为系统资源的管理者
• 向上提供方便易用的服务
  • 图形界面GUI
  • 命令接口
    • 联机命令接口：交互式，用户一句，系统一句，如cmd
    • 脱机命令接口：批处理，如bat
    • 程序接口：在代码中通过系统调用（广义接口）来使用

操作系统的特征

• 并发

  并发：同一时间交替运行多个程序

  并行：同一时间同时运行多个程序（多核CPU）

• 共享

  互斥共享：一个时间段内只允许一个进程访问该资源（临界资源）

  同时访问：同一时间段内多个进程”同时“访问

  并发和共享是操作系统两个最基本的特征

• 虚拟

  空分复用：内存分给多个进程使用，让用户觉得能使用的内存大于物理内存（虚拟内存）

  时分复用：处理机在各个微小的时间段内交替为各个进程服务

• 异步

  进程以不可预知的速度执行

  只有系统拥有并发性，才有可能导致异步

操作系统的发展和分类

• 手工操作阶段：用户独占，资源利用率底，（无操作系统）

• 批处理阶段

  • 单道批处理系统：

    将一批作业放入磁带执行，一次只能执行一道程序，监督系统负责作业的输入输出，CPU有大量时间在等待IO完成

    

  • 多道批处理系统：

    • 优点：

      在输入和输出程序的时候也能进行计算；

      当某道程序因为请求IO操作而暂停运行时，CPU变去运行另一道程序；

      多道、宏观并行、微观串行（轮流使用CPU）；

    • 缺点：

      响应时间较长，不提供人机交互；

    

• 分时操作系统

  以时间片为单位轮流为各个用户/作业服务，请求能被及时响应，主要用于交互式作业。但不能优先处理一些紧急任务

• 实时操作系统

  • 硬实时系统：必须在觉得严格的规定时间内完成
  • 软实时系统：能接收偶尔超时

• 个人计算操作系统、网络操作系统、分布式操作系统。。。

求CPU使用率的题用甘特图比较好求

操作系统运行环境

指令：

• 特权指令：不允许用户直接用的指令，如IO指令、关中断指令等
• 非特权指令：仅限于访问用户的地址空间

CPU的运行模式：

• 用户态（目态）：应用程序运行在用户态
• 内核态（管态）：操作系统内核运行在内核态
• 内核态 –> 用户态：执行特权指令，修改PSW（程序状态字寄存器）标志位
• 用户态 –> 内核态：中断，硬件自动完成切换

操作系统的内核组成：

• 与硬件关联较紧密的模块
  1. 时钟管理：给用户提供系统时间、分时操作系统的时钟中断来切换进程、实时操作系统的截止时间
  2. 中断处理：保护和回复中断现场的信息，转移控制权到相关处理程序
  3. 原语：原子性，最接近硬件的部分，调用频繁
  4. 管理：进程管理、存储器管理、设备管理
• 运行频率较高的模块

中断和异常

• 作用
  中断是让操作系统内核夺回CPU使用权的唯一手段，发生中断时会立即切换回核心态

• 中断的类型

  • 内中断（异常、例外）：
    中断信号来源于CPU内部

    1. 陷阱、陷入指令（trap指令、访管指令）：程序请求内核的服务时使用
    2. 故障：错误条件引发，如缺页故障、地址越界
    3. 终止：使得CPU无法继续执行的硬件故障

  • 外中断（中断）：
    中断信号来源于CPU外部，如时钟中断

    1. 可屏蔽中断：通过INTR线（Interrupt Request line）发出中断请求，可多重中断
    2. 不可屏蔽中断：通过INM线（Non-Maskable Interrupt line）发出请求，多为硬件故障
    • 时钟中断：表示一个固定的时间片已到
    • IO中断请求：表示输入输出处理已经完成

• 中断基本原理
  CPU根据中断的类型去查询中断向量表，找到对应中断处理程序的入口地址

  如果处理程序能够解决问题，则通过中断返回指令返回用户程序继续执行

  如果是不可恢复的致命错误，则终止用户程序

系统调用

• 作用

  应用程序通过系统调用来请求操作系统内核提供的服务，

  主要有设备管理、文件管理、进程管理、进程通信和内存管理，

  这些对系统影响非常大的指令必须由操作系统执行，以保证稳定性和安全性

• 何时会用到系统调用

  与共享资源有关的操作（存储分配、IO操作、文件管理等）

• 系统调用过程

  1. 先通过传参指令将参数传到寄存器中
  2. 再通过陷入指令转入中断处理程序、硬件自动保护中断现场（程序计数器PC、PSW、通用寄存器）
  3. 处理完后恢复现场、返回用户程序

内核结构

1. 宏内核（单内核、大内核）

   系统的主要功能模块都运行在核心态

2. 微内核

   只保留最基本的功能在内核，如与硬件处理紧密相关的部分

   1. 进程管理
   2. 低级存储器管理
   3. 中断和陷入处理

   特点：

   1. 足够小的内核
   2. 基于客户/服务器模式
   3. 应用“机制与策略分离”原理
   4. 采用面向对象

   优点：扩展灵活、可靠安全、可移植性、分布式计算

   缺点：微内核用户态和内核态的转换比宏内核频繁，性能偏低

3. 分成结构

   

   每层只能调用紧邻的下一层

   优点：便于维护、易扩展

   缺点：合理定义每层比较困难、不可跨层调用效率低

4. 模块化

   

   衡量标准：高内聚、低耦合

   优点：加速开发、可理解、可维护

   缺点：接口规定难以满足实际需求，模块间相互依赖，难以调试

5. 外核

   在内核中运行，为虚拟机分配未经抽象的硬件资源

   优点：减少了硬件资源的“映射层”，提升效率

   缺点：降低了系统的一致性，使系统更复杂

操作系统引导

作用：让操作系统运行起来

步骤：

1. 激活CPU：开始执行BIOS指令

2. 硬件自检：在内存最开始的地方构建中断向量表，通电检查硬件

3. 加载带有操作系统的硬盘

4. 加载主引导记录MBR（Master Boot Recored）：作用是告诉CPU去哪个硬盘分区（活动分区）找操作系统

5. 扫描硬盘分区

6. 加载分区引导记录PBR：找到启动管理器

7. 加载启动管理器：找到并激活引导操作系统的程序

8. 加载操作系统

   

虚拟机

第一类虚拟机管理系统

虚拟机管理程序运行在内核态

向上提供若干虚拟机，虚拟机作为用户态的一个进程运行，所在的内核态为虚拟内核态

第二类虚拟机管理系统

在宿主操作系统上运行，如VMWare

进程与线程

进程

概念：进程是一个正在执行程序的实例，是资源分配的基本单位

组成：

1. 进程控制块PCB（Process Control Block）：

   进程创建时新建一个PCB，进程结束时回收PCB，进程存在的唯一标志

   

2. 程序段：程序的代码段

3. 数据段：运行时产生的数据

PCB组织方式：

1. 链接方式：同一状态的PCB在同一队列
2. 索引方式：同一状态的PCB在同一索引表

特征：

1. 动态性：动态地产生、变化和消亡
2. 并发性：多个进程间并发执行
3. 独立性：资源分配的基本单位
4. 异步性：运行速度不可预知

进程状态

就绪态 –> 运行态：获得CPU时间片

运行态 –> 就绪态：1. 时间片用完；2. 有优先级更高的进程在就绪态

运行态 –> 阻塞态：请求某一资源或等待某一事件发生（主动）

阻塞态 –> 就绪态：等待的事件到来时（被动）

进程控制

创建/撤销/转换进程

原语：

• 原子性：运行必须一气呵成，不可中断

• 通过关中断和开中断实现原子性

  

创建进程过程：

1. 分配PID，申请空白PCB
2. 分配运行所需资源
3. 初始化PCB：包括标志信息、CPU状态信息、CPU控制信息和进程优先级等
4. 插入就绪队列

终止进程过程（正常结束、异常结束、外界干预）：

1. 从PCB中读取进程状态
2. （如果在运行）终止运行、终止子进程
3. 将资源归还父进程/操作系统
4. 将PCB从队列中删除

阻塞进程操作（主动行为）：

1. 调用阻塞原语
2. 通过PID找到PCB
3. （如果在运行）保护现场，将上下文保存到PCB中
4. 将PCB插入到相应等待队列

唤醒进程操作（被动行为）：

1. 调用唤醒原语
2. 在等待队列中找到该PCB
3. 从阻塞队列中移除，设置为就绪态，插入到就绪队列

进程通信

高级通信主要有三种方式：

1. 共享存储

   基于数据结构或共享空间，互斥访问

   

2. 消息传递

   通过原语传递指定格式的消息，直接发给对方进程或发给信箱

   

3. 管道通信

   半双工通信，固定大小，先进先出

   满时写进程堵塞，空时读进程堵塞

线程

引入线程的目的是减小程序在并发执行时所付出的时空开销

TCB由线程ID、PC、寄存器集合、运行状态、优先级和堆栈指针等组成

线程是调度的最小单位

线程特点

• 不同线程可以执行相同程序
• 同一进程的线程共享进程资源
• 各个CPU可为一个进程内的各线程服务，缩短进程的处理时间
• 被终止但尚未释放资源的线程被其他线程调用时，从终止态重新开始运行

线程实现方式

1. 用户级线程（UTL）

   用代码模拟线程，内核感知不到线程的存在

   优点：

   1. 节省了模式切换的开销

   缺点：

   1. 一个线程阻塞，所有线程都阻塞
   2. 每次只能运行一个线程

   

2. 内核级线程（KTL）

   在内核的支持下运行的

   优点：

   1. 发挥多核CPU的优势
   2. 一个线程阻塞，其他线程不会跟着阻塞

   缺点：

   1. 线程切换需要切换到核心态，开销较大

   

3. 组合方式

   

   

CPU调度

为什么要CPU调度：CPU和外部设备的速度差距大，等待外部设备会浪费CPU资源

调度的层次

类型	作用	方向	频率
作业调度（高级调度）	从外存后备队列选择一个作业，创建进程	外存 -> 内存	低
内存调度（中级调度）	从外存将挂起的的作业调回内存	外存 -> 内存	中
进程调度（低级调度）	从就绪队列中选择一个进程分配给处理机	内存 -> CPU	高

中级调度的作用是为了提高内存的利用率，将暂时不能运行的进程挂起来

挂起和阻塞的区别：挂起的进程在外存，阻塞的进程还在内存；就绪态和阻塞态的进程可能会被挂起

:star:评价指标

指标	怎么算	意义
CPU利用率	有效工作时间 / (有效工作时间 + 空闲等待时间)
系统吞吐量	完成作业数 / 花费时间	单位时间完成的作业量
周转时间	作业完成时间 - 作业提交时间	作业提交到完成的时间
平均周转时间
带权周转时间	周转时间 / 实际运行时间	>1，周转时间为运行时间的多少倍
平均带权周转时间
等待时间	等待CPU的时间	进程等待时间不包括IO时间
响应时间	首次响应时间 - 提交时间

调度实现

• 排队器：将就绪进程按照一定策略排成一个或多个队列
• 分派器：分配CPU给新进程（进程调度）
• 上下文切换器：切换进程上下文（进程切换）

调度时机

1. 创建新进程时，CPU选择运行父进程还是子进程
2. 运行的进程正常结束或异常终止
3. 阻塞时（IO请求、信号量操作等）
4. IO完成后的IO中断
5. 有更高优先级的进程进入就绪队列
6. 时间片用完

操作系统内核程序临界区：一般是访问某种内核数据结构，不能进行调度和切换

临界区：访问临界资源，等待IO时应该进行进程切换

不能进行进程调度和切换的场景

1. 在处理中断的过程
2. 屏蔽中断的原子操作过程（加解锁、保护中断现场等）

调度方式

1. 非抢占调度方式

   优点：实现简单、开销小，适合早期批处理系统

   缺点：不能用于分时系统和大多数实时系统

2. 抢占调度方式

   提高吞吐率和响应效率有好处

   根据优先权、短进程优先、时间片原则等判断优先级

:star:调度算法

早期批处理系统中使用的调度算法：

	说明	是否抢占	是否导致饥饿	优点	缺点
先来先服务(FCFS)	按作业提交时间执行	×	×	简单	对短作业不利，效率低
短作业优先(SJF)	每次调度时选择就绪队列里运行时间最短的	×	√	平均等待时间、平均周转时间相对较短	对长作业不利
最短剩余时间优先(SRTN)	每次调度、进程进入就绪队列时选择就绪队列里剩余运行时间最短的	√	√	平均等待时间、平均周转时间“最”优	对长作业不利
高响应比优先(HRRN)	每次调度时选择就绪队列里响应比最高的(响应比：(等待时间 + 运行时间) / 运行时间)	×	×	综合考虑了等待时间和运行时间

这些算法没有关注响应时间和任务的紧急程度，交互性差

分时操作系统中使用的调度算法：

	说明	是否抢占	是否导致饥饿	优点	缺点
时间片轮转(RR)	每隔一段时间产生一个时钟中断，激活调度程序调度，时间片设计最好使切换开销占比不超过1%	√	×	公平，响应快	不区分紧急任务，时间片设置不合理开销大
优先级调度算法	调度时选择在就绪队列中优先级最高的进程	×	√	可灵活调整对进程的偏好	可能导致饥饿
多级反馈队列调度算法	如下图	√	√	兼顾长短作业，有较好的响应时间，通用	复杂

静态优先级：创建时决定优先级，之后一直不变

动态优先级：创建时有一个初始值，根据情况调整优先级

优先级从以下几点考虑：

通常：

• 系统进程 > 用户进程
• 前台进程 > 后台进程
• IO型进程 > 计算型进程
• 交互型进程 > 非交互型进程

同步与互斥

临界资源和临界区

临界资源：一次仅允许一个进程使用的资源

临界区：访问临界资源的那段代码

临界资源的访问过程：

1） 进入区：检查是否可进入临界区、设置正在访问临界区标志

2） 临界区：又称临界段

3） 退出区：秦楚正在访问临界区标志

4） 剩余区：代码其他部分

同步

直接制约关系

多个进程合作完成同一个任务

互斥

间接制约关系

进程间互斥地访问临界资源

实现互斥的准则

1. 空闲让进：临界区空闲时，允许一个进程进入
2. 忙则等待：有进程进入临界区时，其他进程等待
3. 有限等待：要保证进程在有限时间里进入临界区
4. 让权等待：进程不能进入临界区时，要让出CPU

基本实现方式

软件实现方式

1. 单标志法

   用一个turn表示能访问临界区的进程号

   若一个进程不再进入临界区，则另一个也无法进入，违反“空闲等待”

   

2. 双标志先检查法

   一个数组flag[2]表示进程想要进入的意愿

   可能导致两个进程都通过进入区，违反“忙则等待”

   

3. 双标志后检查法

   先设置意愿，再进入进入区

   可能导致都卡在进入区，违反“空闲等待”、“有限等待”，导致饥饿

   

4. Peterson算法

   同时有表示意愿的flag[]和表示能访问临界区的进程号的turn

   如果只有一个进程要进入临界区，会导致一直在while里，违反“让权等待”

   

硬件实现方式

1. 中断屏蔽

   通过关中断、开中断实现互斥

   缺点：开关中断需要切换到内核态，效率低；只能在单处理机上使用

2. TestAndSet指令

   原子操作，设置和检查一气呵成，不能实现“让权等待”

   

   

3. Swap指令

   原子操作，互换两个变量的值。

   和TS指令区别不大，只是将保存原来值的操作放到方法外

TAS和Swap是硬件指令

相比于软件实现，硬件实现简单，支持任意多个线程。但硬件实现不能“让权等待”，会产生饥饿

互斥锁

mutex lock，互斥锁，自旋锁

acquire()：获得锁，release()：释放锁，操作都是原子性的

在多处理器系统中，自旋的消耗比进程切换小，因此常用与多处理器系统。

信号量

整型信号量

用一个整型S表示剩余资源数，如果为0则while不断尝试，不遵循“让权等待”。

记录型信号量

遵循“让权等待”

伪代码

typedef struct {
    int value;	// 剩余资源数
    struct process *L;	// 等待队列
} semaphore;

void wait(semaphore S) {
    S.value--;
    if (S.value < 0) {
        add this process to S.L;	// 进入阻塞队列
        block(S.L)	// 阻塞当前进程
    }
}

void signal(semaphore S) {
    S.value++;
    if (S.value <= 0) {
        remove a proceess P from S.L;	// 将一个进程从阻塞队列中移除
        wakeup(P);	// 唤醒进程
    }
}

经典同步问题

生产者-消费者问题

信号量设置：

1. mutex：互斥信号量，用于控制互斥访问缓冲池
2. full：记录“满”的缓冲区数，初值0
3. empty：记录“空”的缓冲区数，初值n

注意：

要先判断“空”/“满”的缓冲区数，再获取mutex，否则可能抱着锁阻塞，导致死锁

释放锁和“空”/“满”的缓冲区数 + 1的顺序可以互换

读者-写者问题

读写、写写互斥；读读共享

信号量设置：

1. count：当前读者数量，初值0
2. mutex：互斥信号量，用于控制互斥访问count，防止读进程重复对rw上锁
3. rw：互斥访问文件，初值1

哲学家进餐问题

信号量设置：

1. chopstick[5]=[1,1,1,1,1]

注意：

如果采用贪心来获取筷子，会导致死锁

吸烟者问题

三个抽烟者，三种材料，每个抽烟者都缺两种不同的材料，缺的都不同。

一个提供者，每次提供两种材料

信号量设置：

1. offer1、offer2、offer3，分别表示两种材料的组合，初值为0
2. finish：用于表示吸烟者吸完烟了，之后提供者才能放材料，初值为0

管程

管理共享资源的资源管理器，封装了对共享资源的操作

各进程只能串行访问管程里的方法

条件变量：带有阻塞队列和入队出队操作的数据结构

死锁

死锁和饥饿的区别

进程数：死锁要两个及以上进程；饥饿可以只有一个进程

进程状态：死锁进程必定处于阻塞态；饥饿进程可能处于就绪态或阻塞态

产生原因：死锁是由于多个进程应竞争资源而造成的僵局；饥饿是由于申请的资源不能在有限时间内获取

死锁产生的原因

1. 系统资源的竞争
2. 进程推进顺序非法

:star:死锁的必要条件

1. 互斥条件：资源最多被一个进程所占有

2. 不可剥夺：资源在未使用完之前不能被其他进程抢夺走，只能主动释放

3. 请求并保持：需要获取多个资源，对已经获得的部分资源保持不放

4. 循环等待：进程间都在等待其他进程释放自己需要的资源，形成了一条等待链。每个资源的数量都是1

   

预防死锁

	说明	缺点
破坏互斥条件	将互斥使用的资源改造成共享资源	可能导致系统不安全，很多时候要保护互斥性
破坏不可剥夺	请求新的资源而得不到满足时，它必须释放已经保存的所有资源	复杂，反复申请和释放资源增加系统开销，吞吐量降低
破坏请求与保持	方法一：预先静态分配：一次性将所需要的资源在运行前都给进程。方法二：进程获取运行初期需要的资源后就开始运行，后面要新的资源需要将已有的资源全部释放	简单，但资源浪费严重，暂时用不到的资源可能被长时间占有。
破坏循环等待	给资源编号，只能按顺序获取	不便于新增资源，可能造成资源浪费，编程麻烦

:star:避免死锁（银行家算法）

能找到安全序列则系统处于安全状态，否则处于不安全状态，可能导致死锁

定义的变量：

1. 可利用资源向量Available：Available[j] = K表示系统中j类资源的可用数为K个
2. 最大需求矩阵Max:Max[i, j] = K表示i进程需要j类资源K个
3. 分配矩阵Allocation：Allocation[i, j]=K表示i进程已获得了j类资源K个
4. 需求矩阵Need：Need[i, j] = K表示i进程还需要j类资源K个。Need = Max - Allocation

死锁检测与消除

资源分配图

阻塞进程：剩余资源数无法满足需求的点

孤立点：可分配资源并已完成分配的点，可将连着的线都去掉

可完全简化：将所有点变成孤立点，此时一定没有发生死锁

死锁定理：不可完全简化表示发生死锁

死锁解除

1. 资源剥夺法：将某些死锁进程挂起，剥夺其资源。要注意防止饥饿发生
2. 撤销进程法：将某些死锁进程撤销，剥夺其所有资源，撤销进程的代价可能很大
3. 进程回退法：回退到没有发送死锁的时点，要设置还原点，复杂

因为撤销进程后，之前运行的东西就作废了，所以代价可能很大

选择撤销进程时考虑的点：

1. 进程优先级
2. 已执行时间
3. 已经使用了多少资源
4. 交互式还是批处理

内存管理

程序链接与装入

将代码装入的内存的步骤：

1. 编译：将代码编译成若干模块
2. 链接：将编译后的模块和所需库函数链接在一起，形成完整的装入模块
3. 装入：由装入模块将转入模块装入内存

装入方式

1. 绝对装入

   只适合单道程序环境

   程序中的逻辑地址与内存地址完全相同

   绝对地址在编译或汇编时给出，或由程序员给出

2. 可重定位装入（静态重定位）

   只适合早期多道批处理环境

   在装入时将相对地址改为绝对地址

   缺点：作业一旦进入内存，整个运行期间就不能在内存中移动，也不能再申请内存空间

   

3. 动态运行时装入（动态重定位）

   装入内存时不修改相对地址，到真正运行时才进行内存转换，需要重定位寄存器

   优点：不需要连续内存块，可动态申请内存块

   

链接方式

1. 静态链接

   运行前将目标模块和库链接成完整的装入程序，之后不再拆开

2. 装入时动态链接

   边装入边链接，便于修改和链接

3. 运行时动态链接

   运行时需要什么模块才对它进行链接，可加快装入速度，减少内存使用，便于共享模块

内存保护

保护用户进程不影响操作系统、用户进程间不互相影响

上下限寄存器

存放进程的上下限地址，指令访问地址时会进行检查是否越界

重定位寄存器、界地址寄存器

重定位寄存器存放起始的物理地址

界地址寄存器存放进程的最大逻辑地址

修改这两个寄存器的值必须使用特权指令，即只有操作系统能改

进程的内存映像

进程的内存映像一般包括：

1. 代码段：只读、共享
2. 数据段：全局变量、静态变量
3. PCB：进程控制块
4. 堆：存放动态分配的变量
5. 栈：用来实现函数调用

内存扩充

覆盖技术

将程序分为多个段，常用的常驻内存（固定区），不常用的需要时再放入内存（覆盖区）

必须由程序员声明覆盖结构，只用于早期操作系统

交换技术

内存空间紧张时，将某些进程暂时换出外存，将已具备运行条件的进程换入内存（中级调度）

PCB是常驻再内存的

磁盘分为：

1. 对换区：连续分配方式，速度快于文件区，追求换入换出速度
2. 文件区：离散分配方式，追求存储空间的利用率

覆盖是在同一进程或程序中的，交换在不同进程、作业间的

连续分配

单一连续分配

描述：内存被分为系统区（低地址）和用户区（高地址），用户区存放用户程序，只能存一道

优点：简单，无外部碎片

缺点：只能用在单任务的操作系统中，有内部碎片，内存利用率极低

固定连续分配

描述：

​ 将用户区换分为多个分区（可以不相等），每个分区只能装一道程序

​ 需要分区说明表来实现内存的分配于回收

优点：简单，无外部碎片

缺点：程序太大时需要使用覆盖技术，有内部碎片，内存利用率低

动态分区分配

描述：

​ 不会预先划分内存区，根据进程大小动态建立分区，也叫可变分区分配

​ 用空闲分区表或空闲分区链记录内存的使用情况

优点：无内部碎片，可根据进程大小动态建立分区

缺点：有外部碎片，可通过“紧凑”技术解决，但相对费时

内部碎片：分配给进程的内存中没有用上的部分

外部碎片：内存中小的难以被利用上的内存块

动态分区分配算法

顺序分配算法

	描述	分区排序顺序	优点	缺点
首次适应算法（First Fit）	每次都顺序查找空闲分区，将第一个满足大小的分区分配给作业	按地址递增顺序排列	保留了高位地址的大空闲区，有利于后续大作业的装入	低地址会出现许多小碎片，每次查找都会经过一遍，增加了开销
最佳适应算法（Best Fit）	将第一个能满足大小的空闲分区分配给作业	按容量递增	能流出更多大空闲分区	会留下最多外部碎片，性能很差
最坏适应算法（Worst Fit）	将第一个能满足大小的空闲分区分配给作业	按容量递减	不容易产生外部碎片	没有很多大分区可用，性能很差
临近适应算法（Next Fit）	也称循环首次适应算法，对First Fit的修改，每次从上一次查找结束的位置开始查找	按地址递增顺序排列	让高低地址的空闲分区以同等概率被分配出去	导致高地址没有大块空闲分区可用，通常比First Fit的效果差

索引分配算法

当系统很大时，空闲分区链可能很长，此时用顺序分配算法的时间开销会很大，此时往往采用索引分配算法

大致思想是：大小相同的空闲分区单独设立空闲分区链，再设置索引表管理这些空闲分区链

	描述	分区排序顺序	优点	缺点
快速适应算法	找到能够容纳进程的最小分区链，然后取出第一块分配给进程		效率高，不产生内部碎片	回收分区时，要合理合并分区，算法复杂，开销大
伙伴系统
哈希算法	建立以空闲区大小为关键字的哈希表，分配时根据大小计算空闲区所在位置

分页存储

概念

page frame=页框=页帧=物理块=内存块：内存分为若干固定大小的分区，页面大小应是2的整数次幂

页=页面：逻辑空间的分区，大小和物理块相同

页号：页面的编号，从0开始

分页管理优点：不产生外部碎片，只产生很小的内部碎片（页内碎片）

逻辑地址结构：

页表（页面映射表）：

实现从页号到物理块号的映射

页表寄存器：存放了页表始址和页表长度

地址变换机构：

计算

页号=逻辑地址/页大小

偏移量=逻辑地址%页大小

页表项地址=页表始址+页号*页表项大小，里面存的就是对应的物理块号

物理地址=物理块号*页面大小+偏移量

页表项的大小：如果以字节编制，则大小应为字节的整数倍，且表示的大小要≥总页数

有时为了方便计算或存储其他信息，会加大页表项的长度

快表

又称联想寄存器（TLB，Translation Lookaside Buffer），属于高速缓存，是硬件，用来存放最近访问的页表项

如果在快表中找到要访问页表项，则只需一次访存+一次访快表就能完成存取数据

如果未找到，则需要两次访存+一次访快表才行

如果没有快表，则每次都需要两次访存

局部性原理

时间局部性：如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。

空间局部性：一旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问。

多级页表

单级页表存在的问题有：

1. 页表需要连续的内存空间
2. 可能占用很多内存

多级页表可以使页表离散存储

注意：

1. 多级页表中各级页表的大小不能超过一个页面
2. 随着级数越多，访存的次数也会增加

分段存储

分段管理是考虑了程序员和用户，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要

概念

段表：保存逻辑空间和内存空间的映射关系

段表项：记录了始值和段长，长度是固定的

段表寄存器：存放段表始址和段表长度

地址变换机构：

段内偏移量也需要判断是否越界

分页和分段的比较

相同点：

1. 都是非连续分配方式
2. 都需要通过地址变换机构实现地址变换
3. 都可以使用快表减少地址变换时间

不同点：

1. 页是信息的物理单位；段是信息的逻辑单位
2. 目的：分页是提高内存利用率；分段是为了更好地满足用户需求
3. 长度：页的大小固定且由系统决定，对用户透明；段的大小不固定由用户决定，对用户可见
4. 地址空间：分页管理的地址空间是一维的；分段管理的地址空间是二维的（分页只需要给出一个逻辑地址就能计算出页号和偏移量，由操作系统来完成；分段需要给出段号和段内偏移量，因为分段是用户决定的）

	优点	缺点
分页管理	不会产生外部碎片，空间利用率高	不方便按照逻辑模块实现信息的共享和保护
分段管理	方便进行共享和保护	段太长为其分配连续空间不方便，会产生外部碎片

段页式管理

将进程按逻辑模块分段，再将各段分页。结合了分页和分段的优点

概念

逻辑地址：由段号、页号、页内偏移量组成

段表项：段号（隐含的）、页表长度、页表存放块号

页表项：页号（隐含的）、内存块号

分页对于用户是不可见的，系统会根据段内地址自动划分页号和页内偏移量

用户要提供段号和段内偏移量（二维）

逻辑地址转换为物理地址过程

段号和页号都要检查是否越界

虚拟内存

建立了“内存-外存”的两级存储器结构，利用局部性原理实现高速缓存

特点

1. 多次性：无需将作业一次性全部装入内存，只需要当前运行的那部分程序和数据装入内存即可运行
2. 对换性：将需要的程序调入内存（换进），将暂不需要的调入外存（换出），由操作系统完成
3. 虚拟性：用户看到的内存容量，远大于实际容量

管理方式

页表机制

基本分页的页表项：页号、物理块号

请求分页的页表项新增：

1. 状态位：是否已调入内存
2. 访问字段：在一段时间被访问的次数
3. 修改位：调入内存后是否被修改过
4. 外存地址：该页在外存的存放地址

缺页中断机构

要访问的页面不在内存时，产生缺页异常（内部异常），阻塞缺页的线程

将要访问的页面调入内存（没有空位要淘汰其他页面），修改页表项

若页面被淘汰，根据是否修改来判断是否要写回外存

地址变换机构

页框分配

驻留集：给一个进程分配的页框的集合，一般不小于工作集的大小

工作集：某个时间段内进程实际访问的页面集合

抖动：刚刚换入（换出）的页面马上又换出（换入）页面，说明分配给进程的物理块太少

分配策略

	说明	优缺点
固定分配局部置换	分配固定数目的物理块，缺页只能从分配给自己的内存中进行替换	难以确定应分配的物理块数，太少会频繁出现缺页中断，太多会降低资源利用率
可变分配全局置换	先分配一定数目的物理块，后从空闲物理块中根据情况增减，缺页则从空闲物理块队列中取出一块进行分配或淘汰一个未锁定的页面来分配	比上一种灵活，盲目增加物理块会降低系统并发度
可变分配局部置换	先分配一定数目的物理块，缺页只能从分配给自己的内存中进行替换，根据缺页率动态增减分配的物理块	复杂

页面置换算法

缺页率：缺页次数 / 总访问页面次数

	说明	优缺点
最佳置换算法（OPT，Optimal）	优先淘汰最长时间不会被访问的页面	性能最好，只在理论上，用来评估其他算法的性能
先进先出置换算法（FIFO）	优先淘汰最先进入内存的页面	简单，性能差，可能出现Belady异常（驻留集越大，性能反而差）
最近最久未使用算法（LRU，least recently used）	有限淘汰最近最久没访问的页面	性能好，但需要硬件支持，开销大
时钟置换算法（clock）、最近未使用算法（NRU）	循环扫描，淘汰第一个访问位为0的页面，将经过的访问位1改为0	简单，开销小，未考虑页面是否被修改过
改进型时钟置换算法	（访问位，修改位）形式	开销小，性能也不错

内存映射文件

操作系统向应用程序提供的一个系统调用。

在磁盘文件与进程的虚拟地址空间之间建立映射关系，将一个文件当做内存中的一个大字符数组来访问，而不通过文件IO操作来访问

内存映射还能用来共享内存

文件管理

概念

文件(File)：以硬盘为载体的存储在计算机上的信息集合。用户输入输出以文件为基本单位

文件的构成：存储空间、分类、索引和访问权限等

文件的属性：名称、类型、创建者、所有者、位置、大小、保护、创建/修改/存取时间

数据项：文件系统中最低级的数据组织形式

记录：一组相关的数据项的集合

文件逻辑结构

指从用户角度出发看到的文件的组织形式

无结构文件

由字符流构成，又称流式文件，如txt文件

有结构文件

由一个及以上的记录构成的文件，又称记录式文件。

根据记录的长度，分为：

1. 定长记录：所有记录长度相同
2. 变长记录：各个记录长度不一定相同

根据记录的组织形式，分为：

1. 顺序文件：记录按顺序排列，定长的可随机存取

2. 索引文件：为每个记录在索引表中设置一个索引表项，包含记录的指针和长度。索引表是定长的顺序文件

   

   需要额外的索引表，增加了存储开销

3. 索引顺序文件

   顺序文件和索引文件的结合，一组记录对应一个索引表项提高了查找效率

   

4. 散列文件：

   通过记录的hash值直接计算出物理地址。具有很高的存取速度，但存在hash冲突

文件物理结构

指将文件存储在外存上的存储组织形式，磁盘块的大小通常与内存的页面大小相同

文件分配方式：

• 连续分配

  要求每个文件在磁盘上占有一组连续的块，进程访问磁盘时的寻道数和寻道时间最小

  优点：支持顺序访问和直接访问，速度快

  缺点：要连续的存储空间，可能产生外部碎片；要事先知道文件的长度，无法动态增长

• 链接分配

  离散分配

  • 隐式分配：指向下一个的指针在磁盘块中

    只支持顺序访问，访问磁盘次数多，效率低

  • 显式分配：将指针都存放在一张内存中的文件分配表（File Allocation Table）里（一个磁盘对应一张，开机时调入内存）

    支持顺序和直接访问，减少了访问磁盘的次数，但FAT需要占用一定内存

• 索引分配

  打开文件时，没必要将整个FAT都读入内存，因此将文件的盘块号集中成一个索引表（块）读入内存

  • 单级索引分配方式

    优点：支持直接访问

    缺点：索引表占用内存太大

  • 多级索引分配方式

    

    优点：加快了对大型文件的查找效率

    缺点：对于小文件来说，访问磁盘的次数增加了

  • 混合索引分配方式

    为了照顾小、中、大文件而采用混合索引

    小文件采用直接索引，大文件采用间接索引

    

文件控制块

File Control Block，存放控制文件需要的各种信息，以实现按名存取

FCB的有序集合称为文件目录

文件目录也是文件，称为目录文件

为了减小FCB的体积，将除了文件名的其他信息放到索引节点中，FCB只存文件名和索引节点的指针

存放在磁盘上的索引节点称为磁盘索引节点

存放在内存中的索引节点称为内存索引节点，相比磁盘索引节点新增了索引节点号、状态、访问计数等

文件目录

目录管理要实现按名存取

目录结构：

• 单级目录结构

  只建立一张目录表，每个文件占一个目录项

  缺点：查找速度慢，文件不允许重名，不便于共享文件

  

• 二级目录结构

  分为主文件目录和用户文件目录

  解决了多用户间的文件重名问题，可以实现访问限制

  缺点：缺乏灵活性，不能文件分类

  

• 树形目录结构

  缺点：不便于文件共享

  

• 无环图目录结构

  在树形目录结构的基础上增加了一些指向同一节点的有向边，使整个目录成为一个有向无环图

  便于共享文件

  

存储空间管理

概念

卷（volume）：包含文件系统的分区。包含目录区和文件区

目录区：存放FCB

文件区：存放文件数据

管理方式

	说明	分配	回收	优缺点
空闲表法	连续分配方式。空闲表（第一个空闲盘块号，空闲盘块数）	与内存相似	与内存相似	分配速度快
空闲链表法	空闲盘块链、空闲盘区链	盘块的按盘块分配、盘区的从盘区里面裁出来或几个盘区合一块		盘块简单、效率低；盘区效率高、复杂
位示图法	每个二进制位对应一个盘块	改为“1”	改为“0”	容易找到空闲盘块，位示图大小可能会很大
成组链接法	超级快，存放下一组空闲盘块数和空闲块号

文件操作

创建：

1. 在外存中找到文件所需空间
2. 在目录中创建对应的目录项

删除：

1. 找到目录中的目录项
2. 回收占用的磁盘块
3. 删除对应的目录项

读：

1. 给出要读的文件在打开文件表中的索引号（文件描述符）
2. 给出要读入多少内容、放在内存哪里

写：

1. 给出要写的文件在打开文件表中的索引号（文件描述符）
2. 给出要写回多少数据、数据在内存哪里

打开：

1. 找到目录中的目录项
2. 将目录项复制到打开文件表中（避免多次重复检索目录）
3. 之后用户使用打开文件表的编号来指明要操作的文件（不再使用文件名）

关闭：

1. 删除打开文件表中的对应表项
2. 回收内存空间
3. 系统打开文件表的打开计数器cnt-1，若cnt=0则删除表项

文件共享

• 硬链接：

  只有cnt=0时外存中的文件才会被删除

• 软连接：

  类似于windows的快捷方式，共享文件被删除后就无法访问

文件保护

• 口令保护：为文件设置一个口令，用户提供口令以访问文件。口令存在系统中，不安全
• 加密保护：用一个密码对文件加密，用户提供密码对文件反向解密。加解密需要耗费时间
• 访问控制：用访问控制表(ACL)，记录用户/组的访问权限。灵活，可以实现复杂的文件保护功能

文件系统层次结构

• 用户需要通过操作系统提供的接口发出上述请求——用户接口
• 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录 项——文件目录系统
• 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限—— 存取控制模块（存取控制验证层）
• 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文 件系统与文件信息缓冲区
• 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址——物理文件系统
• 要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块
• 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块

文件系统布局

• 在磁盘中的结构

  

• 在内存中的结构

  • 目录结构缓存
  • 系统打开文件表
  • 进程打开文件表

虚拟文件系统

屏蔽不同文件系统的差异和操作细节，向上为用户提供了文件操作的统一调用接口

虚拟节点用来统一在主存中的文件数据结构

文件系统挂载

在VFS中注册新挂载的文件系统。内存中的挂载表（mount table）包含每个文件系统的相关信息，包含文件系统类型、容量大小等。

IO设备

磁盘

磁盘地址用 柱面号、盘面号、扇区号 决定

磁盘分类：

1. 固定头磁盘：磁头不动，每个磁道一个磁头
2. 活动头磁盘：磁头通过磁头臂移动，每个盘面一个，所有磁头共进退
3. 固定盘磁盘：盘片不能换
4. 可换盘磁盘：盘片可以换

传统磁盘：扇区按固定圆心角度划分，存储密度从最外道向里道增加

现代磁盘：盘面划分若干环带，同一环带内的所有磁道具有相同的扇区数。越外层扇区越多

磁盘调度算法

一次操作的时间：

​ 寻道时间（启动磁头臂+移动磁头（调度算法决定））+

​ 旋转延迟时间（找到目标扇区所需的时间）+

​ 传输时间（读写速度）

	说明	优点	缺点
先来先服务（FCFS）		公平	性能差
最短寻找时间优先（SSTF）	优先处理离磁头最近的磁道	性能较好，平均寻道时间短	会产生饥饿
扫描算法（SCAN、电梯算法）	移到头了才会转向	不会产生饥饿	时间比SSTF长，各磁道的响应时间不平均
LOOK调度算法	在当前方向上没有请求了就转向	比SCAN速度更快
循环扫描算法（C-SCAN）	只有一个方向处理请求，到头了迅速返回起点	各磁道的响应时间平均	比SCAN寻道时间长
C-LOOK调度算法	只有一个方向处理请求，没请求了迅速返回起点

减少延迟时间的方法

交替编号（同一盘面内）：磁头读入一个扇区后需要短暂的处理时间。逻辑上相邻的块物理上保持一定间隔，在间隔的时间里处理数据

错位命名（不同盘面间）：

磁盘管理

低级格式化（物理格式化）：划分扇区

高级格式化（逻辑格式化）：将若干柱面分区，如C盘、D盘

初始化程序（自举程序）：初始化CPU、寄存器、内存等

自举装入程序：方便修改自举程序，将自举程序放在磁盘，自举装入程序负责将自举程序读入内存

坏块：损坏的扇区

固态硬盘

固态硬盘（SSD，Solid State Disk），基于闪存

闪存翻译层：将CPU的逻辑读写请求翻译成对物理设备的读写控制信号

读写：数据以页来读写，一个页可写一次读多次。只有整个块被擦除后才能再写。访问任何地址速度是一样的

读快写慢：要修改一页，需要将整块复制到一个新块上再对页进行修改（以块为单位擦除）

磨损均衡：

1. 动态磨损均衡：写入时自动选择较新的闪存块
2. 静态磨损均衡：读多写少的数据挪到老块，腾出较新的闪存块

设备控制器

也叫IO接口，CPU可控制IO接口，由IO接口来控制设备

设备控制器与CPU间：

一对一

• 数据线：传送读写数据、控制信息和状态信息
• 地址线：传送IO接口中的寄存器编号
• 控制线：传送读写等控制信息

设备控制器与设备间：

一对多

• 数据信号
• 控制信号
• 状态信号

寄存器：

• 数据寄存器：保存CPU或设备传来的数据
• 控制寄存器：保存CPU传来的控制信息
• 状态寄存器：保存设备的执行结果或状态信息

寄存器编址方式：

• 内存映射编址（统一编址）：将主存地址空间分出一部分IO端口进行编址
• 寄存器独立编址（独立编址）：寄存器地址和主存分开编址

IO控制方式

• 程序直接控制

  CPU不断询问是否已准备好数据，当发现状态寄存器已就绪，则读数据寄存器一个字到CPU寄存器中，再把CPU寄存器中的内容放入内存

  优点：简单

  缺点：CPU空转，利用率低

• 中断驱动

  设备准备完后，设备控制器发出中断信号来告知CPU。CPU读取一个字的数据到CPU寄存器，然后再存到主存，之后阻塞进程，继续执行其他操作

  优点：不再需要轮询，提升了利用率

  缺点：以字（节）为单位进行干预，效率仍然低

• DMA

  直接存储器存取，IO设备将数据直接放到内存

  优点：以块为单位传输，CPU只在传输的开始和结束有干预

  缺点：CPU每发出一条IO指令，只能读写一个或多个连续的块

• 通道控制

  将IO任务存在内存中（通道程序），告诉通道任务在内存中的位置，由通道来完成规定的IO任务，完成后发出中断信号告知CPU。一个通道可对应多个IO控制器

  优点：一次传输一组块

IO软件层次结构

IO接口

1. 字符设备接口

   以字符为单位存取和传输，如键盘、打印机等

   特征：传输速率低、不可寻址

2. 块设备接口

   以数据块块为单位存取和传输，如磁盘等

   特征：传输速率快、可寻址

3. 网络设备接口

   网卡

阻塞IO和非阻塞IO：

1. 阻塞：用户进程调用IO操作时，进程就被阻塞。如字符设备接口
2. 非阻塞：用户进程调用IO操作时，不阻塞进程。如块设备接口

缓存和缓冲区

• 磁盘高速缓存

  利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息

• 缓冲区

  • 单缓冲
  • 双缓冲
  • 循环缓冲
  • 缓冲池

缓存用于存放经常要访问的数据

缓冲用于高速设备和低速设备的数据交换，缓和高速设备和低速设备之间速度的差距

设备分配和回收

数据结构：

• 设备控制表（DCT）：每个设备对应一张
• 控制器控制表（COCT）：每个控制器对应一张
• 通道控制表（CHCT）：每个通道对应一张
• 系统设备表（SDT）：记录整个系统中所有设备的情况

安全分配：进程获得设备后便会阻塞，直到IO操作完成

不安全分配：进程发出IO请求后仍然继续运行，可以拥有多个设备，可能造成死锁

分配步骤：

1. 分配设备：查询SDT中的DCT
2. 分配控制器：根据DCT找到COCT
3. 分配通道：根据COCT找到CHCT

SPOOLING技术（假脱机）：

脱机：IO输入不需要人来输入，如磁带

假脱机：用软件实现脱机

驱动程序接口

接收上层应用发来的抽象IO请求，将它们转换为具体要求后发送给设备控制器

复试简答题

1.文件链接方式

• 隐式链接：文件的所有块通过指针链接在一起，形成一个链表，随机访问效率低。
• 显式链接：文件的块位置信息存储在外部数据结构中，而不是存储在块本身，随机访问效率高。
• 索引链接：使用索引块存储文件块位置，适合大文件，随机访问效率高。

FAT（File Allocation Table，文件分配表）是一种用于管理磁盘上文件存储的数据结构。它是显式链接的一种实现方式，用于记录文件在磁盘上的存储位置和分配情况。

2.什么是分时系统，分时系统的特点

分时系统（Time-Sharing System） 是一种操作系统的设计模式，允许多个用户通过终端同时使用计算机资源。在分时系统中，CPU 的时间被划分为很小的时间片（Time Slice），每个用户或任务轮流使用 CPU 的时间片，从而实现多个用户或任务“同时”执行的效果。

特点：

1. 允许多个用户通过终端同时访问系统
2. 每个任务或用户轮流使用 CPU
3. 用户可以通过终端与系统实时交互
4. 系统响应速度较快

3.死锁的四个必要条件

死锁（Deadlock） 是指多个进程或线程在执行过程中，因为竞争资源而互相等待，导致它们都无法继续执行的状态

1. 互斥条件：资源一次只能被一个进程占用
2. 请求和保持：进程已经占有了至少一个资源，同时又在等待获取其他被占用的资源
3. 不可抢占：进程已经占有的资源不能被强行剥夺，必须由进程主动释放
4. 循环等待：存在一个进程等待的循环链，每个进程都在等待下一个进程所占有的资源

4.进程和线程的区别

进程 进程是程序的一次执行实例，是操作系统资源分配的基本单位，具有独立的内存空间和资源，进程切换的开销较大

线程 是 CPU 调度的基本单位，共享进程的内存空间和资源，线程切换的开销较小

5.什么是抖动

当系统频繁地在内存和磁盘之间进行页面交换（Page Swapping）时，会导致 CPU 的大部分时间都花在处理页面置换上，而不是执行实际的任务，从而导致系统性能急剧下降。这种现象被称为抖动

原因：内存不足；页面置换算法不合理

6.简述PCB的内容

PCB 是操作系统中用于管理和控制进程的核心数据结构，包含了进程的标识信息、状态信息、调度信息、上下文信息、内存管理信息、文件管理信息、资源使用信息、进程通信信息和统计信息。通过 PCB，操作系统可以高效地管理进程的生命周期、资源分配和上下文切换。