操作系统
2022-09-06 11:05:06 14 举报AI智能生成
登录查看完整内容
操作系统知识点
作者其他创作
大纲/内容
多个事件在同一时间间隔内发生，宏观上是同时发生，微观上是有先后顺序的交替发生。
并行是指计算机真正具有同时处理多个事件的能力，在同一时刻完成多个事件的工作。（多核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根据优先级次序进行作业调度/进程调度（分抢占式/非抢占式）
优先级调度算法
公平，响应快
不能区分紧迫程度，频繁切换进程增加消耗。
缺点
按照到达就绪队列的先后顺序，轮流获取CPU在一个时间段内，进程在这个时间段内未执行完，剥夺CPU进入就绪队列
时间片轮转算法RR(Round robin)
综合考虑了等待时间和运行时间，不会出现饥饿现象
每次调用都要计算响应比
响应比=（等待时间+要求服务时间（运行时间））/要求服务时间（运行时间）
每次调用前计算作业（进程）的响应比，选择响应比最高的调用
高响应比优先算法HRRN(Hightest response ratio next)
n能够区别进程的紧急程度
可能出现饥饿现象
设置多个就绪队列，按优先级从高到低，时间片从小到大排列，只有当第1~i-1队列都为空时，才会调用第i队列
多级反馈队列调度算法
调度算法
处理机调度
带权周转时间=周转时间/执行时间
多个进程因为等待对方进程所使用的资源，导致多个进程都阻塞无法推进的现象。
进程资源请求被阻塞的同时又保持自己的资源。
请求和保持条件
进程已经获得的资源在使用完之前不能被剥夺。
不剥夺条件
导致死锁的资源不能被发生死锁的进程同时得到。
互斥条件
存在循环等待链，链中每一个进程请求的资源被下一个进程所拥有。
循环等待条件
产生的条件
缺点：可能导致资源浪费，因为有些资源只使用很小一段时间，还可能导致其它进程的饥饿现象。
进程在运行前请求运行过程中使用的所有资源，进程在运行过程中不能申请新的资源
破坏请求和保持条件
可能导致前一段的工作失效。
可能导致饥饿现象
大量申请资源释放资源，增加了系统的开销。
当进程请求资源被阻塞时，应该立即释放所拥有的所有资源
破坏不剥夺条件
并不是所有的资源都可以改成共享。
把只能互斥使用的资源改为可以共享使用。
破坏互斥条件
增加新设备时会打乱资源的序号
资源的序号和实际使用资源的顺序不同造成资源浪费
增加了用户在编程时的限制。
对系统中的所有资源进行线性排序，进程只有拥有小编号的资源才能申请大编号的资源。
破坏循环等待条件
破坏产生死锁的四个条件之一
预防死锁（静态策略）
如果系统分配资源后，找不出一个安全序列，系统就进入了不安全状态（可能发生死锁），如果进入安全状态就 一定不会发生死锁。
安全序列：按照这种序列分配资源，所有进程都能顺利进行。
表示还有多少可利用资源。长度为m的一维数组。
Available
表示各个进程对资源的最大需求数。n×m数组
Max
表示已经给各个进程分配了多少资源。n×m数组
Allocation
表示各个进程最多还需要多少资源。Max-allocation=Need
Need
表示进程申请的资源，长度为m的一维数组。
进程的请求向量
数据结构
3：所有进程的Finish[i]=ture，则系统处于安全状态。
算法步骤
安全性算法
4:进行安全性算法，检测本次资源分配后系统是够处于安全状态，否则就取消本次资源分配。
设Requesti是请求向量，Requesti[j]=K，表示进程需要K个Requesti[j]类型的资源
在进程提出资源申请后，计算能否找出安全序列，使系统进入安全状态（不可能发生死锁），如果找不到安全序列，就让进程阻塞等待。银行家算法就是计算资源在某个进程运行中能够找出一个安全序列。银行家算法就是预计每一个具备运行你条件将要运行的进程都会有阻塞的情况，计算它阻塞后系统剩下的资源依然至少有一个调用顺序可以满足其它所有的进程的运行，这样就预防了死锁。
银行家算法
在资源分配过程中防止系统进入不安全状态。
避免死锁(动态策略)
将死锁进程占有的资源剥夺
资源剥夺法
强制撤销死锁的进程
撤销进程法
将死锁的进程回退到足以避免死锁的地步
进程回退法
解除死锁的方法
资源分配图不可简化，系统就死锁。
允许死锁的发生，不过OS会检测死锁并采取措施解除死锁。
死锁的检测和解除
死锁的处理
死锁
一次仅允许一个进程使用的资源。
涉及同一个资源的临界区叫做相关临界区
每个进程访问临界资源的那段代码叫做临界区
临界区
检测是否可以进入临界区，设置正在访问临界区标志
进去区
执行访问临界资源的那段代码
处理正在访问临界区标志
退出区
做其它处理
剩余区
临界资源访问过程
临界资源
多个进程共同完成某个任务时在某些位置上的工作次序产生了制约关系。
进程调度：用合适的算法调度就绪队列中的进程。
进程同步:协调进程之间的工作次序。
和进程调度的区别
临界区空闲时，允许一个进程立即访问
空闲让等
当已有进程进入临界区时，其它进程必须等待。
忙则等待
对于请求访问临界区的进程，应保证能在有限时间内进入临界区。
有限等待
当进程不能进入临界区，应当释放处理器，防止进程忙等待
让权等待
当一个进程进入临界区，使用临界资源时，其它进程必须等待它使用完毕临界资源， 才能访问相关临界区。
进程互斥（间接制约关系）
防止两个进程为了进入临界区而无限等待。先设置自己的不允许进入标志再设置进程状态标志，这时候再检测另外一个进程的不允许进入标志和进程状态标志。
Peterson算法
软件同步机制
在锁测试以前关闭中断，在锁测试结束以后再打开中断。
关中断
简称TS(TSL)指令，是一条原语，由硬件实现，执行过程中不允许被中断。
利用Text-and-Set指令实现互斥
又称为对换指令，由硬件实现，执行过程不允许被中断。
利用Swap指令直线进程互斥
系统能及时响应外部事件的请求，在规定时间完成对该事件的处理，并控制所有实时任务协调一致的运行。
实时系统
硬件同步机制
进程同步机制
原语：原语是一种特殊的程序段，其执行不可被中断，原语由开中断/关中断指令实现。
用来解决互斥同步问题，只能被两个原语访问wait(S)、signal（S），也可记为V操作和P操作。
用于表示资源数目的整形量
整形信号量：
除需要一个用于代表资源数目的整型变量 外，再增加一个进程链表 ，用于链接所有等待该资源的进程。记录型信号量是不存在“忙等”现象的进程同步机制。
记录型信号量
互斥信号量初值mutex为1
每个进程的临界区代码置于P（mutex）V（mutex）之间
遗漏P原语不能保证互斥访问，遗漏V原语不能使用临界资源后将其释放。
同一进程中必须成对使用原语P、V，不能次序错误、重复、遗漏
实现多个进程的互斥
①分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作(或两句代码)；
③在“前操作”之后执行V；
④在“后操作”之前执行P 。
实现同步实现同步
①要为每一对前驱关系各设置一个同步变量；
②在“前操作”之后对相应的同步变量执行 操作；
③在“后操作”之前对相应的同步变量执行 操作。
实现前驱关系
基本应用
信号量
①多个彼此可以交互并共用资源的线程
②多个与资源使用有关的变量
③一个互斥锁
④一个用来避免竞态条件的不变量
管程是一种特殊的软件模块
定义
①模块化。管程是一个基本的软件模块，可以被单独编译。
②抽象数据类型。管程中封装了数据及对于数据的操作，这点有点像面向对象编程语言中的类
③信息隐藏。管程外的进程或其他软件模块只能通过管程对外的接口来访问管程提供的操作，管程内部的实现细节对外界是透明的。
④使用的互斥性。任何一个时刻，管程只能由一个进程使用。进入管程时的互斥由编译器负责完成。
管程
系统中有一组生产者进程和一组消费者进程，生产者进程每一次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注：这里的“产品”理解为某种数据)。生产者、消费者共享一个初始为空、大小为 的缓冲区。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。缓冲区是临界资源，各进程必须互斥地访问。
问题描述
①生产者—消费者之间的同步关系表现为：一旦缓冲池中所有缓冲区均装满产品时，生产者必须等待消费者提供空缓冲区；一旦缓冲池中所有缓冲区全为空时，消费者必须等待生产者提供满缓冲区。②生产者—消费者之间还有互斥关系：由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。
问题分析
①关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
②整理思路。根据各进程的操作流程确定 操作的大致顺序。
③设置信号量。设置需要的信号量，并根据题目条件确定信号量的初值。(互斥信号量初值一般为 ，同步信号量的初值需要看对应资源的初始值是多少)
PV操作题目分析的步骤：
互斥的实现是在同一个进程中进行的一对 操作。
同步的实现是在两个进程中进行的，在一个进程中执行P操作，在另一个进程中执行V操作。
如何实现
生产者消费者问题
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。
两类进程：写进程、读进程互斥关系：写进程-写进程、写进程-读进程。读进程与读进程不存在互斥问题。写者进程和任何进程都互斥，设置一个互斥信号量 ，在写者访问共享文件前后分别执行 操作。读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对 执行操作。有蜂考，不挂科如果所有读者进程在访问共享文件之前都执行操作，那么会导致各个读进程之间也无法同时访问文件。这是读者写者问题的核心思想：和其实就是对共享文件的“加锁”和“解锁”。既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问，那么我们可以让第一个访问文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。可以设置一个整数变量 来记录当前有几个读进程在访问文件。读者写者问题最核心的问题是如何处理多个读者可以同时对文件的读操作。
读者写者问题
哲学家进餐问题
进程同步（同步也叫直接制约关系）
操作系统
0 条评论
回复 删除
下一页
