操作系统思维导图模板_ProcessOn思维导图、流程图

特征

并发

多个事件在同一时间间隔内发生，宏观上是同时发生，微观上是有先后顺序的交替发生。

并行是指计算机真正具有同时处理多个事件的能力，在同一时刻完成多个事件的工作。（多核cpu）

共享

概念

操作系统管理的资源可供多个并发执行的进程共同使用

互斥共享方式

在特定时间段内只允许一个进程访问其中的资源

同时共享方式

在特定时间段内允许多个进程对资源进行访问。

虚拟

异步

多个进程并发执行，但是由于资源的有限，进程的执行并不是一贯到底的，而是走走停停，以不可预知的速度向前推进。

发展历程

单道批处理系统

多道批处理系统

分时处理系统

实时处理系统

概念

控制管理整个计算机的软硬件资源，组织计算机的工作，并提供给用户和其它软件比较方便的接口，是计算机最基本的系统软件。

功能

资源管理

处理器管理

处理器的分配和运行以进程为基本单位

内存管理

文件管理

设备管理

为用户和其它软件提供管理硬件的接口

命令接口

联机命令接口

脱机命令接口

程序接口

由一组系统调用组成

用户通过系统调用控制操作系统

用作扩充机器

没有软件的计算机叫裸机，有软件的计算机叫扩充机或虚拟机。

运行环境

用户态

应用程序运行的环境。

内核态

内核运行的环境

内核

计算机最底层的软件

时钟管理

中断机制

原语

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

中断（外中断）

cpu正在运行的程序的运行环境从用户态转换为核心态，有了中断才能实现程序的并发执行

外设请求

人工干预

异常（内中断）

资源中断

资源不够用

强迫中断

软硬件故障

进程

概念

系统进行资源分配和调度的基本单位

组成

程序控制块（PCB）

包含操作系统对进程进行管理需要的各种信息。如：进程描述、资源分配清单。

程序段

进程运行所执行的代码

数据段

进程运行过程中使用和产生的数据。如：变量、常量。

组织方式

链接方式

按照进程状态不同，将进程的PCB分为多个队列，操作系统持有指向各个队列的指针。

索引方式

按照进程状态不同，将进程的PCB分为多张索引表，操作系统持有指向各个索引表的指针。

特征

动态性

进程是程序的一次执行过程，动态的产生、变化、消亡。

并发性

内存中可以存在多个进程的实体，多个进程可并发执行。

独立性

进程是资源分配和调度的基本单位，是独立运行的单位。

异步性

进程以不可预测的速度向前推进。

结构性

进程都是由PCB、程序段、数据段组成。

进程的状态

创建态

申请PCB创建进程

就绪态

已经具备运行条件，缺少CPU

运行态

进程占用CPU正在运行的状态

阻塞态

进程因等待某个事件发生而暂时无法运行的状态。

终止态

进程运行结束或出现错误或被系统终止

线程

存在的意义

简化进程间通信，以小开销提高进程内的并发程度。

概述

是进程内执行运算的最小单位，是调度和分派的最基本单位，不拥有系统资源，只拥有一点运行必不可少的资源，但是线程之间可以共享一个进程中的所有系统资源。线程可以创建其它线程，它们之间可以并发执行。

处理机调度

基本准则

CPU利用率

系统吞吐量

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

周转时间

从作业提交到作业完成所经历的时间

等待时间

进程处于就绪状态的总时间

响应时间

用户提出请求到系统首次响应所需要的时间

三级调度

进程调度（低级调度）

将CPU分配给就绪队列中的一个进程

中级调度

为了提高内存的利用率和系统吞吐量，将暂时不能运行的进程调至外存，当它具有运行条件并且内存空间足够时，将它调回内存中，变为就绪态。

作业调度（高级调度）

给外存中处于的后备状态的作业分配内存和设备，建立进程。

进程调度方式

非抢占式（非剥夺式）

