导图社区计算机操作系统

计算机操作系统

王道考研计算机408计算机操作系统完整导图（含所有概念，且针对每个概念附带小题考察）学习整本书，靠整个导图就够啦~

编辑于2023-04-20 12:39:51 山东省

王道
计算机408
整本书
附带题目

教主

他的近期作品查看更多>>

计算机操作系统

社区模板帮助中心，点此进入>>

教主

他的近期作品查看更多>>

相似推荐
大纲

互联网9大思维
- 30.8k
- 2.2k
- 360
MindMaster
组织架构-单商户商城webAPP 思维导图。
- 13.8k
- 176
- 15
Kacyun
域控上线
- 1.5k
- 10
- 5
jackrao
python思维导图
- 5.1k
- 230
- 8
(*^▽^*)
css
- 1.2k
- 41
- 5
A张舫
CSS
- 3.1k
- 187
- 33
journey
计算机操作系统思维导图
- 3.9k
- 196
- 21
journey
计算机组成原理
- 1.4k
- 70
- 10
journey
IMX6UL(A7)
- 475
- 5
- 1
Handler XU
考试学情分析系统
- 611
- 10
- 1
蒋龙

（操作系统）

第一章总框架

1.1概述

概述

概念

控制整个计算机系统的软硬件资源

合理组织、调度计算机的工作与资源的分配，进而为其他软件提供方便接口和环境的程序集合

特征

并发

操作系统的并发性是指计算机系统能同时运行多个程序

宏观上并行、微观上串行

并行与并发

并发微观上仍是多个程序交替执行

并行是同一时刻运行多个程序、需要硬件支持

共享

定义

系统中的资源能供多个并发进程共同使用

分类

互斥共享方式

规定一段时间内仅允许一个进程访问该资源

称为临界资源或独占资源

如打印机、磁带机

同时访问方式

可供多个进程宏观上“同时”访问、微观上“分时共享”

如磁盘、重入码编写的文件

虚拟

定义

把一个物理实体变成若干逻辑上的对应物

技术

时分复用技术

空分复用技术

多道程序技术

虚拟处理器

只有一个CPU、但能为多个用户服务、让用户感觉CPU只为自己服务

虚拟存储技术

虚拟内存

从逻辑上扩充存储器容量

虚拟设备技术

虚拟设备

将一台I/O物理设备虚拟为多台逻辑上的I/O设备、使原理仅允许一段时间内一个用户的独占设备使用变成一段时间内多个用户使用的共享设备

异步

定义

多道程序允许多个进程并发执行、但资源有限、进程的执行不是一贯到底、而是走走停停、以不可预知的速度前进、这就是进程的异步性

影响

系统运行在随机环境下、可能会出现不可预知的错误

若运行环境相同、操作系统需保证多次运行结果相同

功能

资源管理

处理机管理

进程控制

进程同步

进程通信

死锁处理

处理机调度

内存管理

内存分配

地址映射

内存保护与共享

内存扩充

文件管理

文件存储空间管理

目录管理

文件读写管理与保护

设备管理

缓冲管理

设备分配

设备处理

虚拟设备

提供接口

命令接口

用户利用这些命令来组织和控制作业的执行

分类

联机命令接口

又称交互式命令接口

强调交互性、适用于分时或时实操作系统

马上给出反馈

脱机命令接口

又称批处理命令接口

相当于用户给出了“任务清单”、系统按清单逐条完成命令

后台自己运行

程序接口

又称系统调用命令、广义指令、编程人员可以利用它来请求操作系统服务

如图形用户界面GUI、即图形接口，调用的接口就是系统调用命令

1.2概述

操作系统分类与发展

手工操作阶段

特点

手工操作、人工干预

用户独占全机

批处理阶段

单道批处理

特点

自动性（无需人工干预）

顺序性

单道性

内存仅允许一道程序

CPU需要等待I/O操作

多道批处理

允许多个程序进入内存在CPU交替运行

特点

多道

宏观并行

微观串行

缺点

不提供人机交互、不能了解运行情况、控制计算机

分时操作系统

将处理机运行时间分成很短的时间片、按时间片流把处理机分配给各联机作业使用

实现人机交互的功能

特点

同时性

分时操作系统可以支持多个用户同时访问计算机，每个用户都可以在自己的终端上进行操作。

交互性

分时操作系统可以实现人机交互的功能，用户可以通过终端输入命令、查看输出等方式与计算机进行交互。

独立性

分时操作系统可以让多个用户同时独立地进行操作，每个用户都可以在自己的进程中执行任务，而不会影响其他用户的操作。

及时性

分时操作系统可以实时响应用户的操作请求，减少等待时间，提高用户的使用效率。

实时操作系统

硬实时操作系统、软实时操作系统

硬实时操作系统：

硬实时操作系统的最重要特点是对任务的执行时间进行严格的限制，任务必须在指定的时间内完成，否则将导致系统出现严重的错误。硬实时操作系统通常用于需要对时间要求十分严格的应用程序，如控制系统、航空航天等。

软实时操作系统：

软实时操作系统对任务的执行时间要求相对宽松一些，可以接受任务完成时间略有超时的情况。软实时操作系统通常用于需要处理大量数据的应用程序，如图像处理、语音识别等。

