学习建议：结合书和笔记把知识过一遍 —> 买题库刷试卷 —> 始终学不明白的题目去刷章节题目 —> 背新增试卷题目

关于本笔记：写者参加2022年5月的考试，参考《全国计算机等级考试四级教程操作系统原理（2021年版）》和 上的一些资源，在看书的过程中写下本笔记，基于markdown。笔记中黄色高亮的都是试卷中出现过的或者比较重要的概念，可以重点记忆一下。读者可以通过浏览本笔记，了解操作系统原理大致内容以及重点位置，然后一直刷题。备考时间仓促，笔记中难免有错误的地方，读者可以自行加以修改。

zhzeng

2022-05-29

百度 盘链接：PDF格式笔记
提取码：1234

其他学习资源：知乎的两篇题目类型总结和解析，写的很不错！

1. 知乎——操作系统1
2. 知乎——操作系统2

文章目录

• 第一章 操作系统概论
• • 操作系统的概念
  • • 计算机系统
    • 操作系统的定义
    • 操作系统的特征
    • 研究操作系统的观点
    • 操作系统的功能
  • 操作系统发展
  • 操作系统的分类
  • • 批处理操作系统
    • SPOOLing技术
    • 分时系统
    • 实时操作系统
    • 嵌入式操作系统
    • 个人计算机操作系统
    • 络操作系统
    • 分布式操作系统
    • 智能卡操作系统
  • 操作系统结构
  • • 整体式结构
    • 层次结构
    • 微内核（客户机/服务器）结构
• 第二章 操作系统运行机制
• • 中央处理器CPU
  • • CPU的构成和基本工作方式
    • 特权指令和非特权指令
    • 处理器的状态
    • 程序状态字PSW
  • 存储体系
  • • 存储器的层次结构
    • 存储保护
  • 中断与异常机制
  • • 中断与异常的概念和分类
    • 中断系统
  • 系统调用
  • • 系统调用简介
    • 系统调用处理过程
  • I/O技术
  • 时钟
• 第三章 进程线程模型
• • 多道程序设计模型
  • • 程序的顺序执行
    • 多道程序设计环境的变化
    • 程序的并发执行
  • 进程模型
  • • 进程的概念
    • 进程的状态及其状态的转换：
    • 进程控制块（PCB）
    • 进程控制
  • 线程模型
  • • 线程的引入
    • 线程的概念
    • 线程实现机制
    • Pthread线程包
  • 进程（线程）调度
  • • 概述
    • 调度算法设计原则
    • 进程（线程）调度算法
• 第三章 并发与同步
• • 进程（线程）间相互作用
  • 进程互斥
  • 信 量
  • 经典的线程同步问题
  • 管程
  • 进程通信
  • • 共享内存
    • 消息机制
• 第五章 内存管理
• • 基本概念
  • • 存储体系
    • 存储管理的任务
    • 地址转换
  • 分区存储管理方案
  • • 固定分区
    • 可变分区
    • 分区管理方案的优缺点
  • 覆盖技术与交换技术
  • • 覆盖技术
    • 交换技术
  • 页式存储管理方案
  • • 基本思想
    • 存储空间的分配与回收
    • 地址转换与快表
  • 虚拟存储技术与虚拟页式存储管理方案的实现
  • • 虚拟存储技术
    • 虚拟页式存储管理
    • 段式与段页式存储管理方案
• 文件管理
• • 概述
  • • 文件和文件系统
    • 文件分类
    • 文件系统的功能
  • 文件的结构
  • • 文件的逻辑结构
    • 文件的物理结构
    • 文件的存储介质
    • 文件的存取方式
  • 文件目录
  • • 文件目录的组成
    • 文件目录结构
    • 树形目录
    • 路径名
    • 目录操作
  • 文件系统的实现
  • • 存储空间的分配和回收
    • 实现文件系统的表目
    • 记录的成组与分解
    • 文件的操作
  • 文件的保护和安全
  • • 文件的共享
    • 文件的保护
    • 文件的存取权限
    • 文件的保密
  • 文件系统的性能
  • Windows的FAT文件系统和UNIX文件系统
  • • Windows的FAT文件系统
    • UNIX文件系统
• 第七章 I/O设备管理
• • 设备与设备分类
  • • 设备管理的重要性
    • 设备管理的任务
    • 设备的分类
  • I/O硬件组成
  • • 计算机I/O系统的结构
    • I/O设备数据传送控制方式
  • I/O软件的特点及结构
  • • 设备驱动程序
    • 与设备无关的系统软件
    • 用户空间的I/O软件
  • 典型的I/O技术
  • • 缓冲技术
    • 设备分配技术
  • I/O性能问题及解决方案
• 第八章 死锁
• • 死锁基本概念
  • • 死锁的概念
    • 死锁产生的原因
    • 产生死锁的必要条件
    • 解决死锁的方法
  • 死锁预防
  • • 破环“互斥”条件
    • 破环“不可剥夺”条件
    • 破环“请求和保持”条件
    • 破环“循环等待”条件
  • 死锁避免
  • • 安全与不安全状态
    • 银行家算法
  • 死锁检测与解除
  • • 死锁检测
    • 死锁解除
  • 资源分配图
  • • 死锁的表示——资源分配图
    • 死锁判定法则
    • 资源分配图化简法

