导图社区操作系统

操作系统

计算机操作系统思维导图，给各位小伙伴参考。

编辑于2020-09-07 09:28:50

阿龙

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

操作系统
计算机操作系统思维导图，给各位小伙伴参考。

操作系统

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

阿龙

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

操作系统
计算机操作系统思维导图，给各位小伙伴参考。

相似推荐
大纲

互联网9大思维
- 33.8k
- 906
- 2.4k
- 390
MindMaster
安全教育的重要性
- 6.5k
- 853
- 97
- 18
issen
组织架构-单商户商城webAPP 思维导图。
- 14.6k
- 3
- 184
- 10
Kacyun
个人日常活动安排思维导图
- 7.2k
- 0
- 78
- 0
少儿栏目外景策划波波老师
域控上线
- 1.6k
- 162
- 11
- 4
jackrao
西游记主要人物性格分析
- 15.2k
- 1.3k
- 636
- 105
issen
17种头脑风暴法
- 194.0k
- 3.8k
- 11.6k
- 3.9k
MindMaster
python思维导图
- 5.4k
- 523
- 242
- 7
(*^▽^*)
css
- 1.2k
- 1
- 43
- 3
A张舫
CSS
- 3.2k
- 261
- 188
- 33
journey

操作系统

操作系统概述

概念、功能和目标

概念

功能和目标

系统资源管理者

处理机管理

存储器管理

文件管理

设备管理

用户和系统间接口

命令接口

联机

脱机（批处理）

程序接口

系统调用命令，通过程序间接使用

对硬件的拓展

扩充机器（虚拟机）

特征

并发

并发concurrency

两个或多个事件宏观同时发生，微观交替发生

并行parallelism

两个或多个事件同一时刻发生

共享

互斥共享

摄像头

同时共享（同一时间段内同时）

发送文件

虚拟

例如复用、虚拟内存等

异步

进程走走停停（原因：并发）

发展和分类

单道批处理

多道批处理

分时操作系统

实时操作系统

运行机制和体系结构

运行机制

指令instruction

处理器能识别、执行的命令

分类

特权指令

不允许用户程序使用，例如内存清零

非特权指令

例如普通运算指令

如何判断是否可以执行特权指令？

处理器状态

用户态（目态、0）：非特权

核心态（管态、1）：特权+非特权

以此分类程序

内核程序

能执行特权指令，运行在核心态

应用程序

用户态

内核

体系结构

大内核：计算机层次结构中内核下面两层

微内核：计算机层次结构图中内核最底层

中断和异常

中断的基本概念

有了中断，单道批处理->多道批处理

CPU收到中断，切换为核心态处理中断

中断是用户态->核心态切换的唯一途径

核心态->用户态：执行一个特权指令，将程序状态字PSW的标志位设置为用户态（0）

中断的分类

内中断（异常、例外、陷入）

信号来源

CPU内部

与当前执行指令有关

分类

自愿中断

指令中断

强迫中断

硬件故障（缺页）

软件故障（x/0）

分类

陷阱

有意为之

故障

错误条件引起，可恢复

终止

不可恢复

外中断（狭义的中断）

信号来源

CPU外部

与当前执行指令无关

例如

外设请求，例如打印机完成任务后

人工干预，用户终止进程

系统调用

组成程序接口

避免各个进程随意使用系统资源，统一通过系统调用进行管理

需要在核心进行，需要特权指令

高级语言：应用程序->库函数->系统调用

进程与线程

进程基础

进程的定义

单道程序

计算机的所有资源，包括IO等都是单个程序的

多道程序

引入进程、进程实体的概念

系统需要记录每个程序运行到哪里，数据在哪里，分配了哪些系统资源

进程实体

PCB进程控制块（描述进程的各种信息）

程序段

数据段

PCB是进程存在的唯一标志

创建进程=创建PCB

撤销进程=撤销PCB

进程定义、

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

定义重点

动态性

进程的组成

程序段：代码

数据段：程序运行时使用的、产生的数据（变量，宏定义的常量）

PCB：操作系统管理程序运行所需信息

进程描述信息

PID

UID

进程控制+管理信息

资源分配清单

处理机信息

进程的组织

链接

索引

进程的特征