当一个进程运行时，即使有其它优先级更高的进程进入就绪队列，仍然让目前运行的进程继续占用CPU，直到进程结束阻塞才将CPU分配给其它进程。

抢占式（剥夺式）

可以根据人为制定的规则，将正在正常运行的进程的CPU分配给其它进入就绪队列中的进程。

调度算法

先来先服务算法FCFS(First come first serve)

先到达的进程/作业,先被OS进程调度（低级调度）/高级调度（作业调度）

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

短作业优先调度算法SJF(Short job first)

作业时间/进程运行时间越短，越先被OS作业调度(高级调度)/进程调度（低级调度）

优点

最短的平均等待时间、平均周转时间

缺点

没有考虑进程/作业的紧迫程度

对长作业不利，会出现饥饿现象

必须先计算作业/运行时间

优先级调度算法

OS根据优先级次序进行作业调度/进程调度（分抢占式/非抢占式）

优点

可以区分进程/作业的紧迫程度

缺点

优先级低的进程/作业可能会出现饥饿现象

时间片轮转算法RR(Round robin)

按照到达就绪队列的先后顺序，轮流获取CPU在一个时间段内，进程在这个时间段内未执行完，剥夺CPU进入就绪队列

优点

公平，响应快

缺点 

不能区分紧迫程度，频繁切换进程增加消耗。

高响应比优先算法HRRN(Hightest response ratio next)

每次调用前计算作业（进程）的响应比，选择响应比最高的调用

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

优点

综合考虑了等待时间和运行时间，不会出现饥饿现象

缺点

每次调用都要计算响应比

多级反馈队列调度算法

设置多个就绪队列，按优先级从高到低，时间片从小到大排列，只有当第1~i-1队列都为空时，才会调用第i队列

优点

n能够区别进程的紧急程度

缺点

可能出现饥饿现象

带权周转时间=周转时间/执行时间

死锁

概念

多个进程因为等待对方进程所使用的资源，导致多个进程都阻塞无法推进的现象。

产生的条件

请求和保持条件

进程资源请求被阻塞的同时又保持自己的资源。

不剥夺条件

进程已经获得的资源在使用完之前不能被剥夺。

互斥条件

导致死锁的资源不能被发生死锁的进程同时得到。

循环等待条件

存在循环等待链，链中每一个进程请求的资源被下一个进程所拥有。

死锁的处理

预防死锁（静态策略）

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

破坏请求和保持条件

进程在运行前请求运行过程中使用的所有资源，进程在运行过程中不能申请新的资源

缺点：可能导致资源浪费，因为有些资源只使用很小一段时间，还可能导致其它进程的饥饿现象。

破坏不剥夺条件

当进程请求资源被阻塞时，应该立即释放所拥有的所有资源

缺点

可能导致前一段的工作失效。

可能导致饥饿现象

大量申请资源释放资源，增加了系统的开销。

破坏互斥条件

把只能互斥使用的资源改为可以共享使用。

缺点

并不是所有的资源都可以改成共享。

破坏循环等待条件

对系统中的所有资源进行线性排序，进程只有拥有小编号的资源才能申请大编号的资源。

缺点

增加新设备时会打乱资源的序号

资源的序号和实际使用资源的顺序不同造成资源浪费

增加了用户在编程时的限制。

避免死锁(动态策略)

在资源分配过程中防止系统进入不安全状态。

安全序列：按照这种序列分配资源，所有进程都能顺利进行。

如果系统分配资源后，找不出一个安全序列，系统就进入了不安全状态（可能发生死锁），如果进入安全状态就一定不会发生死锁。

银行家算法

在进程提出资源申请后，计算能否找出安全序列，使系统进入安全状态（不可能发生死锁），如果找不到安全序列，就让进程阻塞等待。银行家算法就是计算资源在某个进程运行中能够找出一个安全序列。银行家算法就是预计每一个具备运行你条件将要运行的进程都会有阻塞的情况，计算它阻塞后系统剩下的资源依然至少有一个调用顺序可以满足其它所有的进程的运行，这样就预防了死锁。