第一章 操作系统概论

操作系统的概念

计算机系统

定义：计算机系统是一种可以按用户的要求接收和存储信息，自动进行数据处理并输出结果信息的系统。计算机系统（系统资源）包含：

• 硬件系统（硬件资源）：计算机系统工作的实体承载平台，中央处理器( CPU)、内存储器、外存储器以及各类型的输入/输出设备(键盘、鼠标、显示器、打印机等)。
• 系统软件（软件资源）：保障计算机系统按用户指定的要协调工作的系统，由各种程序和数据组成，包括应用软件、支撑软件和系统软件。
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-z1Jyc5RI-1653824653094)(:/3dcdf5d648d64009bd7b22d33cfb151e)]
  通讯录不是操作系统管理的系统资源，而时钟是。

操作系统的定义

操作系统是计算机系统中的一个系统软件，操作系统的任务是：

1. 组织和管理计算机系统中的硬件及软件资源；
2. 向用户提供各种服务功能，如面向程序开发者的程序设计接口、面向用户的用户接口（命令输入和系统调用）。

操作系统的特征

1. 并发性：指在计算机系统中同时存在若干个运行着的程序，在宏观上看，这些程序在同时向前推进；
2. 共享性：指操作系统程序与多个用户程序共用系统中的各种资源，包括中央处理器，内存储器，外存储器和外部设备（互斥共享，如打印机，同时共享，如硬盘）；
3. 随机性：不能对所运行的程序行为以及硬件设备情况作出任何事先假定，是在一种随机的环境下进行的。

研究操作系统的观点

对于操作系统本质的不用看法

1. 软件的观点：操作系统是一种大型软件系统，多功能程序集合；
2. 资源管理的观点：操作系统负责记录资源请求与分配的过程，提供一些机制去协调程序间的竞争与同步，以及虚拟技术来扩充资源等。在计算机系统中，硬件和软件基本资源可以分为以下几部分：中央处理器、储存器（内存和外存）、外部设备和信息（文件）。
3. 进程的观点：：操作系统负责控制和协调运行中的程序；
4. 虚机器的观点：操作系统把原来计算机(裸机)扩充为功能强、使用方便的计算机系统；
5. 服务提供者的观点：操作系统提供了一系列功能和使得的工作环境为用户服务，为用户使用便利，该服务提供者提供了一组功能强大、方便、易用的广义指令(称为系统调用)。

操作系统的功能

1. 进程管理：对中央处理器进行管理，又称处理器管理，控制程序执行以使得CPU资源得到充分的利用；
2. 存储管理：管理计算机内存的资源，包括内存的分配与回收、存储保护、存储共享和内存扩充；
3. 文件管理：有效支持文件存储、检索和修改等操作解决文件共享、保密和保护问题，以使用户方便、安全地问文件；
4. 设备管理：操作系统向用户提供设备管理;
5. 用户接口：操作系统是用户与计算机系统间的接口，包括命令和、程序接口（一组系统调用）、图形见界面接口。

操作系统发展

手工操作—>监控程序—>多道批处理—>分时系统—>UNIX通用操作系统—>个人计算机操作系统—>Android操作系统。

操作系统的分类

批处理操作系统

1. 设计思想：收集打包成批作业，启动操作系统自动控制执行；
2. 优点：系统资源利用率高，作业吞吐率高，整个系统效率高
3. 缺点：用户不能直接与计算机交互，不适合调试程序
4. 一般指令和特权指令：用户模式(为用户服务的用户模式称为目态) , 是一般指令。特权模式(为系统专用的特权模式称为管态)，是特权指令，包括输入输出指令、停机指令等，只有监控程序才能执行特权指令。用户程序通过系统调用实现特权指令，可以实现目态到管态的转换。

SPOOLing技术

1. 设计思想：在内存中同时保持多个作业，主机可以以交替的方式同时处理多个作业。在多道批处理系统中，关键技术就是多道程序运行、SPOOLing技术（假脱机技术）等；
2. 通道：专门用来控制输入输出的硬件，实现输出输出操作和处理器动作的自动并行处理。例如，打印机打印流程。

分时系统

1. 设计思想：操作系统以时间片为单位，轮流为每个终端用户服务。
2. 特点：分时操作系统追求的目标是及时响应用户输入的交互命令，分时在前，批处理在后
   • 多路行：指有多个用户在同时使用一台计算机；
   • 交互性：指用户根据系统响应的结果提出下一个请求；
   • 独占性：指每个用户感觉不到计算机为其他人服务，因为处理速度快；
   • 及时性：指系统能够对用户提出的请求及时响应；
3. 影响时间片值设置的主要因素是：
   • 系统响应时间；
   • 就绪进程的数目；
   • 计算机的处理能力；

实时操作系统

1. 设计思想：在严格时间范围内，对外部请求做出反应，系统具有高度可靠性。严重后果—>硬实时系统，通常无灾难性的后果—>软实时系统。