动态性

并发性

独立性：资源分配及调度的基本单位

异步性

结构性

进程的状态及其转换

五种状态

三种基本状态

运行态

就绪态

阻塞态

另外两种状态

创建态

终止态

进程的转换

进程控制

定义

控制进程状态转换

原语

防止PCB修改内容和修改队列中间插入其他操作导致系统错误

实现方式

关中断

原语代码

开中断

核心态下的特权指令

功能

更新PCB信息

将PCB插入合适的队列

分配、回收资源

分类

创建

终止

阻塞+唤醒

切换

进程通信

原因

各个进程的内存地址空间相互独立

方式

共享储存

两个进程对共享空间访问必须是互斥的（P、V操作）

分类

基于数据结构

低级通信方式

效率低

对数据格式有限制

基于存储区

数据的形式、存放位置由进程控制

操作系统只在内存中划出一块共享区域

高级通信方式

效率高

管道

连接读写进程的一个共享文件

本质

内存中一个大小固定的缓冲区

半双工

同一时间内只能单向传输

如果要全双工：两个管道

工作流程

管道写满：写进程的write()系统调用将被阻塞

管道变空：读进程的read()系统调用将被阻塞

没写满不允许读，没读空不允许写

数据读取时被抛弃，所以只能有一个读进程

消息传递

格式化消息

消息头+消息体

分类

直接通信

消息->接收进程的消息缓冲队列

间接通信

消息->信箱->接收进程

线程

为什么要线程

进程

串行->并行

进程内：串行的执行程序代码

只有进程的问题

QQ同时可以

视频

文字聊天

传送文件

显然，不能通过一个程序顺序处理就可以实现

引入线程

增加进程内部的并发度

线程

CPU的基本执行单元

程序执行流的最小单位

（进程：除CPU外的系统资源的分配单位）

线程和进程对比

线程的属性

分类

用户级线程

线程管理工作由应用程序负责

对用户不透明，对操作系统透明

不需要切换到核心态

内核级线程

线程管理工作由操作系统负责

需要切换到核心态

处理机分配的单位

多线程模型（内核级线程和用户级线程）

一对一模型

优点

开销小、效率高

不需要切换核心态

缺点

一个用户级线程被阻塞时，整个进程都会被阻塞

只能单核运行

一对多模型

和一对一相反

多对多

结合两者优点

处理机调度

调度的三个层次

高级调度

作业从后备队列调入

外存和内存之间的调度

每个进程只有一次

中级调度

引入虚拟存储技术、提高内存利用率和系统吞吐量

挂起状态

暂时调到外存等待的进程状态

PCB常驻内存（挂起时仍需对进程进行管理，管理信息在PCB中）

分类（七状态模型）

就绪挂起

阻塞挂起

从挂起队列调入内存为中级调度

低级调度（进程调度）

就绪->运行

高频

进程调度（低级调度）的时机、切换

进程调度的时机

需要进行

主动放弃

被动放弃

不能进行

处理中断的过程中

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

临界资源

各个进程互斥访问的资源

例如打印机打印中，临界资源不会解锁，此时如果不进行进程调度，则CPU空闲

内核程序临界区

用来访问内核数据结构，例如进程的就绪队列

例如进程A在访问就绪队列的内核程序临界区，则其会对就绪队列上锁，在退出临界区以前，其他程序无法访问就绪队列，也就无法完成进程调度

原语

进程调度的方式

非抢占式

开销小，但是无法及时处理紧急任务，适合批处理系统

抢占式

分时、实时操作系统

广义的进程调度

狭义的进程调度

就绪队列中选择要运行的进程

进程切换

一个进程让出处理机，另一个进程占用处理机

步骤

保存原来运行进程的数据

恢复新的运行进程的数据

调度算法的评价指标

CPU利用率

系统吞吐量=作业数/时间

周转时间

等待高级调度

等待I/O时间

等待低级调度

CPU执行时间

等待时间

作业

建立进程后等待时间+建立进程前在外存中后备队列等待时间

进程

进程建立后的等待时间，IO算作服务，不计入等待时间

响应时间

调度算法

分类

批处理系统

先来先服务FCFS

算法思想

公平

规则

先来先服务