特点

及时性

实时操作系统需要能够及时响应任务的请求，并保证任务在规定的时间内完成。

可靠性

实时操作系统需要能够保证任务的正确性和可靠性，不能出现系统崩溃等情况。

交互性不如分时操作系统

实时操作系统一般不提供人机交互的功能，因为这会影响任务的执行时间。

网络操作系统和分布式计算机系统

网络操作系统

网络操作系统是一种能够通过网络连接多个计算机的操作系统，可以实现资源共享、任务分配等功能。网络操作系统主要用于大型企业、政府机构等需要共享资源和信息的组织中。常见的网络操作系统有Windows Server、Linux等。

分布式计算机系统

分布式计算机系统是一种由多台计算机通过网络连接形成的计算机系统，其中每台计算机都可以独立地完成一部分计算任务，然后将结果传递给其他计算机继续处理。分布式计算机系统通常用于大规模计算任务，如科学计算、数据处理等。常见的分布式计算机系统有Hadoop、Spark等。

个人计算机系统

个人的手机、电脑等等

1.3概述

操作系统运行环境

CPU的运行状态

用户态（目态）

不允许执行特权指令

用户自编的程序运行在用户态

核心态（管态、内核态）

可以执行特权指令

操作系统内核程序运行在核心态

注：特权指令：如I/O指令、置中断指令、涉及用户不可见寄存器的指令、总体包括系统调用指令、针对时钟、中断、和原语操作的指令

系统内核

操作系统最接近底层、硬件的部分，它负责操作系统和硬件之间的交互

时钟管理

时钟设备通常是一个硬件时钟，可以产生一定的周期性中断信号，用于控制系统的时间精度和时间同步。

中断机制

中断机制是操作系统中的一个核心模块，用于处理各种硬件和软件中断事件。

原语

特点

处于操作系统最底层、最接近硬件的部分

这些程序的运行具有原子性、不可中断

运行时间比较短、调用频繁的程序

例如，P（阻塞）操作和V（唤醒）操作就是操作系统中的原语，它们被广泛应用于进程同步和互斥访问控制等场景中。

系统控制的数据结构及处理

操作系统的数据结构

进程控制块PCB

作业控制块

设备控制块

空闲区登记表

内存分配表

基本操作

进程管理

内存管理

设备管理

中断和异常

中断（外中断）

I/O中断、时钟中断（时间片用完）、人工干预

强迫中断

异常（内中断）

计算机内部发生问题

自愿中断

指令中断

陷入指令trap

强迫中断

硬件故障

软件中断

地址非法、校验错、页面失效、缺页、非法指令、除数为零、用户程序执行特权指令自行中断INT

作用

内中断不能被屏蔽、应立即处理

通过中断方式进行CPU用户态与核心态的切换

系统调用

提供给用户程序的接口，让用户和程序能够调用操作系统

分类

设备管理

文件管理

进程控制

进程通信

内存管理

运行环境

运行环境是指操作系统提供给用户程序的运行时环境。用户程序需要在运行环境下才能正常执行，而运行环境是由操作系统提供和管理的。

运行环境通常包括进程控制块、内存分配和保护、文件系统、设备驱动、系统调用等组件。

Trap指令

操作系统进入管态

又称访管指令、陷入指令、不是特权指令

在用户态执行访管指令、CPU将从用户态切换到核心态、操作系统随之对系统调用进行处理

用户态切换到核心态（目态转到管态）

用户程序调用系统调用

发生一次中断

用户程序产生了一个错误状态

用户程序企图执行一条特权指令

管态转回目态

由核心态切换到用户态一般执行中断返回指令（特权指令）

第一章易错

易错辨析

辨析1

命令接口

作用：用户通过命令接口来进行作业的组织和控制

shell命令解析器

命令解释器

程序接口

作用：用户通过在程序使用这些系统调用命令来请求操作系统的服务

广义指令

即系统调用命令

辨析2

ROM

存放一部分自举程序的区域

附：完整的自举程序放在磁盘启动块上，位于磁盘的固定位，称为启动磁盘/系统磁盘

RAM

系统开机后、操作系统会自动加载到系统区，RAM

辨析3

库函数

语言或应用程序的一部分，运行在用户空间

系统调用

是操作系统的一部分，运行在内核空间中

联系

库函数会使用系统调用实现一些功能，没有使用系统调用的库函数效率更高

辨析4

中断调用子程序

需要保存断点PC以及PSW

子程序调用

仅需保存断点PC

辨析5

大内核

主要功能模块作为一个紧密联系的整体运行在核心态

微内核

需要频繁地在核心态和用户态进行切换

分离了内核与服务、服务与服务

服务越少越稳定

辨析6

特权指令

清内存、置时钟、分配系统资源、修改虚存的段表或页表、修改用户访问权限

在用户态下使用特权指令将产生中断以阻止用户使用特权指令

非特权指令

用户态下运行使用的指令

联系

用户态转换为核心态的唯一途径是中断或异常

刷题

操作系统的功能有？

什么是异步？请简述异步的影响。

什么是虚拟化技术？请简述时分复用技术、空分复用技术、虚拟存储技术和虚拟设备技术。