嵌入式操作系统

运行在嵌入式芯片环境中，对整个芯片以及它所操作、控制的各种部件装置等资源进行统协调、调度、指挥和控制的系统软件。

个人计算机操作系统

1. 单用户多任务操作系统,如MS-DOS、WIN95、WIN98 等；
2. 多用户多任务操作系统，如WINXP、WIN7、LINUX 等。

络操作系统

为计算机 络配置的操作系统,包括 络管理、通信、安全、资源共享和各种 络应用(WEBDNSDHCPF TPEMAILVAD 等)。
多用户多任务 络操作系统： WIN2003、WIN2008、LINUX。

分布式操作系统

1. 设计思想：将大量的计算机通过 络联结在一起，可以获得极高的运算能力及广泛的数据共享；
2. 特点
   • 统一的操作系统；
   • 实现资源的深度共享：迁移式共享；
   • 透明性：感受到本地主机和非本地主机的区别；
   • 自治性：平等地位，一个主机的失效一般不会影响整个分布式系统；
3. 集群：分布式系统的一种，由群处理器密集构成，集群操作系统专门服务于这样的集群。以低成本和以太 设备构造出性能相当于超级计算机运算性能的集群。

智能卡操作系统

智能卡中的集成电路包括中央处理器CPU，实际上是一台卡上的单片机操作系统。

操作系统结构

整体式结构

将总功能分解为若干个子功能，即根据完成的功能来划分（模块组合法），实现每个子功能程序的称模块。

1. 优点：结构紧密，接口简单直接，系统效率较高；
2. 缺点：独立性差、随意性差、可适应性差。

层次结构

把操作系统的所有功能模块，按功能流程图的调用次序，分别将模块排列成若干层，各层间模块单向依赖或单向调用关系，使模块间调用的无序性（整体式结构）变为有序性。

1. 优点：整体问题局部化，各模块组织结构和依赖关系清断明了；
2. 层次式结构分层原则：
   • 适应性：为方便移植，当硬件环境改变时，放在紧靠硬件的最低层通过BIOS 修改；
   • 多操作方式：共同使用的基本部分放在内层，改变的部分放在外层；

微内核（客户机/服务器）结构

采用客户机/服务器结构的操作系统就适宜于应用在 络环境下分布式处理的计算机环境中，称为微内核结构。

1. 特点：
   • 运行在核心态(特权态度，也称管态)的内核，内核提供基本操作，如线程调度、虚拟存储、消息传递、设备驱动以及内核原语操作集和中断处理等。提供一个很小的功能集合，称为微内核；
   • 运行在用户态(非特权状态，也称目态)的进程层，除内核外，操作系统所有其它部分被分成若个相对独立的进程，实现一组服务，称为服务进程。提供系统功能、文件系统服务以及 络服务等
2. 优点：
   • 可靠：各分支独立，不受其它组成部分损坏或崩溃；
   • 灵活：各接口规范且版主维护性好；
   • 分布式：分布式处理能力；
3. 缺点：效率较低，不适用于通信频繁的系统。

第二章 操作系统运行机制

中央处理器CPU

CPU的构成和基本工作方式

1. 一般CPU由运算器、控制器、寄存器及高速缓存组成：
   • 运算器：实现任何指令中的算术和逻辑运算，是计算机计算的核心
   • 控制器：负责控制程序运行的流程，包括取指令、维护CPU 状态、CPU 与内存的交互等。
   • 寄存器：是指令在CPU 内部作处理的过程中暂存数据、地址以及指令信息的存储设备。
   • 高速缓存：处于CPU 和物理内存间，由控制器中的内存管理单元( Memory Management Unit, MMU )管理，速度快于内存，低于寄存器。