数据结构

Available

表示还有多少可利用资源。长度为m的一维数组。

Max

表示各个进程对资源的最大需求数。n×m数组

Allocation

表示已经给各个进程分配了多少资源。n×m数组

Need

表示各个进程最多还需要多少资源。Max-allocation=Need

进程的请求向量

表示进程申请的资源，长度为m的一维数组。

算法步骤

设Requesti是请求向量，Requesti[j]=K，表示进程需要K个Requesti[j]类型的资源

1：Requesti[j]<=Available[i,j]，表示可利用资源足够满足申请的资源

2：Requesti[j]<=Need[i,j]，判断进程请求的资源是否超过了它最多需要的资源数目

3：模拟将资源分配给进程，Available[i,j]-=Requesti[j];Need[i,j]-=Requesti[j];Allocation[i,j]+=Requesti[j];

4:进行安全性算法，检测本次资源分配后系统是够处于安全状态，否则就取消本次资源分配。

安全性算法

数据结构

Work,系统可提供给进程运行的各类资源数目，长度为m，在执行安全性算法开始时Work=Available[i,];

Finish,表示系统是够有足够的资源分配给进程,初始值为Finish[i]=false;

算法步骤

1：进程集合中寻找进程满足系统有足够的资源分配给进程，Finish[i]=false，Need[i,j]<=Work[j];

2：当进程获得资源并且执行完毕后释放所有的资源，Work[j]+=Allocation[i,j];Finish[i]=ture;再循环执行步骤一

3：所有进程的Finish[i]=ture，则系统处于安全状态。

死锁的检测和解除

允许死锁的发生，不过OS会检测死锁并采取措施解除死锁。

资源分配图不可简化，系统就死锁。

解除死锁的方法

资源剥夺法

将死锁进程占有的资源剥夺

撤销进程法

强制撤销死锁的进程

进程回退法

将死锁的进程回退到足以避免死锁的地步

进程同步（同步也叫直接制约关系）

临界资源

一次仅允许一个进程使用的资源。

临界区

每个进程访问临界资源的那段代码叫做临界区

涉及同一个资源的临界区叫做相关临界区

临界资源访问过程

进去区

检测是否可以进入临界区，设置正在访问临界区标志

临界区

执行访问临界资源的那段代码

退出区

处理正在访问临界区标志

剩余区

做其它处理

概念

多个进程共同完成某个任务时在某些位置上的工作次序产生了制约关系。

和进程调度的区别

进程调度：用合适的算法调度就绪队列中的进程。

进程同步:协调进程之间的工作次序。

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

当一个进程进入临界区，使用临界资源时，其它进程必须等待它使用完毕临界资源，才能访问相关临界区。

空闲让等

临界区空闲时，允许一个进程立即访问

忙则等待

当已有进程进入临界区时，其它进程必须等待。

有限等待

对于请求访问临界区的进程，应保证能在有限时间内进入临界区。

让权等待

当进程不能进入临界区，应当释放处理器，防止进程忙等待

进程同步机制

软件同步机制

Peterson算法

防止两个进程为了进入临界区而无限等待。先设置自己的不允许进入标志再设置进程状态标志，这时候再检测另外一个进程的不允许进入标志和进程状态标志。

硬件同步机制

关中断

在锁测试以前关闭中断，在锁测试结束以后再打开中断。

利用Text-and-Set指令实现互斥

简称TS(TSL)指令，是一条原语，由硬件实现，执行过程中不允许被中断。

利用Swap指令直线进程互斥

又称为对换指令，由硬件实现，执行过程不允许被中断。

实时系统

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

信号量

用来解决互斥同步问题，只能被两个原语访问wait(S)、signal（S），也可记为V操作和P操作。

原语：原语是一种特殊的程序段，其执行不可被中断，原语由开中断/关中断指令实现。