作业调度还是进程调度

作业调度：哪个作业先到达后备队列

进程调度：哪个进程先到达就绪队列

抢占式非抢占式

非抢占式

优缺点

简单，公平

带权周转时间特别大，对长作业有利，对短作业不利

饥饿

不会

短作业优先SJF

算法思想

追求较少平均等待时间，平均周转时间，平均带权周转时间

规则

短作业优先

作业调度还是进程调度

作业SJF，短作业优先

进程SPF，短进程优先

抢占式非抢占式

SPF/SJF

非抢占式

最短剩余时间优先算法SRTN（Shortest Remaining Time Next）

抢占式

优缺点

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

饥饿

会产生饥饿

高响应比优先HRRN

算法思想

响应比优先

规则

响应比=（等待时间+要求服务时间）/（要求服务时间）

作业调度还是进程调度

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

抢占式非抢占式

非抢占式

优缺点

综合前两者

饥饿

不会饥饿

交互式系统

时间片轮转

算法思想

公平

规则

轮流

作业调度还是进程调度

进程调度：时间片是CPU的时间片，只有建立了进程后才能被分配时间片

抢占式非抢占式

抢占式

优缺点

优点

公平

响应快

缺点

切换有开销

不区分任务的紧急程度

饥饿

不会

优先级调度

算法思想

实时操作系统需要处理紧急任务

算法规则

优先级

系统进程优先

前台进程优先

I/O繁忙型进程优先

作业调度还是进程调度

作业调度+进程调度+I/O调度

抢占式非抢占式

都有

优缺点

优点：灵活

缺点：饥饿

饥饿

会产生饥饿

多级反馈队列

算法思想

折中

算法规则

多级队列

优先级从高到低

时间片从小到大

FCFS，用完时间片后放入下一级队列队尾

作业调度还是进程调度

进程调度

抢占式非抢占式

抢占式

优缺点

饥饿

会产生饥饿（源源不断的短进程）

同步、互斥

概念

什么是进程同步（直接制约关系，各进程需要直接合作）

异步性：并发执行的进程以各自独立的、不可预知的速度向前推进

进程同步机制：控制并发的程序运行的顺序

什么是进程互斥（间接制约关系）

资源共享方式

互斥：临界资源

同时

对于临界资源的访问，必须互斥的进行

四个部分

进入区（上锁）

临界区（访问临界资源）

退出区（解锁）

剩余区（其他）

原则

空闲让进

忙则等待

有限等待

让权等待（释放CPU，防止忙等待）

进程互斥实现方式（软件）

单标志法

进程访问完临界区后权限转交

每个进程进入临界区的权限只能由另一个进程赋予

缺点

违背空闲让进

P0允许访问，但是P0一直不访问，则P1无法访问临界区（P1进入的权限只能由P0赋予）

双标志先检查

boolean flag[n]标记各个进程想进入临界区的意愿

先检查，后设置flag[i]=true，进入临界区

缺点

违背忙则等待

检查和上锁不是一气呵成，导致两个进程同时进入临界区

双标志后检查

后检查

缺点

违反空闲让进，有限等待

Peterson算法

flag[n] + turn

未遵循让权等待的原则

进程互斥实现方式（硬件）

中断屏蔽方法

利用开、关中断指令

过程

关中断（只对单核有用）

临界区

开中断（只对单核有用）

优点

简单高效

缺点

不适用于多处理机

只适用于内核进程（开关中断只能在内核态运行）

TestAndSet

硬件实现，执行过程不允许中断

优点

适用于多处理机

缺点

不能满足让权等待（while(TestAndSet(&lock));）

Swap指令

硬件实现，执行过程不允许中断

算法和TAS逻辑相同，所以优缺点和TAS一样

优点

适用于多处理机

缺点

不能满足让权等待（while(TestAndSet(&lock));）

信号量

使用操作系统提供的一对原语来对信号量进行操作

信号量

实质

变量

表示

系统资源数量

实现方式

原语

关中断+开中断

将检查和上锁放在关中断+开中断之间

原语

wait(S) = P(S)

signal(S) = V(S)

分类

整型信号量

操作

初始化

用法

wait(S);

使用打印机资源

signal(S);

