王道操作系统第一二章
前言·
看到南大jyy OS的课,内存等等,当时感觉新鲜有挑战,现在暑假有时间了,却感觉头大,没拼劲了
总之,还是从简单的入手,建立好相关的概念再说
共18个小时,预计7月份9-16号,也就是一周即可刷完
呵呵,flag要倒了,因为这几天只是在看小说
参考:《王道操作系统》学习笔记总目录+思维导图_王道操作系统思维导图_BitHachi的博客-CSDN博客
感觉第一章和概念部分给了自己一种比较简单的错觉(早知道,还是王道),后面的调度、互斥很难的,只是粗浅地看视频很难学会;和计组也有一些互通的内容
第一章 操作系统概述·
1.1 OS概念功能特征·
首先举了MAC、WINDOWS、Linux的例子
然后通过计算机系统的层次结构:裸机(纯硬件)- 操作系统 - 应用程序(软件)- 用户(用户也有部分和操作系统接触)
操作系统的概念:
操作系统(Operating System,OS
)是指控制和管理整个计算机系统的硬件和软件资源,并合理地组织调度计算机的工作和资源的分配;以提供给用户和其他软件方便的接口和环境;它是计算机系统中最基本的、最接近系统硬件的系统软件。(向)
- 是系统最基本最核心的软件,属于系统软件
- 合理的组织、调度计算机的工作与资源的分配
- 为用户和其它软件提供方便的接口和环境
通过打开QQ视频聊天的例子引出了OS作为系统资源的管理者,提供的功能:
- 处理器管理
- 存储器管理
- 文件管理
- 设备管理
命令接口用户可直接使用,包含:
- 联机/交互式命令接口
- 脱机/批处理命令接口
程序接口:允许用户通过程序间接使用,可以在程序中进行系统调用来使用程序接口。普通用户不能直接使用程序接口,只能通过程序代码间接使用。
除此以外,还有GUI,当然也是属于用户可直接使用,也有认为用户接口不包括GUI的教材
![](https://img-blog.csdnimg.cn/20200220220130442.png)
操作系统的四个特征:·
- 并发
- 共享
- 虚拟
- 异步
并发:两个或多个事件在同一时间间隔内
发生,这些事件在宏观上是同时发生的,在微观上是交替发生的, 操作系统的并发性指系统中同时存在着多个运行的程序
并行
:两个或多个事件在同一时刻
发生(真的同时发生)
一个单核(CPU)同一时刻只能执行一个程序,因此操作系统会协调多个程序使他们交替进行(这些程序在宏观上是同时发生的,在微观上是交替进行的)
操作系统是伴随着“多道程序技术出现的”,因此操作系统和并发是一同诞生的
共享:资源共享,是指系统中的资源可以供内存中多个并发执行的进程
共同使用
- 互斥共享:某个资源在一段时间内只能允许
一个进程
访问;例如:摄像头 - 同时共享:某个资源在在一段时间内可以
同时
允许多个
进程访问;例如:硬盘
并发性和共享性互为存在条件(如果无法并发,那么共享没有意义,因为只能有一个程序在运行)
虚拟:是把一个物理上的实体变为若干逻辑上的对应物。物理实体实际存在,逻辑对应物是用户感受到的
- 虚拟处理器(CPU):通过多道程序设计技术,采用让多道程序并发执行的方法,分时来使用一个CPU,实际物理上只有一个CPU,但是用户感觉到有多个CPU 时分复用技术
- 虚拟存储器:从逻辑上扩充存储器容量,用户感觉到的但实际不存在的存储器 空间复用技术
技术有:空分复用技术和时分复用技术
*没有并发性,就没有必要有虚拟性,(因为,只有一个程序嘛)
异步:多道程序环境允许多个程序并发
执行,但由于资源有限,如cpu只有一个,进程的执行并不是一贯到底的,而是走走停停的,它以不可预知的速度向前推进。
由于并发运行的程序会争抢着使用系统资源,而系统中的资源有限,因此进程的执行不是一贯到底的,而是走走停停的,以不可预知的速度向前推进(看这句话好理解)可以理解成排队买饭,但拿到饭不一定是完全按排队顺序,因为有些饭做的时间长,另外,做饭做饭是一批批相同的饭做的
1.2 OS的发展与分类·
1.2 操作系统的发展和分类(手工、单道/多道批处理、分时、实时、网络、分布式、嵌入式、个人计算机)_BitHachi的博客-CSDN博客
手工操作阶段:人机速度不匹配(手工装/取纸带慢,机器相对来说更快:速度差)
批处理阶段:
- 单道批处理系统(引入脱机输入输出技术:外围机+磁带);取消了手工装/取纸带,缓解人机速度矛盾,资源利用率依然低
- 多道批处理系统(例如计算机输入输出时同时可以计算);多道程序并发执行;不提供人机交互功能(OS诞生)
分时操作系统:提供人机交互功能;无法优先处理紧急任务
实时操作系统:
- 硬实时:必须在绝对严格的规定时间内完成处理
- 软实时:能接受偶尔违法时间约定
- 能优先处理紧急任务,可靠性强
除此以外,还有网络OS、分布式OS、PC OS
*甘特图:甘特图是一种项目管理工具,用于展示项目任务在时间轴上的安排。(多项目进度横轴)
1.3 OS的运行机制–中断和异常–系统调用·
高级语言代码-编译->机器指令 程序运行的过程就是CPU执行指令的过程
内核程序和应用程序
内核程序必须是特权指令(例如内存清零),且在内核态(核心态、管态)下执行
反之,应用程序是非特权指令,在用户态/目态下执行
CPU处于内核态,说明运行的是内核程序,可以执行特权指令(拓展:CPU中有一个寄存器叫程序状态字寄存器PSW;二进制位1表示内核态,0表示用户态)
内核(Kernel)是OS中最重要的部分,有很多内核程序构成
内核态–>用户态:一条修改PSW(程序状态字寄存器)的特权指令
用户态–>内核态:由中断引起,硬件自动完成
中断和异常:
中断:会使CPU由用户态变为内核态,使OS重新夺回对CPU的控制权(中断是唯一途径)
中断类型:
*下面内中断中终止和故障可能有标注错误
- 内中断:与当前执行的指令有关,中断信号来源于CPU内部
- 试图在用户态执行特权指令 终止ABORT
- 指令非法e.g.执行除法指令,除数为0 终止ABORT
- 请求使用系统内核的服务,此时会执行一条特殊的指令–陷入指令,该指令会引发一个内部中断信号 陷入TRAP
- 故障FAULT 缺页故障
- 外中断:与当前执行的指令无关,中断信号来源于CPU外部
- 时钟中断:由中断部件发来的中断信号
- I/O中断:由I/O设备发来的中断信号
也有:内中断称为异常,外中断称为(狭义的)中断
找到相应的中断处理程序:通过中断向量表实现
系统调用:
其实如果你多练算法多敲代码多打比赛,时间长了,你就会有一种类似英语语感的这种东西,你看着这些就不再抽象,很好理解 ——某弹幕
*操作系统作为用户和计算机硬件之间的接口,需要向上提供一些简单易用的服务,主要包括命令接口和程序接口,程序接口由一组系统调用组成
系统调用:操作系统对应用程序/程序员提供的接口;可理解为可供应用程序调用的特殊函数,使处理器由用户态切换到核心态
打印机的例子:用户想要使用打印机的互斥共享资源,只能通过系统调用操作系统内核发出请求,内核会对各个请求协调处理
什么功能需要系统调用实现(凡是与共享资源相关的操作,会直接影响到其他进程的操作,需要操作系统的介入,就需要系统调用;保证系统稳定安全,防止非法操作):
- 设备管理
- 文件管理
- 进程管理
- 进程通信
- 内存管理
系统调用和库函数:系统调用处于底层;有的库函数是对系统调用的进一步封装;应用程序通过高级语言间接实现系统调用
系统调用的过程:
- 传递系统调用参数,陷入指令/Trap/访管
- 由操作系统内核程序处理系统调用请求
- 返回应用程序
1.4 操作系统的体系结构·
操作系统分为内核和非内核(例如:GUI不属于内核部分)
名称 | 大内核 | 微内核 |
---|---|---|
内核态 | 进程管理、存储管理、设备管理 + 时钟管理、中断处理、原语 | 时钟管理、中断处理、原语 |
用户态 | 进程管理、存储管理、设备管理 | |
特点 | 将OS的主要模块都作为系统内核,运行在核心态 | 只保留最基本的功能在内核 |
优点 | 高性能 | 内核功能少,结构清晰,易于维护 |
缺点 | 内核代码庞大,结构混乱,难以维护 | 需要频繁地在核心态用户态之间切换,性能低(消息传递) |
名称 | 分层结构 | 模块化 | 外核 |
---|---|---|---|
特点 | 每层可单向调用更低一层提供的接口 | 将OS按功能划分为多个模块(主模块+可加载) | 分配未经抽象的硬件资源 |
优点 | 便于调试验证 | 动态加载、适用性强;可直接调用,效率高 | 使用灵活;减少虚拟资源的映射层,提升效率 |
缺点 | 效率低,无法跨层调用;难以合理定义各层的边界 | 模块接口定义未必合理;难以调试 | 降低一致性;系统复杂 |
1.5 操作系统引导BOOT·
这一节解释:开机–> 让OS运行起来
磁盘的开头:主引导记录MBR:包含磁盘引导程序和分区表
C盘:活动分区,安装了OS
C盘的开头:引导记录PBR(负责找到“启动管理器”)和根目录
主存:RAM和ROM(BIOS):包含ROM引导程序,即自举程序
1.6 虚拟机·
虚拟机:使用虚拟化技术,将一台物理机虚拟化为多台虚拟机器(virtual machine VM/Hypervisor),每个虚拟机器都可以独立运行一个操作系统
- 直接运行在硬件上:
- 只有虚拟机管理程序运行在内核空间;其他OS运行在用户空间
- 使用特权指令时被VMM截获
- 第一类VMM运行在最高特权级(Ring 0)
- 运行在宿主操作系统上:
- 例如:VMware或VirtualBox
- 分配的是虚拟内存和虚拟磁盘
- 可迁移性更好 .iso
- 第二类VMM部分在用户态,部分在内核态
第二章 进程管理·
2.1_1 进程的概念、组成、特征·
程序:静态的,存放在磁盘里的可执行文件,一系列的指令集合
进程process:动态的,是程序的一次执行过程
*同一程序多次执行对应多个进程
区分进程:当进程被创建时,OS为进程分配唯一的、不重复的process ID进程ID、进程所属用户UID、分配的I/O设备、内存文件等
进程描述信息,进程控制管理信息,资源分配信息,处理机相关信息都被保存在一个数据结构:进程控制块PCB(Process Control Block)
进程实体(映像)的组成:PCB、程序段(程序代码/指令序列)、数据段(运行中产生的各种数据,例如变量)||进程是进程实体的运行过程,系统资源调度分配的独立单位
进程的特征:动态性、并发性、独立性、异步性、结构性
2.1_2 进程的状态与转换·
状态:
- 创建态:进程正在创建时,OS为进程分配资源、初始化PCB
- 就绪态:进程创建完成后,已经具备运行条件,由于没有空闲CPU,暂时无法运行
- 运行态:一个进程正在CPU上运行,CPU会执行该进程对应的程序(执行指令序列)
- 阻塞态:在事件发生前,进程无法继续向下执行,进程从CPU下去,进入阻塞态
- 终止态:一个进程可以执行exit系统调用,请求OS终止该进程,进程下CPU,回收内存空间等资源和PCB
进程的整个生命周期大部分处于三个基本状态:运行态、就绪态、阻塞态
运行–>阻塞 主动行为 || 阻塞–>运行 被动(不是进程能控制的)
PCB有一个变量state表示进程当前状态
进程的组织:
- 链接方式:根据状态的不同创建队列(指针指向处于XX状态的进程,队列形式)
- 索引方式:根据状态的不同创建索引表
2.1_3 进程控制·
进程控制:对系统的所有进程实施有效的管理,具有功能:实现创建新进程、撤销已有进程、进程的状态转换等
进程控制通过原语实现,原子性,执行过程中一气呵成,不允许被中断
例如:需要执行两步操作:PCB2的state设为1,将PCB2从阻塞状态队列放到就绪状态(若是此时有中断信号打断,不能一气呵成,那么就会导致OS的某些关键数据结构信息不一致)
通过关中断指令和开中断指令实现原语:执行了关中断指令后,不再例行检查(每执行一条指令检查|一条程序包含多条指令)中断信号
讲述了各种进程状态转换的原语(既流程)和切换事件(常见例子)
*作业调度:从外存中挑选一个程序,放入内存开始运行
进程切换时,先在PCB中保存这个进程的运行环境,即必要的CPU的寄存器,例如:PSW PC IR 通用寄存器
进程控制原语,通用操作:更新PCB信息,将PCB插入合适队列,分配/回收资源
2.1_4 进程间通信IPC·
进程间通信(Inter-Process Communication):指两个进程之间产生数据交互
各进程的内存地址空间独立,为保证安全,不能直接访问其他进程的地址空间
进程通信三种方式:
- 共享存储:设置共享存储区(避免出错,各个进程对共享空间的访问互斥,PV操作实现)
- 消息传递:进程间数据交换以格式化的消息为单位,进程通过"发送消息/接受消息"原语进行数据交换;通信方式:(直接,A直接发给B,间接:类似公共存储"信箱")
- 管道通信:pipe文件,开辟大小固定的内存缓冲区,FIFO单向,类似队列,限制写入读取位置,只能头或尾
- 互斥,即当一个进程正在对pipe执行读/写操作时,其它(另一)进程必须等待。
- 同步,指当写(输入)进程把一定数量(如4KB)的数据写入pipe,便去睡眠等待,直到读(输出)进程取走数据后,再把他唤醒。当读进程读一空pipe时,也应睡眠等待,直至写进程将数据写入管道后,才将之唤醒。
- linux进程的管道通信- 博客园 刚在想:管道通信为什么要互斥访问,自己想反正一个头读数据,一个尾部写数据,直接边读边写呗,上面即为解答
发现前面的章节也可能用到后面的知识,重听一遍还是很有必要的
2.1_5 线程的概念·
啊,从这开始当时啥笔记也没做,现在就得花时间了
本来想,线程不如直接把进程下划分为多个子进程,不过看到这么多线程和进程间的差异,感觉创造”线程“这个概念有必要的(QQ程序/进程,有视频聊天和文件传输两个功能/线程)感觉写的不好:子进程和线程的区别-CSDN博客 进程与子进程及线程 - 苦心明 - 博客园 (cnblogs.com)
线程是一个基本的CPU执行单元,也是程序执行流/调度的最小单位(如QQ的视频聊天和文件传输功能)
进程只作为除CPU外的系统资源的分配单位(如打印机、内存地址空间分配给进程)
线程间并发:如果同一进程内的线程切换,则不需要切换进程环境,系统开销小
2.1_6 线程的实现方式和多线程模型·
用户级线程User-Level Thread ULT
早期OS只支持进程,线程通过应用程序内(处于用户态)的线程库(调度管理线程)实现
线程库:例如 while 视频聊天,文字聊天,文件传输
用户级线程切换不需切换到核心态,系统开销小;若一个用户级线程被阻塞,整个进程阻塞
内核级线程Kernel-Level Thread KLT
管理在操作系统内核;切换线程发生变态,开销大
多线程模型
- 一对一:一个用户级线程映射到一个内核级线程
- 多对一:多个用户级线程映射到一个内核级线程
- 多对多:需用户级线程数更多(自己想的是利用同一类资源或捆绑类的,放在一起)克服了并发度不高和开销大的缺点
2.1_7 线程的状态与转换·
就绪、运行、阻塞态的转换和进程方式一致
组织控制:TCB线程控制块,和PCB类似
2.2_1 调度的概念、层次·
当有一堆任务要处理,但由于资源有限,无法同时处理这些事物,就需要确定某种规则来决定处理任务的顺序
高级调度:作业:一个具体的任务
低级调度:进程/处理机:就绪队列选取一个进程,并分配处理机
中级调度:内存:内存不足时,可将某些进程的数据从队列中调出到外存,等内存空闲或进程需要运行时再重新调入,暂时调出的进程状态称为挂起状态,举了<手机杀后台的例子>
挂起态(suspend)可细分为就绪挂起、阻塞挂起(这两个和之前的5个进程状态合并为七状态模型)
*阻塞态的程序映像还在内存,挂起态调到外存
2.2_2进程调度的时机、切换与过程、方式·
一些需要进程调度的情况:
主动放弃:
- 进程正常终止
- 运行过程中发生异常而终止
- 进程主动请求阻塞(如等待IO)
被动放弃:
- 分给进程的时间片用完
- 有更紧急的事需要处理(IO中断)
- 有更高优先级的进程进入就绪队列
不能进程切换时机:处理中断,原语,进程在操作系统内核程序临界区中
临界资源:一个时间段只允许一个进程使用的资源,各进程需要互斥地访问临界资源
临界区:访问临界资源地那段代码
进程调度的方式:
非剥夺调度方式:非抢占方式,只允许进程主动放弃处理机
剥夺调度方式:抢占方式,有更重要紧迫进程,会暂停当前执行进程
2.2_3调度器和闲逛进程·
调度器scheduler
I/O中断原理 - 博客园 (cnblogs.com)当外部设备的I/O模块准备好时,它会发送给CPU一个中断信号,CPU则会“立即”做出响应,暂停当前程序的处理去服务该I/O设备的程序。
idle闲逛进程:没有其他就绪进程时,运行闲逛进程(能耗低,指令周期末尾例行检查中断)
2.2_4调度算法的评价指标·
CPU利用率:CPU忙碌时间/总时间
系统吞吐量:单位时间内完成作业的数量
周转时间:从作业被提交给系统开始,到作业完成为止的时间间隔;平均周转时间,周转时间和/作业数;带权周转时间:作业周转时间/作业实际运行时间
等待时间:进程/作业 等待进入服务的时间
响应时间:从用户提出请求到首次产生响应所用的时间
2.2_5–2.2_7调度算法·
学习思路或关心问题:算法思想、算法规则、适用于作业调度还是进程调度、(非)抢占式、优缺点、是否导致饥饿
周转时间=完成时间-到达时间;带权周转时间=周转时间/运行时间;等待时间=周转时间-运行时间-(IO时间)
先来先服务FCFS:
非抢占式
短作业优先SJF:(J指Job,P指Process)
非抢占式:每次调度时选择当前已到达且运行时间最短的进程
抢占式的SJF,最短剩余时间优先算法SRTN:每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间更短比当前运行的时间更短,就由新进程抢占,当然,进程完成时也需要调度
在所有进程同时可运行/几乎同时到达,那么,SJF调度算法的平均等待时间、平均周转时间最少
长作业长时间无法得到服务,可能产生饥饿
高响应比优先HRRN:
每次调度时先计算每个作业的响应比,选出最高的;响应比=(等待时间+要求服务时间)/要求服务时间(如果是抢占式,要求服务时间会变化吗)
好吧,这是非抢占式的算法
*上面三种算法,没有区分任务紧急程度,交互性差,只适用早期的批处理系统
时间片轮转调度算法RR(Round-Robin):
按照各进程到达就绪队列的顺序,轮流让各个进程执行
常用于分时操作系统,更注重响应时间,因而不计算周转时间
默认新到达的进程先进入就绪队列,刚才下处理机的排在队尾
时间片太大,时间片轮转调度算法会退化为先来先服务,增大进程响应时间(例如10个进程,用完时间片后的响应时间=单个时间片*9,因此时间片大,响应时间长);时间片太小,进程切换频繁(切换进程开销占1% is OK)
优先级调度算法:
每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程
非抢占式只需在进程主动放弃处理机时调度即可,而抢占式需在每次有新来进程时检查调度
通常,系统进程、前台进程、I/O繁忙型(相比计算型)进程更优先
动态优先级:等待时间长,适当提升优先级;运行时间长,适当降低优先级
不断有高优先级进程可能导致饥饿
多级反馈队列调度算法:
设置多个就绪队列,队列的优先级逐个降低,时间片递增。该队列的进程时间片结束后,进入下一时间片队列的队尾
第二章 2.3 2.4部分·
2.3_1进程同步、进程互斥·
同步:并发性带了异步性(不确定那个进程先运行);但有时要求进程的工作顺序
互斥:对临界资源的访问,需要互斥进行,即一段时间只能允许一个进程访问资源
实现互斥的代码:
- 进入区:检查是否可以进入临界区,需要“上锁”
- 临界区:访问临界资源的实际操作代码
- 退出区:负责“解锁”
- 剩余区:其他代码
四个原则:
- 空闲让进:临界区空闲时,应允许一个进程访问
- 忙则等待:临界区正被访问时,其他试图访问的进程需要等待
- 有限等待:要在有限时间进入临界区,保证不会饥饿
- 让权等待:进入不了临界区的进程,要释放处理机,防止忙等
感觉操作系统调度、互斥的处理策略和生活中也很类似
2.3_2进程互斥的软件实现方法·
单标志法:两个进程在访问完临界区后会把使用临界区的权限交给另一个进程,即每个进程进入临界区的权限只能被另一个进程赋予
双标志先检查:设置一个布尔型数组flag[],数组中每个元素用来标记各进程想进入临界区的意愿,即检查其他的flag数组若全为false,则自己的flag[i]设为true,然后访问临界区【如果能解决检查和上锁一气呵成就OK了】
双标志后检查:先上锁后检查(避免忙则等待实现不了的意外情况,但违背了空闲让进和有限等待,产生饥饿)
Peterson算法:
1 | flag[0]=true;//0号进程表达想用的意愿 |
依然没能解决让权等待问题
2.3_3进程互斥的硬件实现方法·
中断屏蔽方法:
关中断、临界区、开中断;与原语类似,先禁止中断操作
简单高效
不适用多处理机、只适用于操作系统内核进程
TestAndSetLock指令
只是加锁操作,不区分进程,进程记录上一次锁状态为old,加锁lock=true,相当于也锁上自己和未来的下一个人,返回old;如果old是true,则有人再用,等待完毕后,自己使用,使用后,将lock锁状态修改为false,即下一个个人的返回结果old为false可用;但自己还没用完,则下一个人的old为true,下一个人无法使用
实现简单,无需像软件一样检查逻辑漏洞,使用于多处理机环境
不满足“让权等待”,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,造成忙等
Swap指令
while(old==true) Swap(&lock,&old);
也称Exchange或XCHG指令
优缺点与TSL一致
2.3_4 互斥锁·
spin lock自旋锁:需要连续循环忙等的互斥锁
需忙等,时间片用完下处理机,违反“让全等待”
优点:等待期间不用切换进程上下文,多处理机(多核)系统,若上锁时间短,等待代价低
1 | acquire(){ |
2.3_5 信号量机制·
解决了让权等待问题
整型信号量
一对原语:wait(s)和signal(s){括号里的S是函数调用时传入的一个参数}通常简写为P、V操作(荷兰语)
用一个整数型的变量作为信号量,用来表示系统中某种资源的数量(只有三种操作:初始化、P操作、V操作)
感觉让权等待和下处理机恢复是需要平衡的问题| 忙等确实太拉了,应该让进程睡眠等待,其他进程退出后唤醒睡眠进程才对 合理
记录型信号量:
相比之下增加了block和wakeup原语,感觉记录型信号量这个名字起的不好
1 | typedef struct{//记录型信号量的定义 |
2.3_6 信号量实现进程互斥、同步、前驱关系·
信号量对应资源;P(S):申请一个资源
互斥:
- 分析并发进程的关键活动,划定临界区
- 设置互斥信号量mutex初始值为1
- 进入区 P()申请资源
- 退出区 V()释放资源
1 | /*记录型信号量的定义*/ |
同步:让本来并发的进程相互配合、有序推进
semaphore=0;//初始化同步信号量,初始值为0
P1(){code1,code2,V(S),code3}; P2(){P(S),code4,code5,code6};
由于P2要执行的code4前必须要P(S),而S初始值为0,资源只能由P1()执行完code2后释放,借此实现了进程同步;V(S)放到code2后来释放资源/作为code4运行的条件。
在“前操作”之后执行V(S) code2–>V(S)
在“后操作”之前执行P(S) P(S)–>code4
前驱:就是多级同步问题
1 | 前驱图的代码逻辑://相较于数据结构的图简单得多 |
2.3_7-8 (多)生产者-(多)消费者问题·
进程和进程之间发生的等待被对方唤醒的情况称为:死锁
先互斥后同步会死锁;先互斥,那么自己也无法访问(但是感觉是条件没有配置好:问题类似于i–>0和–i>=0 运算顺序变了,修改好临界值依然可用)
多生成消费者问题:指的是产品种类
举了一个盘子,放/吃苹果、橘子的问题(当只有一个盘子资源时,不需设置mutex互斥;但例如两个盘子,可能造成两个进程写入缓冲区的数据互相覆盖的情况)
不需要分别设置4个(2乘2)唤醒,而可以通过设置单个信号量(盘子)来考虑【盘子变空的事件角度】
2.3_9 吸烟者问题·
一个生产者,生产多种产品的问题
2.3_10 读写者问题·
允许多个读者同时读操作(允许同时读和多生产者多消费者产生了差异;读者进程不会改变数据),但允许一个写者写文件,且写的时候不允许其他读写操作
P(W)可以理解为为请求服务的进程创建阻塞队列
1 | semaphore rw = 1;//实现共享文件的互斥 |
读读不互斥、写与其他互斥:核心思想:设置了一个计数器count记录当前访问共享文件的读进程数;第一个/最后一个会引发写操作的禁止或允许,而其他的则是默认允许读操作并行;
count的检查和赋值无法一气呵成,用到互斥信号量
解决写进程饥饿,是通过 P(w)w新变量,来阻塞新的源源不断的读进程,来保证一定能使count降为0,释放rw,使得可以写进程操作
2.3_11 哲学家进餐问题·
避免死锁:最多允许四名哲学家进餐,这样可以有一个哲学家可以进餐,不会死锁
要求奇数号哲学家先拿左,偶数号先拿右,相邻的会直接产生冲突,避免占有一只筷子再等待另一只的情况
设置编号:奇号先使用
1 | semaphore chopstick[5]={1,1,1,1,1}; |
可以再找博客看看
2.3_12 管程·
为什么要引入管程: 信号量机制:编写程序困难,易出错
组成:
- 共享数据结构
- 对数据机构初始化的语句
- 一组来访问数据结构的过程/函数
特征:
- 各外部进程/线程只能通过管程提供的特定入口才能访问共享数据
- 每次仅允许一个进程在管程内执行某个内部过程
管程和面向对象的“类”类似,“封装”思想
由编译器负责实现各进程互斥地进入管程中的过程;管程中设置条件变量和等待/唤醒操作,以解决同步问题
Java:关键字synchronized来描述函数:使得函数一段时间内只能被一个线程调用
1 | static class monitor{ |
2.4 死锁 预防 避免 检测和解除·
死锁的概念
各进程因竞争资源造成的一种互相等待对方资源,导致各进程都阻塞,都无法向前推进的现象
饥饿:由于长时间得不到想要的资源,某进程无法向前推进的现象
死循环:某进程执行过程中一直挑不出某个循环的现象。程序逻辑bug或故意设计
死锁产生的必要条件:
- 互斥条件
- 不剥夺条件:进程获得的资源未使用完之前,不能强行夺走,只能主动释放
- 请求和保持条件:进程已经保持了一个资源,但又提出了新的资源请求,而该资源又被其他进程占有,此时进程被阻塞,但又对自己持有的资源保持不放
- 循环等待条件:存在一种资源的循环等待链,链中的每一个进程已获得的资源同时被下一个进程所请求
实现互斥的P操作在实现同步的P操作之前,就有可能导致死锁
死锁的预防:
-
针对互斥条件:提出将互斥使用的资源(逻辑上)改造为允许共享使用,如:SPOOLing技术(缺点:系统安全)
-
不剥夺条件:设置主动释放条件;设置进程间优先级(缺点:实现复杂、可能造成之前工作失效,只适用于易保存和恢复的资源、反复申请释放资源会增大开销,降低系统吞吐量、一直放弃的话会造成饥饿)
-
请求和保持条件:设置运行前必须申请到全部资源才能获得(有些资源只需使用很短时间,但运行期间一直保持的话,会造成资源利用率低,甚至进程饥饿)
-
循环等待条件:每个进程必须按编号递增请求资源,避免申请之前进程已申请|正在占用的资源(不便于添加新设备,资源浪费,用户编程麻烦)
避免死锁:
安全序列:系统按照某序列分配资源,每个进程都能顺利完成。
若能找到一个安全序列,则系统是安全状态;当然,安全序列有多个
不安全状态只是可能发送死锁,安全状态则一定不会发生死锁
对于n个进程,m钟资源
最大需求矩阵Max;分配矩阵Allocation;最多还需求Need矩阵;长度为m的一维数组Available表示可用资源;进程Pi用一个长度为m的一维数组Requesti表示本次申请的资源数
如果Requesti[j]<=Need[i,j] (0<=j<=m);
则检查Requesti[j]<=Available[j] (0<=j<=m),则尝试分配,大于则,资源不足不分配
假设分配后,更新矩阵,检查回收后是否依然有能继续分配满足的进程/处于安全状态
多种类型资源采用多维向量 (a,b,c)
检测和解除:
考虑实现死锁检测算法的数据结构
为了对死锁检测:
- 用某种数据结构来保存资源的请求和分配信息
- 提供一种算法,利用上述信息来检测系统是否进入死锁状态
如果某时刻系统的资源分配图是不可完全简化的,那么此时系统死锁
R1有3个资源 R2有2个资源;P1申请R2两个,占用R1两个;P2占有R1,R2各一个,申请R1一个;死锁
解除:
- 资源剥夺法:挂起(暂时放到外存上),并抢占其资源,分配给其他死锁进程
- 撤销回退法(进程终止法):强制撤销部分或全部死锁进程,并剥夺资源;实现简单,代价大,需重头再来
- 进程回退法:让一个或多个死锁进程回退到足以避免死锁的地步,要求系统记录进程的历史信息,设置还原点
结束谁:进程优先级、已执行多久、还要多久、进程使用多少资源、交互式还是批处理式
第二章终于结束!1W字