首页  思维导图  详情

操作系统 - 2 ing

2021-07-12 15:03:47   17  举报





AI智能生成

操作系统

作者其他创作

大纲/内容

第 1 章：计算机系统概述

1.1 操作系统的基本概念

概念

负责管理协调硬件，软件等计算机资源的工作

为上层用户、应用程序提供简单易用的服务

是一种系统软件，是最接近硬件的软件

目标和功能

功能

处理机管理，存储器管理，文件管理，设备管理

示例：操作系统协调用户使用QQ进行视频聊天的流程

目标：向上层提供服务

给普通用户提供的接口

GUI 图形化用户接口。也就是桌面

命令接口

联机命令接口（交互式命令接口）

如 cmd 终端

脱机命令接口（批处理命令接口）

如 .bat 文件，可批量执行提前写好的指令

给软件 / 程序员提供的接口

程序接口，即系统调用

在程序中进行系统调用来使用程序接口。普通用户不能直接使用程序接口，只能通过程序代码间接使用

操作系统对硬件的扩展

没有任何软件支持的计算机称为 “裸机”

把覆盖了软件的机器成为扩充机器，又称之为虚拟机

特征

并发

单核CPU同一时刻只能执行一个程序，各个程序只能并发地执行

并行

多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行

共享

互斥共享

一个时间段内只允许一个进程访问该资源
如：微信视频和QQ视频进程同一时间只能有一个进程使用摄像头

同时共享

允许一个时间段内由多个进程“同时”对它们进行访问
如：游戏和网易云音乐同一时间可以同时使用扬声器

虚拟

空分复用技术

如虚拟存储技术，用外存扩大主存容量

时分复用技术

如虚拟处理器技术，把 1 个物理 CPU 视为 2 个逻辑 CPU

异步

进程 A 执行 n 条指令后，CPU 切换到进程 B 执行指令，CPU 再回到进程 A执行指令
所以进程 A 程序段的执行不是“一气呵成”的，是走走停停的，如果进程 B修改了进程 A 所使用的资源，就可能出现异步引起的进程同步不安全问题

1.2 操作系统的发展和分类

手动操作阶段

单用户单任务，CPU 速度快。用户输入 & 计算机输出慢

批处理阶段

单道批量处理系统（引入脱机输入输出技术）

单用户单任务。用文件替代用户输入，加快了输入速度

多道批处理系统（操作系统开始出现）

单用户多任务。在单道批处理系统的基础上，通过流水线思想实现并行执行程序

分时操作系统

多用户多任务，CPU 为每个终端完全平均分配服务时间以实现多用户操作；拥有了人机交互功能（Req & Res）

实时操作系统

在分时操作系统的基础上添加了任务优先级，优先为紧急的任务分配服务时间片或分配更多的时间片

实时操作系统的分类

硬实时系统：必须在绝对严格的规定时间内完成任务

软实时系统：能接受偶尔违反时间规定

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

1.3 操作系统的运行环境

操作系统的运行机制

两种指令

特权指令

组成内核程序

非特权指令

组成应用程序

两种处理器状态

内核态/核心态/管态：能执行特权指令和非特权指令

用户态/目态：只能执行非特权指令

切换状态的时机

内核态下，执行特权指令切换为用户态

用户态下，非法事件引起中断，中断中由硬件自动完成切换到内核态

用户态下，可通过执行“陷入”指令，切换到内核态

中断和异常的概念

中断的作用

“中断”是让操作系统内核夺回CPU使用权的唯一途径

中断的分类

内中断（也称异常、例外）

例子1：试图在用户态下执行特权指令
例子2：故障。执行除法指令时发现除数为0
例子3：陷入。陷入指令引起的中断
PS：“终止”也会引起内中断

系统调用就是由陷入指令实现的

外中断（也称中断）

每一条指令执行结束时，CPU 都会例行检查是否有外中断信号

例子1：时钟中断——由时钟部件发来的中断信号（定时的时钟中断用于实现计算机的并发特性）
例子2：I/O中断——由输入/输出设备发来的中断信号

中断机制的基本实现原理

中断处理程序一定是内核程序，需要运行在“内核态”

中断响应会让 CPU 去执行中断程序

系统调用

什么是系统调用

OS 对应用程序 / 程序员提供的接口

系统调用和库函数的区别

有的库函数是对系统调用的进一步封装

有的库函数没有使用系统调用

为什么系统调用是必须的？

什么功能需要系统调用

设备管理，文件管理，进程控制，进程通信，内存管理

系统调用的过程

传参，陷入指令/Trap/访管，由 OS 内核程序处理系统调用请求，返回应用程序

1.4 操作系统的体系结构（了解即可）

大内核 / 单内核 / 宏内核

微内核