2. 处理器中的寄存器：
   • 用户可见寄存器，对程序运行速度影响很大：
     • 数据寄存器：通用寄存器，主要用于各种算术逻辑指令和访存指令，对具有浮点能力和多媒体能力的处理器来说，浮点处理过程的数据寄存器和整数处理时的数据寄存器般是分离的；
     • 地址寄存器：用于存储数据及指令的物理地址、线性地址或有效地址，用于某种特定方式的寻址如变址寄存器、段指针、栈指针等；
     • 条件码寄存器：保存在CPU 操作结果的各种标记位这些标记在条件分支指令中被测试，以控制程序指令的流向；
   • 控制和状态寄存器（不可见），操作控制处理器：
     • 控制和状态寄存器：用于控制处理器的操作，一般由具有特权的操作系统代码使用以控制其它程
       序的执行；
     • 程序计数器(Program Countef(PC 记录将要取出的指令的地址；
     • 指令寄存器(Instruction Register ，IR) ：包含最近取出的指令；
     • 程序状态字(Program Status Word, PSW) ：记录处理器运行模式信息。
3. 执行指令的基本过程：处理器从存储器读取一条指令—>执行指令。
4. 中央处理器CPU完成的工作：取指令、设置CPU状态、响应中断请求。

特权指令和非特权指令

单用户、单任务：全部指令。
多用户、多任务：区分特权指令和非特权指令。

1. 特权指令：只能由操作系统使用的指令，不允许般用户使用。如：启动某设备、设置时钟、控制中断等；
2. 非特权指令：一般用户使用的，只有简单权限。如：打开、新建、访问、读取等。

处理器的状态

1. 管态和目态
   • 管态：指操作系统管理程序运行的状态，具有较高特权级别，又称特权态(特态)、系统、内核态；
   • 目态：指用户程序运行时的状态，具有较低特权级别，又称普通态(普态)、用户态；
2. CPU状态的转换
   • 目态到管态的转换：其转换的途径是通过中断或异常中断响应时交换中断向量，新中断向量中的PSW 程序状态字的CPU 状态位标志为管态；
   • 管态到目态的转换：通过设置PSW 指令实现从操作系统向用户程序转换系统启动时CPU 初始状态为管态，装入操作系统；操作系统退出执行时，让用户程序在目态执行。

程序状态字PSW

1. CPU 工作状态代码：指明管态还是目态是操作系统还是用户；
2. 条件码：反映指令执行后的结果特征；
   • CF ：进位标志位，若算术操作产生的结果在最高有效位发生进位或借位则将其置1；
   • ZF ：结果为零标志位，若结果为0 则将其置1 ，反之清零；
   • SF ：符 标志位OF ：溢出标志位；
   • OF ：溢出标志位；
   • PF：奇偶位，如果结果的最低有效字节包含偶数个1 位则该位置1，否则清零 ；
3. 中断屏蔽码：指出是否允许中断；
   • TF：陷阱标志位；
   • IF：中断使能（中断屏蔽）标志位；
   • VIF：虚拟中断标志位；
   • VIP：虚拟中断待决标志位；
   • IOPL： IO 特权级别；

存储体系

存储器的层次结构

1. 容量：是存储系统的基础；主存-辅存结构用来解决存储系统容量的问题
2. 速度：要能匹配处理器的速度；寄存器>Cache>内存，Cache-主存结构用来解决CPU与主存速度不匹配的问题
3. 成本：选择合适的存储器的成本范围；

存储保护

对主存中的信息加以严格的保护，使操作及其它程序不被破坏，是其正确运行的基本条件之一。

1. 界地址寄存器（界限寄存器）：存放用户作业在主存中的下限和上限地址，越界中断或存储保护中断；
2. 存储键：一个由二进位组成存储保护键附加在每个存储块上；

中断与异常机制

中断与异常的概念和分类

1. 中断：指CPU 对系统中或系统外发生的异步事件的响应，是所有要打断处理器的正常工作次序，并要求去处理某一件事情的一种常用手段。包括时钟中断、输入输出中断、控制台中断和硬件故障中断等。
   • 中断源：引起中断的事件称为中断事件或中断源；
   • 中断请求：中断源向处理器发出的请求信 ；
   • 中断处理程序：处理中断事件的那段程序；
   • 中断断点：发生中断时正在执行的程序的暂停点；
   • 中断响应：处理器暂停当前程序转向处理中断的过程；
   • 中断返回：中断处理结束后恢复原来程序的执行；
   • 中断字：一个计算机系统提供的中断源的有序集合；
   • 中断向量表：中断处理程序入口地址映射表；
   • 中断向量：中断处理程序入口地址，由程序状态字PSW 和指令计数器PC 值组成；
   • 中断作用：能充分发挥处理器的使用效率，提高系统的实时能力；
2. 异常：由正在执行的指令引发的，属于内因。包括程序性中断，如算术溢出、被除零、虚拟储存中的缺页等，和访管指令（系统服务请求）异常。

中断系统

1. 中断请求的接收：在计算机硬件的中断逻辑线路和中断寄存器实现，中断逻辑线路中有若干个专接受中断信 的触发器，每个触发器称中断位，全部触发器称为中断寄存器。
   • 触发器值为1 时，表示该触发器收到中断信 （变化状态）；
   • 触发器值为0 时，表示该触发器无中断信 （初始状态）；
2. 中断响应的机制：处理器的控制部件中设置有中断信 扫描结构，在每条指令执行周期内的最后时刻扫描中断寄存器查看是否有中断信 到来。
   • 无中断信 ：处理器继续执行下一条指令；
   • 有中断信 ：处理器接收由硬件中断装置发来的中断向量代 ；
     中断请求响应工作过程：
     （1）处理器接收中断信 ；
     （2）保护现场，将中断断点程序状态字PSW 和程序计数器PC 值存入系统堆栈；
     （3） 分析中断向量，取得中断处理程序的入口地址；
     （4） 将处理器PC 置来中断处理程序的入口地址；
     （5）调用中断处理程序；
3. 中断优先级与中断屏蔽
   • 多级中断与中断优先级：在多根请求线从不同设备连接到中断逻辑线路上的中断信 的不同中断级别的级别处理；
   • 中断屏蔽：在整个中断系统中，可以允许或禁止中断系统对某些类别的中断响应，由PWS中的中断屏蔽位决定。此外还有一些不可屏蔽的中断信 ，属于机器故障中断，比如内存奇偶校验出错，掉电等。

系统调用

系统调用简介

系统调用就是用户在程序中调用操作系统所提供的一些子功能，由特殊的机器指令完成实现。系统调用可以看作是“扩充”的机器指令。

1. 系统调用与一般过程调用的区别：
   • 运行在不同的系统状态：调用程序在用户态，被调用程序运行在在系统态；
   • 状态转换：通过软中断机制由用户态转换成核心态，在操作系统核心分析后，转向相应的系统调用处理子程序；
   • 返回问题：系统调用在返回调用程序前先运行调度程序，将调用进程放入就绪队列；
   • 嵌套调用：一个被调用过程执行期间还可以调用另一个系统调用；
2. 系统调用命令是作为扩充机器指令，增强系统功能，方便用户使用提供把系统调用命令称为”广义命令”即软件实现的。系统调用的分类：
   • 进程控制类系统调用：对进程的控制，如创建和终止进程等文件操作类系统调用：对文件的系统调用,如创建、打开、关闭等；
   • 进程通信类系统调用：被用在进程间传递消息和信 ；
   • 设备管理类系统调用：被用来请求和释放有关设备，以及启动设备操作等；
   • 信息维护类系统调用：用户获取有关信息维护的系统调用，如当前时间和日期，文件的访问和修改时间等；

系统调用处理过程

1. 陷入( TRAP ) ：在系统中为控制系统调用服务的机构，或异常处理机构把由于系统调用引起处理机中断的指令称为陷入或异常指令(或称访管指令)。处理机在用户程序中执行称为用户态（目态），在系统程序中执行称为系统态（管态）。
2. 参数传递过程：
   • 通过有关通用寄存器传递；
   • 通过堆栈传递；
   • 通过陷入指令自带传递；

I/O技术

1. I/O结构：设备控制器，再由设备控制器分别控制各台外部设备的运行。对设备控制器的操作是由处理器直接发出的I/O 指令来实现CPU 定期轮询各个I/O 设备控制器的状态，如果有I/O 处理请求，CPU 就处理，直到该I/O 处理完毕。由于效率太低，已被淘汰！
2. 通道：是独立于中央处理器、专门负责数据I/O 传输工作的处理单元。通道对外部设备实行统一的管理，它代替CPU对I/O操作进行控制，从而CPU和外部设备可以并行工作，所以通道又称为I/O处理机。其原理是：
   • 逐个指令检查、启动设备；
   • 控制权转到通道；
   • 通道控制信息传送，CPU 继续执行程序；
   • 形成I/O 中断事件可以实现CPU 和各种外部设备的并行工作；
3. DMA技术：直接存储器访问( Direct Memory Access , DMA )技术通过系统总线中的一个独立控制单元，即DMA控制器，自动地控制成块数据在内存和I/0 单元间的传送。DMA 指令包含： I/O 设备编址、开始读或写的主存编址、需要传送的数据长度、是否请求一次读或写等信息。DMA请求是外设对DMA控制器提出的请求。
4. 缓冲技术：缓冲技术是用在外部设备与其他硬件部件之间的一种数据暂存技术利用存储器件在外部设备中设置了数据的一个存储区域,称为缓冲区。
   • 用途：用在外部设备与外部设备间的通信上，用在外部设备与处理器间；
   • 原因： CPU 处理数据速度与设备传输数据速度不匹配,用缓冲区缓解；

时钟

1. 时钟的作用：
   • 在多道程序环境中发现陷入死循环，防止机时浪费;
   • 在分时系统中，间隔实现各个作业按时间片轮运行;
   • 在实时系统中，按要求时间间隔输出正确时间信 ；
   • 实时唤醒按照给定时间执行的各外部事件；
   • 记录用户使用各设备的时间和外部事件发生时间间隔;
   • 记录用户和系统所需要的绝对时间，年月日；
2. 时钟相关的概念：
   • 硬件时间：电路中的晶体振荡器，每隔一定间隔产生固定的脉冲频率，时钟电路中的时钟寄存器依据时钟电路所产生的脉冲数，对时钟寄存器加1；
   • 软件时钟：利用内存单元模拟时钟寄存器，采用一段程序；
   • 绝对时钟：在计算机系统中不受外界干扰、独立运行的一种时钟；
   • 相对时钟：又称间隔时钟，只计算从某个时间初值开始的一段时间间隔；

第三章 进程线程模型

多道程序设计模型

程序的顺序执行

采用多道程序设计可以提高CPU的利用率，缩短作业周转时间，最终提高系统吞吐量。

1. 程序：一个在时间上按严格次序前后相继的机器指令或高级语言编写的语句的操作序列。程序顺序执行的特点：
   • 顺序性：程序和机器执行的活动严格按顺序执行；
   • 封闭性：资源的状态只有程序本身的动作才可以改变；
   • 确定性：程序执行的结果与它的执行速度无关也称为程序执行结果与时间无关性。CPU 在执行程序时，两个动作间停顿对程序计算结果不产生影响；
   • 可再现性：程序在不同时间执行，只要初始条件相同，何时重复执行都得到相同结果；

多道程序设计环境的变化

1. 多道程序设计技术的引入：单CPU的并发程序按给定的时间片交替在处理机执行，执行时间重叠，而多CPU 的并发程序在各自处理机上运行。顺序环境和并发环境下的利用率计算（P45）。
2. 多道程序设计环境的特点:
   • 独立性：每道程序都是逻辑独立的；
   • 随机性：程序和数据的输入与执行开始时间都是随机的；
   • 资源共享性：资源共享将导致对进程执行速度的制约；

程序的并发执行

指两个或两个以上程序在计算机系统中同处于已开始执行且尚未结束的状态，其特性是：

• 并发程序在执行期间具有相互制约关系：执行暂停执行；
• 程序与计算不再一一对应：允许多个作业调用一个共享程序段；
• 并发程序执行结果不可再现：宏观同步，在单CPU 还是顺序执行；

进程模型

进程的概念

进程( Process )是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，包括系统进程和用户进程两类。

1. 进程与程序的联系和区别：
   • 联系：程序是构成进程的组成部分之一，一个进程的运行是执行它对应的程序。进程是由程序、数据和进程控制块PCB 三部分组成；
   • 区别：程序是静态的，而进程是动态的。程序的存在是永久的，而进程是暂时的。一个进程可以执行一个或多个程序，一个程序也可以构成多个进程；
2. 进程的特性：
   • 并发性：一个进程的第一个动作可以在另一个进程的最后个动作结束前开始；
   • 动态性：进程动态产生动态消亡。在进程生命周期内状态动态变化；
   • 独立性：一个进程是个相对完整的资源分配单位；
   • 交往性：一个进程在运行过程中可能会与其它进程发生直接或间作用；
   • 异步性：每个进程按照各自独立的、不可预知的速度向前推进；

进程的状态及其状态的转换：

1. 三状态进程模型：
   (1) 运行状态：指进程已获得CPU，并且在CPU 上执行的状态，单CPU 最多一个进程处于运行态；
   (2) 就绪状态：指一个进程已经具备运行条件，但由于没有获得CPU 而不能运行所处的状态。一旦把CPU 分配给它，该进程就可运行，允许有多个就绪进程；
   (3)等待状态：也称阻塞状态或封锁状态，指进程因等待某种事件发生而暂时不能运行的状态；
   进程状态转换为：
   时间片用完，从运行状态到就绪状态。
   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FOQGuH5F-1653824653096)(:/3e67cd9614ae4e7eae2038b84bee380b)]
