操作系统王道考研

《操作系统王道考研》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

操作系统王道考研・第一章计算机系统概述•01操作系统的概念（定义）•概念（定义）•负责管理协调硬件、软件等计算机资源的工作•为上层用户、应用程序提供简单易用的服务•是ー种系统软件»资源的管理者•处理及管理•存储管理•文件管理•设备管理•命令接口・联机命令接口•直接在命令行输入•脱机命令接口»写命令脚本•02操作系统的四个特征・操作系统的特征«并发（Concurrence）最基本的特征•概念:指两个或多个事件在同一时间间隔内发生。这些时间宏观上是同时发生的,微观上是交替发生的.•并行:指两个或多个事件在同一时刻同时发生.•单核与多核•单核CPU同一时刻只能运行ー个程序,并发执行程序•多核CPU同一时刻可以执行多个程序,并行执行程序・共享（Sharing）•ー最基本的特征,二者互为存在条件•概念:即资源共享,是指系统中的资源可供内存中多个并发执行的进程共同使用.・两种资源共享方式•互斥共享方式•ー个时间段内只允许一个进程访问该资源啊・例子:摄像头,QQ和微信不能同时使用

1•同时访问方式・允许ー个时间段内由多个进程"同时"对他们逬行访问（宏观同时）・例子:发送文件、扬声器（真同时）•如果失去并发性,系统中只有一个程序正在运行,共享性失去意义.・如果失去共享性,QQ和微信不能同时访问硬盘资源,无法实现同时发送文件,也就无法并发.・虚拟（Virtual）・概念:把ー个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的,而逻辑上对应物（后者）是用户感受到的.・虚拟存储器技术,内存划分给多个程序使用:虚拟技术中的"空分复用技术"・虚拟处理器,处理器被多个程序使用:虚拟技术中的“时分复用”技术,微观上交替执行.・没有并发性,也就谈不上虚拟性・异步（Asynchronism）•概念:在多道程序环境下,允许多个程序并发执行,但由于资源有限,进程的执行不是ー贯到底的,而是走走停停,以不可预知的速度向前推逬.•如果失去并发性,系统只能串行执行各个程序,当程序执行完毕后オ会归还.只有系统拥有并发性,オ有可能导致异步性.•03OS的发展与分类•手工操作阶段・纸带•输入输出速度较慢,处理速度快,用户独占全机,人机速度矛盾,导致资源利用率极低・批处理阶段・单道批处理系统•主要特征•自动性,磁带上的作业能自动逐个运行•顺序性,作业的完成顺序与进入内存的M页序应完全相同•单道性,内存中仅有一道程序运行,即监督程序每次从磁带上只调入一道程序逬入内存运行,当该程序完成或发生异常时,オ换入其后继程序进入内存运行.•外围机•引入脱机输入働岀技术（用外围机+磁带）,并由监督程序负责控制作业的输入、输出•监督程序__操作系统的雏形•优点

2・缓解人及速度矛盾,提升资源利用率•缺点•内存中只能有一道程序运行•CPU有大量时间是在空闲等待I/O完成,利用率依然较低・多道批处理系统（操作系统开始出现）•优点・多道程序并发执行,共享计算机资源.资源利用率大幅提升,CPU和其他资源更能保持"忙碌”状态,系统吞吐量增大.•缺点•没有人机交互功能,提交作业后只能等待计算机处理,无法对中间过程逬行干预,比如调试,输入参数»分时操作系统•概念:计算机以时间片为单位轮流为每个用户/作业^务,各个用户可通过终端与计算机进行交互.•优点•用户的请求可以被即时相应,解决了人机交互问题.»允许多个用户同时使用一台计算机,并且用户对计算机的操作相互独立,感受不到别人的存在.・用户感觉独占全机

3•缺点•不能优先处理紧急任务。•操作系统对每个用户/作业都是完全公平的,循环地为每个用户/作业服务ー个时间片J不区分任务点而紧急行。・实时操作系统•计算机系统接收到外部信号后及时逬行处理,并且要在严格的时限内处理完事件.实时操作系统的主要特点是及时性和可靠性.•优点•能够响应ー些紧急任务,某些紧急任务不需时间片排队.•硬实时系统•必须在绝对严格的规定时间内完成处理.•（导弹控制系统、自动驾驶系统・软实时系统・能接受偶尔违反事件规定•网络操作系统•把网络中的各个计算机有机地结合起来,实现数据传输等功能.•实现网络中各种资源的共享（如文件共享）和个台计算机之间的通信.•WindowsNT就是ー种典型的网络操作系统,网站服务器就可以使用.»分布式操作系统•主要特点是:分布性和并行性.•系统中各台计算机地位相同,任何工作都可以用分布在这些计算机上,由它们并行、协同完成这个聞.»个人计算机操作系统

4•WindowsXP、MacOS・004操作系统的运行机制・程序是如何运行的•C语言代码・编译・机器指令（二逬制）・CPU执行机器指令•两种程序•内核程序•执彳升否又指令•应用程序»只能执行非特权指令•两种指令•特权指令»如:内存清零指令,这些指令影响重大,只允许管理者（操作系统内核）使用。•非特权指令•如:加法指令、减法指令。・两种处理器状态•用于区分此时正在运行的是内核程序or应用程序•内核态（核心态、管态）»运行的是内核程序»可以执行特权指令•用户态（目态）»运行的是应用程序»只能执行非特权指令•如何区分这两种状态?・CPU中的PSW寄存器（程序状态字寄存器）,其中有个二进制位,1表示"内核态"0表示"用户态"•ロ两种状态的切换•内核态•用户态•执行一条特权指令一修改PSW的标志位为用户态,操作系统主动让出CPU控制权・用户态•内核态

5•由"中断"引发,CPU硬件自动完成变态过程,触发中断信号意味着操作系统将强行夺回CPU的使用权・05中断和异常•中断的作用•中断会使CPU由用户态变为内核态,使操作系统重新夺回对CPU的控制权•如果没用中断机制,就无法逬行并发•中断是操作系统内核夺回CPU使用权的唯一途径・中断的类型•内中断（也称异常、例外）•与当前执行的指令有关,中断信号来源于CPU内部»由某个指令引发的中断•陷阱、陷入（trap）•由陷入指令引发的,是应用程序故意引发的•如:系统调用•故障（fault）•由错误条件引起,可能被内核程序修复。•如:缺页故障•终止（abort）・由致命错误引起,内核程序无法修复该错误.•如:整数除。、非法使用特权指令•外中断（也称中断）•与当前执行的指令无关,中断信号来源于CPU外部•时钟中断•由时钟部件发来的中断信号•时钟部件每隔ー个时间片,归给CPU发送ー个时钟中断信号•I/O中断・由输入输出设备发来的中断信号•中断机制的基本原理•不同的中断信号,需要用不同的中断处理程序来处理•内中断:CPU在执行指令时会检查是否有异常发生»外中断:每个指令周期末尾,CPU都会检查是否有外中断信号需要处理。•中断向量表•CPU检测到中断后,根据中断信号的类型去查询中断向量表,找到相应的中断处理程

6序（运行在内核态）在内存中的存放位置•06系统调用•什么是系统调用?•概念:操作系统提供给应用程序（程序员7编程人员）使用的接口,可以理解为一种可供应用系统调用的特殊函数,应用系统可以通过系统调用来请求获得操作系统内核的服务。・程序接口由系统调用组成。・系统调用与库函数的区别・普通应用程序•直接逬行系统调用»使用库函数（有的库函数会涉及系统调用）•编程语言•向上提供库函数•或把系统调用封装为库函数•操作系统・向上提供系统调用・小例子:为什么系统调用是必须的?•用户通过系统调用请求资源,由操作系统内核进行统一管理分配,避免混乱。•什么功能要用系统调用实现?・系统调用（按功能分类）•设备管理

7・完成设备的请求/释放Z启动等功能•文件管理•完成文件的读/写/创建/删除等功能•进程控制•完成逬程的创建Z撤销/阻塞/唤醒等功能•进程通信•完成逬程之间的消息传递7信号传递等功能•内存管理•完成内存的分配/回收等功能・系统调用的过程•传递系统调用参数•执行陷入/trap/访管指令（用户态）•内核程序处理系统调用（核心态）•返回应用程序・07操作系统的体系结构•内核・对系统资源进行管理的功能•进程管理»存储器管理•设备管理•时钟管理•利用时钟中断实现计时功能•中断处理•原语（设备驱动、CPU切换等）•ー种特殊的程序,具有原子性.这段程序的运行不能被中断。・变态的过程是有成本的,消耗时间,频繁地变态会降低系统性能

8・非内核功能・如:GUI•Ubuntu、CentOS主要工作是实现内核功能,内核都是使用Linux内核•大内核•将操作系统的主要功能模块都作为系统内核,运行在核心态•优点:高性能•缺点:内核代码庞大,结构混乱,难以维护.•典型的大内核/宏内核Z单内核操作系统•Linux、Unix•微内核•只把最基本的功能保留在内核•优点:内核功能说好,结构清晰,方便维护•缺点:需要频繁地在核心态和用户态之间切换,性能低•典型的微内核操作系统•WindowsNT•第二章进程管理•01进程的概念、组成、特征•概念・进程和程序的区别・程序:是静态的,就是个存放在磁盘里的可执行文件,就是一系列的指令集合.・进程（Process）:是动态的,是程序的ー次执行过程.・操作系统如何区分逬程•当进程被创建时,操作系统会为该逬程分配ー个唯一的、不重复的PID（ProcessID,进程ID）•ー个逬程实体（进程映像）由PCB、程序段、数据段组成•进程是动态的,进程实体是静态的•进程是逬程实体的运行过程,是系统进行资源分醐ロ调度的ー个独立单位。•PCB是进程存在的唯一标志!•进程控制块（PCB）・进程描述信息・进程标识符P1D

9•用户标识符UID・进程控制和管理信息•CPU、磁盘、网络流量使用情况统计・逬程当前状态:就绪态/阻塞态/运行态…・资源分配清单•正在使用哪些文件•正在使用哪些内存区域•正在使用哪些I/O设备•处理机相关信息•PSW、PC等等各种寄存器的值（用于实现进程切换）•程序段・三个QQ进程的程序段相同,数据段、PCB不同•数据段•梅正•动态性（逬程最基本的特征）•进程是程序的一次执行过程,是动态地产生、变化和消亡的.•并发性•内存中有多个逬程实体,各进程可并发执行•独立性•逬程是能独立运行、独立获得资源、独立接受调度的基本单位•异步性・各进程按各自独立的、不可预知的速度向前推逬,操作系统要提供“逬程同步机制”来解决异步问题。・结构性•每个逬程都会配置一个PCB。结构上看,进程由程序段、数据段、PCB组成。・02进程的状态与转换»状态•运行状态（Runing）»占有CPU,并在CPU上运彳亍•单核CPU同一时刻只会有一个进程处于运行态,多核CPU可能有多个进程处于运行态•就绪状态（Ready）•具备运行韶牛,但由于没有空闲CPU,而暂时不能运行