计算机系统的层次结构（内核主要由时钟管理，中断处理，原语，
系统控制的数据结构及处理—进程管理、存储器管理、设备管理等）

大内核结构和微内核结构（Linux 是大内核结构，Windows 是微内核结构）

第 2 章：进程管理

2.1 进程与线程

2.1.1 进程

进程的概念

程序时静态的，进程是动态的，是程序执行一次的表现

进程的组成

PCB（Program Control Block 进程控制块）

进程描述信息

进程标识符 PID，用户标识符 UID 等

进程控制和管理信息

CPU、磁盘、网络流量的使用情况统计

当前进程状态：就绪态/阻塞态/运行态/...

资源分配清单

正在使用哪些文件，内存区域，I/O 设备

处理机相关情况

即当前进程的上下文，如 PSW、PC 等寄存器的值

程序段

程序在内存中的代码段

数据段

程序运行过程中在内存中产生的数据

进程的特征

动态性，并发性，独立性，异步性，结构性

其中，独立性指进程是能独立运行（在引入线程概念前是这样）、独立获取资源、独立接受调度的基本单位

异步性会在“进程同步”里讲

进程的组织

链接方式方式

以 PCB 为队列节点，按照进程状态将每个 PCB 分到不同的队列中。操作系统持有这些队列的头结点指针

索引方式

以 PCB 为节点，建立索引表，以索引表的方式查询指定 PCB。操作系统持有索引表的指针

2.1.2 进程的状态和转换

状态

就绪态：进程已具备运行条件，等待 CPU 为其分配时间片

运行态：CPU 正在为进程工作

阻塞态：进程在运行状态下不再具备运行条件。便会从运行切为阻塞，等待再次具备运行状态

创建态：操作系统为新进程分配资源、创建 PCB

终止态：操作系统回收进程的资源（PCB，程序段，数据段）

进程运行条件

进程所需要的系统资源（如指定数据访问权或硬件设备的使用权）

CPU 为当前进程分配了时间片

进程状态间的转换

就绪态->运行态：进程具备运行条件后被调度

运行态->就绪态：时间片到，或 CPU 被优先级更高的进程抢占

运行态->阻塞态：进程不具备所需的资源，主动进入阻塞态等待系统资源分配或某事件发生

阻塞态->就绪态：进程得到所需的系统资源，并分配到 CPU 的时间片

创建态->就绪态：操作系统完成创建进程的工作

运行态->终止态：进程运行结束，或运行时宇道不可修复的错误

2.1.3 进程的控制

还讲了进程运行时，进程切换的机制

基本概念

进程控制就是用原语实现进程转换

原语是 OS 内核中用关&开中断指令实现的具有原子性的程序段

实现进程状态转换的原语

进程的创建，终止，阻塞，唤醒，切换

通常做以下 3 件事
更新 PCB；把 PCB 插入合适的队列；分配和回收资源

阻塞和唤醒要成对出现

进程失去 CPU 使用权时需要保存进程的上下文
进程重新获取 CPU 使用权时需要恢复上下文

PS：作业就是磁盘中的程序，作业调度就是从磁盘中选一个程序令其开始运行

2.1.4 进程的组成

2.1.5 进程通信：不同的进程间如何传递数据 / 共享数据

进程通信概念

每个进程的内存空间相互独立且只能被本进程访问

共享存储

为需要通信的多个进程开辟一块都有权限访问的内存空间。但空间中的数据只能互斥访问

管道通信

创建管道文件，一个进程写文件，一个进程读文件实现一个管道文件的半双工通信

文件被写满后才能被读，文件被读完后才能重新被写

消息传递

进程通过收发报文通信。OS 提供“发送/接受报文原语”

直接通信

源进程直接向目标进程发送报文

间接通信

源进程向信箱发送报文，目标进程从信箱中找属于自己的报文

2.1.6 进程的概念和多线程模型

线程的概念

引入线程前：一个进程对应一个程序，一个进程只能串行执行，一个程序需要并行运行多个功能（QQ聊天，QQ视频。QQ传文件）

引入线程后：一个进程对应一个程序，一个进程中的多个线程能并行执行，每个线程可以对应程序中一个需要独立运行的功能

带来的变化

资源分配、调度

进程是资源分配的基本单位，线程是调度的基本单位

并发性

系统开销

同一进程内的线程切换，不需要切换进程环境，系统开销小
不同进程内的线程切换，需要切换进程环境，系统开销大

线程的属性

每个线程都哟一个线程 ID，线程控制块（TCB）

线程也有就绪、阻塞、运行三种基本状态

同一进程的不同线程间共享进程资源，线程间的通信无需 OS 干预

线程的实现方式

背景

早期。通过线程库实现“假线程”，OS 只能感知到进程的存在

