前言

为了准备秋招及春招,现阶段的任务是将所学过的知识进行复习,并串联起来。而操作系统中,最为重要的就是进程、线程、内存、文件

还有一些很常问的一些技术点,堆和栈、内存分区、虚拟内存 + 物理内存、进程 + 线程 + 协程、死锁、分片机制、五大组件、中断和系统调用 、同步和异步等等问题。

对于操作系统的理解,对于这些基础的计算机知识的掌握是必须深入学习,要花很大的功夫去理解清楚这些,工作中,对于真实线上系统的稳定性、对于底层技术的理解是有帮助的,操作系统是面试中常见问题之一。


OS概述

操作系统(Operating System)

  • 控制和管理整个计算机系统的硬件和软件资源,并合理组织和调度资源分配(系统资源的管理者
  • 为用户和应用软件提供接口和服务(向上层提供方便易用的服务
  • 最基本的系统软件,对硬件机器功能进行拓展(最接近硬件的一层软件

指令:CPU能识别、执行的最基本的指令,二进制机器代码

操作系统提供的服务、功能?

  1. GUI,图形用户界面
  2. 命令接口:联机(交互式)命令接口windows中的cmd,脱机(批处理)命令接口.bat文件
  3. 系统调用,需通过程序间接使用printf函数

操作系统的特点?

  • 并发。指两个或多个事件在同一时间间隔内交替执行。区别于并行的概念,并行指的是同一时刻同时发生单核 CPU同一时刻只能执行一个程序,因此各个程序只能并发执行;而多核 CPU则可以并行执行相应CPU数量的程序。
  • 共享。资源共享,系统资源可供多个并发的进程共同使用。互斥共享(摄像头)和同时共享(访问磁盘资源)
  • 虚拟。把一个物理上的实体变为若干个逻辑上的对应物。空分复用技术(虚拟存储器,虚拟内存)和时分复用技术(虚拟处理器)。没有并发性,虚拟性就没有存在的意义
  • 异步。在多道程序环境下,允许多个程序并发执行,但系统资源是有限的,因此进程的执行不是一贯到底的,而是走走停停,以不可预知的速度向前推进。没有并发性,也就不存在异步性

用户态、内核态

内核态->用户态。执行一条特权指令,修改PSW标志位为“用户态”

用户态->内核态。由“中断”引发,硬件自动完成变态的过程。凡是需要操作系统介入的地方,都会引发中断信号,意味着强行夺回CPU的控制权

中断

中断的出现,可以使操作系统夺回对CPU的控制权(用户态->内核态),避免出现一个程序从始至终占用着CPU的情况,保证并发性

内外中断的内外指的是,使得中断发生的指令来自于CPU内还是外

内中断(异常),与当前指令有关,来源于CPU的内部。如以下例子

  • 用户态下执行特权指令
  • 执行除法指令时,除数为0
  • 应用程序请求操作系统内核的服务,执行陷入指令(陷入指令是在用户态 执行的,执行陷入指令后立刻引发内中断,使CPU进入核心态

外中断,与当前指令无关,来源于CPU的外部。如以下例子

  • 时钟中断。当一个时间片完毕后,时钟部件就会发送一个中断信号给CPU。这时的CPU是处于用户态的

系统调用:凡是需要对共享资源进行访问,就一定需要操作系统介入,并使用系统调用来实现

OS引导(boot)

在这里插入图片描述

  1. CPU执行主存中特定地址的ROM引导程序(作用:硬件自检,将主引导记录读入RAM)
  2. 把磁盘中第一块的主引导记录读入内存,执行磁盘引导程序,扫描分区表(作用:找到活动分区)
  3. 从活动分区中读入引导记录并执行(作用:找到启动管理器)
  4. 执行OS初始化程序,完成开机

进程管理(处理机CPU)

进程概念

进程出现的意义?

更好地描述和控制 程序 的并发执行,实现操作系统的并发性和共享性

什么是进程?进程由什么组成?

  1. 进程是程序的一次执行过程
  2. 是资源分配和调度的独立单位
  3. 是对一个正在执行程序的一种抽象

PCB程序段数据段构成了进程实体
PCB是进程存在的唯一标识,包含了PID、UID和所分配给进程的内存、文件等各种信息
程序段由程序的可执行文件,一系列的指令组成
数据段是进程在执行过程中产生的数据

进程状态

创建态、终止态

就绪态、运行态、阻塞态

  • 就绪态->运行态:分配了CPU资源
  • 运行态->就绪态:时间片到,或被其它优先级更高的进程抢占
  • 运行态->阻塞态:申请某种资源,或等待某一事件的发生
  • 阻塞态->就绪态:资源分配到位,等待的事件发生
  • 创建态->就绪态:初始化PCB,并分配相应资源

进程通信

指两个进程之间产生数据交互

各进程的内存地址空间相互独立,所以进程通信必须要有操作系统参与

共享存储

因为各进程间的地址空间是分隔开的,想要实现数据交互,只能另外开辟一个共享存储区,步骤为:

  1. 申请一片共享内存区
  2. 将共享内存区映射到进程自己的地址空间

各个进程对共享存储区的访问是互斥(PV)的

  • 基于存储区的共享。由进程控制数据形式以及存放位置
  • 基于数据结构的共享。
消息传递
  • 格式化的消息为单位
  • 用“发送消息 / 接收消息”两个原语进行数据交换

消息传递可以分为两种方式:

  1. 直接通信方式。发送进程要指明接收进程的ID,反之接收也要进行指定
  2. 间接通信方式。以“信箱”作为中间实体进行通信。从原先要指定进程的ID变为指定信箱的ID。可以多个进程往同一个信箱send消息,也可以多个receive消息
管道通信

管道,就是一个固定大小的内存缓冲区

  • 半双工通信。同一时刻只能存在一个方向的数据通信
  • 各进程互斥访问管道
  • 管道在被写满或者读空时,写/读进程将会被阻塞

线程机制

什么是线程?为什么要引入线程?

为了使程序能够并发执行,我们引入了进程。
但有了进程以后,有的进程可能需要“同时 ”做很多事,而传统的进程只能串行地执行一系列程序。因此,引入了线程,来增加并发度

  • 程序执行流的最小单位由进程变为了线程
  • 进程是系统资源分配的基本单位,而线程是CPU调度的基本单位
  • 进程实现并发的同时,线程也具有并发性,从而使得一个进程内多种任务可以同时执行
  • 引入线程使得系统的开销减小。实现线程级的并发时,由于不需要切换进程环境,系统开销小

用户级线程、内核级线程

  1. 用户级线程的管理工作由应用程序通过线程库实现;内核级线程则由操作系统的内核完成
  2. 用户级线程不需要操作系统切换至核心态;而内核级需要切换
  3. 操作系统能意识到内核级线程的存在,而意识不到用户级线程,会将它看成一整个进程
优点 缺点
用户级线程 不需要切换至核心态,系统开销小,效率高 如果一个用户级线程被阻塞,会导致整个进程都被阻塞,并发度不高。多个线程不能充分利用多核处理机实现并行运行
内核级线程 一个内核级线程被阻塞,其余线程不受影响。多线程可在多核处理机上并行执行 需要变态,开销大,成本高

内核级线程才是CPU调度的基本单位

进程调度

调度:以某种规则处理任务的执行顺序

三个层次

区别是所要进行调度的对象,由大至小,由高至低

  • 高级调度(作业调度):作业,一个具体的任务。用户向操作系统提交一个作业,表明希望让操作系统启动一个程序,并处理一个具体的任务。每一个作业只调入一次,调出一次,会创建对应的PCB。(外存\rightarrow内存,面向作业)
  • 中级调度(内存调度):把处于挂起状态的进程,重新调入内存。内存不足时,会暂时将某些进程的数据调出外存。待内存空闲或进程需要时,再重新调入内存。(外存\rightarrow内存,面向进程)
  • 低级调度(进程 / 处理机调度):从就绪队列中按照某种规则选择一个进程,将处理机分配给它。最基本的一种调度,频率很高。(内存\rightarrowCPU)

挂起态:进程映像调到了外存。(就绪挂起,阻塞挂起)

要做什么? 调度发生在? 发生频率 对进程状态的影响
高级调度 按照某种规则,从后备队列中选择合适的作业调入内存,并为其创建进程 外存\rightarrow内存(面向作业) \rightarrow创建态\rightarrow就绪态
中级调度 按照某种规则,从挂起队列中选择进程将其数据调回内存 外存\rightarrow内存(面向进程) 挂起\rightarrow就绪
低级调度 按照某种规则,从就绪队列中选择进程为其分配处理机 内存\rightarrowCPU 就绪态\rightarrow执行态

调度评价指标

  • CPU利用率:忙碌时间 / 总时间
  • 系统吞吐量:单位时间内完成作业的数量
  • 周转时间:从提交到被完成所经历的时间
  • 平均周转时间:各作业的周转时间之和 / 作业数
  • 带权周转时间:作业周转时间 / 实际运行时间( 1\geq1 )。带权周转时间越小,用户体验越好。周转时间相同时,运行时间的长短所带来的体验会不一样,因此有了这个指标
  • 平均带权周转时间:各作业带权周转时间之和 / 作业数
  • 等待时间:周转时间 - 等待时间
  • 响应时间:从提交请求到首次响应所经过的时间

进程调度算法

  1. 算法思想
  2. 算法规则
  3. 作业调度 or 进程调度
  4. 抢占 or 非抢占
  5. 优缺点
  6. 饥饿:某进程 / 作业长期得不到服务

FCFS

先来先服务,First Come First Server

按照作业 / 进程到达时间的先后顺序进行服务

  • 非抢占式
  • 优点:公平、算法实现简单
  • 缺点:对长作业有利,而对短作业不利。排在长作业后的短作业,带权周转时间很大
  • 不会饥饿

只考虑了等待时间,而没有考虑运行时间

SJF

短作业优先,Short Job First

最短,指的是要求服务的时间最短

每次调度时选择当前已到达运行时间最短的作业 / 进程

  • 默认是非抢占式(抢占式:最短剩余时间优先算法)
  • 优点:平均等待时间、平均周转时间“最短”
  • 缺点:不公平。短作业有利,长作业不利
  • 长作业饥饿

最短剩余时间优先算法,Shortest Remaining Time Next

每当有新的进程加入就绪队列,比较新加入进程的剩余运行时间与当前运行的进程剩余时间。如果更短,新进程则会抢占处理机,原进程重新回到就绪队列

只考虑了运行时间,而没有考虑等待时间

HRRN

高响应比优先算法,Highest Response Ratio Next

响应比=等待时间+要求服务时间要求服务时间响应比=\frac{等待时间+要求服务时间}{要求服务时间}

计算响应比,选择响应比最高的作业 / 进程为其服务

  • 非抢占式,只有当前运行的进程主动放弃CPU时,才进行调度
  • 优点:综合考虑等待时间与运行时间
  • 不会饥饿

既考虑了等待时间,又考虑了运行时间

时间片轮转

Round-Robin

时间片大小为2:

公平、轮流地为各个进程服务,让每个进程在一定时间间隔内都可以得到响应

设置时间片不宜过大,否则算法会退化为先来先服务算法
如果太小(切换进程开销占比不超过1%),会导致进程切换过于频繁
所以太大太小都不行

  • 用于进程调度,只有进程才有被分配处理机时间片这一概念
  • 只能是抢占式
  • 优点:公平;让各个进程得到及时的响应;适合分时操作系统
  • 缺点:进程切换有开销;不区分任务的紧急程度
  • 不会饥饿

优先级调度

根据任务的紧急程度,决定处理顺序

每个作业 / 进程有各自的优先级,调度时选择优先级较高的作业 / 进程

(本题优先数越大,优先级越高)

非抢占式的优先级调度算法,每次调度时选择当前已到达优先级最高的进程。当前进程主动放弃处理机时发生调度。

抢占式的优先级调度算法,除了进程主动放弃处理机的情况,当就绪队列发生改变时,也需要检查是否抢占

  • 优点:用优先级区分紧急程度,适用于实时操作系统。可以灵活地调整对各种作业 / 进程被服务的机会
  • 缺点:若频繁地有更高优先级的进程到来,可能导致饥饿
  • 会发生饥饿

多级反馈队列

对所有调度算法的折中

规则如下:

  1. 设置多个就绪队列,优先级从高到低,时间片从小到大
  2. 新进程到达时先进入第1级队列,按FCFS原则排队等待分配时间片
  3. 若在一级队列的时间片用完后还未结束,进行下一级优先队列的队尾
  4. 只有K级队列为空时,才会为K+1级队列中的进程分配时间片
  5. 发生抢占时(在k级队列运行的过程中,若更上级的队列1~k-1级进入了一个新的进程,新进程会抢占处理机 ),被抢占处理机的进程重新放回本队列的队尾

特点如下:

  • 用于进程调度
  • 抢占式
  • 优点:公平;响应快;照顾了短进程;
  • 缺点:会饥饿,不断的有高优先级的短进程到来

进程同步、进程互斥

进程同步

进程同步:对多个相关的进程在执行次序上进行协调,以使并发执行的各进程之间能有效地共享资源相互合作,从而使程序的执行具有可再现性

进程间制约关系:

  • 间接制约关系(互斥关系,互斥地访问临界资源)
  • 直接制约关系(同步关系、合作关系)

同步机制 / 临界互斥应遵循的规则:

  1. 空闲让进:当临界区空闲时,应使一个请求进入临界区的进程立即进入
  2. 忙则等待:当有进程正在临界区时,其它进程必须等待
  3. 有限等待:进程等待进入临界区的时间必须是有限的,防止死等
  4. 让权等待:一旦一个进程无法进入临界区,则必须让出处理机,防止忙等
进程互斥

进程互斥:当一个进程正在访问某个临界资源时,另一个也想要访问的进程必须等待

逻辑上的实现:

  1. 进入区。设置正在访问临界资源标志
  2. 临界区。访问临界资源
  3. 退出区。解除正在访问临界资源的标志
  4. 剩余区

死锁问题

死锁:各进程互相等待对方手里的资源,处于一种僵持局面,若无外力作用,该组进程中的所有进程均无法继续向前推进,称为进程死锁

死锁的4个必要条件:

  1. 互斥条件:对必须互斥访问的资源的争抢才会引起死锁
  2. 不剥夺条件:进程保持的资源只能主动释放,不可强行剥夺
  3. 请求与保持条件:保持某些资源不放的同时,请求别的资源
  4. 循环等待条件:存在一种进程资源的循环等待链,链中的每一个进程所拥有的资源正在被下一个进程所请求

什么时候会发生死锁?

  • 对不可抢占性资源(打印机)的竞争
  • 进程的推进顺序不当,即请求和释放资源的顺序不当

预防死锁

破坏死锁4个必要条件中的某一个或某几个

  • 破坏互斥条件。SPOOLing技术(将互斥资源改为共享资源)。但大多情况下不可行
  • 破坏不可剥夺条件。进程在请求某一资源得不到满足时,选择放弃已有的全部资源 或者 从别的进程那强行剥夺需要的资源
  • 破坏请求与保持条件。静态分配方式,在进程开始运行前一次性申请完它所需要的全部资源,而后的过程中不需要再请求资源
  • 破坏循环等待条件。顺序资源分配法,即给系统中的每一个资源编号。一个进程只有拥有了小编号的资源,才能去申请大编号的资源

避免死锁(银行家算法)

安全序列:系统按照某种序列分配资源,则每个进程都能顺利完成

在不安全状态,不一定发生死锁。发生死锁,一定是在不安全状态。
不安全状态只是发生死锁的必要条件

银行家算法的核心思想:

  • [x] 在资源分配之前,预先判断这次分配是否会导致系统进入不安全状态

资源总数(10,5,7),剩余可用资源(3,3,2)

算法步骤:

  1. 检查本次申请的资源数是否不超过最先声明的请求资源数
  2. 检查本次申请的资源数是否不超过系统剩余可用的资源
  3. 如果满足1、2条件,则预分配资源给当前请求的进程,并更新数据
  4. 进行【安全性检测】,如果不会进入不安全状态,则正式分配

安全性检测:

检查当前的剩余可用资源是否能够满足某一个进程的最大需求,如果可以,则把该进程加入安全序列。待进程执行结束后,把该进程所持有的资源全部回收

死锁的检测与解除

检测是否发生了死锁。
发生了死锁后,如何从死锁状态中解脱出来

死锁定理:如果某时刻系统的资源分配图是不可完全简化的,那么此时系统死锁

而在上述的图中,先找到请求资源小于等于剩余资源的结点,消去边

表示可完全简化,没发生死锁


解除死锁的方法:

  1. 资源剥夺法。挂起(暂时放到外存)某些死锁进程,并抢占它的所有资源,将这些资源分配给其它死锁进程
  2. 撤销进程法。强制撤销部分、甚至全部死锁进程,并剥夺这些进程的资源,意味着从头再来
  3. 进程回退法。让一个或多个死锁进程回退到不发生死锁的位置。这要求系统记录进程的历史信息

内存管理(存储器)

分页分段

分页的作用,好处?和分段有什么区别?

把进程分页,各个页面可离散地放到各个内存块当中
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。即进程的页面与内存的页框具有一一对应关系

既免除了移动信息的工作,又充分利用了内存空间;消除了动态分区法的碎片问题,提升了内存空间的利用率

分页的参数:

  1. 页面:将进程的逻辑地址空间分为大小相等的分区
  2. 页框:将进程的物理地址空间分为大小相等的分区
  3. 页表:记录页面到页框的对应关系

和分段的区别:

  1. 分页是固定大小且各个页面大小相等的;分段大小不等,根据程序逻辑划分;
  2. 分页主要目的是为了提升内存的空间利用率,分段是为了满足用户编程和使用上模块化的需求;
  3. 分页是信息的物理单位,是用户不可见的,页长由系统确定,只能从页大小的整数倍地址开始;分段是信息的逻辑单位,是用户可见的,由用户根据需要确定,段起始可以从内存任何地址开始。

内存分配机制

内存分配的机制?

  • 单一连续分配:也称单用户存储管理。将内存分为系统区和用户区两部分。用户区一次只能装入一个作业
  • 固定分区分配:将内存用户空间划分为若干个大小相等的区域,每个分区只装入一道作业
  • 动态分区分配:按照作业大小分区,但划分的时间、大小、位置都是动态的

虚拟内存

什么是虚拟内存?

基于局部性原理,实现信息的部分装入,从逻辑上为用户提供一个比物理内存容量大得多的、可寻址的内存储器

局部性原理

  • 时间局部性:近期执行的某条指令或者被访问的某个数据,在不久后很可能再次被执行或访问
  • 空间局部性:某个存储单元被访问后,不久后其附近的存储单元也有可能被访问到

虚拟内存的特征:

  • 多次性:一个作业被分成多次调入内存执行(最重要
  • 对换性:允许在作业的运行过程中进行换进、换出
  • 虚拟性:能够从逻辑上扩充内存容量,用户可使用的内存容量远大于实际内存容量

页面置换算法

请求分页存储管理中的页面算法:决定应该换出哪个页面,追求更少的缺页率

  • 当所访问的信息不在内存时,由操作系统负责将所需的信息从外存调入内存
  • 若内存空间不足,由操作系统负责将内存中暂时用不到的信息调出内存

OPT

最佳置换算法,optimal

在这里插入图片描述
每次选择淘汰的页面,将是以后不再使用(向后看)的页面。

性能最好,但无法实现

FIFO

先进先出置换算法

在这里插入图片描述
每次选择淘汰的页面,是最早进入内存的页面

实现简单,但算法性能差

Belady异常——当为进程分配的物理块数增大时,缺页次数不减反增的异常现象

LRU

最近最久未使用置换算法,least recently used

在这里插入图片描述
每次选择淘汰的页面,是最近最久未使用(往前看)的页面

算法性能好,最接近OPT,但需要专门的硬件支持

CLOCK

时钟置换算法,CLOCK算法;最近未用算法,NRU算法

  • 为每个页面设置一个访问位
    • 访问位为1,表示最近访问过
    • 访问位为0,表示最近没被访问过
  • 内存中的每个页面通过链接指针,链接成一个循环队列
  • 当需要淘汰一个页面的时候,只需检测访问位。如果有0,则将其换出;如果是1,则置为0

简单的CLOCK算法选择一个淘汰页面的时候,最多会经过2轮扫描。即使第1轮没有出现访问位为0的,第二轮由于第一轮将1置0,则一定会在第2轮出现

改进CLOCK

在考虑一个页面是否有被访问过的基础上,还考虑了该页面是否进行了修改。如果被修改了,则需要写回外存,会执行IO操作。所以应该优先淘汰没有修改过的页面

  • 为每个页面同时增加(访问位修改位)
  1. 先找(0,0),最近没被访问,也没修改
  2. 找不到再找(0,1),顺便将扫描过的页的访问位置0,最近没访问,但被修改
  3. 再找(0,0),最近访问过,但没修改
  4. 最后找(0,1),既访问,也修改

改进型的CLOCK算法选择一个淘汰页面的时候,最多会经过4轮扫描

文件管理

文件结构

文件系统中文件是如何组织的?

文件的逻辑结构:
1、流式文件
这是一种无结构的文件,文件内的数据不再组成记录,只是一串顺序的信息集合,称为字节流文件。

2、记录式文件
这是一种有结构的文件,它包含若干逻辑记录,逻辑记录是文件中按信息在逻辑上的独立含义所划分的信息单位。

文件的物理结构:
1、顺序文件:又称连续文件,是一种逻辑记录顺序和物理块顺序完全一致的文件;
2、连接文件:存放信息的物理块不必连续,使用连接字进行连接。
3、索引文件:系统为每个文件建立索引表,可以有不同的索引形式,具有连接文件、记录可以散列存储,具有直接读写任意记录的能力;缺点是索引表的空间开销和查找时间过大。
4、直接文件:使用哈希法,实现快速存储。

文件共享是指多个进程使用同一个文件,不仅为不同进程完成共同任务所必需,而且节省大量外存空间,减少因文件复制而增加的I/O操作次数。

文件共享的方式:静态共享、动态共享和符号连接共享。

静态共享:从多个目录可以到达同一个文件,无论进程是否运行都会存在的连接是静态的。

动态共享:不同应用进程或同一用户的不同进程,并发地访问同一文件。

磁盘调度

磁盘调度算法

  1. 先来先服务算法FCFS:按照请求到达的顺序先后处理;
  2. 最短查找时间算法SSTF:计算当前所有距离当前指针最近请求进行服务,但可能会造成饥饿;
  3. 扫描算法SCAN:只有磁头移动到最边缘的磁道时才可以改变磁头的方向;
  4. 循环扫描算法C-SCAN:只有沿某个指定的方向移动时,才会响应请求。移动边缘后回到起始点,返回途中不响应请求

设备管理

缓冲区

作用:

  1. 缓和CPU与I/O设备之间速度不匹配的问题
  2. 减少对CPU的中断频率,放宽对CPU中断相应时间的限制
  3. 解决数据粒度不匹配的问题
  4. 提高CPU与I/O设备间的并行性

说一说操作系统中缓冲区溢出怎么处理?

指当计算机向缓冲区填充数据时超出了缓冲区本身的容量,溢出的数据覆盖在合法数据上

  • 设置合理的缓冲区大小上限

参考资料

  1. 《深入理解计算机系统》
  2. 《王道408—操作系统》