操作系统核心考点（面试/期末复习）

第一章 操作系统引论一、操作系统OS的定义与作用定义OS是配置在硬件资源上的第一层软件是对硬件系统的首次扩充。核心作用作为计算机资源的管理者负责处理机管理、存储器管理、文件管理、设备管理。作为用户与计算机硬件系统的接口用户通过OS使用计算机硬件资源。作为扩充机器无软件的计算机称为“裸机”OS将裸机改造为功能更强、更易使用的“虚拟机”。二、操作系统的发展历程人工操作方式 → 脱机I/O方式 → 单道批处理系统 → 多道批处理系统 → 分时系统 → 实时系统 → 嵌入式操作系统脱机I/O事先将用户程序和数据通过纸带输入磁带CPU需用时从磁带高速调入内存减少CPU等待时间。单道批处理系统内存中仅保持一道作业连续处理缺点I/O请求时CPU处于等待状态利用率低。多道批处理系统用户作业先存于外存后备队列由作业调度程序选若干作业调入内存共享CPU和系统资源提升CPU利用率。分时系统核心满足人机交互支持多用户共享主机让每个用户感觉独占主机无其他用户干扰。实时系统分为硬实时如导弹制导系统必须严格按时完成和软实时如火车订票系统允许轻微延迟。三、操作系统的基本特征并发一段时间内宏观上有多个程序同时运行微观上CPU分时切换执行。共享系统资源被多个进程共同使用分为两种互斥共享临界资源一段时间内仅允许一个进程访问如打印机。同时共享允许多个进程同时访问如硬盘。虚拟通过时分复用、空分复用技术将一个物理实体转化为多个逻辑对应物如虚拟内存、虚拟CPU。异步进程以不可预知的速度向前推进OS通过PCB协调保证进程最终完成。四、操作系统内核内核是OS中与硬件紧密相关、最基本、最核心的软件常驻内存作用保护核心软件提高OS运行效率。内核两大核心功能一支撑功能中断处理、时钟管理、原语操作。原语由若干条指令组成完成特定功能的过程具有原子性要么全做、要么不做执行过程不可中断。原子操作不可分割的基本操作单位是原语的核心特性。二资源管理功能进程管理进程状态管理、进程调度与分配、PCB的创建与撤销。存储器管理内存空间分配与回收、内存保护、地址映射、内存扩充。设备管理缓冲区管理、设备分配与回收。五、处理机的两种工作模式用户态目态0态用户程序运行的模式仅能执行非特权指令不会损害系统。内核态管态、系统态1态OS内核运行的模式可执行特权指令如修改内存地址、控制设备。切换方式用户程序通过系统调用从用户态切换到内核态请求OS内核完成特定功能。系统调用应用程序请求OS内核完成某一功能的特殊过程调用是用户程序与OS内核交互的唯一途径。六、中断和异常一中断外中断引入目的支持CPU与设备的并行操作。定义来自CPU执行指令以外的事件与当前指令无关如I/O结束中断、时钟中断。不同计算机的中断指外中断处理过程各具特色就其多数而论中断处理流程如下图所示。各阶段处理流程的描述如下1关中断。2**保存断点。**为保证中断服务程序执行完毕后能正确地返回到原来的程序必须将原来的程序的断点即程序计数器 PC保存起来。3**引出中断服务程序。**其实质是取出中断服务程序的入口地址送入程序计数器 PC。4**保存现场和屏蔽字。**进入中断服务程序后首先要保存现场现场信息一般是指程序状态字寄存器 PSWR 和某些通用寄存器的内容。5**开中断。**允许更高级中断请求得到响应。6**执行中断服务程序。**这是中断请求的目的。7**关中断。**保证在恢复现场和屏蔽字时不被中断。8**恢复现场和屏蔽字。**将现场和屏蔽字恢复到原来的状态。9**开中断、中断返回。**中断服务程序的最后一条指令通常是一条中断返回指令使其返回到原程序的断点处以便继续执行原程序。以上是多重中断的流程其中1~3 步是由硬件中断隐指令完成的4-9 步是由中断服务程序完成的。二异常内中断、例外、陷入引入目的处理CPU执行指令本身出现的问题。定义源自CPU执行指令内部的事件分为两类出错事件如非法操作码、地址越界、算术溢出、缺页异常。用户请求如系统调用。特点处理依赖当前程序运行现场不可被屏蔽。七、操作系统的主要功能处理机管理进程控制、进程同步、进程通信、死锁处理、处理机调度。存储器管理核心是提高内存利用率包括内存分配与回收、地址映射、内存保护与共享、内存扩充。文件管理计算机中信息以文件形式存在负责文件的创建、删除、读写、保护等。设备管理完成用户I/O请求方便用户使用设备提高设备利用率。接口管理包括用户接口如图形界面、命令行和程序接口如系统调用。八、操作系统的结构简单式结构模块化结构分层式结构微内核结构仅保留OS最基本功能如进程通信、中断处理体积小、可扩展性强。外核结构第二章 进程的描述与控制一前趋图有向无环图DAG用于描述进程间执行的先后顺序如A进程完成后B进程才能执行。二程序的执行方式顺序执行特征为顺序性、封闭性独占全机资源、可再现性多次执行结果一致。并发执行特征为间断性CPU分时切换、失去封闭性共享资源、不可再现性多次执行结果可能不同。三进程的描述1. 进程的定义进程是程序的执行过程是系统进行资源分配和调度的独立单位创建进程的实质是创建其对应的PCB进程控制块。2. 进程的特征动态性由创建产生、调度执行、撤销消亡。并发性可与其他进程并发执行。独立性是资源分配和调度的独立单位。异步性以不可预知的速度推进。3. 进程的状态及转化三大基本状态就绪态等待CPU调度、执行态占用CPU运行、阻塞态等待某事件完成如I/O。补充具有挂起操作的状态转换挂起就绪、挂起阻塞核心是将进程从内存移至外存释放内存资源。四进程控制块PCB1. PCB的作用1 作为进程独立运行的基本标志创建进程即创建其PCBPCB存在则进程存在。2实现间断式运行进程中断时CPU现场信息如寄存器、程序计数器保存在PCB中再次调度时恢复。3 提供进程管理所需信息OS通过PCB实现对进程的控制和管理。4提供进程调度所需信息供调度算法选择下一个执行的进程。5实现进程间的同步与通信通过PCB中的相关信息如等待队列指针协调进程交互。2. PCB包含的核心信息进程标识信息PID进程唯一ID、父进程ID、用户ID、进程名称、优先级。进程状态信息记录当前状态新建、就绪、运行、阻塞、终止用于调度判断。处理机上下文核心程序计数器PC记录下一条要执行的指令地址、通用寄存器、程序状态字PSW用于进程切换时保存/恢复现场。进程调度信息调度优先级、时间片大小、等待队列指针、调度算法所需参数。3. PCB的组织方式操作系统中系统会把所有PCB集中管理主要三种组织方式线性表方式顺序表把所有PCB连续存放在一个数组中不管进程状态统一排列。 优点结构简单、实现容易。缺点查找、增删效率低进程多的时候开销大。链表方式最常用按照进程状态分类分别形成多条链表 就绪队列所有就绪等待CPU的进程。 运行队列当前正在运行的进程单CPU只有1个阻塞/等待队列等待某事件I/O、信号的进程。优点增删进程速度快调度方便分类清晰。缺点查找指定进程较慢。索引表方式建立若干索引表就绪索引表、阻塞索引表等。索引表中存放对应状态PCB的地址指针PCB本体集中存放。优点兼顾查找速度与动态管理适合进程数量多的系统。四进程创建终止阻塞和唤醒引起进程创建的事件用户登录作业调度批处理进程请求创建子进程提供服务系统主动创建服务进程进程创建过程申请空白PCB为新进程分配其运行所需的资源初始化PCB程序状态、优先级、程序计数器等将新进程插入就绪队列。引起进程终止的事件进程正常运行结束进程运行异常终止外界强制干预终止进程进程终止过程撤销进程的相关链接释放进程占用的各类资源回收进程控制块PCB引起进程阻塞的事件发起I/O请求等待特定事件发生等待获取临界资源进程阻塞过程当前进程放弃CPU修改PCB状态为阻塞移入对应阻塞队列调度其他进程执行。引起进程唤醒的事件进程等待的事件完成如I/O结束、资源释放、等待信号到达。进程唤醒过程将进程从阻塞队列移出修改PCB状态为就绪插入就绪队列等待系统调度。五进程通信的类型低级通信仅传递少量控制信息效率低、数据传输能力弱。共享变量信号量、信号高级通信可大批量传输数据方便高效分为三类共享存储器开辟共享内存空间进程直接读写交换数据。消息传递将通信的数据封装在消息中以消息为单位收发数据分为直接通信、间接通信。管道通信利用管道文件用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件实现父子进程或亲缘进程单向数据传输。六线程1. 线程的定义线程是进程内的一个执行单元是进程中独立的调度和执行实体一个进程可包含多个线程共享进程的地址空间与资源线程自身仅拥有少量私有资源。进程是资源分配的基本单位线程是调度的基本单位。2. 线程的基本特征轻型实体线程自身资源极少创建与销毁开销远小于进程。共享资源同一进程内所有线程共享进程内存、文件、设备等资源。独立调度线程是操作系统调度和分派的基本单位。并发执行同一进程内多线程可并发运行提升程序执行效率。依附进程线程不能独立存在进程消亡则所属所有线程随之终止。3. 线程与进程的区别资源分配单位进程是系统资源分配的基本单位拥有独立完整的地址空间与系统资源。线程仅拥有少量私有资源共享所属进程的全部资源无独立地址空间。每个线程中有线程控制块TCBThread control block调度执行单位进程早期OS以进程为调度单位切换开销大。线程现代OS以线程为调度单位切换仅需保存少量上下文开销极小。开销成本进程创建、撤销、切换开销大系统负担重。线程创建、撤销、切换速度快系统开销低。通信方式进程进程间地址空间隔离需依靠高级通信机制管道、消息、共享内存完成通信。线程同进程内线程共享地址空间可直接读写全局变量实现通信简单高效。独立性与稳定性进程各进程相互独立一个进程崩溃不会影响其他进程。线程同一进程内线程高度耦合单个线程异常崩溃会导致整个进程终止。地址空间进程拥有独立的虚拟地址空间相互隔离。线程同进程内所有线程共用同一地址空间。4. 线程的实现方式用户级线程ULT线程管理全部由用户空间的线程库完成操作系统内核感知不到线程存在仅能识别进程线程切换在用户态完成无需内核介入不用切换状态切换开销小。缺点单进程内多个用户级线程无法利用多核CPU一个线程阻塞会导致整个进程阻塞。内核级线程KLT线程的创建、调度、管理由操作系统内核实现内核可直接感知线程线程切换需陷入内核态支持多核并行执行某一线程阻塞不影响同进程其他线程。缺点线程切换、创建销毁开销相对更大。混合实现方式结合用户级线程与内核级线程的优势采用多对一、一对一、多对多映射模型既保留用户级线程低开销的特点又可借助内核级线程实现多核调度与阻塞隔离是当前主流操作系统常用方案。5. 进程和程序的区别1 程序是永存的进程是暂时的进程是程序的一个实例是程序的一次执行过程。2程序是静态的观念进程是动态的观念3程序是进程的代码部分4进程在内存中程序在外存中5进程和程序不是一 一对应的 一个程序可对应多个进程即多个进程可执行同一程序 一个进程可以执行一个或几个程序。第三章 处理机调度和死锁一处理机调度的层次三层调度高级调度外存 → 内存选作业中级调度内存 ↔ 外存换进程低级调度就绪 → 运行抢CPU1. 高级调度长程调度/作业调度对象外存后备作业功能从外存作业队列中挑选作业调入内存为其创建进程、分配资源放入就绪队列。频率最低分钟/小时级调度。作用决定多少作业进入系统调控系统负载。2. 中级调度内存调度对象挂起进程功能负责进程的挂起与激活在内存和外存之间调换进程缓解内存紧张。频率中等。作用提高内存利用率与系统吞吐量实质是存储器管理的对换功能。3. 低级调度进程调度/短程调度对象内存就绪进程/线程功能从作业的就绪队列选中一个进程分配CPU使其运行。频率最高毫秒级最频繁。作用直接决定CPU的实时分配是最核心的调度。二 作业和作业调度1. 作业作业是比程序更为广泛的概念是用户提交给操作系统的完整任务单位包含程序、数据、作业控制指令是用户请求系统完成的一项完整工作。存在位置未运行时存放在外存后备队列组成程序原始数据作业说明书关系作业调入内存后为每个作业设置了一个作业控制块JCB, 会为其创建对应进程。2. 作业调度高级调度、长程调度作业调度是处理机三层调度中的高级调度是操作系统按照一定算法从外存后备作业队列中选取合适作业调入内存分配必要资源、创建进程并加入进程就绪队列的过程。调度对象外存中的后备作业核心任务决定哪些作业可以进入内存参与竞争CPU调度频率最低执行速度慢适用场景多道批处理系统为主分时、实时系统一般无高级调度。三进程调度任务1. 进程调度任务保存CPU现场信息保存当前运行进程的**CPU现场信息便于进程再次调度时恢复执行。按某种算法选择进程按照预设调度算法从就绪队列中选择一个就绪进程。将CPU分配给进程将CPU使用权分配给选中进程恢复其运行现场使其投入运行。2. 进程调度机制排队机制系统将所有就绪进程按规则组织为就绪队列统一管理。分派机制调度程序选中目标进程后完成上下文切换分配CPU资源。切换机制保存旧进程上下文、加载新进程上下文完成进程切换。进程调度通过调度程序实现核心包含排队器、分派器、上下文切换器三个机制排队器将就绪进程按策略组织成队列以提升调度效率分派器从就绪队列中取出选定进程上下文切换器则通过保存/恢复进程的CPU现场信息如寄存器内容完成进程切换将CPU分配给新进程运行。为降低切换开销现代计算机常采用多组寄存器的硬件方案来减少切换耗时。对应示意图3. 进程调度方式1抢占式调度剥夺式当有更高优先级进程到达、或当前进程时间片用完时立即暂停正在运行的进程强行剥夺其CPU资源调度新进程执行。优点响应速度快、系统实时性强、公平性好。缺点进程切换频繁系统开销较大。适用分时系统、实时系统。2非抢占式调度非剥夺式一旦进程获得CPU就会一直运行直到进程主动放弃CPU运行结束、主动阻塞才进行调度切换。优点调度简单、切换开销小。缺点系统响应慢、紧急任务无法及时处理。适用早期批处理系统。二处理机调度算法一、调度算法目标处理机调度是合理分配CPU资源在多进程/多线程并发场景下高效利用处理器不同场景核心目标如下资源利用率最大化CPU使用率减少空闲等待时间。系统吞吐量单位时间内完成进程数量越多系统效率越高。响应时间交互式系统中缩短用户请求的等待响应时长。周转时间批处理系统核心缩短进程从提交到完成的总耗时。公平性合理分配资源保证各进程公平占用CPU避免饥饿。实时性实时系统中确保紧急任务按时限完成。二、常见处理机调度算法1. 先来先服务FCFS规则按进程到达顺序依次调度非抢占式。特点实现简单长进程会阻塞短进程短作业不利适合批处理。2. 短作业优先SJF规则优先调度预计运行时间最短的进程 即短作业分抢占式/非抢占式。特点吞吐量高、平均周转时间短易导致长进程饥饿需预估运行时长无法实现人机交互。3. 时间片轮转RR规则按到达顺序排队每个进程分配固定时间片时间耗尽则切换进程。特点抢占式响应快适配分时交互系统时间片大小影响系统性能。4. 优先级调度算法规则按进程优先级分配CPU每个进程都有一个优先数默认小的优先数优先级高高优先级优先执行分抢占/非抢占。特点可保障紧急任务低优先级进程易饥饿可通过动态优先级调整优化。5. 多级反馈队列调度规则设置多个优先级队列优先级越高的队列时间片越短新进程入高优先级队列时间片用完降级转入下一级队列I/O进程优先级提升。特点综合多种算法优势无需预知进程运行时长是操作系统默认主流调度算法兼顾交互与批处理。6. 高响应比优先HRRN规则引入响应比 (等待时间运行时间)/运行时间即响应时间/运行时间每次调度选响应比最高进程。特点兼顾短作业与长作业当等待时间相同则运行时间短的作业先执行此时类似SJF当运行时间相同则等待时间短的作业先运行此时类似FCFS避免饥饿平衡等待时间与运行时长不过调度前计算进程的响应比会增加系统开销。7. 最早截止时间优先算法EDF适用于实时系统抢占式动态调度。调度规则优先选择截止时间最早的任务投入运行。特点动态调度资源利用率高能有效保证实时任务按时完成是经典实时调度算法。8. 最低松弛度优先算法LLF适用于实时系统。松弛度公式松弛度 截止时间 - 当前时间 - 剩余运行时间调度规则每次选择松弛度最低的进程优先执行。特点实时性强临近超时任务会被优先调度防止任务错过截止时间。(三进程死锁定义必要条件处理方法一、定义指多个进程在并发执行中各自占有部分资源又互相等待对方所持有的资源导致所有进程都无法继续推进、无限阻塞的僵持状态。简单理解你拿着我需要的资源我拿着你需要的资源双方都不放手、互相等待谁都无法运行。二、死锁产生的四个必要条件缺一不可互斥条件资源同一时刻仅允许一个进程使用请求与保持进程已占有资源又申请新资源且不释放已有资源不可抢占已分配的资源不能被强行抢占只能进程主动释放循环等待进程间形成循环等待资源的闭环。三、死锁处理方法死锁预防破坏三个必要条件中任意一个互斥条件不能改变从根源杜绝死锁发生。1破坏“请求和保持”条件规定所有进程必须一次性申请全部所需资源从而破坏‘“请求”条件。只要有一种资源不能满足进程的要求即使其他资源空闲也不分配给该进程而是让其等待从而破坏了“保持”条件。2破坏“不可抢占”条件当一个进程保持了某些不可抢占资源而又提出新的资源请求必须释放已经保持的所有资源待以后需要时再重新申请。3破坏 “循环等待” 条件对系统所有资源进行统一编号排序规定所有进程必须严格按照资源编号递增顺序申请资源杜绝循环等待的环路形成。死锁避免不强制破坏必要条件动态判断资源分配安全性银行家算法为典型代表合理分配资源规避死锁。避免死锁实质在于使系统在进行资源分配前不进入不安全状态。** 银行家算法 **主要思想是避免系统进入不安全状态在每次进行资源分配时它首先检查系统是否有足够的资源满足要求如果有则先试行分配并对分配后的新状态进行安全性检查。如果新状态安全则正式分配上述资源否则拒绝分配上述资源。这样就保证系统始终处于安全状态从而避免死锁现象的发生。死锁检测与解除允许死锁自发发生系统不提前限制资源申请定期检测系统是否存在死锁若检测到死锁通过终止进程、抢占回收资源等方式解除死锁。资源分配图由进程结点、资源结点、请求边、分配边组成用来直观描述进程与资源的占用、申请关系。资源分配图的完全简化若能消去图中所有的边使所有的进程节点都成为孤立的节点则称该图为可完全简化。死锁定理资源分配图不可完全简化是系统产生死锁的充分必要条件。终止死锁进程的方法1一次性终止全部死锁进程直接杀死所有陷入死锁的进程彻底破除死锁环路。优点操作简单、快速解除死锁缺点系统开销大进程已完成的工作全部作废数据丢失严重。2逐个终止死锁进程依次撤销按照一定策略每次只终止一个死锁进程回收其资源不断检测直到死锁完全解除。常用选择策略- 优先终止优先级低的进程- 优先终止运行时间短、代价小的进程- 优先终止占用资源少的进程忽略死锁鸵鸟策略默认死锁发生概率极低不做任何处理主流操作系统普遍采用。什么是饥饿与死锁有什么差别等待时间给进程推进和响应带来明显影响时成为进程饥饿。饥饿并不代表系统已经死锁但至少有一个程序的执行被无限期地推迟。差别① 进入饥饿的进程可以只有一个但是死锁必须大于等于两个② 出于饥饿状态的进程可以是一个就绪进程但是死锁状态的进程必定是阻塞进程。四进程资源分类一、按可否抢占划分可抢占资源可强行从进程收回不会造成破坏。例CPU、内存。不可抢占资源不能强行抢占只能由进程主动释放。例打印机、磁带机。二、按使用方式划分临界资源独占资源同一时刻仅允许一个进程使用需要互斥访问。例打印机、摄像头、临界数据。共享资源可同时被多个进程并发访问。例只读文件、公共内存区域。三、按资源实例数量划分单实例资源系统仅有一个多实例资源系统存在多个可用第四章 进程同步一、进程同步基本概念1. 两种制约关系间接相互制约互斥多个进程竞争临界资源因资源独占性产生制约同一时刻仅允许一个进程访问属于互斥关系。例多个进程竞争打印机、全局变量。直接相互制约同步进程间存在执行先后次序约束为完成协作任务形成等待-唤醒关系一个进程执行依赖另一个进程的运行结果属于同步关系。例生产者写完数据消费者才能读取数据。2. 临界资源与临界区临界资源一次仅允许一个进程使用的独占型共享资源硬件/软件。例打印机、磁带机、全局变量、缓冲区。临界区每个进程中访问临界资源的那段代码片段,多个进程的临界区代码必须互斥执行。事件 Event允许一个线程在处理完一个任务后主动唤醒另外一个线程执行任务。事件分为手动重置事件和自动重置事件。手动重置事件被设置为激发状态后会唤醒所有等待的线程而且一直保持为激发状态直到程序重新把它设置为未激发状态。自动重置事件被设置为激发状态后会唤醒一个等待中的线程然后自动恢复为未激发状态。二、同步机制四条准则重点空闲让进临界资源空闲时允许请求进入临界区的进程立即进入提高资源利用率。忙则等待临界资源已被占用其他请求进程必须等待保证临界区互斥访问。有限等待等待进入临界区的进程等待时间必须有限避免永久阻塞、饥饿问题。让权等待进程无法进入临界区时主动放弃CPU转入阻塞态不忙等、不浪费处理机资源。三、实现临界区互斥的方法1. 软件实现单标志法、双标志先检查、双标志后修改、Peterson算法特点纯代码逻辑实现无需硬件支持逻辑复杂易出错。2. 硬件实现关闭中断进入临界区关中断退出开中断简单粗暴粒度大。硬件原子指令Test-And-Set、Swap指令硬件保证操作原子性。3. 信号量机制主流利用信号量PV操作高效实现同步与互斥。互斥量 Mutex互斥量是内核对象只有拥有互斥对象的线程才有访问互斥资源的权限。因为互斥对象只有一个所以可以保证互斥资源不会被多个线程同时访问当前拥有互斥对象的线程处理完任务后必须将互斥对象交出以便其他线程访问该资源比如P(mutex)与V(mutex)在临界区前后成对使用。信号量 Semaphore信号量对象保存了最大资源计数和当前可用资源计数每增加一个线程对共享资源的访问当前可用资源计数就减1如P(Semaphore), 只要当前可用资源计数大于0就可以发出信号量信号如果为0则将线程放入一个队列中等待。线程处理完共享资源后应在离开的同时将当前可用资源数加1, 如V(Semaphore),。如果信号量的取值只能为0或1那么信号量就成为了互斥量四、信号量机制1. 整型信号量定义整型变量S仅能通过P、V原语操作P操作申请资源S--若S0进程阻塞等待。V操作释放资源S若S≤0唤醒一个阻塞进程。缺点不满足让权等待存在忙等。2. 记录型信号量常用包含信号量值value 阻塞等待队列。value 0空闲资源数量value 0资源刚好占用完毕value 0等待进程的数量完全满足同步四大准则让权等待无忙等。3. 信号量分类互斥信号量初值1用于临界区互斥访问。同步信号量初值0或资源数控制进程执行先后顺序。资源信号量初值为系统可用资源总数。五、经典同步互斥问题1. 生产者-消费者问题问题描述一组生产者进程负责往缓冲区写入数据一组消费者进程从缓冲区取出数据缓冲区大小有限两者并发执行需满足缓冲区满生产者阻塞缓冲区空消费者阻塞缓冲区同一时刻仅允许一个进程访问互斥核心信号量设置empty同步信号量初值n空闲缓冲区数量full同步信号量初值0已存数据缓冲区数量mutex互斥信号量初值1保护缓冲区临界区代码核心逻辑生产者P(empty) → P(mutex) → 写入数据 → V(mutex) → V(full)消费者P(full) → P(mutex) → 取出数据 → V(mutex) → V(empty)易错点同步信号量P操作必须放在互斥信号量P操作之前防止死锁。2. 哲学家进餐问题核心矛盾竞争左右筷子临界资源易循环等待引发死锁。解决思路最多允许4位哲学家同时进餐奇数号先拿左筷、偶数号先拿右筷一次性申请两只筷子破坏循环等待条件3. 读者-写者问题读-读不互斥读-写互斥写-写互斥。第一类读者写者读者优先读进程可并发写进程易饥饿。第二类读者写者写者优先保证写操作及时执行实时性更强。六、管程1. 定义管程是一种高级同步机制将共享数据、操作数据的过程、同步控制封装为一个整体仅允许管程内过程访问共享数据自动保证互斥弱化底层PV操作难度。2. 组成共享数据结构操作数据的过程条件变量实现等待/唤醒解决同步3. 优势无需手动编写PV操作自动实现临界区互斥代码可读性强、不易出错。七、AND型信号量 信号量集AND型信号量一次性申请进程所需全部资源要么全部分配、要么全不分配破坏请求与保持预防死锁。信号量集一次性申请多个同类资源设定下限阈值提升资源分配灵活性。第五章 内存管理存储器管理的功能存储管理的主要任务是为多道程序的运行提供良好的环境方便用户使用存储器提高存储器的利用率以及从逻辑上扩充存储器故应具有以下功能内存的分配和回收实施内存的分配回收系统或用户释放的内存空间。地址变换将逻辑地址转换成物理地址。扩充内存借助于虚拟存储技术为用户提供比内存空间大的地址空间从逻辑上扩充内存。存储保护保证进入内存的各道作业都在自己的存储空间内运行互不干扰。将用户程序变为可在内存中执行的程序的步骤1编译由编译程序将用户源代码编译成若干目标模块2链接由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起形成一个完整的装入模块。3装入由装入程序将装入模块装入内存中运行。程序的链接方式静态链接在程序运行之前先把各个目标模块及所需库链接为一个完整的可执行程序以后不再拆开。装入时动态链接将应用程序编译后所得到的一组目标模块在装入内存时采用边装入边链接的链接方式。运行时动态链接知道程序运行过程中需要一些模块时才对这些模块进行链接。程序的装入方式绝对装入在编译时就知道程序将要驻留在内存的物理地址编译程序产生含有物理地址的目标代码不适合多道程序设计。可重定位装入根据内存当前情况将装入模块装入到内存的适当位置地址变换通常在装入时一次完成之后不再改变也称静态重定位。当操作系统为程序分配一个以某地址为起始地址的连续主存区域后重定位时将程序中指令或操作数的逻辑地址加上这个起始地址就得到了物理地址。动态运行装入允许程序运行时在内存中移动位置把装入模块装入到内存后的所有地址都是相对地址在程序执行过程中每当访问到相应指令或数据时才将要访问的程序或数据的相对地址转换为物理地址。动态重定位的实现要依靠硬件地址变换机构。覆盖技术和交换技术覆盖技术把一个大的程序划分为一系列覆盖每个覆盖是一个相对独立的程序单位把程序执行时并不要求同时装入内存的覆盖组成一组成为覆盖段这个覆盖段分配到同一个存储区域这个存储区域成为覆盖区它与覆盖段一一对应。覆盖段的大小由覆盖段中最大的覆盖来确定。为了解决内存容量太小的问题打破了必须将一个程序全部信息装入内存后才能运行的限制。交换技术把暂时不用的某个程序及数据部分从内存移到外存中去以便腾出必要的内存空间或者把指定的程序或数据从外存读到相应的内存中并将控制权交给他让其在系统上运行的一种内存扩充技术。处理器的中级调度就是采用交换技术。覆盖技术和交换技术区别① 与覆盖技术相比交换技术不要求程序员给出的程序段之间的覆盖结构② 交换技术主要在进程和作业之间进行覆盖技术主要在同一个进程或作业中进行交换技术主要在进程和作业之间进行覆盖技术主要在同一个进程或作业中进行③ 覆盖技术只能覆盖于覆盖程序段无关的程序段交换进程由换出和换入两个过程组成。覆盖技术只能覆盖于覆盖程序段无关的程序段交换进程由换出和换入两个过程组成。内存连续分配管理方式1.单一连续分配内存在此方式下分为系统区和用户区系统区仅提供给操作系统使用通常在低地址部分用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。这种方式的优点是简单、无外部碎片可以釆用覆盖技术不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中有内部碎片存储器的利用率极低。2.固定分区分配固定分区分配是最简单的一种多道程序存储管理方式它将用户内存空间划分为若干个固定大小的区域每个分区只装入一道作业。当有空闲分区时便可以再从外存的后备作业队列中,选择适当大小的作业装入该分区如此循环。固定分区分配在划分分区时有两种不同的方法。分区大小相等用于利用一台计算机去控制多个相同对象的场合缺乏灵活性。分区大小不等划分为含有多个较小的分区、适量的中等分区及少量的大分区。3.动态分区分配动态分区分配又称为可变分区分配是一种动态划分内存的分区方法。这种分区方法不预先将内存划分而是在进程装入内存时根据进程的大小动态地建立分区并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。动态分区分配算法在进程装入或换入主存时如果内存中有多个足够大的空闲块操作系统必须确定分配哪个内存块给进程使用这就是动态分区的分配策略考虑以下几种算法(1) 首次适应(First Fit)算法空闲分区以地址递增的次序链接。分配内存时顺序查找找到大小能满足要求的第一个空闲分区。(2) 最佳适应(Best Fit)算法空闲分区按容量递增形成分区链找到第一个能满足要求的空闲分区。(3) 最坏适应(Worst Fit)算法又称最大适应(Largest Fit)算法空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区也就是挑选出最大的分区。(4) 邻近适应(Next Fit)算法又称循环首次适应算法由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找。