假线程下，一个线程阻塞会导致整个进程阻塞，并发度不高

后期。OS 真正支持线程

OS 支持的线程，并发度高

用户级线程

用户感知的逻辑上存在的线程。由程序员令处理器在用户态下管理，线程切换不需要变态

内核级线程

OS 感知的“物理”上存在的线程。由 OS 令处理器在内核态下管理，线程切换需要变态

缺点：线程的调度，切换等需要处理器切换为内核态，开销大

TCB 是内核级线程的，用户级线程没有

用户级线程是“代码逻辑”的载体
内核级线程是“运行机会”的载体

多线程模型

一对一模型（纯内核级线程）。并发性强，线程切换导致的系统开销大（因为每个用户级线程的切换一定都是内核级线程的切换）

多对一模型（纯用户级线程）。并发性弱，线程切换导致的系统开销小（因为用户级线程的切换可在用户态下进行）

操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位

多对多模型（集大成者，集一对一和多对多的优点）

2.2 处理机调度

调度的概念

操作系统用某种的算法，选择一个进程将处理器分配给它

调度的层次

高级调度：作业调度

按照某种规则，从后备队列（想要被运行的程序组成的队列）中选择合适的作业将其调入内存，并为其创建进程

发生频率：最低

中级调度：内存调度

按照某种规则，从挂起队列中选择合适的进程将其数据调回内存

暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列

发生频率：中等

底级调度：进程调度

按照某种规则，从就绪队列中选择一个进程为其分配处理器

发生频率：最高

调度的时机、切换与过程

进程切换方式

非剥夺调度方式（非抢占式）

只能由当前正在运行的进程主动放弃 CPU

剥夺调度方式（抢占式）

可由操作系统剥夺当前进程的 CPU 使用权

进程切换的时机

主动放弃

进程正常终止；进程发生异常；进程阻塞

被动放弃

进程的时间片用完；有更紧急的事情需要处理；有优先级更高的进程需要处理

不能切换进程的情况

处理中断过程中

PS：原子操作 / 原语，本质上事使用了关中断程序

进程在操作系统内核程序临界区中不能进行调度与切换

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源
临界区：访问临界资源的那段代码

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列

如：内核程序访问就绪队列，给就绪队列上锁。结果切换进程时，因为就绪队列被上锁导致无法调度新进程

进程切换过程

1. 保存旧现场。如果有必要，保存当前进程的环境和数据资源

2. 恢复新现场。如果有必要，恢复调度线程的环境和资源数据

PS：狭义的调度：从就绪队列里选择一个进程。广义上的调度：从就绪队列中选择一个进程和进程切换两个步骤

调度算法的评价指标

CPU 利用率：CPU“忙碌”的时间占总时间的比例

系统吞吐量：单位时间内完成作业的数量

周转时间（用户关心）：从作业被提交给系统开始，到作业完成为止的这段时间间隔
平均周转时间（OS 关心）

带权周转时间：周转时间 / 作业实际运行时间（CPU为作业的工作时间）
平均带权周转时间

等待时间：进程/作业处于等待处理机状态时间之和

响应时间：从用户提交请求到首次产生响应所用的时间

和周转时间有点像

经典的调度算法

批处理操作系统的经典调度算法

先来先服务（FCFS，First Come First Serve）

规则：对就绪队列中的进程执行 FIFO 规则

非抢占

缺点：对短作业不利；考虑等待时间，没考虑运行时间；不会导致饥饿

短作业优先（SJF，Shortest Job First）

规则：当前（实时）完成作业所需时间最短的进程优先运行

默认是非抢占式，也有抢占式版的

抢占版的叫“最短剩余时间优先算法（SRTN）”。抢占式的性能比非抢占式的好

缺点：对长作业不利；没考虑等待时间，考虑运行时间；会导致饥饿

高响应比优先（HRRN，Highest Response Ratio Next）

规则：当前（实时）优先选择响应比最高的进程

响应比：（等待时间+要求服务时间）/ 要求服务时间。响应比一定 >= 1

非抢占式

权衡了等待时间和运行时间；不会导致饥饿

分时操作系统的经典调度算法

时间片轮转（RR，Round-Robin）

规则：为作业平均分配 CPU 的时间片

抢占式

此抢占式非优先级。若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到

缺点：不区分优先级；不会导致饥饿

优先级调度

规则：优先选择优先级最高的

有抢占式的，也有非抢占式的

缺点：会导致饥饿

PS：静态型优先级调度，作业的优先级是固定的；动态型优先级调度，作业的优先级可在运行时修改

多级反馈队列

规则：有多个优先级递减的队列，新作业进入优先级最高的队列。用 RR 算法从优先级最高且有作业的的队列中调度作业，作业每被调度一次，优先级-1