10•阻塞状态（Waiting/Blocked,又称:等待态）（三种基本状态）»因等待某ー事件而暂时不能运行•创建状态（New,又称新建态）・进程正在被创建,操作系统为进程分配资源、初始化PCB•终止状态（Terminated,又称:结束态）»进程正在从系统中撤销,操作系统会回收进程拥有的资源、撤销PCB•state变量,1表示创建态,2表示就绪态,3表示运行态•状态间的转换•就绪态•运行态•进程被调度•运行态•就绪态»时间片到•处理机被抢占•运行态•阻塞态»等待系统资源分配・或等待某时间发生（逬程主动行为）・阻塞态・就绪态•资源分配到位,等待的事件发生（被动行为）,操作系统发起

11[gpr\BBBMl123332SIj阻塞态今就绪态是不是进程自身、＞——匕/能控制的，是ー不…,料械动行为..|注意:不能由阻塞态直接转换为运行态,x也不能由就緒态直接转换为阻事态（因为祺A爼富本・进程・就・»囲,必然需要•进程的组织方式•链接方式•按照逬程状态将PCB分为多个队列•操作系统持有指向各个队列的指针•过程•索引方式タ喇曲・11/歯師显ヨ111运行态今阻塞态是ー种进程自身做出的主动行为1^^23■•根据逬程状态的不同,建立几张索引表•操作系统持有指向各个索引表的指针•过程

12阻事索引衣・03进程控制•基本概念•概念:进程控制的主要功能是对系统中的所有进程实施有效的管理,它具有创建新进程、撤销已有进程、实现进程状态转换等功能。•实质:实现逬程状态转换•过程图•如何实现进程控制:用“原语"实现•如何实现原语的"原子性"•用关中断指令和开中断指令这两个特权指令实现原子性・逬程控制相关的原语•进程的创建•创建原语•申请空白PCB•为新锦成分配所需资源•初始化PCB•将PCB插入就绪队列（创建态•就绪态）•引起逬程创建的事件・用户登录•分时系统中,用户登录成功，系统会为其建立一个新的进程•作业调度

13・多道批处理系统中,有新的作业放入内存时,会为其建立一个新的进程•提供服务•用户向操作系统提出某些请求时,会新建一个逬程处理该请求•应用请求•由用户进程主动请求创建一个子逬程・进程的终止・就绪态/阻塞态/运行态・终止态・无•撤销原语•从PCB集合中找到终止进程的PCB•若进程正在运行,立即剥夺CPU,将CPU分配给其他逬程•终止其所有子进程・进程间的关系是树形结构•将该进程拥有的所有资源归还给父进程或操作系统•删除PCB»引起逬程终止的事件•正常结束»进程自己请求终止（exit系统调用）•异常结束•整数除〇、非法使用特权指令,然后被操作系统强行杀掉•外界干预・Ctrl+Alt+delete,用户选择杀掉逬程・逬程的阻塞•阻塞原语（运行态•阻塞态）•找到要阻塞的进程对应的PCB•保护进程运行现场,将PCB状态信息设置为“阻塞态",暂时停止进程运行•将PCB插入响应时间的等待队列•引起逬程阻塞的事件•需要等待系统分配某种资源•需要等待相互合作的其他逬程完成工作・进程的唤醒（成对出现）•唤醒原语（阻塞态・就绪态）

14•在事件等待队列中找到PCB•将PCB从等待队列移除,设置逬程为就绪态•将PCB插入就绪队列,等待被调度•引起逬程唤醒的时间・等待事件发生（因イ可事阻塞,就应由何事唤醒）・进程的切换»切换原语（运行态・就绪态、就绪态・运行态）•将运行环境信息存入PCB•PCB移入相应队列•选择另ー个逬酬行,并更新其PCB•根据PCB恢复新进程所需的运行环境»引起逬程切换的事件•当前进程时间片到•有更高优先的进程il!达•当前逬程主动阻塞•当前逬雌止•04进程通信•逬程之间的信息交换•共享存储•设置f共享空间•要互斥地访问共享空间•两种方式•基于数据结构的共享（低级）・基于存储区的共享（高级）•消息传递•进程间的数据交换以格式化的消息（Message）为单位.•进程通过操作系统提供的"发送消息/接收消息"两个原语进行数据交换•消息头,消息体•直髄B方式•消息直接挂5リ接收进程的消息缓冲队列上•间凝信方式

15•消息要先发送到中间实体（信箱）中,因此也称（信箱通信方式）。•例子:电子邮件系统•管道通信•只能采用半双工通信,某ー时间段内只能实现单向的传输•各逬程要互斥地访问管道•数据以字节流写入管道,当管道写满时,写进程的write。系统调用将被阻塞,等待读进程将数据取走。当数据被全部取走,管道变空,读进程的read。系统调用将被阻塞。•如果没写满,就不允许读。如果没读空,就不允许写.•数据一旦被读出,就被抛弃,因此,读逬程最多只能有一个•05线程・什么是线程,为什么要引入线程?•线程是ー个基本的CPU执行单元,也是程序执行流的最小单元。•引入编航,进籲线可以并发,进程内的各绩貶间也可以并发•引入线程后,进程只作为除CPU之外的系统资源的分配单位・打印机、内存地址空间都是分配给进程的•引入线程机制后,有什么变化・资源分配、调度»传统逬程机制中,进程是资源分配、调度的基本单位・引入线程后,逬程是资源分配的基本单位,线程是调度的基本单位•并发性・传统逬程机制中,只能进程间并发・引入线程后,各线程间也能并发,提高了并发度•系统开销・传统的逬程间并发,需要切换进程的运行环境,系统开销很大・线程间并发,如果是统ー进程内的线程切换,不需要切换进程环境,开销小・引入线程后,并发所带来的系统开销减小・线程有哪些重要的属性•线程是处理机调度的单位•多CPU计算机中,各个线程可占用不同的CPU•每个线程都有一个线程id,线程控制块（TCB）•线程也有就绪、阻塞、运行三种基本状态•线程几乎不用有系统资源•同一逬程的不同线程间共享逬程的资源

16•由于共享内存地址空间,同一逬程中的线程间通信甚至无需系统干预•同一逬程中的线程切换,不会引起进程切换•不同逬程中的线程切换,会引起进程切换•切换同逬程内的线程,系统开销很小•切换逬程,系统开销较大・06线程的实现方式ー多线程模型»线程实现的方式«用户级编呈(User-Level-thread,ULT)»线程库•优点・开销小,效率高•缺点•如果单个线程被阻塞,整个进程都会被阻塞,并发度不高。•多个线程无法在多核处理机上并行运行.•内核级线程•操作系统会为每个内核级线程建立相应的TCB(ThreadControlBlock,线程控制块),通过TCB对线程逬行管理。‘内核级线程"就是"从操作系统内核视角看能看到的线程“•优点•当一个线程被阻塞后,别的线程还可以继续执行,并发能力强。•多线程可在多核处理机上并行执行。•缺点・ー个用户进程会占用多个内核级线程,线程切换由操作系统内核完成,需要切换到核心态,因此线程管理的成本高,开請大。・多线程模型»ー对ー模型»ー个用户级线程映射到ー个内核级线程。每个用户进程有与用户级线程同数量的内核级雌•优点

17•当ー个线程被阻塞后,别的线程还可以继续执行,并发能力强。•多线程可在多核处理机上并行执行。•缺点•ー个用户逬程会占用多个内核级线程,线程切换由操作系统内核完成,需要切换到核心态,因此线程管理的成本高,开销大。•多对ー模型•多个用户级线程映射到一个内核级线程。且ー个进程只被分配ー个内核级线程。•优点・用户级线程的切换在用户空间即可完成,不需要切换到核心态,线程管理的系统开销小,效率高•缺点•当ー个用户级线程被阻塞后,整个逬程都会被阻塞,并发度低。多个线程不可在多核处理机上并行运行•操作系统只"看得见"内核级线程,因此只有内核级线程オ是处理机分配的单位。・多对多模型・n用户及线程映射到m个内核级线程（n>=m）。每个用户进程对应m个内核级线程。•克服了多对一模型并发度不高的缺点（ー个阻塞全体阻塞）,又克服了一对ー模型中一个用户进程占用太多内核级线程,开销太大的缺点。・用户级线程是"代码逻辑”的载体•内核级线程是"运行机会"的载体・07处理机调度概念、层次・处理机调度•基本概念•当有一堆任务要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的丿1项序,这就是“调度”研究的问题。•三个层次•高级调度（作业调度）•按一定的原则从外存的作业后备队列中挑选ー个作业调入内存,并创建进程,毎个作业只调入一次,调出ー次。作业调入时会建立PCB（调出时オ撤销PCB.・中级调度（内存调度）•按照某种策略决定将哪个处于挂起状态的进程重新调入内存。•内存不够时,可将某些逬程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。•暂时调到外存等待的进程状态为挂起状态（挂起态,suspend）.被挂起的逬程PCB会被组织成挂起队列

18•高频・低级调度（逬程调度/处理机调度）•按照某种策略从就绪队列中选取一个逬程,将处理机分配给它.•进程调度是操作系统中最基本的ー种调度,在一般的操作系统中都必须配置进程调度。・三层调度的联系、对比要做什么训虎发生在・.金重演时进市间级谢皮（作业谢庚）テ】抜汹ノ曳＜内存涮度＞低纟及谢皮按，探累キリ虫りUJ,从后路队歹リタト存ー内存「卜选手笔合玷:的イ乍セ将エセ谢入（mfr句作、1セ）内"•Jfソッ1セ仓リ建进手学依1憔把和】现リ!リ,从珏身队ダリタトイ，つ内疗,い选抒件适がJ进程がfi（数妳;＜IfiiKリ进程）週IE內行按，憔栄种规リリJ・从沈缙队歹リ内存ーCPU如U氐无-＞仓リ中智在后CIUI辜キ椒,就缙（进程训，望）ヰ・选拝ーー个进程为声i3•Nd处aa机•补充知识・进程的“挂起态"•就绪挂起•阻塞挂起»七状态模型・08进程调度的时机、切换与过程调度方式»的•什么时候需要逬程调度?•主动放弃•进程正常终止•运行过程中发生异常而终止•逬程主动请求阻塞（如等待レ〇）•被动放弃«分给逬程的时间片用完•有更紧急的事需要处理（如I/O中断）•有更高优先级的进程进入就绪队列•什么时候不能进行进程调度?

19•在处理中断的过程中。中断处理过程复杂,与硬件密切相关,很难做到在中断处理过程中进行逬程切换.•进程在操作系统内核程序临界区中。•在原子操作过程中（原语）.原子操作不可中断,要一气呵成（如之前讲过的修改PCB中进程状态标志,并把PCB放到相应队列）•2012年联考真题»进程在操作系统内核程序临界区中不能进行调度与切换口•进程处于临界区时不能进行处理机调度口•普通临界区/内核临界区•临界资源•一个时间段内只允许ー个逬程使用的资源。各逬程需要互斥地访问临界资源。•临界区・访问临界资源的那段代码。•内核程序临界区・一般是用来访问某种内核数据结构的・如:进程的就绪队列（由各就绪进程的PCB组成）•切换与过程•"狭义的调度”与“切换"的区别•狭义的逬程调度•指的是从就绪队列中选中一个要运行的逬程。（这个进程可以是刚刚被暂停执行的进程,也可能是另ー个进程,后ー种情况就需要进程切换）•进程切换•指一个进程让出处理机,由另一个逬程占用处理机的过程。•广义的逬程调度包含了选择ー个逬程和进程切换两个步骤。•进程切换的过程需要做什么?・过程•对原来运行进程各种数据的保存・对新的逬程各种数据的恢复（如:程序计数器、ネ呈序状态字、各种数据寄存器等处理机现场信息,这些信息一般保存在逬程控制块）»有代价的,如果过于频繁进行进程调度、切换,系统的效率会降低。•方式•非剥夺调度方式（非抢占式）・非剥夺调度方式,又称^抢占方式。即,只允许逬程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该逬程终止或主动要求

20进入阻塞态。・实现简单，系统开销小但是无法及时处理紧急任务,适合于早期的批处理系统•剥夺调度方式（抢占式）»剥夺调度方式,又称抢占方式。当ー个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机,则立即暂停正在执行的逬程，将处理机分配给更重要紧迫的那个进程。・可以优先处理更紧急的进程,也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统・09调度算法的评价指标（计算）•CPU利用率•指CPU"忙碌”的时间占总时间的比例。•利用率=忙碌的时间/总时间（道Z秒）•甘特图•系统吞吐量.单位时间内完成作业的数量・系统吞吐量=总共完成了多少道作业/总共花了多少时间•周转时间•周转时间・指从作业被提交给系统开始，到作业完成为止的这段时间间隔。・（作业）周转时间=作业完成时间一作业提交时间・四部分•作业在外存后备队列上等待作业调度（高级调度）的时间•进程在就绪队列上等待进程调度（低级调度）的时间•进程在CPU上执行的时间•逬程等待I/O操作完成的时间•后三项在ー个作业的整个处理过程中，可能发生多次。•平均周转时间»平均周转时间=各作业周转时间之和/作业数•带权周转时间•带权周转时间=作业周转时间/作业实际运行的时间•平均带权周转时间・平均带权周转时间=各作业带权周转时间之和/作业数•等待时间

21・指进程/作业处于等待处理机状态时间之和.・对于进程来说,等待时间就是指进程建立后等待被服务的时间之和,在等待I/O完成的期间其实进程也是在被服务的,所以不计入等待时间。・对于作业来说,不仅要考虑建立逬程后的等待时间,还要加上作业在外存后备队列中等待的时间。・调度算法只会影响作业;逬程的等待时间。・平均等待时间即各个逬程/作业等待时间的平均值•响应时间•指从用户提交请求到首次产生响应所用的时间.・10调度算法先来先服务、最短作业优先、最高响应比优先•先来先服务（FCFS,FirstComeFirstServe）•算法规则•按照作业/进程到达的先后顺序进行服务•用于作业7进程调度•用于作业调度时,考虑的是哪个作业先到达后备队列•用于逬程调度时,考虑的是哪个逬程先到达就绪队列•非抢占式•优点•公平、算法实现简单•缺点•排在长作业（逬程）后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好。即，FCFS算法对长作业有利,对短作业不利»例如:排队买奶茶・最短作业优先（SJF）•思想•追求最少的平均等待时间,最少的平均周转时间、最少的平均平均带权周转时间•算法规则•最短的作业/逬程优先得到服务(所谓"最短”,是指要求服务时间最短)•每次调度时选择当前已到达且运行时间最短的作业Z进程•用于作业7进程调度・即可用于作业调度,也可用于进程调度。•用于逬程调度时称为"短进程优先(SPF,ShortestProcessFirst)算法•非抢占式•SJF和SPF是非抢占式的算法。但是也有抢占式的版本最短剩余时间优先算法

22(SRTN,ShortestRemainingTimeNext)•最短剩余时间优先算法:每当有逬程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则由新逬程抢占处理机,当前运彳亍近程重新回到就绪队列.另外,当ー个逬程完成时也需要调度。・细节•如果未特别说明,短作业/进程优先算法默认是非抢占式的•在所有进程都几乎同时到达时,采用SJF调度算法的平均等待时间、平均周转时间最少•抢占式的短作业/进程优先调度算法(最短剰余时间优先,SRNT算法)的平均等待时间、平均周转时间最少"•缺点»对短作业有利,长作业不利.•可能产生饥饿现象。»最高响应比优先(HRRN,HighestReponseRatioNext)•思想•要综合考虑作业/进程的等待时间和要求服务的时间•算法规则•在每次调度时先计算各个作业/逬程的响应比,选择响应比最高的作业/进程为其服务•响应比=(等待时间+要求服务时间)/要求服务时间•用于作业7进程调度•既可用于作业调度，也可用于逬程调度•是否可抢占•非抢占式的算法。因此只有当前运行的作业/逬程主动放弃处理机时，オ需要调度，才需要计算响应比

23•优缺点»综合考虑了等待时间和运行时间（要求服务时间）等待时间相同时,要求服务时间短的优先（SJF的优点）要求服务时间相同时,等待时间长的优先（FCFS的优点）对于长作业来说,随着等待时间越来越久,其响应比也会越来越大,从而避免了长作业饥饿的问题•是否饥饿»不会导致饥饿•三种算法的ヒ檄ァ法贝リ官r珀占ア优点生息FCFS白日回七ョヒ为:占べ公干:如映府・力总!イ乍”ヒ手不リSJF/S二IFM3汨拉ノぎコ弋・|_一人上为ムロqi中地・,叁作业不和,PF-tZしセイザSJFg拉后ペ.WIMJ562导マサしt我:雄以IRRZ广!已回ヨト・仓占テ弋j.注加和,。立あ介勺权後!+。口ケ「"J春n-キ亍ロナ「，リ•适用性•适用于早起的批处理系统,FCFS算法也常结合其他的算法使用•11调度算法——时间片轮转、优先级调度、多级反馈队列•时间片轮转调度算法（RR,Round-Robin）•算法规则•按照各逬程？U达就绪队列的顺序,轮流让各个逬程执行一个时间片（如!00ms）,若逬程未在ー个时间片内执行完,则剥夺处理机,将逬程重新放到就绪队列队尾重新排队.•用于作业7进程调度»用于逬程调度（只有作业放入内存建立了相应的进程后,才能被分配处理机时间片）•是否可抢占•若逬程未能在时间片内运行完,将被强行剥夺处理机使用权,因此时间片轮转调度算法属于抢占式的算法.•由时钟装置发出时钟中断来通知CPU时间片已到・•优缺点•优点•公平;响应快,适用于分时操作系统.»缺点・由于高频率的进程切换,因此有一定开销;不区分任务的紧急程度.•不会饥饿•时间片过大的影响

24・如果时间片太大,使得每个进程都可以在一个时间片内就完成,则时间片轮转调度算法退化为先来先服务调度算法,并且会增大进程响应时间。因此时间片不能太大。»优先级调度算法•算法思想•随着计算机的发展,特别是实时操作系统的出现,越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。•调度规则・调度时选择优先级最高的作业/进程•用于作业调度7进程调度•既可用于作业调度,也可用于进程调度。甚至,还会用于在之后会学习的I/O调度中•是否可抢占•抢占式、非抢占式都有。做题时的区别在于:非抢占式只需在逬程主动放弃处理机时逬行调度即可,而抢占式还需在就绪队列变化时,检查是否会发生抢占。•优缺点»优点•用优先级区分紧急程度、重要程度,适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。•缺点・若源源不断地有高优先级逬程到来,则可能导致饥•会导致饥饿・多级反馈队列调度算法•算法思想・对其他调度算法的折中权衡•算法规则•设置多级就绪队列,各级队列优先级从高到低,时间片从小到大•新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束,则进程进入下ー级队列队尾。如果此时已经在最下级的队列,则重新放回最下级队列队尾•只有第k级队列为空时,オ会为k+l级队头的进程分配时间片・抢占式•在k级队列的进程运行过程中，若更上级的队列级）中逬入了一个新逬程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。•对各类型进程相对公平（FCFS的优点）；•每个新到达的进程都可以很快就得到响应（RR的优点）；

25•短进程只用较少的时间就可完成（SPF的优点）；•不必实现估计进程的运行时间（避免用户作假）；•可灵活地调整对各类逬程的偏好程度,比如CPU密集型进程、I/O密集型逬程（拓展:可以将因I/O而阻塞的进程重新放回原队列,这样!/O型进程就可以保持较高优先级）•会饥饿»综合!:檄”法理贝リE拉占?|6忌齡百金0至5供?ロナEJルキ季仑”地占应妥，、ピ•iiSJHチ分吋系约fc多负尋5切扌奂イゴア「的.不IX分优»先经4スく唱?■(AL枚iW应イT地,わエマ华!,坨ノ了ア弋白勺.注寂他攵礴问白勺IX:刈［式分优,先执.シa于美”寸糸绕E•自伝寻双行（例合券级反聞队ザリ较亚乐・注£W型迪融地占川干後j止步666一枚不说e行觥.イヾ史エビr白包0至文”LCft会•适合于交互式系统,比如:Unix・12进程同步、进程互斥•逬程同步•并发性带来了异步性,有时需要通过逬程同步解决这种异步问题。•有的逬程之间需要相互配合地完成工作,各进程的工作推进需要遵循ー一定的先后顺序.•逬程互斥•对临界资源的访问,需要互斥的进行.即同一时间段内只能允许ー个进程访问该资源•四个部分・进入区•检查是否可逬入临界区,若可逬入,需要"上锁"•临界区•访问临界资源的那段代码•退出区・负责"解锁"»剩余区•其余代码部分•需要遵循的原则•空闲让逬«临界区空闲时，应允许一个进程访问•忙则等待•日临界区正在被访问时,其他试图访问的逬程需要等待•有限等待

26•要在有限时间内逬入临界区,保证不会饥饿•让权等待・日进不了临界区的进程,要释放处理机,防止忙等・13进程互斥的软件实现方法•单标志法•算法思想・两个逬程在访问完临界区后会把使用临界区的权限转交给另ー个逬程。也就是说每个进程进入临界区的权限只能被另ー个进程赋予.•intturn=0;//turn表示当前允许进入临界区的进程号•同一时刻最多只允许一个进程访问临界区・双标志先检査•算法思想・设置ー个布尔型数组flagロ,数组中各个元素用来标记各逬程想逬入临界区的意愿,比如"flag⑼=ture"意味着〇号逬程P0现在想要进入临界区.每个进程在进入临界区之前先检查当前有没有别的逬程想逬入临界区,如果没有,则把自身对应的标志flag。设为true,之后开始访问临界区。・双标志后检查•算法思想・双标志先检查法的改版。前ー个算法的问题是先"检查"后"上锁"，但是这两个操作又无法一气呵成，因此导致了两个逬程同时进入临界区的问题。因此，人们又想到先"上锁"后"检查"的方法，来避免上述问题。•优劣•解决了“忙则等待"的问题，违背了“空闲让进"和"有限等待"原则，会产生饥饿。•Peterson算法•算法思想»结合双标志法、单标志法的思想。如果双方都争着想进入临界区,那可以让进程尝试"孔融让梨"（谦让）。做一个有礼貌的进程。•boolflag[2];//表示逬入临界区意愿的数组,初始值都是false•intturn=0;//turn表示优先让哪个逬程进入临界区

27•图解昔后的R0进程二チlag1。］=七r*j0二金uim=1;wHll_e(チlaq11］&&七uir*r*===);cr~±caVsec^±on：Tag(0］=チーIsg：r-emainder-sec^Xon;P1进模:T,Lag(11=tr-Me;七ur~r»=0;winiLeくオ"Lag［。］&&t:ur-r»«-0);ur~£七Xualsection;//我市自己E近入他r区//Eじ（•优先让5Mカ进入QSkCS曲限后谈「い—"Ct否Eg:i!上隼<・幸好可晒会_fag»：IW女犯ヨ佗,收ド內Uセ%伪”小mjraj我・安好可如I:ヌ寸即j女大ヤモ改.你伪”我的イヾハ」/3J如4.../，阻カ粗进・旦・后一次金日ヨ”让a，方ロ目己版mi源報盘お章二城整剧?ゼ86ノ,6冋宰■k区.0手自己日g不=S冋3K区ア/ノ言示进入歯界WRIKg典经•%D^tMWSTaXseuir-rtヨ示优先让W3个进程法入3K区•用软件方法解决了进程互斥问题,遵循了空闲让逬、忙则等待、有限等待三个原则,但是依然未遵循让权等待的原则.・14进程互斥的硬件实现方法•中断屏蔽方法•使用"开关中断"指令实现•优点•简单高效•缺点•只适用于单处理机»只适用于操作系统内核进程・TestAndSet（TS指令"SL指令）•过程:・old记录是否被上锁»再将|ock设为true・检查临界区是否已被上锁（若已上锁,则循环重复前几步）•优点•实现简单•适用于多处理机环境•缺点•不满足"让权等待"»Sw叩指令（XCHG指令）•同TSL・15信号量机制

28・用户进程可以通过使用操作系统提供的ー对原语来对信号量逬行操作,从而很方便的实现了进程互斥、逬程同步.•信号量其实就是ー个变量(可以是一个整数,也可以是更复杂的记录型变量),可以用一个信号量来表示系统中某种資源的数量,比如:系统中只有一台打印机,就可以设置ー个初值为1的信号量。•原语是ー种特殊的程序段,其执行只能一气呵成,不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由"逬入区的各种操作无法一气呵成”,因此如果能把进入区、退出区的操作都用"原语"实现,使这些操作能"ー气呵成"就能避免问题。•一对原语:wait⑸原语和signal⑸原语,可以把原语理解为我们自己写的函数,函数名分别为wait和signal,括号里的信号量S其实就是函数调用时传入的ー个参数。•wait,signal原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此,做题的时候常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)•整型信号量•用ー个整数型的变量作为信号量,用来表示系统中某种资源的数量。•整型信号量与普通整型变量的区别:对信号量只育埶行初始化、P、V三种操作•存在的问题•不满足"让权等待"原则,会发生"忙等"・记录型信号量(高频考点)・即用记录型数据结构表示的信号量。•S.value表示某种资源数,S.L指向等待该资源的队列•P操作中，一定是先S.value-,之后可能需要执行block原语•V操作中，一定是^S.value++,：^可能需要^I行wakeup原语•注意•要能够自己推断在什么条件下需要执行block或wakeup•功能・可以用记录型信号量实现系统资源的"申请"和"释放"・可以用记录型信号量实现进程互斥、进程同步

29イ:-♦>IW［ロwait(S)ヽsigr»al(S运m原4チハr>nj•ー夂・免糸ぞ在決»空fS.valuefTj初ノ仙マ表示:泰统”,把手口ズ寸(/.〉J【，;一S门勺n扌・ぐ(お您B味ヨ光サf”東•IF此力;•安坎彳亍S.valuie-S.valuev〇I!すを,バ垓非贺"京K］JIJblockJ型“;Uし彳)门」匕同I根<ヽ’6-リク注缶》•主后か方攵先处见忖L.彳生队ダiJS.L•ハ・«>r!AL.1名利し击リ用イ工会山£见“也常“理室・*”さワHS门9;大Vケ朶H>/ス进程0舟や次4后.メ・Hs“ca2状语0近SM"voidsignaV(semapl-ior-eS)«s•vaVmc-*-4-siT(S•vdVuev=0)《waKeup(S•l_>:・16用信号量机制实现进程互斥、同步、前驱关系・T信号量对应ー种资源»实现进程互斥•过程•分析并发逬程的关键活动,划定临界区(如:对临界资源打印机的访问就应该放在临界区)•设置互斥信号量mutex,初值为1(semaphoremutex=1;//初始化信号量,默认是记录型信号量)•在进入区P(mutex)申请资源•在退出区V(mutex)释放资源•注意:・对不同的临界资源需要设置不同的互斥信号量。・P、V操作必须成对出现。・实现进程同步・过程•L分析什么地方需要实现“同步关系”,即必须保证"ー前一后"执行的两个操作(或两句代码)•2.设置同步信号量S,初始为〇•3.在"前操作"之后执行V(S)•4.在"后操作"之前执行P(S)・前V后P•演示

30/fj1m-17生产者i肖费者问题•如何实现•生产者、消费者共享一个初始为空、大小为n的缓冲区。・只有缓冲区没满时,生产者オ能把产品放入缓冲区,否则必须等待。・只有缓冲区不空时,消费者オ能从中取出产品,否则必须等待。・缓冲区是临界资源,各进程必须互斥地访问。•实现图解>1.分折什么地方的要虻?ul“I同声关系“.艮ア必须俅证“一utr—•后”共行的两"2.设置旧セイ言。，バS,初贻汨〇3.卷“日仃提作"N后坎行V(S)4.在“用倖作"N削T坎行P(S)RI()<代码エ;代码N:VCS)】代码ヨ;若先执行キリV(S)捺イ乍・贝リS++后S=Xoir寸.由Fs=i..在本オ『可用宠羽,会皿P2斑和不会执行blockJ京诗f.而是维剑君先バオ亍至リP(S)擇作・由于S=O.S--先「丁ル口贡源.UMUtP恒作中会在行blockJiN后’看执彳テ完イぐ型5N.维イ江西彳ユV(S)分し!ヨ于•止匕日夕ギT迸程在俵依七Mltヌ寸应由勺用LN抉作中坎行wakeup映P2雉ホ次行イ七事4rZ*/2T号-匐极注碎刃^*/semapFioreS=0;//そ刀代ー保i正工イ戈ケ34"忌住仗プ5NN団执彳于•实现进程的前驱关系•过程•要为每ー对前驱关系各设置ー个同步信号量•在"前操作"之后对相应的同步信号量执行V操作•在“后操作”之前对相应的同步信号量执行P操作・实现逬程的前驱关系进磔P!ホ“AJイく皿si,P2大イUJイく石马S2.Pヨ中子了£uイぐ皿smP6大イオふJ拉女口下费r马阿洛日眄斤京白ウ同贞尸ア・・行・工に美る一・対3师关奉翔,足一・个进秒リMJ省冋3(兩公侔う正一ロセー后g枚作)因此・1.塞ナリQズ寸面(rge/ヨ戻K设:跄ー个值声E号t2.一“官钳埠作”之后ズ寸オ口=的E声イ百耳雪欧班行v廻胞作3.卷“月;挡fe作“Nmr*r+u心年”司主伯吩・班行p坟作

31

32れ产匸・5み《0共区セ仝»生产;有、油べ昌央・个ー初;女白汨ヤ、大小/eg-W”・只有ー》区:汉:酒时•生尸七オ例记!尸用.收入/ノP只“维打"X干十吋.酒依オオ白自A人中MX.H4，0占占.先爰アひW:星|耐罗ア気海.齐进をW必匆!豆ナ基地必I回・三eEaphoxreeut•ex_1：/メ自ニイ冃fBL,当?翔!*J"丝2At331Iホ□w—EapCoHOeeqヒy=c;ノノド可历イ百廿・fc.*东型阳Mナひ区wemaphoxrefullー〇券，/|ri]"frf"弓ー:fi3c.基5月W产匸占む白勺苦を•看0t豆宁是卷E——进转中迸行——x^r尸ー担奥作•思考:能否改变相邻P、V操作的顺序?•会发生死锁•实现互斥的P操作一定要在实现同步的P操作之后•V操作不会导致进程阻塞,因此,两个V操作顺序可以交换•易错点•实现互斥和实现同步的两个P操作的先后顺序（死锁问题）»两对同步关系实现“一前ー后”需要“前V后P”生产者生产P消费者消费empty//axw.//球/メ亲セ三手ス//血ナ，•18多生产者ー多消费者•加上互斥信号量。互斥的P操作一定要在实现同步的P操作之后,否则可能引起"死锁"daviQhヒe匸()<3hi<1)tP<———エー);Ps人人焉1:,卜耳又•六H平工V

33•2.整理思路。根据各逬程的操作流程确定P、V操作的大致®5序。・3.设置信号量。设置需要的信号量,并根据题目条件确定信号量初值.（互斥信号量初值ー般为1,同步信号量的初始值要看对应资源的初始值是多少）・解决"多生产者ー多消费者问题"的关键在于理清复杂的同步关系。•在分析同步问题（一前ー后问题）的时候不能从单个进程行为的角度来分析,要把“一前一后"发生的事看做是两种"事件”的前后关系。角・次.・先产二普一安シ栏•勿驾IT昆虫"ITJ公選在泞テ!X希XH，引省公系。て!三分析ト打上口リ展史＜-i）a・斤73j阳j。仔」日カイ啖イく日自从m个进不呈わ»口勺用皮・分キ斤.•生ナれ勺リ工呑做及阴i不中“，“竹”门勺ポr/iラ/糸。と匕なn•な口生:从寸个辽!FJ/jソリ"殳・;サ，O白勺i匹•ベガイダ以ドき吉i仑:5i尔:，认尸屮沙｛イ」ザ尔:•川j么をせスノLH乂疋ゆ%:打;ズ求丄，文心，あH仃自，リ方攵入本Ui女”家ふtfXUHff+阁ア.期:么一を共ノLアHズ也桐S尸B7父浓土戈，リ:亲イ日自イ手方夂入本%:凸么ず7，よ。手京足.彦”木・了共设置レq个トリ中イ直";畋分かリ实现ゼspq个“h«r一や”门勺x奉«ドイ谕れ勺うア杆テブアラ去八攵I纟:从・・ルナレ"（Tj"jパエ・:匕丄・.イ父,別いリ•以四I.Mauqメナ“迸科’彳ナンリF“曲:「空イ""イ牛"呪"JHlノし广弓I发:,セハ『”I夂ノL"ーメイ“リ拳イ’ヤ自勺M九ス关系”く洗r空ぐモ.“四—方攵入水呆-hri呪日Tf危及父亲ヨ丸彳テ.tliE・日自及f4亲以彳テ・上キ羊れ勺｛舌.京粒旬T以八J8ハ引ゆイ20读者ー写者问题・实现りシ七角ギ7aplat4

34•19吸烟者问题•代码分析足古处セ杼と貝・—・个セrJg五，ヨee依セ加何・3XZく0エ1》:>elmeXt—J_wei£<イ呼会tL一三:收取上,V<〇王正——3>；>X—

35//用ヨ尸注到〇ヌ寸・〜夂イ牛白勺豆斥6「旬//足—育nk几个3进不呈在ル.旬・イ牛・的互斥6冋?ム论:イじ江タ匕ユエム中,生"M,入g安个法れe以!」j讣jt卖迂イサーyx科】1、，也迸P/イ〈日生IFnt5。"A!（牛キ•'メ占ーイく公セ（.住.イL!セ幷イヾ\/，；,尤丸rりIリ.1価是+O・ナ公、1‘g九一•两种问题的区别与使用U夂行ー”ぜ«イ侬内皿“J角¥,夬歯41^たj「いワル贬I共了一个参与AO・明一K+幺・し，巴轨!〇!reuhuwemmpti〇=erout:E>X(><匕母妙匕五m手vアゴッユ;ガニイヾ曲目イ*:UEルミ行必中J根广Eくハ丁ハ」0寸-イチ匸ア「ア『こ产★只走u转厂,

36・22管程»为什么要引入管程・信号量机制存在的问题・编写程序困难、易出错•高级同步机制・封装的思想・管程是ー种特殊的软件模块•组成部分•1.局部于管程的共享数据结构说明;•2.对该数据结构进行操作的ー组过程;•3.对局部于管程的共享数据设置初始值的语句;•4.管程有一^名字.•基本特征•1.局部于管程的数据只能被局部于管程的过程所访问;•2.ー个逬程只有通过调用管程内的过程才能逬入管程访问共享数据;•3.每次仅允许一个逬程在管程内执行某个内部过程。•拓展1:用管程解决生产者消费者问题・各进程必须互斥访问管程的特性是由编译器实现的•实现方法宣伸«i殳:*7条件空星不“食李マ&/］喚あ法作.以角・决ト寸・I--J屋里拓展:L,用管・角翠決生尸者シ肖费苍冋四［ゝ.上y3(RM)✓Z•冲ユ中gLtSi有《エ七《(n±«em)

37・2.需要在管程中定义用于访问这些共享数据的“入口"——其实就是ー一些函数（如生产者消费者问题中,可以定义ー个函数用于将产品放入缓冲区,再定义ー个函数用于从缓冲区取出产品）・3.只有通过这些特定的“入口”才能访问共享数据・4.管程中有很多"入口”,但是每次只能开放其中一个“入口”,并且只能让一个逬程或线程进入（如生产者消费者问题中,各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个逬程在访问缓冲区.注意:这种互坛常性是由编译器负责实现的,程序员不用关心）.・5.可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个逬程或线程在条件变量上等待（此时,该进程应先释放管程的使用权,也就是让出"入口"）;可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。・ネ呈序员可以用某种特殊的语法来定义ー个管程monitor,之后其他程序员可以使用这个管程提供的入口，方便实现逬程同步/互斥・拓展2:Java中类似于管程的机制•Java中的synchronizedJava111•4U1MiJTJsynchronized扌笛14^-ナ那[司"H'J"HTJsTaT±ecVassmon±*tor-7・23死锁的概念•什么是死锁•在并发环境下,各进程因竞争资源而造成的一种互相等徳防羌里效麓源,导致各逬程都阻塞,都无法向前推曲强象,就是"死锁".・发生死锁后若无外力干涉，这些逬程都将无法向前推逬。•逬程死锁、饥饿、死循环的区别•死锁・各进程昂痔待对方手里的資源，导致各逬程都阻塞,无法向前推逬的现象。•饥饿•由于长期得不到想要的资源,某进程无法向前推进的现象。比如:在短进程优先（SPF）算法中,若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程"饥饿"。•死循环»某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的,有时是程序员故意设计的。•三者的区别!关回点区則

38宛至曳饮タヒ勁（i坏用二星迸程え2川页不リ!^jrttr捺进FE!现豕＜此卷设i上臼勺歹匕和百正不除タト）タビ番九一是小“加i«M£E千#メタカ・「白勺交羽”ヮあ攵年J.17此七〈いイ「宀，个ジ戈1%介以!门《ル见m山】」’7:7,ヒ;仇。わタト・发:生・殳。トエイ1•个汪率VNtT三びLヤ我・发:生廿1依介勺梓呪»XTf正:足:•雨段gi/O设路）•セハr育自足皿物谷《长,6ヌ;イ〈キ“处理+/L），・丁徒シ［イゴ个进不是至上歹ビ砧环。歹ビの向坏g进科n，r以」二处.佥）.ルミイく史よだラノ「象川Jトケ白勺期:ヰ羊川典和士.タビ曼H41外Lt・我№!谎沟g维。不导致FKJ.而小ビ加i五ズ星ホイぐ百得这杂,彷!1就近2至デり打ぎ奈ヨた）MlfF,迦・宛"看坏是刊殳管尸サ丹・ヤ」・死锁产生的必要条件•互斥条件•只有对必须互斥使用的资源的争抢オ会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个逬程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。•不剥夺芻牛・进程所获得的资源在未使用完之前,不能由其他逬程强行夺走,只能主动释放。•请求和保持条件・进程已经保持了至少一个資源,但又提出了新的资源请求,而该资源又被其他进程占有,此时请求进程被阻塞,但又对自己已有的资源保持不放。・循环等待条件•存在ー种进程资源的循环等待链,链中的每ー个进程已获得的资源同时被下ー个进程所请求。•发生死锁时一定有循环等待,但是发生循环等待时未必死锁•什么时候会发生死锁•对不可剥夺资源的不合理分配,可能导致死锁•1.对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁,对可剥夺的资源（CPU）的竞争是不会引起死锁的。.•2.逬程推油I质序非法。请求和释放资源的顺序不当,也同样会导致死锁。例如,并发执行的逬程PLP2分别申请并占有了资源RLR2I之后进程P!又紧接着申请资源R2,而进程P2又申请资源RL两者会因为申请的资源被对方占有而阻塞,从而发生死锁。•3.信号量的使用不当也会造成死锁。如生产者ー消费者问题中,如果实现互斥的P操作在实现同步的P操作之前,就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是ー”种抽象的系统资源）・死锁的处理逻辑•预防死锁•破坏死锁产生的四个必要条件•避免死锁•避免系统逬入不安全状态（银行家算法）・死锁的检测和解除•允许死锁发生,系统负责检测出死锁并解除•24死锁的处理策略ー预防死锁（静态策略）

39•破坏互斥条件•只有对必须互斥使用的资源的争抢オ会导致死锁。・SPOOLing技术把独占设备在逻辑上改造成共享设备・破坏不剥夺条件・不剥夺条件:»进程所获得的资源在未使用完之前,不能由其他逬程强行夺走,只能主动释放。•方案一•某些资源上位使用完,也要主动释放,从而破坏不可剥夺条件。•方案ニ»当某个逬程需要的资源被其他逬程所占有的时候,由操作系统协助,将想要的资源强行剥夺。•缺点•实现复杂•可能会造成前ー阶段工作的失效。只适用于易保存和恢复状态的资源,如CPU•增加系统开销,降低系统吞吐量•可能导致某个进程饥饿•破坏请求和保持条件•请求和例寺条件:・逬程已经保持了至少ー个资源,但又提出了新的资源请求,而该资源又被其他进程占有,此时请求进程被阻塞,但又对自己已有的资源保持不放。•采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有,该进程就不会再请求别的任何资源了。•缺点・资源利用率低。导致某些进程饥饿。•破坏循环等待条件•循环等待条件•存在ー种进程资源的循环等待链,链中的每ー一个逬程已获得的资源同时被下一个逬程所请求。•可采用顺序资源分配法.・首先给系统中的资源编号,规定每个进程必须按编号递増的顺序请求资源,同类资源（即编号相同的资源）一次申请完.•原理分析•一个进程只有已占有小编号的资源时,オ有资格申请更大编号的资源。按此规则,已持有大编号资源的进程不可能逆向地回来申请小编号的资源,从而就不会产生循环等待的现象.•缺点•不方便增加新设备

40•会导致资源浪费»用户变成麻烦•25死锁的处理策略——避免死锁（动态策略）•什么是安全序列•如果系统按照这种序列分配资源,则每个进程都能顺利完成.只要找出ー个安全序列,系统就是安全状态,安全序列可能有多个.•什么是系统的不安全状态,与死锁有何联系•如果分配了资源之后,系统中找不出任何ー个安全序列,系统就进入了不安全状态.可能会导致所有进程都无法顺利的执行下去，也有可能冲洗你回到安全状态.•如果处于安全状态，就一定不会发生死锁.如果进入不安全状态，可能会导致死锁.•如何避免系统进入不安全状态一银行家算法•数据结构•长度为m的ー一维数组Available表示还有多少可用资源•n*m矩阵Max表示各进程对资源的最大需求数•n*m矩阵Allocation表示已经给各进程分配了多少资源・Max-Allocation=Need矩阵表示各逬程最多还需要多少资源»用长度为m的ーイ盪组Request表示进程此次申请的各种资源数・银行家算法步骤•①检查此次申请是否超过了之前声明的最大需求数•②检查此时系统剩余的可用资源是否还能满足这次请求•③试探着分配,更改各数据结构•④用安全性算法检查此次分配是否会导致系统逬入不安全状态•安全性算法步骤・检查当前的剩余可用资源是否能满足某个进程的最大需求,如果可以,就把该进程加入安全序列,并把该进程持有的资源全部回收.・不断重复上述过程,看最终是否能让所有进程都加入安全序列.・系统处于不安全状态未必死锁,但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁.・26死锁的处理策略——检测和解除（允许死锁的发生）•死锁的检测・数据结构资源分配图•两种结点•进程结点・对应一例程•资源结点

41・对应ー类资源,ー类资源可能有多个•两种边•进程结点——>资源结点•表示进程想申请几个资源（每条边代表ー个）・资源结点——>逬程结点・表示已经为逬程分配了几个资源（每条边代表ー个）•是否可以消除所有边•检测死锁的算法•1）在资源分配图中,找出既不阻塞又不是孤点的逬程Pi（即找出一条有向边与它相连,且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量.如下图中,R1没有空闲资源,R2有一个空闲资源。若所有的连接该逬程的边均满足上述条件,则这个进程能继续运行直至完成,然后释放它所占有的所有资源）.消去它所有的请求边和分配边,使之称为孤立的结点.在下图中,P1是满足这一条件的进程结点,于是将P1的所有边消去.・2）进程Pi所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程.在下图中,P2就满足这样的条件.根据1）中的方法逬行一系列简化后,若能消去途中所有的边,则称该图是可完全简化的。•死锁定理•如果某时刻系统的资源分配图是不可完全简化的,那么此时系统死锁。・死锁的解除•一旦检测出死锁的发生,就应该立即解除死锁•并不是系统中所有的逬程都是死锁状态。用死锁检测算法化简资源分配图后,还连着边的那些逬程就是死锁逬程•解除死锁的主要方法有•1.資源剥夺法。挂起（暂时放到外存上）某些死锁进程,并抢占它的資源,将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。•2.撤销进程法（或称终止逬程法）。强制撤销部分、甚至全部死锁进程,并剥夺这些进程的资源。这种方式的优点是实现简单,但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间,已经接近结束了,一旦被终止可谓功亏一豊,以后还得从头再来。•3.逬程回退法。让ー个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息,设置还原点。•如何决定"对谁动手"・1.进程优先级・2.已执行多长时间・3.还要多久能完成・4.进程已经使用了多少资源

42・5.进程是交互式的还是批处理式的•第三章内存管理・01内存的基础知识•什么是内存,有何作用•内存可存放数据。•程序执行前需要先放到内存中才能被CPU处理——缓冲CPU与硬盘之间的速度矛盾•按字节编址•每个存储单元大小为1字节•按字编址•如果字长为16位,按字编址,每个存储单元大小为1个字;16个二进制位・进程运行的基本原理•指令的工作原理•操作码+参数・MOV,A,B・逻辑地址vs物理地址•相对地址•绝对地址•如何实现地址转换•装入的三种方式•绝对装入・编译时产生绝对地址«可重定位装入（静态重定位）•一次分配完所需要的内存空间•动态运行时装入（动态重定位）•动态重定位・重定位寄存器•从写程序到程序运行的过程»编译・由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言）•链接・由链接程序将编译后形成的ー一组目标模块,以及所需库函数链接在ー起,形成一一个完整的装入模块•装入（装载）

43•由装入程序将装入模块装入内存运行»链接的三种方式・静态链接•在程序运行之前,先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块）,之后不再拆开.・装入时动态链接•将各目标模块装入内存时,边装入边链接的链接方式。•运行时动态链接•在程序执行中需要该目标模块时,才对它进行链接.其优点是便于修改和更新,便于实现对目标模块的共享.•02内存管理的概念•内存空间的分配与回收•内存空间的扩充•地址转换・逻辑地址与物理地址的转换•三种装入方式・绝对装入（单道程序阶段,无操作系统）•编译时产生绝对地址»可重定位装入（早期多道批处理阶段）•装入时将逻辑地址转换为物理地址»动态运行时装入（现代操作系统）•运行时将逻辑地址转换为物理地址,需设置重定位寄存器•存储保护・保证各进程在自己的内存空间内运行,不会越界访问•两种方式•设置上下限寄存器•利用重定位寄存器、界地址寄存器逬行判断・03覆盖与交换（内存空间的扩充）•覆盖技术•解决程序大小超过物理内存总和•将ネ踞分段»固定区・调入后就不再调岀,直至运行结束

44•覆盖区•覆盖区中的程序段在运行过程中会根据需要调入调出•必须由程序员声明覆盖结构,操作系统完成自动覆盖。•缺点•对用户不透明,增加了用户编程负担・交换（对换）技术•内存空间紧张时,系统将内存中某些进程暂时换出外存,把外存中某些已具备运行条件的逬程换入内存（逬程在内存与磁盘间动态调度）•中级调度（内存调度）»决定将哪个处于挂起状态的进程重新调入内存•在外存的什么位置保存被换出的进程»具有对换功能的操作系统中,通常把磁盘空间分为文件区和对换区两部分.»文件区•主要用于存放文件,主要追求存储空间的利用率,因此对文件区空间的管理采用醫散分配方式。・ヌ摑区・对换区空间只占磁盘空间的小部分,被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度,因此对换区空间的管理主要追求换入换出速度,因此通常对换区采用连续分配方式（学过文件管理章节后即可理解）.总之,ヌ接区的I/O速度比文件区的更快。・什么时候交换・内存吃紧时进行,系统负荷降低就暂停•例如・在发现许多逬程运行时经常发生缺页,就说明内存紧张,此时可以换出ー些逬程:・如果缺页率明显下降,就可以暂停换出。・应该换出哪些逬程・优先换出阻塞进程»可换出优先级低的逬程・防止优先级低的进程在被调入内存后很快被换出,还需考虑进程在内存的驻留时间・PCB会常驻内存・虚拟存储技术・04连续分配管理方式・单ー连续分配•内存被分为系统区、用户区•内存中只能有一道用户程序,用户程序独占整个用户区

45•优点•实现简单»无外部碎片•可以采用覆盖技术扩充内存•不一定需要采取内存保护•缺点»只能用于单用户、单任务操作系统•有内部碎片（有些内部空间没有被利用到）•存储利用率极低•固定分区分配•分区大小相等•缺乏灵活性,适用于一台计算机控制多个相同对象的场合•分区大ノ」キ等»增加了灵活性,满足不同大小的进程需求,操作系统根据作业大小情况进行划分•无外部碎片,有内部碎片•动态分区分配•根据进程大小动态地建立分区•分区的大小和数目是可变的•采用什么数据结构记录内存的使用情况・空闲分区表»空闲分区链・动态分区分配算法»动态分区分配没有内部碎片,但是有外部碎片»内部碎片,分配给某逬程的内存区域中,有些部分没有用上•外部碎片,内存中的某些空闲分区由于太小而难以利用»外部碎片可用"紧凑"技术来解决•回收内存的四种情况•回收区之后有相邻的空闲分区•回收区之前有相邻的空闲分区•回收区前、后都有相邻的空闲分区•回收区前、后都没有相邻的空闲分区・05动态分区分配算法

46•首次适应算法(FF,FirstFit)•算法思想•每次都从低地址开始查找,找到第一一个能满足大小的空闲分区。•如何实现・空闲分区以地址递熠的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。・最佳适应算法(BF,BestFit)•算法思想»由于动态分区分配是ー种连续分配方式,为各进程分配的空间必须是连续的一整片区域。因此为了保证当"大逬程”到来时能有连续的大片空间,可以尽可能多地留下大片的空闲区即,优先使用更小的空闲区.•如何实现・空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区.•缺点•每次都选最小的分区逬行分配,会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。・最坏适应算法（WF,WorstFit）•又称最大适应算法（LargestFit）•算法思想・为了解决最佳适应算法的问题ーーー即留下太多难以利用的小碎片,可以在每次分配时优先使用最大的连续空闲区,这样分配后剩余的空闲区就不会大小,更方便使用。•如何实现•空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。・邻近适应算法（NF,NextFit）•算法思想・首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索,就能解决上述问题。•如何实现•空闲分区以地址递增的顺序^列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闱分区链（或空闲分区表）,找到大小能满足要求的第一个空闲分区。•优点

47・首次适应算;去每次都要从头查找,每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时,会更有可能用到低地址部分的小分区,也会更有可能把高地址部分的大分区保留下来（最佳适应算法的优点）・邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用,也就导致了高地址部分的大分区更可能被使用,划分为小分区,最后导致无大分区可用（最大适应算法的缺点）・首次适应算法效果最好*法分区排列廟マ优点^5:点目次瑛成从ユ至り运オ姥!&Cフ勺分区wi汨分区以地近诩，筲次疗扌蚱歹リ纥マ仔右枕徒バ女れ・法幷曲小、田】收分H后向殳不ヌア爱ス才幸1油分IX」火歹リ»丘羽テヂ作FT原住LS应比先蚀あ小的分区・以傢田里妾A分区空加分IK以咨域迪!增次FT弘、歹リ会《广出妾口勺人分lx「被1呆m下・.史能ラ黄足大迸栓泳;小金片,利用《回收づ!泪分［«楼小不适:ハン优先使用空大倉勺分［X：•以5”二产歩太可、的布ハrmgg/キ在ル1分区以冰盘迹造戈次，アナIFザリ•以新衣少ス便以利片」白勺小用け大分1于大五（，京1郊近比ノ衣負r次久!iハワ油空而j东,貞次从上次皆拄あ朿位宣开・0ペ拽仝1浴分［ゴ以地址途界9次カナ“歹リ（可扌需列/发砧王不,衣»イ”リ毎次都从イ氐竝如二M!小分区アF女台檢索.・法方的小く，辱［［天!「"JL「次逞i八攵算法）会使ス用完・06基本分页存储管理的基本概念•内存空间的分配与回收•连续分配管理版•连续分配:为用户逬程分配的必须是一个连续的内存空间。•非连续分配管理方式«非连续分配:为用户逬程分配的可以是一ー些分散的内存空间。»基本分页存储管理•什么是分页存储•内存空间氛围ー个个大小相等的分区,每个分区就是ー个“页框"（页框=页帧=内存块=物理块=物理页面）。每个页框有一个编号,即"页框号"（页框号=页帧号=内存块号=物理块号=物理页号）,页框号次。开始。•将进程的逻辑地址空间也氛围与页框大，J咽等的一个个部分,每个部分称为一个"页"或"页面"。每个页面也有一个编号,即"页号",页号也是ん〇开始•进程的页面与内存的页框有ーー对应的关系。•各个页面不必连续存放,可以放到不相邻的各个页框中。•易混淆«页、页面VS页框、页帧、物理页;«页号、页面号vs页框号、页帧号、物理页号•页表・页表通常存在PCB中

48•一个逬程对应ー张页表»进程的每个页面对应ー个页表项・每个页表项由"页号"和"块号"组成

49•页表记录逬程页面和实际存放的内存块之间的映射关系•具体关系图斑松的注*H地iit空仅J•已知内存大小,页面大小,计算每个页表项需要多大•内存大小僚面大小，换算为比特位,再转换为字节•计算方法・设裁糸绕物为内行人刁、A4GB,リエ|斬人司、当4KB•贝リ，个リ工委皿不少"Z俵为安少字お?4GBg内イ宗4迁公豊セ分为アリN。=4。个内イテ尔内イ，べ歩g港口レを母是〇-22O-X内イ，块弓至少憂用NObit:・沿不テ.至少亜ハJ3B*セボハマ<3*S=2-at>it>——L一中丁ー双セ基I・金g，gU匕れ至个五c人」页ノt：bb・__イ，厚整个束差至少的整•如何实现地址转换•1.计算出逻辑地址对应的【页号，业内偏移量】・2.找到对应页面在内存中的存放位置（查页表）・3.物理地址=页面始址+页内偏移量特点:虽然进程的各个页面是离散存放的,但是页面内部是连续存放白如果要访问逻辑地址A,则ー①确定逻掷地址A对应的“页号”PQ②找到p写页面在内存中的起始地址〈霜要査页衣）。③确定逻辑地址A的“页内偏移気”WQ逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移饉・逻辑地质结构——可拆分为【页号P（页内偏移量W】»页号=逻辑地址/页面大小;・页内偏移量=逻辑地址%页面大小・如果页面大小刚好是2的整数次幕呢•结论:如果每个页面大小为2人KB,用二逬制数表示逻辑地址,则末尾K位即为页内偏移量,

50其余部分就是页号•基本地址变换机构【见P7]•基本分段存储管理•段页式存储管理•内存空间的扩充•地址转换•存储保护・07基本地址变换机构・页表寄存器的作用•存放页表起始地址•存放页表长度・，地址变换过程•1.根据逻辑地址算出页号、页内偏移量•2.页号的合法性检查（与页表长度对比）•3.若页号合法,再根据页表起始地址、页号找到对应页表项•4.根据页表项中记录的内存块号、页内偏移量得到最终的物理地址•5.访问物理内存对应的内存单元・其他小细节・页内偏移量位数与页面大小之间的关系（要能用其中一个条件推出另一个条件）・页式管理中地址是ー维的・实际应用中,通常使ー个页框恰好能放入整数个页表项・为了方便找到页表项,页表一般是放在连续的内存块中的・08具有快表的地址变换机构・什么是快表（TLB）•快表,又称联想寄存器（TLB,translationlookasidebuffer）,是ー种访问速度比内存快很多的高速缓存（TLB不是内存!）,用来存放最近访问的页表项的副本,可以加速地址变换的速度。与此对应,内存中的页表常称为慢表。•引入快表后,地±±的变换过程•①CPU给出逻辑地址,由某个硬件算得页号、页内偏移量,将页号与快表中的所有页号逬行比较。•②如果找到匹配的页号,说明要访问的页表项在快表中有副本,则直接从中取出该页对应的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后,访问该物理地址对应的内存单元。因此,若快表命中,则访问某个逻辑地址仅需一次访存即可。•③如果没有找到匹配的页号,则需要访问内存中的页表,找到对应页表项,得到页面存放

51的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后,访问该物理地址对应的内存单元。因此,若快表未命中,则访问某个逻辑地址需要两次访存（注意:在找到页表项后,应同时将其存入快表,以便后面可能的再次访问。但若快表已满,则必须按照一一定的算法对旧的页表项逬行替换）•局部性原理•时间局部性•如果执行了程序中的某条指令,那么不久后这条指令很有可能再次执行;如果某个数据被访问过,不久之后该数据很可能再次被访问.（因为程序中存在大量的循环）•空间局部性•一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的）•对比图地址空抉ist程*本地:hk金狭相L构CDJfX上5ヽ包检査贝弓告法性售＞衣见衣.拄至リ页由彳字方攵g内存块号（3）根4W内存块号つ页内住秤吊:用至リ物理t地力上65冋目标内衣3元貝c快次倉勺—r交七、交内伏ヨ移出他ナと亚按矶キ检百正亏合法性田在火央.拄至U页【由行收的内疗块サ,并上しギft衣项員やリ至り快セホ内存块号ら双内住铐出9至リ物冲地址怎）5冋目标内行m无•09两级页表・单级页表存在什么问题?如何解决?•所有页表项必须连续存放,页表过大时需要很大的连续空间•在一段时间内并非所有页面都用得到,因此没必要让整个页表常驻内存•两级页表•将长长的页表再分页•逻辑地址结构:【一级页号,二级页号,页内偏移量】•注意几个术语:页目录表/外层页表/]5级页表•如何实现地址变换?•班照地址结构将逻辑地址拆分成三部分•②从PCB中读出页目录表始址,根据ー级页号査页目录表,找到下ー级页表在内存中的存放位置•③根据二级页号查表,找到最终想访问的内存块号•④结合页内偏移量得到物理地址・两级页表问题需要注意的几个细节•多级页表中,各级页表的大小不能超过ー个页面。若两级页表不够,可以分更多级

52•多级页表的访存次数（假设没有快表机构）——N级页表访问一个逻辑地址需要N+1次访存•10基本分段存储§理^式・什么是分段（类似于分页管理中的“分页”）・将地址空间按照程序自身的逻辑关系划分为若干个段,每段从〇开始编址・每个段在内存中占据连续空间,但各段之间可以不相邻・逻辑地址结构:【段号,段内地址】•什么是段表（类似于分页管理中的“页表”）•记录逻辑段到实际存储地址的映射关系•每个段对应ー个段表项.各段表项长度相同,由段号（隐含）段长、基址组成•如何实现地址变换•1.由逻辑地址得到段号、段内地址•2.段号与段表寄存器中的段长度比较,检查是否越界•3.由段表始址、段号找到对应段表项•4.根据段表中记录的段长,检查段内地址是否越界•5.由段表中的"基址+段内地址"得到最终的物理地址•6.访问目标单元•分段、分页管理的对比•分页对用户不可见,分段对用户可见•分页的地址空间是ー维的,分段的地址空间是二维的•分段更容易实现信息的共享和保护（纯代码可重入代码可以共享）•分页（单级页表）、分段访问ー个逻辑地址都需要两次访存,分段存储中也可以引入快表机构・11段页式管理方式・分页、分段管理方式中最大的优缺点・将地址空间按照程序自身的逻辑关系划分为若干个段,在将各段分为大小相等的页面・将内存空间分为与页面大小相等的ー个个内存块,系统以块为单位为进程分配内存・逻辑地址结构:【段号,页号,页内偏移量】•分段+分页的结合——段页式管理方式•每个段对应ー个段表项.各段表项长度相同,由段号（隐含）、页表长度、页表存放地址组成•每个页对应一个页表项.各页表项长度相同,由页号（隐含）、页面存放的内存块号组成•段表、页表•1.由逻辑地址得到段号、页号、页内偏移量•2.段号与段表寄存器中的段长度ヒ匕较,检查是否越界

53•3.由段表始址、段号找到对应段表项•4.根据段表中记录的页表长度,检查页号是否越界•5.由段表中的页表地址、页号得到查询页表,找到相应页表项•6.由页面存放的内存块号、页内偏移量得到最终的物理地址•7.访问目标单元•如何实现地址变换•第一次——查段表、第二次——查页表、第三次——访问目标单元•可引入快表机构,以段号和页号为关键字査询快表,即可直接找到•最终的目标页面存放位置。引入快表后仅需一次访存•12虚拟内存的基本概念・传统存储管理方式的特征、缺点•一次性»作业必须一次性全部装入内存后才能开始运行。这会造成两个问题:・①作业很大时,不能全部装入内存,导致大作业无法运行;・②当大量作业要求运行时,由于内存无法容纳所有作业,因此只有少量作业能运行,导致多道程序并发度下降。・驻留性・一旦作业被装入内存,就会一直驻留在内存中,直至作业运行结束。事实上,在ー个时间段内,只需要访问作业的一小部分数据即可正常运行,这就导致了内存中会驻留大量的、暂时用不到的数据,浪费了宝贵的内存资源。•局部性原理•时间局部性»现在访问的指令、数据在不久后很可能会被再次访问・空间局部性•现在访问的内存单元周围的内存空间,很可能在不久后会被访问•高速缓曲术»使用频繁的数据放到更高速的存储器中・虚拟内存的定义和特征•定义・程序不需全部装入即可运行,运行时根据需要动态调入数据,若内存不够,还需换出ー些数据。・多次性:无需在作业运行时一次性全部装入内存,而是允许被分成多次调入内存.・对换性:在作业运行时无需一直常驻内存,而是允许在作业运行过程中,将作业换入、换出。・虚拟性:从逻辑上扩充了内存的容量,使用户看到的内存容量,远大于实际的容量。•如何实现虚拟内存技术

54•借助离散分配的内存管理方式（基本分页存储管理、基本分段、基本段页式）•访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存（请求调页功能）•内存空间不够时,将内存中暂时用不到的信息换出到外存（页面置换功能）•虚拟内存的实现»请求分页存储管理•请求调页•页面置换•请求分段存储管理•请求调段•段置换•请求段页式存储管理・13请求分页管理方式•页表机制•在基本分页的基础上增加了几个表项•状态位:表示页面是否已在内存中•访问字段:记录最近被访问过几次,或记录上次访问的时间,供置换算法选择换出页面时参考•修改位:表示页面调入内存后是否被修改过,只有修改过的页面オ需在置换时写回外存•外存地址:页面在外存中存放的位置•缺页中断机构•找到页表项后检查页面是否已在内存,若没在内存,产生缺页中断•缺页中断处理中,需要将目标页面调入内存,有必要时还要换岀页面•缺页中断属于内中断,属于内中断中的“故障”,即可能被系统修复的异常•一条指令在执行过程中可能产生多次缺页中断・地址变换机构•找到页表项是需要检查页面是否在内存中•若页面不再内存中，需要请求调页•若内存空间不够,还需换出页面•页面调入内存后，需要修改相应页表项•14页面置换算法•最佳置换算法(OPT)•最佳置换算法(〇PT,Optimal):每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面,这样可以保证最低的缺页率。・最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下

55来会访问到的是哪个页面.操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。・先进先出置换算法(FIFO)•先逬先出置换算法(FIFO):每次选择淘汰的页面是最早逬入内存的页面•实现方法:把调入内存的页面根据调入的先后®5序排成个队列，需要换出页面时选择队头页面即可.队列的最大长度取决于系统为进程分配了多少个内存块。•Belady异常——当为逬程分配的物理块数增大时,缺页次数不减反增的异常现象。•只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应,因为先逬入的页面也有可能最经常被访问。因此，算法性能差•最近最久未使用置换算法(LRU)•最近最久未使用置换算法(LRU,leastrecentlyused):每次淘汰的页面是最近最久未使用的页面•实现方法:赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t.•当需要淘汰：ー个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。•时钟置换算法(CLOCK)•时钟置换算法是ー种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU,NotRecentlyUsed)

56・简单的CLOCK算法实现方法:为每个页面设置ー个访问位,再将内存中的页面都通过链接指针链接成一个循环队列。»当某页被访问时,其访问位置为1.•当需要淘汰一个页面时,只需检查页的访问位。•如果是〇,就选择该页换出;•如果是1,则将它置为〇,暂不换出,继续检査下ー个页面,若第一轮扫描中所有页面都是1,则将这些页面的访问位依次置为〇后,再进行第二轮扫描（第二轮扫描中一定会有访问位为〇的页面,因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）・改逬型的时钟置换算法・简单的时钟置换算法仅考虑到ー个页面最近是否被访问过。事实上,如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时,オ需要写回外存。・因此,除了考虑一个页面最近有没有被访问过之外,操作系统还应考虑页面有没有被修改过.在其他条件都相同时,应优先淘汰没有修改过的页面,避免I/O操作。这就是改逬型的时钟置换算法的思想。修改位=o,表示页面没有被修改过;修改位=i,表示页面被修改过。・为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1,1）表示ー个页面近期被访问过,且被修改过。•算法规则玲スム夫见贝リエギt月斤イギ可能初z宜』典的页面す作“戈,ー个储坏队ダリSTS-年仑「从当0"イ夂堵IJFg付“苗弃」第一个（o,o）按.ホキ仑ナI指iイく«塞区イ壬1可・标志・（立、洸二，仑エお:浜ー，仑ナ1扌曲穴:收・贝リ車羽iチr15页面分配策略vi・査・1•だ筑ー个<〇,1>irjwiHjj-倂按。不年仑的・所イすむ“itt过的哂访R”へ£为0期一:キ仑ニオ:二密二・仑士“苗为攻,贝リ.壬:防，“花•代扌戈弟一个（〇,〇>门勺中贞用于替换-今キ仑齐!描イ<1F住改任何标・上:位泊レU轮二若率三寺企为描央畋.贝リ，丘羽i・为箍.表找帝一个<〇,1>rKj«Wl，lJT二玲按..を会イ3一一个做彼垃，い.因ut,Aj2tn'2ui_〇ukpt與克;厶法拝一・个泡汰页nn&・彩由丁ー第一ー半仕已将所イ『通•方MJNZHt为。.［大］止ヒ纟る过第三车仑、第uu车仑オヨ扌苗-•几种置换算法的比较「——ス法小則イOPTへ优先淘汰，枝K!吋SJ内不会被ジ门“白勺ザエ［fij缺あ:率右支n«だ法实FIFO优先/d冰，!丈先进入内存ポノりX而实现俺a可能H1斑LRU优先淘汰，^近般久没让/”J的页面中に曰自彳艮女子史米亨•学賓CLOCK砧臼（表1界S幷员ifii第一キ仑淘汰防「ハJ位し=。臼勺.,や竹制用过的双ifiiめイ文改R:！.时第——キ仑没法・レ・贝リ进行第二％:M描e实エ见前中fH未セバ改过。改进尊Mclockく己攵进型ZRU）若戸!（Si句イ立,屮务改位:ン门勺形式衣坯.W«J第一轮:準汰（6。ッ第二轮:泡冰（〇,1>.并附拒1报过的双向S同位W置RO豕三キ仑:渝决<〇,〇〉第uqキ仑:淘汰<〇,1>算迂开钠ィ“”

57・驻留集・驻留集・指请求分页存储管理中给逬程分配的物理块的集合。・在采用了虚拟存储技术的系统中,驻留集大小一般小于进程的总大小.・若驻留集太小,会导致缺页频繁,系统要花大量的时间来处理缺页,实际用于进程推进的时间很少;・驻留集太大,又会导致多道程序并发度下降,资源利用率降低.所以应该选择ー个合适的驻留集大小.・固定分配:操作系统为每个逬程分配ーー组固定数目的物理块,在进程运行期间不再改变。即,驻留集大小不变・可变分配:先为每个进程分配一定数目的物理块,在进程运行期间,可根据情况做适当的增加或减少・即,驻留集大小可变・局部置换:发生缺页时只能选进程自己的物理块逬行置换。・全局置换：可以将操作系统保留的空闲物理块分配给缺页进程,也可以将别的进程持有的物理块置换到外存,再分配给缺页逬程。•页面分配、粉策略•固定分配局部置换•固定分配局部置换:系统为每个进程分配一一定数量的物理英,“在整个运行期向都不改变。若逬程在运外行中发生缺页,则只能从该进程在内存中的页面中选岀ーー页换岀,然后再调入需要的页面。这种策略的缺点是:很难在刚开始就确定应为每个进程分配多少个物理块オ算合理。（采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给岀的参数来确定为ー个逬程分配的内存块数）•可变分配全局置换・刚开始会为每个进程分配一定数量的物理块。操作系统会保持ー一个空闲物理块队列。当某进程发生缺页时,从空闲物理块中取出ー块分配给该进程;若已无空闲物理块,则可选择一个未锁定的页面换出外存,再将该物理块分配给缺页的进程。采用这种策略时,只要某逬程发生缺页,.都将获得新的物理块,仅当空闲物理块用完时,系统オ选择ー个未锁定的页面调出。被选择调出的页可能是系统中任何一个逬程中的页,因此这个被选中的逬程拥有的物理块会减少,缺页率会增加。•可变分配局部置换・刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时,只允许从该进程自己的物理块中选出一个进行换出外存。如果逬程在运行中频繁地缺页,系统会为该逬程多分配几个物理块,直至该进程缺页率趋势适当程度;反之,如果逬程在运行中缺页率特别低,则可适当减少分配给该逬程的物理块。»可变分配全局置换:只要缺页就给分配新物理块»可变分配局部置换:要根据发生缺页的频率来动态地增加或减少进程的物理块•调入页面的时机・预调页策略:一般用于进程运行前•请求调页策略:进程运行时,发现缺页再调页

58•从何处调页・对换区一采用连续存储方式,速度更快;文件区一采用离散存储方式,速度更慢.・对换区足够大:运行将数据从文件区复制到对换区,之后所有的页面调入、调出都是在内存与对换区之间逬行・ヌ撤区不够大:不会修改的数据每次都从文件区调入;会修改的数据调出到对换区,需要时再从ヌ懒区调入•抖动（颠簸）现象•页面频繁换入换出的现象。主要原因是分配给逬程的物理块不够•工作集•在某段时间间隔里,逬程实际访问页面的集合。驻留集大小一般不能小于工作集大小。・第四章文件管理•0I初识文件管理•文件定义:ー组有意义的信息的集合•文件的属性•文件名:由创建文件的用户决定文件名,主要是为了方便用户找到文件,同一目录下不允许有重名文件。•标识符:一个系统内的各文件标识符唯一一,对用户来说毫无可读性因此标识符只是操作系统用于区分各个文件的ー种内部名称.•类型:指明文件的类型.•位置:文件存放的路径（让用户使用）、在外存中的地址（操作系统使用,对用户不可见）•大小:指明文件大小•创建时间、上次修改时间、文件所有者信息•保护信息:对文件逬行保护的访问控制信息•操作系统向上提供哪些功能«创建文件（create系统调用）•删除文件（delete系统调用）•读文件（read系统调用）•写文件（write系统调用）•打开文件（open系统调用）•关闭文件（close系统调用）•文件内部应该如何被组织起来（文件的逻辑结构）•文件之间应该如何被组织起来（目录结构）•文件应如何存放在外存中（文件的物理结构）•操作系统如何管理外存中的空闲块（存储空间的管理）

59•操作系统需要提供的其他文件管理功能•文件共享•文件保护・02文件的逻辑结构・无结构文件»有结构文件•顺序文件・串结构:记录顺序与关键字无关・JI质序结构:记录按关键字1顺序排列・可变长记录的顺序文件无法实现随机存取,定长记录可以・定长记录、顺序结构的顺序文件可以快速检索（根据关键字快速找到记录）・最大缺点:不方便增加/删除记录•索引文件»建立一张索引表,每个记录对应-个表项。各记录不用保持顺序,方便增加删除记录»索引表本身就是定长记录的顺序文件,一个索引表项就是一条定长记录,因此索引文件可支持随机存取»若索引表按关键字顺序排列,则可支持快速检索・解决了顺序文件不方便增/删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间•索引顺序文件»将记录分组，每组对应ー一索引表项・检索记录时光II®序查索引表，找到分组,再顺序查找分组•当记录过多时,可建立多级索引表•03文件目录•文件控制块（实现文件目录的关键数据结构）・ー个文件对应ー个FCB,个FCB就是一个目录项,多个FCB组成文件目录•对目录的操作才叟索、创建文件、删除文件、显示文件、修改文件•目录结构・单级目录结构・一个系统只有一张目录表,不允许文件重名・两级目录结构•不同用户的文件可以重名,但不能对文件进行分类•多级目录结构（树形目录结构）

60•不同目录下的文件可以重名,可以对文件进行分类,不方便文件共享»系统根据“文件路径”找到目标文件»从根目录出发的路径是“绝对路径"（ソ照片/2015-08/自拍jipg”）»从“当前目录”出发的路径是“相对路径"（ソ照片/2015-08/自拍jpg"）•无环图目录结构»在树形目录结构的基础上,增加一些指向同一节点的有向边,使整个目录成为ー个有向无环图»为共享结点设置一个共享计数器,计数器为〇时オ真正删除该结点・索引结点（对文件控制块的优化）・除了文件名之外的所有信息都放到索引结点中,每个文件对应一个索引结点・目录项中只包含文件名、索引结点指针,因此每个目录项的长度大幅减小・由于目录项长度减小,因此每个磁盘块可以存放更多个目录项,因此检索文件时磁盘I/O的次数就少了很多・04文件的物理结构（文件分配方式）・对非空闲磁盘块的管理（存放了文件数据的磁盘块）•连续分配•链接分配»链接分配采取离散分配的方式,可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。•隐式链接•隐式链接ー除文件的最后ー个盘块之外,每个盘块中都存有指向下一个盘块的指针.文件目录包括文件第一块的指针和最后ー块的指针。•优点:彳昉便文件拓展，不会有碎片问题,外存利用率高。•缺点:只支持）I质序访问,不支持随机访问,査找效率低,指向下一个盘块的指针也需要耗费少量的存储空间.•题目中没有要求,默认是隐式链接的链接分配•显式链接•把用于链接文件各物理块的指针显式地存放在ー张表中,即文件分配表（FAT,FileAllocationTable）,一个磁盘只会建立一张文件分配表.开机时文件分配表放入内存,并常驻内存。•优点:很方便文件拓展,不会有碎片问题,外存利用率高,并且支持随机访问。相比于隐式链接来说,地址转换时不需要访问磁盘,因此文件的访问效率更高。«缺点:文件分配表的需要占用一定的存储空间.•索引分配・①链接方案:如果索引表太大,ー个索引块装不下,那么可以将多个索引块链接起来存放.缺点:若文件很大,索引表很长,就需要将很多个索引块链接起来.想要找到i号索引块,必须先依次读入〇

61〜i-1号索引块,这就导致磁盘I/O次数过多,查找效率低下.•②多层索引:建立多层索弓1（原理类似于多级页表）.使第一层索引块指向第二层的索引块.还可根据文件大小的要求再建立第三层、第四层索引块.采用K层索引结构,且顶级索引表未调入内存,则访问ー个数据块只需要K+1次读磁盘操作.•缺点:即使是小文件,访问ー个数据块依然需要K+1次读磁盘。•③混合索引:多种索引分配方式的结合.例如,一个文件的顶级索引表中,既包含直接地址索引（直接指向数据块）,又包含ー级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）.・优点：对于小文件来说,访问ー个数据块所需的读磁盘次数更少.•超级超级超级重要考点:•①要会根据多层索引、混合索引的结构计算出文件的最大长度（Key:各级索引表最大不能超过ー个块）；•②要能自己分析访问某个数据块所需要的读磁盘次数（Key:FCB中会存有.指向顶级索引块的指针,因此可以根据FCB读入顶级索引块.每次读入下一级的索引块都需要一次读磁盘操作.另外,要注意题目条件ー顶级索引块是否已调入内存）•各种文件分配方式的区别

621Llow2I目マ期内行16艘ノ的“デ分!"uaソ0文:イ十分Eg必匆小卷":白勺码旧:欣，口:幻彳状リ、迂竹k也J顿中"貝乂!5拄E19主すC産TIBL5れ按3ペ除・イ牛IK！ム更无マー个盆块N建匸如央弓-纣;束坎E南挙次KJすレ可足分B包i接タト,れ壬个・い夬“，普1i仔#ザ珀Pタトイ，不リハハキ・Z,.l«Jド廿曲:上欠れ勺升ir零トイ千跖3・・兄力・什品甚ア弋在立——弓に辽水キ二分西已衣《fat）,gg块サ畛:r*目行・代宣•对空闲磁盘块的管理•06逻辑结构vs物理结构•逻辑结构•用户（文件创建者）的视角看到的亚子•在用户看来,整个文件占用连续的逻辑地址空间•文件内部的信息组织完全由用户自己决定,操作系统并不关心•物理结构・由操作系统决定文件采用什么物理结构存储•操作系统负责将逻辑地址转变为（逻辑块号,块内偏移量）的形式,并负责实现逻辑块号到物理块号的映射•07文件存储空间管理