不满足让权等待，会发生忙等

记录型信号量（解决忙等）

核心：自我阻塞

信号量机制实现进程互斥

互斥信号量mutex

初始值=1

信号量机制实现进程同步

同步信号量semaphore

初始值=0

信号量机制实现前驱关系

每一对前驱关系都是一个进程同步问题

设置多个s=0

生产者消费者问题

单生产者+单消费者

生产，消费的代码不要放在PV操作之间，否则降低并发度

多生产者+多消费者

吸烟者问题

读者写者问题

要求

只允许一个写

允许多个读

写完成前不允许读写

写之前其他读写退出

实现方式

添加count变量，记录读进程

第一个读进程加锁

if(count==0)P(rw); count++;

最后一个读进程退出时解锁

count--; if(count==0)V(rw);

一个rw=1实现文件互斥

一个mutex实现读进程加锁和count++，count--和解锁一气呵成

上述算法问题

饥饿

只要有读进程，写进程就需要一直等待

解决

w=1用于解决写进程饥饿

在写进程整体和读进程加锁外围加上P(w)和V(w)

哲学家进餐

重点

每个哲学家需要同时持有两个临界资源才可以执行

导致

可能产生死锁

如何防止死锁

最多四个哲学家吃饭

奇数哲学家优先左边筷子，偶数优先右边筷子

仅当哲学家左右两只筷子都可以使用时才可以拿起筷子

管程

信号量机制问题：

编写程序困难

易出错

思想

封装

管程的定义和特征

类似于一个类

仅允许一个进程在管程内执行某个内部过程（方法）

由编译器实现各进程互斥进入管程中的过程（方法）

管程中设置条件变量和wait、notify解决同步问题

Java中的synchronized

同一时间只能被一个线程调用

死锁

必要条件

互斥

不可剥夺

请求和保持

循环等待

处理策略

预防

破坏死锁的必要条件

互斥

例如SPOOLing技术，将独占设备变成共享设备

不剥夺

方案

方案一、请求资源不能得到满足时，释放所有资源（饥饿问题）

方案二、按优先级强制剥夺

缺点

实现复杂

可能导致前一阶段工作失效，一般只能用于易保存易恢复的资源，如CPU

反复申请释放资源，降低系统吞吐量

方案一饥饿

请求和保持

方案

一次性申请

缺点

系统资源严重浪费

对资源需求大的进程饥饿

循环等待

方案

顺序资源分配法：按编号从小到大分配资源

缺点

不方便新增设备

资源浪费

编程麻烦

避免

防止系统进入不安全状态（银行家算法）

安全序列

系统以这种序列分配资源，则每个进程都能顺利完成

可能有多个

安全状态

存在安全序列

不安全状态

分配了一个资源后，找不出一个安全序列

有可能死锁

有可能回到安全状态

算法思想

以是否会进入安全状态决定是否分配资源

检测和解除

死锁检测

资源分配图

两种节点

进程节点

资源节点，代表一类资源

两种边

请求边：进程指向资源

分配边

可完全简化=没有死锁发生（其实就是找到了一个安全序列，系统处于安全状态）

消除不掉的边连接所有死锁进程

死锁解除

资源剥夺法

挂起死锁进程，抢占资源

撤销进程法

代价很大

进程回退法

回退到可以避免死锁的点

操作系统需要记录进程历史信息

内存

基础知识

什么是内存

CPU<-内存<-外存

内存地址

每个地址对应一个存储单元

一个存储单元由计算机按什么编址

逻辑地址

相对位置

链接方式（形成完整的逻辑地址）

静态链接

装入时链接

运行时动态链接

装入方式（形成物理地址）

绝对装入（单道）

只适用于单道程序环境

静态重定位（早期多道批处理）

装入程序负责逻辑地址->物理地址，直接加

装入时分配全部内存空间

运行期间不能移动

动态重定位

动态运行时装入

运行时进行重定位

内存管理的概念

内存空间的分配与回收

内存空间的虚拟（逻辑）扩充

地址转换（逻辑->物理）

内存保护（各自在自己的内存空间工作，互不干扰）

方法一、CPU中设置一对上下限寄存器

方法二、采用重定位寄存器（start）+界地址寄存器（length）