2. 五状态进程模型：
   (1) 运行状态( Running ) ： 进程占用处理机资源;处于此状态的进程数目小于等于处理机数目, 在没有其它进程执行时，自动执行系统的空闲进程；
   (2) 就绪状态( Ready ) ：进程已获得除处理机外的所需资源，等待分配处理机资源;只要分配处理机就可执行;
   (3) 阻塞状态( Blocked ) ：由于进行等待I/O 操作或进程同步等条件而暂停运行时处于阻塞状态，如申请系统服务或资源、通信、I/O等。即使处理机分配该进程，也无法继续执行；
   (4) 创建状态( New) ：进程正在创建过程中还不能运行，如分配和建立进程控制块表项、建立资源表格并分配资源,加载程序并建立地址空间等；
   (5) 结束状态( Exit) ： 进程已经结束运行，回收除进程控制块外其它资源，并让其它进程从进程控制块中收集有关信息；
   进程状态转换为：
   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QOiOZ8fR-1653824653097)(:/edc27079de5f4dd29dbec7e861c4e727)]
3. 七状态进程模型：进一步区分进程的地址空间状态

   • 好处：

     • 提高处理机效率：就绪进程表为空时有空闲空间用于提交新进程；
     • 可为运行进程提供足够内存：资源紧张时可把某些进程换到外存；
     • 有利于调试：在调试时挂起被调试进程，方便对其地址空间读写；

   • 四种意义有变化或新的状态：

     • 就绪状态：进程在内存且可立即进入进行状态;
     • 阻塞状态：进程在内存并等待某事件的出现;
     • 阻塞挂起状态：进程在外存并等待某事件的出现;
     • 就绪挂起状态：因为内存不足，使得进程在外存，但只要进入内存，即可运行;

   • 进程状态转换为：记下来！
     运行—>就绪：抢占处理机，时间片用完，进程创建完成
     [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jHWUmx14-1653824653098)(:/f20b6186a9c7407491ca6e4e864d0735)]