什么是共享？请简述互斥共享和同时访问共享两种方式。

请简述操作系统的并发特征。

什么是操作系统？操作系统的作用是什么？

设备管理

什么是缓冲管理？为什么需要缓冲管理？

什么是设备分配？有哪些常见的设备分配算法？

什么是设备处理？有哪些常见的设备处理方式？

什么是虚拟设备？有哪些常见的虚拟设备技术？

文件管理

什么是文件存储空间管理？有哪些常见的文件存储空间管理方式？

什么是目录管理？有哪些常见的目录管理方式？

什么是文件读写管理与保护？常见的文件读写方式有哪些？如何保护文件安全？

内存管理

什么是内存分配？有哪些常见的内存分配算法？

什么是地址映射？为什么需要地址映射？

什么是内存保护与共享？有哪些常见的内存保护与共享技术？

什么是内存扩充？常见的内存扩充方式有哪些？

资源管理

什么是进程控制？为什么需要进程控制？

什么是进程同步？举例说明。

什么是进程通信？常见的进程通信方式有哪些？

什么是死锁？死锁的必要条件是什么？如何避免死锁？

什么是处理机调度？常见的处理机调度算法有哪些？

提供接口

什么是命令接口？联机命令接口和脱机命令接口有什么区别？

什么是程序接口？常见的程序接口有哪些？如何利用程序接口请求操作系统服务？

命令接口和程序接口的区别是

什么是中断？分为哪两种类型？

进程管理、内存管理和设备管理分别指什么？它们在操作系统中的作用是什么？

操作系统中的数据结构有哪些？它们各自的作用是什么？

什么是原语？它在操作系统中扮演着什么样的角色？

什么是中断机制？在操作系统中有哪些常见的中断事件？

时钟管理在操作系统中的作用是什么？常用的时钟设备是什么？

什么是特权指令？它的例子有哪些？

什么是核心态？它与用户态有什么区别？

在CPU的运行状态中，什么是用户态？它有哪些特点？

个人计算机系统是指什么？举例说明。

网络操作系统和分布式计算机系统有什么区别？它们的应用场景是什么？

实时操作系统有哪些特点？它们分为哪两类？它们的应用场景有哪些？

分时操作系统有哪些特点？

多道批处理有哪些特点和缺点？

单道批处理有哪些特点？

手工操作阶段有哪些特点？

中断的作用是什么？

什么是系统调用？分类有哪些？

什么是运行环境？运行环境通常包括哪些组件？

什么是Trap指令？在什么情况下会触发Trap指令？Trap指令的作用是什么？

用户态和核心态分别允许执行哪些指令？何时会发生用户态和核心态的切换？

第二章总框架

2.1.1进程与线程

进程

概念

进程是进程实现运行的过程、是系统资源分配是调度的基本单位

特征

动态性

具有生命周期

并发性

提高系统资源利用率

独立性

独立运行、调度、拥有资源

异步性

执行的间断性、需要操作系统提供同步机制

结构性

进程结构：PCB、程序段、数据段、

进程状态与转换

状态：运行态、就绪态、阻塞态、创建态、结束态（前三为基本态）

阻塞态是缺少处理机和某些别的资源就绪态是仅仅缺少处理机资源

转换

运行态→就绪态

时间片用完/更高优先级进程抢占

就绪态→运行态

获得处理机调度

运行态→阻塞态

等待除了处理机的某资源（主动行为）

只有处于运行态的进程才有可能将其转换为阻塞态

自我调用阻塞原语

阻塞态→就绪态

等待的事件到来（被动行为）

其他进程调用唤醒原语

进程控制

创建

分配唯一的进程标识号、申请PCB（申请失败则创建失败）

分配资源、内存空间、（若资源不足、并非创建失败、而是进入阻塞态）

初始化PCB的信息

终止

正常结束

异常结束

存储越界、保护错、非法指令、特权指令错、I/O故障

阻塞和唤醒

必须成对使用

切换

进程切换是在内核支持下实现的

辨析1

进程切换

运行进程改变了、环境信息改变了

处理机模式切换

用户态←→核心态、CPU现场改变、进程环境无需改变

辨析2

调度

决定将资源分配给哪个进程、是决策行为

切换

实际分配行为、执行行为

先有调度后有切换

进程组织

PCB（进程控制块）

进程存在的唯一标识，常驻主存

PCB内容

描述信息、控制和管理信息、资源分配清单、处理机相关信息（存放CPU各寄存器值）

PCB的组织方式

链接方式

索引方式

程序段

能被调度在CPU执行的代码段、可被多个进程共享

数据段

进程的原始数据或进程加工数据的中间结果或最终结果

一个进程由上述三部分组成（环境、程序、数据）

进程通信

操作系统提供同步互斥工具PV操作、具体数据交换用户自己实现

定义

指进程之间的信息交换、PV操作是低级通信方式、以下为高级通信方式

共享存储

定义

进程间存在一块可直接访问的共享空间

高级共享方式

基于存储区的共享

低级共享方式

基于数据结构的共享

消息传递

定义

进程间的数据交换以格式化的消息为单位、通过发送消息和接收消息原语进行数据交换

方式

直接通信方式