整形信号量：

用于表示资源数目的整形量

记录型信号量

除需要一个用于代表 资源数目的整型变量 外，再增加一个进程链表 ，用于链接所有等待该资 源的进程。记录型信号量是不存在“忙等”现象的进程同步机制。

基本应用

实现多个进程的互斥

互斥信号量初值mutex为1

每个进程的临界区代码置于P（mutex）V（mutex）之间

同一进程中必须成对使用原语P、V，不能次序错误、重复、遗漏

遗漏P原语不能保证互斥访问，遗漏V原语不能使用临界资源后将其释放。

实现同步实现同步

①分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两 个操作(或两句代码)；

②设置同步信号量 ,初始为0 ；

<ol><li>③在“前操作”之后执行V；</li></ol>

④在“后操作”之前执行P 。

实现前驱关系

①要为每一对前驱关系各设置一个同步变量；

②在“前操作”之后对相应的同步变量执行 操作；

③在“后操作”之前对相应的同步变量执行 操作。

管程

定义

管程是一种特殊的软件模块

①多个彼此可以交互并共用资源的线程

②多个与资源使用有关的变量

③一个互斥锁

④一个用来避免竞态条件的不变量

特征

①模块化。 管程是一个基本的软件模块，可以被单独编译。

②抽象数据类型。 管程中封装了数据及对于数据的操作，这点有点像面向对象编程语言中的类

③信息隐藏。 管程外的进程或其他软件模块只能通过管程对外的接口来访问管程提供的 操作，管程内部的实现细节对外界是透明的。

④使用的互斥性。 任何一个时刻，管程只能由一个进程使用。进入管程时的互斥由编译器负责 完成。

生产者消费者问题

问题描述

系统中有一组生产者进程和一组消费者进程，生产者进程每一次生产一个 产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注：这里 的“产品”理解为某种数据)。 生产者、消费者共享一个初始为空、大小为 的缓冲区。 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。 缓冲区是临界资源，各进程必须互斥地访问。

问题分析

①生产者—消费者之间的同步关系表现为：一旦缓冲池中所有缓冲区均装 满产品时，生产者必须等待消费者提供空缓冲区；一旦缓冲池中所有缓冲区全为 空时，消费者必须等待生产者提供满缓冲区。 ②生产者—消费者之间还有互斥关系：由于缓冲池是临界资源，所以任何进 程在对缓冲区进行存取操作时都必须和其他进程互斥进行。

PV操作题目分析的步骤：

①关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

②整理思路。根据各进程的操作流程确定 操作的大致顺序。

③设置信号量。设置需要的信号量，并根据题目条件确定信号量的初值。(互 斥信号量初值一般为 ，同步信号量的初值需要看对应资源的初始值是多少)

如何实现

互斥的实现是在同一个进程中进行的一对 操作。

同步的实现是在两个进程中进行的，在一个进程中执行P操作，在另一个进 程中执行V操作。

读者写者问题

问题描述

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同 时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进 程)同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个 读者同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的 读者和写者全部退出。

问题分析

两类进程：写进程、读进程 互斥关系：写进程-写进程、写进程-读进程。读进程与读进程不存在互斥问 题。 写者进程和任何进程都互斥，设置一个互斥信号量 ，在写者访问共享文 件前后分别执行 操作。 读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对 执行 操作。 有蜂考，不挂科 如果所有读者进程在访问共享文件之前都执行 操作，那么会导致各个 读进程之间也无法同时访问文件。 这是读者写者问题的核心思想： 和 其实就是对共享文件的“加锁”和“解锁”。既然各个读进程 需要同时访问，而读进程与写进程又必须互斥访问，那么我们可以让第一个访问 文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。可以设置一个 整数变量 来记录当前有几个读进程在访问文件。 读者写者问题最核心的问题是如何处理多个读者可以同时对文件的读操作。

哲学家进餐问题