覆盖与交换

内存空间的扩充

覆盖（淘汰）

解决

程序大小超过物理内存综合

思想

程序分段

常用段常驻内存的固定区

不常用的段放在内存覆盖区

按照自身逻辑结构，让那些不可能同时被访问的程序共享同一个覆盖区

缺点

必须由程序员声明，对用户不透明

同一个程序或者进程中

交换

思想

内存空间紧张时，将内存中某些进程暂时换出外存

PCB常驻内存，进程挂在挂起队列

实现

不同进程和作业之间

虚拟存储

分配管理方式

连续分配

单一连续分配（只能有一道用户程序，内部碎片）

系统区

用户区

固定分区分配（内部碎片）

分区大小相等

分区大小不等

动态分区分配（外部碎片）

系统使用什么数据结构记录内存的使用情况

空闲分区表

空闲分区链

分配的算法

四种动态分区分配算法

首次适应（最好）

从低地址顺序查找

不需要对空闲分区链/表进行重新排列

最佳适应

按容量由小到大查找

缺点

每次分配几乎都会产生很小的外部碎片

所以这种算法会有很多的外部碎片

最坏适应算法

按容量由大到小

缺点

“大进程”无处安放

临近适应算法

首次适应始终从低地址开始查找，导致低地址部分出现很多小的空闲分区，大部分查找都会跳过它们

临近适应算法改为从上次查找结束的位置开始查找，降低查找的开销

不需要对空闲分区链/表进行重新排列

高地址部分的大分区容易被使用，大进程无处安放

分配和回收的过程

外部碎片通过紧凑来解决

非连续分配

基本分页管理

地址是一维的

如何实现地址转换

页号

页面在内存中起始地址

页表

每个进程一个页表

页表每行为一个页表项

页表项=页号（逻辑地址）+块号（物理地址）

进程每一页对应一个页表项

每个页表在内存中连续存放

页号=index，不需要显示表示

页内偏移量

逻辑地址=concat（页号，页内偏移量）

基本地址变换机构

页表寄存器

两次访问内存

页表

访问目标内存单元

具有快表的地址变换机构

局部性原理

时间局部性

最近访问过，不久后它可能再次被访问

空间局部性

访问了某个存储单元，不久后它附近的也可能会被访问

快表TLB

高速缓冲存储器

快表命中的话，只需一次访问内存+一次访问告诉缓冲存储器

两级页表

单级页表的问题

所有页表项都需要连续存放，需要较大的连续空间

没有必要让所有页表项都常驻内存（局部性原理）

解决

问题一：套娃

页目录表+非连续存放的页表

问题二：虚拟存储技术

不在内存中，产生缺页中断，调入内存

基本分段存储管理方式

段

按程序自身逻辑划分

分配规则

每个段各自连续，各段可以不相邻

优点

编程方便，程序可读性更高

段号+段内地址

段表

分段、分页对比

分页

系统需求，对用户不可见

页的大小固定

地址是一维的

分段

更好的满足用户需求，对用户可见，用户编程需要给出段名

段的长度取决于用户的程序

地址是二维的

更容易实现信息的共享和保护

外部碎片

段页式管理

段号+页号+页内偏移量

虚拟内存

内存空间的扩充方式

覆盖

交换

虚拟存储

传统存储管理方式缺点

一次性

作业必须一次性装入内存才能运行

导致

大作业无法运行

并发度低

驻留性

装入后一直驻留直到结束

局部性原理（时间、空间）+高速缓存

特征

多次性

多次装入

对换性

无需一直常驻，可换入换出

虚拟性

从逻辑上扩充了内存

必然采用离散分配

请求分页

请求分段

请求段页式

请求分页

新增功能

请求调页、段功能

页面、段置换功能

页表新增字段

状态位

是否在内存中

访问字段

换出时供参考

修改位

没有修改的不需要写回外存

外存地址

缺页中断机构（内中断的故障）

缺页的进程阻塞

页面置换算法

最佳OPT

以后永久不被使用或者最长时间不再使用的页面

无法实现，用于衡量别的算法

先进先出

Belady异常

为进程分配的物理块数增大，缺页次数不降反增

算法性能差

最先进入的通常最容易被访问