发送的消息挂在消息缓冲队列

间接通信方式

发到中间实体“信箱”，因此也称“信箱通信方式”

管道通信

定义

实现读进程和写进程通信的共享文件（pipe文件，是一种文件系统）

管道机制的功能

互斥、同步、确定对方存在

特点

固定缓冲区、半双工通信、读完才能写、写完才能读

2.1.2进程与线程

线程

引入目的

减小程序在并发执行的时空开销

定义

线程是进程的一个实体，是CPU基本的执行单位，是程序执行流的最小单位。

属性

是被系统调度和分派的基本单位，作为处理机的基本分配单位

不独立拥有资源，与其他线程共享进程拥有的资源

进程切换时空开销大、同一进程下的线程切换开销小

由于共享进程资源，线程之间的通信很容易，甚至不需要操作系统干预，线程间可以直接读/写进程数据段来通信

也有就绪、阻塞、运行等基本状态

实现方式

用户级线程

有关线程的管理工作都由应用程序完成，内核意识不到线程的存在

内核级线程

有关线程的管理工作都由内核完成，应用程序只有一个内核级线程的编程接口

组合方式

用户级线程与内核级线程的组合实现

多线程模型

实现用户级线程与内核级线程的连接方式

分类

多对一模型

多个用户级线程映射到一个内核级线程，线程管理在用户空间完成，执行在内核空间

缺点：一个线程在内核中运行阻塞，整个进程阻塞，多个线程不能并发执行（因为在内核只有一个线程）

一对一模型

一个用户级线程映射到一个内核级线程

并发能力强，但创建内核线程过多开销大

多对多模型

n个用户级线程映射到m个内核线程，m<=n

一对一模型和多对一模型的折中，提高并发性和资源利用率

2.2处理机调度

处理机调度

概念

哪个进程先执行的问题

从就绪队列中按照一定算法选择一个进程分配处理机给它运行