抢占式（因为用 RR 算法实现的调度）

缺点：可能会导致饥饿

2.3 进程同步

进程同步的基本概念

进程同步

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因需要在某些位置上协调它们的工作次序而产生的制约关系

进程互斥

进程互斥就是不同进程对临界资源的互斥访问

访问临界资源的逻辑

进入区：检查是否可进入临界区，若可进入，则对临界区“上锁”

临界区：进程中访问临界资源的代码段

退出区：释放临界资源，相当于“解锁”

剩余区：做其他处理；不操作临界资源

进程互斥访问临界区原则

空闲让进。临界区空闲时，应允许一个进程访问

忙则等待。临界区正被访问时，其它试图访问的进程必须等待

有限等待。进程要在有限时间内进入临界区，保证不会饥饿

让权等待。进不了进阶区的进程，应立即释放处理器，方式忙等

实现进程互斥的方法

软件实现

单标志法（不安全）

算法描述：进入临界区只做“检查”，不“上锁”
存在问题：不遵循“空闲让进”原则。因为资源必须被两个进程轮流访问

不安全场景：轮到 P0 进程访问资源，但 P0 没有访问，P1 想要访问资源就只能等待 P0 访问后才能访问

双标志先检查（不安全）

算法描述：先检查对方访问资源的意愿，如果对方不访问资源，则自己一定访问资源
存在问题：违反“忙则等待”原则。原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的

不安全场景：P0 和 P1 都没想访问资源。P0 和 P1 在进入区发现对方没有访问资源的意愿，结果 P0 和 P1 都进入临界区

双标志后检查（不安全）

算法描述：先表名自己需要访问资源的意愿，再在进入区检查对方的意愿
存在问题：违背了“空闲让进”和“有限等待”。存在饥饿问题

不安全场景：P0 和 P1 都表达的访问资源的意愿，所以在进入区检查对方到对方的意愿后会等待对方修改意愿。导致饥饿（不是死锁，因为线程均未进入临界区）

Peterson 算法（安全，但不完美）

算法描述：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，进程会尝试谦让
问题：违反“让权等待”原则。如果某个进程无法进入临界区，那么它不会主动放弃 CPU 并进入阻塞态

turn 变量表示当前持有最高优先级的进程

不存在不安全场景。只是因为违反“让权等待”原则而显得不是那么高效

PS：如果双标志先检查和双标志后检查能实现“检查”和“上锁”能一气呵成（保证其原子性）那么算法就没有安全隐患

硬件实现

中断屏蔽法（安全，但不完美）

使用“开/关中中断”指令保证一个 CPU 上运行的进程不会被切换。单处理器失去异步性即可保证资源的串行访问

限制

仅适用于系统进程上，而非用户进程上。“开/关中断”指令应该由内核控制，而不应该由用户控制

仅适用于单处理器。因为 2 号 CPU 并不会因为 1 号 CPU 关中断而不再切换进程，所以计算机整体上没有失去异步性

TestAndSet / TS 指令 / TSL 指令（安全，但不完美）

算法描述：TestAndSet 方法实现上锁和检查一气呵成。如果 old 为 true 表示上锁失败

TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成

误区

Q：从上述代码来看，如果 old 为 false 时，多个进程的 TS 方法可能会均返回 true 并进入临界区

A：实际上 TS 指令的执行是由硬件的逻辑电路实现的，为理清逻辑才用代码形式说明 TS 的执行流程。即理论上不存在多个进程同时占用 TS 逻辑电路的情况，也即 TS 方法只能被串行执行。下面的 Swap 指令同理

缺点：违背“让权等待”

Swap 指令 / XCHG 指令 / CAS（安全，但不完美）

算法描述：原理和 TS 相同，实现检查并上锁的原子操作。old 初值为 true 表示上锁意愿，通过 swap 交换 old 和 lock，如果 old 能换出 false，表示锁之前未被占用并成功被 old 交换值（old 的值为 true，所以成功交换值表示 lock 被设为 true，即上锁）

缺点：违背“让权等待”

信号量（安全，且完美）

概念

wait原语（P 操作）和 signal原语（V 操作）实现阻塞进程和唤醒进程。通过合理调用 PV 操作，不断阻塞和唤醒进程实现进程串行访问资源

整型信号量原语（安全，但违反“让权等待”，还是不完美）

属性：S。表示资源能接受的并发进程数

方法：wait(S)。本质是原语，所以只能被串行执行

方法：signal(S)。本质是原语，所以只能被串行执行

记录型信号量原语（安全，完美）

属性：S。表示资源能接受的并发数；L。表示阻塞队列中想要访问此资源的进程

方法：wait(S)。本质是原语，所以只能被串行执行

方法：signal(S)。本质是原语，所以只能被串行执行