进程控制块（PCB）

进程控制块（PCB）是在操作系统核心中为进程定义一个专门的数据结构。

1. 进程的组成：由指令、数据和进程控制块（PCB）三部分组成，其中PCB是进程的灵魂所在；
2. PCB内容：分为调度信息和现场信息两大部分
   • 调度信息：供进程调度时使用的，描述了进程当前所处的状况,包括进程名、进程 、存储信息、优先级、当前状态资源清单“家族” 关系、消息队列指针、进程队列指针和当前打开文件等；
   • 现场信息：刻画了进程的运行情况。只记录那些可能会被其它进程改变的寄存器，如程序状态字、时钟等；
3. PCB组织：以适当的方式组织管理PCB
   • 线性方式：将所有PCB 不分状态组织在一个连续表
   • 索引方式：对于具有相同状态的进程，分别设置各自的PCB 索引表，表目为PCB 在PCB 表（线性表）中的地址，构成了就绪索引表和等待索引表；
   • 链接方式：对于具有相同状态进程的PCB，通过PCB 中的链接字构成一个队列。按先进先出原则出队，若队列指针为0 时，表示队尾空；
4. 进程的队列：将所有进程的PCB排成若干个队列，分类如下
   • 就绪队列：进程入队和出队次序与处理机调试算法有关；
   • 等待队列：每一个等待事件一个队列；
   • 运行队列：在单CPU 系统中整个系统有一个运行队列；