层次(调度方式）

高级调度、作业调度

从外存上处于后备状态的作业中挑一个，分配内存、资源，建立相应进程

从外存到内存的调度

每个作业只调入一次、调出一次

中级调度、内存调度

为了提高内存利用率和系统吞吐量，将暂时不能运行的进程调到外存（挂起状态），将能运行的进程从外存调到内存

低级调度、进程调度

按照某种策略在就绪队列挑选一个进程分配处理机给它

能否调度

不能调度与切换

处理中断的过程中

当CPU正在处理一个中断时，由于中断服务程序需要运行在特权模式下，因此不能被其他进程打断，此时不能进行调度和切换。

进程在操作系统内核程序的临界区中

当一个进程进入了内核的临界区（也称为互斥区）时，由于内核正在处理当前进程的请求，因此不能切换到其他进程。此时，不能进行调度和切换。

完全屏蔽中断的原子操作过程中

完全屏蔽中断的原子操作过程中：在某些情况下，为了保证对共享资源的操作是原子的，必须关闭中断，此时不能进行调度和切换。

应该调度与切换

方式

非剥夺式

一旦CPU分配给一个进程，该进程就会保持CPU直至运行结束或转换到等待态

适合批处理系统、不能用于分时系统和实时系统

剥夺式

遵循一定原则的情况下，切换正在运行的进程

原则：优先权、短进程优先、时间片原则

评价准则（调度算法）

CPU利用率

系统吞吐量

单位时间内CPU完成的作业数量

周转时间

作业提交到作业完成的时间

公式

周转时间 T

作业完成时间-作业提交时间

平均周转时间

每个作业周转时间的平均值

(作业1 T+作业2T+……+作业nT)/n

带权周转时间

周转时间/实际运行时间

平均带权周转时间

每个作业的带权周转时间的平均值

等待时间

等待处理机的时间和

响应时间

从提交到首次响应的所用的时间

交互式系统中，响应时间是衡量调度算法的重要准则之一

算法

先来先服务算法（FCFS）

顺序

属于不可剥夺算法

对短作业不利，对长作业有利

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

短作业优先算法（SJF）

时间长短

对短作业有利、对长作业不利

可能会导致长作业的“饥饿”现象

平均等待时间、平均周转时间最少

优先级调度算法

优先级

优先级用于描述作业的紧迫程度

算法分类

非剥夺式优先级调度

剥夺式优先级调度

优先级分类

静态优先级

进程创建时已确定、不可改变

动态优先级

可以动态调整

优先级原则

系统进程>用户进程

交互进程（前台）>非交互进程（后台）

I/O型进程>计算进程

高响应比优先算法

FCFS与SJF算法的平衡

服务时间短、响应比高，利于短作业(体现SJF)

等待时间长，响应比也会提高，同时兼顾长作业（体现FCFS）

克服了饥饿现象

时间片轮转算法

主要适用于分时操作系统

划分时间片，先来先服务，时间片到就被剥夺处理机

执行结束、时间片还有时间、也要释放处理机

多级反馈队列调度算法

时间片轮转算法和优先级调度算法的综合，通过动态调整优先级和时间片大小

设置多个就绪队列、赋予不同优先级

每降一个优先级的队列时间片递增

优点

短作业优先、周转时间短

长作业也能得到处理（但没有处理完的部分可能会饥饿）

2.3.1进程同步

进程同步

概念

同步

一次允许多个进程参与某个过程

进程的直接制约关系，同步源于进程的相互合作

因为多道程序下进程并发运行，具有异步性，想要协调进程之间的制约关系，需要引入同步机制。

同步机制

空闲让进

忙则等待

有限等待

让权等待

临界资源

定义

一次仅允许一个进程访问的资源，如大多数的物理设备，也有某些变量、数据也是临界资源

组成

进入区

检查临界区标志/设置正在访问临界区标志

临界区

进程访问临界资源的代码段（临界段）

退出区

清除正在访问临界区标志

剩余区

互斥

进程的间接制约关系，进程访问临界资源的制约关系

临界区互斥的方法

软件实现法

单标志检查法

进入区：turn = 1，1为允许进入临界区的进程编号

退出区：turn = 0，允许1号进程进入临界区

这种算法进程只能交替进入临界区

当P1离开，turn = 0、进程0不访问，但进程1还是不能访问，违背“空闲让进”

双标志先检查法

先检查对方标志、再设置自己标志

进入区

①while（flag[i]）；检查，进程i在访问则等待、

②flag[j] = true；进程j标志自己在访问临界区

退出区

flag[j]=false ；进程j不使用临界区

特点

这种算法不用交替进入、可以连续使用，但是当进程检查标志后可能发生进程切换，可能会出现同时访问临界区的情况，违背了“忙则等待”

双标志后检查法

先设置自己标志、再检查对方标志

进入区

flag[i] = true；进程i设置自己的标志

while(flag[j])；检查进程j是否在访问临界区

退出区

flag[i] = false；

特点

这种算法不会导致同时访问临界区的现象，但进程相互谦让可能会导致“饥饿”现象

Perterson算法

为了防止同时进入、也为了防止无限等待、设置了变量turn

进入区

flag[i]=true;turn = j; i想访问、但是先让j进

while(flag[j]&&turn = j); 等待

特点

相互谦让、最后一个谦让的等待

不符合让权等待

用flag解决互斥访问、用turn解决了“饥饿”现象

是单标志检查法和双标志后检查法的结合

硬件实现法

通过硬件支持实现临界区互斥访问的方法称为低级方法、元方法

中断屏蔽方法

关闭系统的中断功能

关中断→临界区→开中断

限制了处理机交替执行程序的能力、中断权利交给用户不安全。

硬件屏蔽方法

原子操作、不会被中断

TestAndSet

while TestAndSet(&lock)

Swap

简单、但不符合“让权等待”，也可能会导致“饥饿”现象

2.3.2进程同步

经典同步问题

信号量机制

定义

解决同步互斥问题的机制

整型信号量

整型信号量被定义为一个用于表示资源数目的整型量S

缺点

只要信号量S<=0，就会不断测试，违背“让权等待”原则

记录型信号量

不存在“忙等”现象的进程同步机制

数据结构

用于表示资源数value、等待资源的等待队列

原语

wait（S）;申请一个资源，资源数S<0，进程自我阻塞，放到等待队列

signal(S);释放一个资源，若资源数此时S<=0，唤醒一个进程

作用

实现同步

进程间执行具有先后次序

设置信号量 semaphore = 0；

实现互斥

进程间互斥访问临界区

设置信号量 semaphore = 1；

实现前驱关系

实际上就是实现同步、只是不同语句之间的次序不同，需要设置多个信号量，且都为0；

分析过程

①找出进程数、分析是同步问题还是互斥问题，还是同步互斥的综合问题

②确定进程执行的次序（同步），资源数、

③设置信号量，S=0（同步），S=1（互斥），S=n（资源数）

经典同步问题

生产者-消费者问题

生产者和消费者既存在同步关系、也存在互斥关系

生产者生产了、消费了才能消费（同步）

两者互斥访问临界区——缓冲区（互斥）

读者-写者问题

读者和写者互斥访问文件资源，写者和写者、读者都为互斥关系、但读者不互斥读文件资源

设置计数器count = 0；当一个读者进来count++，一个读者出去count--；最后一个读者释放临界区资源

写进程容易“饿死”

解决写进程“饿死”的方法

读写公平法

相对公平、写进程没有绝对优先

哲学家进餐问题

哲学家与左右邻居是互斥关系，让一位哲学家拿到左右两根筷子但又不造成饥饿或死锁

解决办法

至多允许4名哲学家同时进餐

哲学家互斥拿筷子

吸烟者问题

系统有三个吸烟者一个供应者，吸烟者分别有烟草、胶水、纸，供应者提供这些物品两两的组合，一次提供一种，三个吸烟者轮流吸烟

供应者与吸烟者是同步关系，吸烟者是互斥关系

2.2.4进程管理

死锁

概念

多个进程因争夺资源而造成的相互等待

产生原因

不满足其中之一就不会造成死锁

系统资源的竞争

进程推进顺序非法

死锁产生的必要条件

互斥条件

所请求的资源只能互斥使用

不剥夺条件

进程使用完资源之前不能被强行夺走，只能主动释放

请求和保持

该进程保持了至少一个资源，但又提出新的资源请求

循环等待

存在一种进程资源的循环等待链

处理策略

死锁预防

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

破坏互斥条件

允许资源能共享使用、但某些资源是只能互斥使用的、所以这个方法有局限性

破坏不可剥夺条件

当一个已保持了某些不可剥夺资源但又请求新的资源而得不到满足时。它必须释放已经保持的所有资源

缺点

反复地申请和释放资源会增加系统开销

这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，不能用于打印机等资源

破坏请求和保持条件

采用预先静态分配方法

进程在运行前一次申请完它所需要的全部资源

缺点

系统资源被严重浪费

可能导致进程“饥饿”

破坏循环等待条件

采用顺序资源分配法

给系统的资源编号，规定每个进程必须按编号申请资源，同类资源一次申请完

缺点

限制了新类型设备的增加

可能会造成资源浪费

给用户编程带来麻烦

避免死锁

在分配资源过程中，采取某种办法防止系统进入不安全状态、从而避免死锁

系统安全状态

指系统能按照某种进程推进顺序（P1，P2,……，Pn）为每个进程Pi分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成

并非所有的不安全状态都是死锁状态，但系统进入不安全状态，便可能进入死锁状态

系统处于安全状态，就可以避免进入死锁状态

银行家算法

思想

可用资源分配给某个进程，看是否能满足它当前的全部需求，满足则分配，然后等它运行完，再回收它释放的资源

数据结构

可用资源向量Avaliable

含有m个元素的数组、每个元素代表一类可用资源的数目

最大需求矩阵Max

nxm矩阵，n个进程中每个进程对m类资源的最大需求

分配矩阵Allocation

定义系统中每类资源当前已分配给每个进程的资源数

需求矩阵Need

nxm矩阵，表示n个进程对m类资源尚需的资源数

Need = Max - Allocation

死锁的检测及解除

无须采取任何限制性措施，允许进程在运行过程中发生死锁，通过系统检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁

资源分配图

简化资源分配图可以检测系统状态S是否为死锁状态

死锁定理

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

死锁解除

资源剥夺法

挂起某些死锁进程并抢夺它的资源，以便让其他进程继续推进

撤销进程法

强行撤销部分，甚至全部死锁进程，并剥夺这些进程的资源

可按进程优先级和撤销进程的代价的高低进行

进程回退法

让一个或多个进程回退到足以回避死锁的地步

刷题

针对“概念”节点：

请描述进程的概念是什么？

进程是系统资源分配和调度的基本单位，这意味着什么？

针对“特征”节点：

动态性特征指什么？进程具有什么生命周期？

并发性特征的作用是什么？如何提高系统资源利用率？

独立性特征指什么？进程是如何独立运行、调度和拥有资源的？

异步性特征的意义是什么？为什么需要操作系统提供同步机制？

结构性特征指什么？进程的结构是怎样的？包含哪些组成部分？

针对“进程状态与转换”节点：

进程状态有哪些？基本态有哪些？

进程在什么情况下会从运行态转换为就绪态？

进程在什么情况下会从就绪态转换为运行态？

进程在什么情况下会从运行态转换为阻塞态？

进程在什么情况下会从阻塞态转换为就绪态？

进程控制

创建

解释进程创建的概念

列举创建进程需要进行的步骤

说明资源不足时进程创建的处理方式

终止

区分进程正常结束和异常结束

列举可能导致进程异常结束的情况

阻塞和唤醒

解释阻塞和唤醒的概念

说明阻塞和唤醒必须成对使用的原因

切换

区分进程切换和处理机模式切换的概念

说明进程切换和处理机模式切换的异同

区分调度和切换的概念

解释调度和切换的先后顺序及原因

进程组织：

PCB

解释 PCB 的概念及作用

列举 PCB 的内容和作用

说明 PCB 的组织方式及优缺点

程序段和数据段

解释程序段和数据段的概念及作用

解释环境、程序和数据的概念及它们之间的关系

进程通信：

定义

解释进程通信的概念及作用

区分低级通信方式和高级通信方式的概念

共享存储

解释共享存储的概念及作用

区分高级共享方式和低级共享方式的概念

消息传递

解释消息传递的概念及作用

区分直接通信方式和间接通信方式的概念

管道通信

解释管道通信的概念及作用

说明管道机制的功能

解释管道通信的特点

线程引入的目的是什么？举例说明。

线程的定义是什么？线程是什么实体？

线程有哪些属性？线程和进程之间有什么区别？

线程的实现方式有哪些？分别有什么优缺点？

什么是多线程模型？多线程模型有哪些分类？分别有什么特点？

线程切换开销相对进程切换开销会更小，为什么？

线程之间的通信有哪些方式？它们有什么特点？

用户级线程与内核级线程的组合方式可以如何实现？

一对一模型相对于多对一模型有什么优缺点？

评价准则（调度算法）

什么是CPU利用率？

如何计算系统吞吐量？

什么是周转时间？如何计算平均周转时间和带权周转时间？

什么是等待时间？

什么是响应时间？在交互式系统中，响应时间为何是衡量调度算法的重要准则之一？

调度方式

什么是调度方式？

高级调度和作业调度的作用是什么？

什么是中级调度？其作用是什么？

什么是低级调度？其作用是什么？

能否调度

列举三种不能进行调度和切换的情况。

什么是完全屏蔽中断的原子操作过程？

方式

什么是非剥夺式调度？适用于哪些系统？

什么是剥夺式调度？有哪些原则？

什么是哪个进程先执行的问题？有哪些情况下不能进行调度和切换？

什么是CPU利用率？调度算法中，为什么需要考虑CPU利用率？

什么是系统吞吐量？如何计算系统吞吐量？

什么是周转时间？周转时间的公式是什么？如何计算平均周转时间？

什么是带权周转时间？如何计算带权周转时间？如何计算平均带权周转时间？

什么是等待时间？如何计算等待时间？

什么是响应时间？响应时间对于什么类型的系统是重要的？

总结评价准则中各项指标的主要作用和应用场景。

先来先服务算法（FCFS）

请简要说明先来先服务算法的优缺点，以及其适用的作业类型。

短作业优先算法（SJF）

请简要说明短作业优先算法的优缺点，以及可能导致的问题。

优先级调度算法

请简要说明优先级调度算法的分类，以及静态优先级和动态优先级的区别。

高响应比优先算法

请简要说明高响应比优先算法与FCFS和SJF算法的平衡点在哪里，以及其解决了什么问题。

时间片轮转算法

请简要说明时间片轮转算法适用于哪种类型的操作系统，以及其如何处理长作业和时间片到期但仍未执行完的进程。

多级反馈队列调度算法

请简要说明多级反馈队列调度算法的优点和缺点，并解释可能导致长作业“饥饿”的原因。

请简述同步的概念和作用。

列出同步机制中的四种策略，并简要解释每种策略的含义。

请定义临界资源，并简要介绍其组成。

请解释互斥的概念和作用。

什么是一次允许多个进程参与某个过程？请给出一个例子。

请解释单标志检查法中的"turn"变量的作用以及当P1离开后的问题。

请解释双标志先检查法中的"flag"数组的作用以及可能导致同时访问临界区的情况的原因。

请解释双标志后检查法中的"flag"数组的作用以及可能导致"饥饿"现象的原因。

请解释Perterson算法中的"flag"和"turn"变量的作用，以及与前两种算法的区别。

什么是“关闭系统的中断功能”？

什么是硬件实现法？为什么又称为低级方法、元方法？

中断屏蔽方法的实现原理是什么？有何限制和不足之处？

硬件屏蔽方法中的TestAndSet和Swap指令是什么？它们有何不足？

定义

信号量机制是用于解决什么问题的机制？

整型信号量

整型信号量被定义为什么？

简述整型信号量的缺点。

记录型信号量

记录型信号量能否避免“忙等”现象？

简述记录型信号量的数据结构。

什么是原语，记录型信号量中有哪些原语？

信号量机制的作用

信号量机制可以实现哪些功能？

在实现前驱关系时，需要设置多少个信号量，且它们的初始值应该是多少？

分析过程

信号量机制的分析过程包括哪些步骤？

在分析信号量机制时，需要确定哪些信息？

生产者-消费者问题

简述生产者和消费者的同步关系和互斥关系。

生产者和消费者在访问哪个共享资源时需要互斥？

读者-写者问题

简述读者和写者互斥访问的共享资源。

如何解决写进程“饿死”问题？

简述读写公平法的原理。

哲学家进餐问题

哲学家和哪些实体之间存在互斥关系？

简述如何解决哲学家进餐问题。

吸烟者问题

简述系统中有哪些实体以及它们之间的关系。

哪些实体之间存在同步关系？哪些实体之间存在互斥关系？

多个进程因争夺资源而造成的相互等待被称为什么现象？

以下哪个条件不属于死锁产生的必要条件？

A. 互斥条件

B. 不剥夺条件

C. 请求和保持

D. 可预测性

互斥条件是指什么？

A. 所请求的资源可以同时被多个进程使用

B. 所请求的资源只能互斥使用

C. 进程在请求资源时必须等待其他进程释放资源

D. 进程可以随时剥夺其他进程的资源

请简述不剥夺条件的含义。

在请求和保持条件下，一个进程在保持至少一个资源的情况下，是否可以继续提出新的资源请求？请简述。

以下哪种情况可能导致死锁？

A. 系统资源的竞争

B. 进程推进顺序合法

C. 进程在使用资源时可以被其他进程强行剥夺资源

D. 没有循环等待现象

什么是死锁？简单描述一下。

列举一些造成死锁的原因。

死锁产生的必要条件有哪些？简单描述一下每个条件的含义。

什么是互斥条件？举一个例子。

什么是不剥夺条件？举一个例子。

什么是请求和保持？举一个例子。

什么是循环等待？举一个例子。

死锁预防

列举破坏死锁产生的四个必要条件之一的方法。

简述破坏互斥条件的方法，以及该方法的局限性。

简述破坏不可剥夺条件的方法，以及该方法的缺点和适用场景。

简述破坏请求和保持条件的方法，以及该方法的缺点和适用场景。

简述破坏循环等待条件的方法，以及该方法的缺点和适用场景。

避免死锁

简述系统安全状态的定义。

简述银行家算法的思想和数据结构。

死锁的检测及解除

简述资源分配图的作用。

简述死锁定理的条件。

列举死锁解除的三种方法，并简述其原理。

第三章总框架

3.1内存管理

内存管理

内存的分配与回收

地址转换

逻辑地址转换为物理地址

内存空间的扩充

逻辑上扩充主存、采用虚拟存储技术、自动覆盖技术

内存保护

方法

通过在CPU设置上、下限寄存器、每当CPU要访问地址时，就要跟这个两个寄存器比较，判断有无越界

采用重定位寄存器和界地址寄存器来实现保护

重定位寄存器含最小物理值

界地址寄存器含逻辑地址最大值

每个逻辑地址必须小于界地址寄存器的值

程序的执行过程

编译

由编译程序将用户的代码编译成若干个【目标模块】

链接

由链接程序将编译后的【目标模块】及相关的库函数链接在一起，形成【装入模块】（链接期间形成【逻辑地址】）

分类

静态链接

装入内存前、程序运行前，链接完毕

装入时动态链接

边装入内存边链接

运行时动态链接

程序执行时需要该目标模块时才进行链接

优点是便于修改和更新，便于实现对目标模块的共享

装入

概念

由装入程序将装入模块装入内存

分类

绝对装入

编译程序产生绝对地址的目标代码，逻辑地址与物理地址完全相同

只适用于单道程序环境

静态重定位

又称可重定位装入

多个目标模块的地址都是从0开始，程序中的地址是相对地址

重定位

装入时将目标程序中的指令和数据的修改过程称为重定位

特点

地址变换通常是在装入时一次完成的

一个作业装入时要分配全部的内存空间、运行期间不能移动、也不能再申请空间

动态重定位

又称运行时动态装入

装入模块装入内存后，不立即变换相对地址，而是等到程序运行时才进行地址变换，需要一个重定位寄存器

特点

可以动态申请分配内存、可以分配到不连续的存储区中

程序可以在内存中移动

便于程序段的共享

扩充内存

覆盖技术

把用户空间分成【固定区】和【覆盖区】

经常活跃的部分放在【固定区】

不可能同时被访问的程序段可共享一个【覆盖区】

必须由程序员声明覆盖结构，操作系统完成覆盖

缺点

对用户不透明，增加用户编程负担

交换（对换）技术

概念

把内存中暂时不能运行的进程或暂时不用的程序或数据换出到外存，以便腾出足够的空间，把已经具备运行条件的进程或所需要的程序和数据换入内存

换出

若内存紧张，启动了对换程序，优先选择换出阻塞进程，若无阻塞进程则换出优先级低的就绪进程

若换出程序和数据必须换出的是非共享的程序和数据

换入

对换进程定时执行换入操作，检查PCB集合中所有进程的状态，找出“已就绪”但已换出的进程，将其调入内存（**省略一系列讨论）

磁盘分区

对换区

追求换入换出的速度

采用连续分配方式

被换出的进程的数据就在对换区

文件区

追求存储空间利用率

采用离散分配方式

覆盖与交换的区别

交换主要在不同进程（或作业）之间进行（如中级调度）

覆盖是用于同一个程序或进程中

3.2内存管理

内存管理

连续分配

单一连续分配

特点

此方式下内存分为系统区和用户区，系统区供操作系统使用（通常在低地址部分）

用户区只放一道程序，因此不会发生越界访问等问题。不需要内存保护

无外部碎片、有内部碎片、只能单用户使用、内存利用率极低

固定分区分配

概念

最简单的多道程序存储管理方式，此方式将用户区分为若干个【大小固定】的区域

特点

分区大小相等 / 分区大不相等

有一张分区说明表、分区始址、大小、状态

可能程序太大放不进固定的分区中

无外部碎片、有内部碎片

不能实现多进程共享主存储区、空间利用率低

动态分区分配

概念

在进程装入内存时，根据进程大小动态建立分区

特点

有外部碎片（可以通过“紧凑”技术解决）、无内部碎片

分配策略

首次适应算法FF

空闲分区以【地址递增】的方式进行链接

低地址部分可能会有很多外部碎片、增加了查找开销

最佳适应算法BF

空闲分区以【容量递增】的方式形成分区链

会产生【最多】的外部碎片

最坏（大）适应算法WF

空闲分区以【容量递减】的方式形成分区链

导致很快没有可用的大内存块

产生碎片的可能性最小、查找效率最高

邻近适应算法NF

又称循环首次适应算法

分配内存时从上次查找结束的位置开继续查找

使内存的分配均匀，但可能导致很快没有可用的大内存块

非连续分配

基本页式存储管理

目的

出于计算机设计角度考虑、提高内存利用率、分页通过硬件机制实现、对用户完全透明

分类

根据运行作业是否要把作业的所有页面都装入内存才能运行分为【基本分页式存储管理】【请求分页式存储管理】

基本分页式存储管理

请求分页式存储管理

特点

内存分为大小固定的块、进程也以块为单位进行划分，申请空间时也以块为单位逐个申请

类似于固定分区技术、不会产生外部碎片

会产生内部碎片、但每个进程平均只产生半个块大小的内部碎片（页内碎片）

页面大小固定，地址空间是一维的