进程控制

进程控制是对进程在整个生命周期中各种状态间的转换进行有效的控制，通过原语实现

1. 原语：由若干条指令组成，用来实现某个特定的操作，通过一段不可分割的或不可中断的程序实现其功能，原语的执行必须是连续的，一旦开始执行就不能间断，直到执行结束。原语是在管态下执行，并且常驻内存。原语和系统调用都可以被进程调用，两者差别在于原语有不可中断性，它是通过在其执行过程中关闭中断实现的，且一般由系统进程调用。
2. 进程控制原语：进程状态间的转换
   • 创建原语： 一个进程可以使用创建原语创建一个新的进程，前者称为父进程，后者称为子进程，子进程又可以创建新的子进程，构成新父子关系。创建一个进程的主要任务：建立进程控制块PCB；
   • 撤销原语：撤销进程的实质就是撤销PCB，一旦PCB 撤销进程就消亡了；
   • 阻塞原语：某进程执行过程中，需要执行I/O 操作，则由该进程调用阻塞原语把进程从运行态转换为阻塞态。过程：中断CPU 执行，以PCB 现场信息中，当前状态置为等待状态,插入到该事件的等待队列去；
   • 唤醒原语：一个进程因为等待事件的发生而处于等待状态，当等待事件完成后，就用唤醒原语将其转换为就绪状态。过程：在等待队列中找到该进程，置进程的当前状态为就绪状态，然后将它从等待队列中撤出并插入到就绪队列中排队，等待调度执行。
3. UNIX类操作系用的进程控制操作：父进程通过调用fork() 函数创建子进程，步骤包括：
   • 为子进程分配个空闲proc 结构（进程描述/标识符）；
   • 赋予子进程唯一标识pid；
   • 以一次一页的方式复制父进程用户地址空间；
   • 获得了进程继承的共享资源的指针，如打开的文件等；
   • 子进程就绪，加入调度队列；
   • 对子进程返回标识符0（pid=0），向父进程返回子进程的pid（>0）；
4. fork() 函数执行特点：只被调用一次，却会返回两次，一个在调用进程(父进程)中，一次是在新创建的子进程中。P57代码分析，pid标识符问题，以及fork()后执行两次的问题。
5. wait()函数：是父进程用来获取子进程的结束状态并回收资源的。

线程模型

线程的引入

1. 线程的引入：为了减少程序并发执行时所付出的时间和空间开销，使操作系统具有更好的并发性。而引入进程的目的是为了使多个程序并发执行，以改善资源利用率及提高系统效率。

线程的概念

线程是进程中的一个实体,是处理器CPU 调度和分派的基本单位，比进程更小的基本单位。

1. 线程的属性：
   • 每个线程有一个唯一的标识符和一张线程描述表，记录了线程执行的寄存器和栈等现场状态；
   • 不同的线程可以执行相同的程序；
   • 同一进程中的各个线程共享该进程的内存地址空间；
   • 线程从创建开始经历各种状态变化；
2. 引入线程的好处：
   • 创建一个新线程花费时间少。因不需另行分配资源,因此创建线程比创建进程要快，且系统的开销也少；
   • 两个线程的切换花费时间少；
   • 由于同进程内的线程共享内存和文件，线程间相互通信无须调用内核，故不需要额外的通信机制，使通信更简便，信息传送速度也快；
   • 线程能独立执行，充分利用和发挥处理器与外围设备并行工作能力；
3. 线程与进程的比较：
   • 调度：线程作为调度和分派的基本单位，进程作为资源的基本单位；
   • 并发性：在一个进程中的多个线程之间也可以并发执行；
   • 拥有资源：线程不拥有系统资源，但也有必不可少的资源，比如线程相关的系统栈；
   • 系统开销：在创建或撤销线程时，系统付出的开销更小；

线程实现机制

线程实现的方式不同：

1. 用户级线程
2. 内核级线程
3. 混合实现方式

Pthread线程包

几个主要函数的调用
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bIxGghk2-1653824653099)(:/6b2fbaf370ae4cb3a75fd2b9104930a2)]

进程（线程）调度

进程挂起是把进程从内存转到外存，进程唤醒是把进程从外存转到内存，算法包括内外存交换算法、进程页面调入算法和进程页面淘汰算法。调度是分层次的，一般分为高级调度、中级调度和低级调度。

1. 高级调度：也称作业调度，按定原则对磁盘中处于后备状态的作业进行选择并创建为进程
2. 中级调度：按给定的原则和策略，将处于磁盘对换区中,肯具备运行条件的就绪进程调入内存
   或将处于内存就绪状态或内存阻塞状态的进程交换到对换区
3. 低级调度：进程(线程)调度是决定就绪队列中哪个进将获得处理机，并实际将处理机分配给该进程的操作

概述

1. 进程（线程）调度的主要功能：记录系统中所有进程（线程）的执行状况。
2. 进程（线程）调度的时机：
   • 正在执行的进程(线程)运行完毕；
   • 正在执行的进程(线程)调用阻塞原语将自己阻塞进入等待状态；
   • 正在执行的进程(线程)调用阻塞原语操作，因资源不足而被阻塞，或调用了唤醒原语操作激活了等待资源的进程(线程) ；
   • 时间片用完;
   • 就绪队列中的进程(线程)优先级高于当前运行进程(线程)时，引发进程(线程)调度；
3. 关于抢占：
   • 可抢占方式：即就绪队列中一旦有优先级高于当前运行进程(线程)存在时，立即进行调度，转让CPU；
   • 不可抢占方式：即一旦把CPU 分配给个进程(线程)， 就一直占用CPU，直到该进程(线程)自己因调用原语操作或等待I/O 而进入阻塞状态，或时间片用完时才让出CPU，重新执行进程(线程)调度。

调度算法设计原则

1. 进程行为：几乎所有进程的(磁盘) I/O 请求或计算都是交替突发的
2. 系统的分类：批处理、交互式和实时系统
   • 批处理系统：该处理减少了进程的切换从而改善了性能，如处理薪水册、存贷清单账目支出、利息计算(在银行)、索赔处理(保险公司)等周期性作业；
   • 交互式系统：避免一个进程霸占CPU 拒绝为其它进程服务，抢占是必需的。服务器属于此类系统，通常它们要服务多个远程用户；
   • 实时系统：只运行那些用来推进现有应用的程序,而交互式是通用的，运行任意的非协作甚至是有恶意的程序；
3. 调度算法的设计目标：取决于环境，例如批处理、交互式和实时系统，但有一些目标是适用于所有系统的，包括两个，公平和保持系统的所有部分尽可能忙碌。
   • 批处理系统：运行大量批处理作业的大型计算中心的管理为了掌握其系统的工作状态，通常检查三个指标：吞吐量、周转时间以及CPU 利用率。
     • 吞吐量：系统每小时完成的作业数量；
     • 周转时间：指从一个批处理作业提交时刻开始直到该作业完成时刻为止的统计平均时间。数据度量了用户要得到输出所需的平均等待时间，越小越好；对不同调度算法求周转时间
     • CPU 利用率：用于对批处理系统的度量；
   • 交互式系统：最小响应时间与均衡性。
   • 实时系统：是或多或少必须满足截止时间和可预测性，速率单调调度算法、最早最终实现优先调度算法。

进程（线程）调度算法

进程(线程)调度算法解决以何种次序对各就绪进程(线程)进行处理机的分配，以及按何种时间比例让进程(线程)占用处理机。

1. 先来先服务：最简单的是非抢占的先来先服务( First-Come First-Severed，FCFS )算法。进程按请求CPU 的顺序使用CPU，可用于作业调度。
2. 最短作业优先：当输入队列中有若干个同等重要的作业被启动时，调度程序应使用最短作业优先( Shortest Job First, SJF )算法。可用于作业调度。
3. 最短剩余时间优先：最短作业优先的抢占式版本是最短剩余时间优先( Shortest Remaining TimeNext ，SRTN)算法。调度程序总是选择其剩余运行时间最短的那个进程运行。
4. 轮转法：轮转( Round Robin , RR )算法最早来自分时系统，原基本思想是将CPU 的处理时间划分成一个个时间片，就绪队列中的诸进程轮流运行个时间片。当时间片结束时，就强迫运行进程让出CPU ，该进程进入就绪队列，等待下一次调度。
5. 最高优先级算法( Highest Priority First , HPF )进程(线程)调度每次将处理机分配给具有最高优先级的就绪进程(线程)。进程(线程)的优先级由进程(线程)优先数决定。进程(线程)优先级的设置可以是静态的也可以是动态的。可用于作业调度。
6. 多级反馈队列算法：多级队列算法综合了先进先出调度算法、时间片轮转算法和可抢占式最高优先级算法的一种进程(线程)调度算法。
7. 最短进程优先：如何从当前可运行进程中找出最短的那个进程，通过进程过去的行为进行推测，并执行估计运行时间最短那个，通过当前测试值和先前估计值进行加权平均而得到下一个估计值的技术称作老化( Aging )。
8. 实时系统中的调度算法：实时系统是种时间起着主导作用的系统，即系统的正确性不仅取决于计算的逻辑结果，而且还依赖于产生结果的时间。

第三章 并发与同步

进程（线程）间相互作用

1. 相关进程与无关进程
   • 相关进程：在逻辑上具有某种进程；
   • 无关进程：在逻辑

     声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！