复习指导课件

操作系统复习指导操作系统基本概念操作系统是控制和管理计算机系统的硬件和软件资源，合理地组织计算机工作流程及方便用户使用的程序和数据的集合。操作系统的功能和主要特征主要功能:处理机管理存储管理设备管理文件管理用户接口主要特征并发性共享性虚拟性不确定性（随机性）单用户操作系统批处理操作系统分时操作系统实时操作系统网络操作系统分布式操作系统多处理操作系统操作系统的分类五大类型(批处理、实时、分时、网络、分布)用户与操作系统的接口用户与操作系统的三级接口作业（命令）控制级接口程序级接口图形级接口四个概念:系统态、用户态、特权指令、访管制令作业的概念、组成以及作业控制块的内容作业：由不同的顺序相连的作业步组成。作业步：在一个作业的处理过程中，计算机所做的相对独立的工作。作业流：一次有一批作业进入系统，并在操作系统控制下，一个接一个地顺序进行处理。作业的类别批处理作业交互式作业(终端作业)作业由程序、数据和作业说明书三部分组成。系统调用的实现过程实际上系统调用语句本身是硬件提供的（机器指令），但其所调用的功能是操作系统提供的。每种机器的机器指令集中都有一条系统调用指令。陷入指令系统子程序sub0A0sub1A1subnAnsubiAi......陷入处理机构1)保护处理机现场2)取系统调用功能号并寻找子程序入口3)恢复处理机现场并返回入口地址表A0A2Ai......An....系统调用....用户程序作业调度作业调度性能衡量指标(1)作业平均周转时间T(Ti为每个作业的周转时间；tc作业完成时刻；ts作业进入系统时刻)(2)平均带权周转时间W（Ti为每个作业的周转时间；tr为作业实际运行时间）高响应比优先（HRF:HighestResponseRatioNext）：响应比最高的作业优先启动。响应比=周转时间/估计运行时间

=（等待时间+估计运行时间）/估计运行时间

=1+等待时间/估计运行时间高优先级优先（HPF：HighestPriorityFirst）：由用户指定作业优先级，优先级高的作业启动。假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间，应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间。最短作业优先算法结果最高响应比优先算法结果顺序程序特征：程序执行的顺序性程序执行的封闭性程序执行结果的确定性（可再现性）

多道程序设计的特征并发性独立性动态随机性相互制约性进程定义：Process

进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程，是系统进行资源分配和调度的独立单位进程进程的组成要素：用户程序用户数据进程控制块PCB进程的特征动态性独立性并发性、异步性

结构化进程与程序的区别进程是动态的，程序是静态的;进程是暂时的，程序的永久的;进程与程序的组成不同;进程可以创建其它进程，而程序不能；进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。进程状态转换图

中断、内核、原语基本概念中级调度新建态挂起就绪态挂起等待态高级调度低级调度运行态就绪态等待态终止态处理机调度的层次

引进进程调度的时机当一个进程运行完毕，或由于某种错误而终止运行当一个进程在运行中处于阻塞状态（等待I/O）当有一个优先级更高的进程就绪（可抢占式）例如：新创建一个进程，一个等待进程变成就绪在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）分时系统中时间片到线程的特点：是进程的一个实体，可作为系统独立调度和分派的基本单位。不拥有系统资源（只拥有从属进程的全部资源，资源是分配给进程）一个进程中的多个线程可并发执行。（进程可创建线程执行同一程序的不同部分）线程（Thread）定义：是进程的一个实体，是CPU调度的基本单位。线程自己基本上不拥有系统资源，只留有几个寄存器，但它可以与同属同一个进程的其他线程共享进程所拥有的全部资源。进程互斥：指在多道程序环境下，每次只允许一个进程对临界资源进行访问。进程同步：指多个相关进程在执行次序上的协调。临界资源:一次仅供一个进程使用的资源。在进程中涉及到临界资源的程序段叫临界区。多个进程的临界区称为相关临界区。进程互斥与同步机制V(S)：①S∶=S+1;②若S>0，则调用V(S)的进程继续运行；③若S≤0，从等待信号量S的阻塞队列中唤醒头一个进程，然后调用V(S)的进程继续运行。V操作的原语V(sem)semsem+1sem≤0?唤醒等待队列中的一个进程继续自己的程序执行NY利用P.V操作实现进程的同步与互斥司机与售票员问题生产者与消费者问题管程：把分散的各同类临界区集中起来。并为每个可共享资源设立一个专门的机构来统一管理各进程对该资源的访问。消息缓冲通讯技术的基本思想是：根据“生产者-消费者”原理，利用内存中公用消息缓冲区实现进程的信息交换。死锁概念：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称这一组进程或系统此时发生了死锁。四个必要条件：互斥控制（资源独占）非剥夺控制（不可剥夺）逐次请求（部分分配，占有申请）环路条件（循环等待）原因： 系统资源不足； 进程推进顺序不合适；对死锁的采取的对策

(1)鸵鸟策略。(2)预防策略。(3)避免策略。(4)检测和解除。预防死锁破坏死锁四个必要条件中的一个或多个，来防止死锁。解决方法：静态资源分配

资源有序分配法

系统中对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配。避免死锁最具有代表性算法：银行家算法。

例如，设系统中有10台磁带机，由三个进程A、B、C共享。假定A、B、C已分别占用了2台、3台、3台，它们的最大需求量分别为4台、6台、8台。（假定只有当满足了最大需求量后才能释放所占用的全部资源。）单项资源的银行家算法进程名已分配数尚需申请数最大需求数剩余资源ABC2332354682Availabler1r2r3230maxr1r2r3P1753P2322P3902P4222P5433allocationr1r2r3P1010P2302P3302P4211P5002needr1r2r3P1743P2020P3600P4011P5431P2:532P4:743P1:753P3:1055P5:1057P2P4P1P3P5多项资源的银行家算法地址变换(地址再定位,地址映射)直接指定方式:程序员在编序时或编译程序对源程序进行编译时，所用的是实际存储地址。名空间——程序逻辑空间——逻辑地址（相对地址，虚地址）存储空间——物理地址（绝对地址，实地址）逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。分区存储管理原理：把内存分为一些大小相等或不等的分区，每个应用进程占用一个或几个分区。每个进程占据一个分区。特点：适用于多道程序系统和分时系统支持多个程序并发执行难以进行内存分区的共享问题：可能存在内碎片和外碎片。内碎片：占用分区之内未被利用的空间外碎片：占用分区之间难以利用的空闲分区。固定分区

预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，但分区大小固定不变，每个分区装一个且只能装一个作业。相关技术：覆盖交换可变分区按空闲块链接方式不同，有四种分配算法：首次适应法下次适应法（循环首次适应法）最佳适应法最坏适应法可再定位式分区和多重分区概念和原理分页存储管理页：把用户程序按逻辑页划分成大小相等的部分。用户程序分页的划分是由系统自动完成的，对用户是透明的。一页的大小为2的整数次幂。内存块：按页的大小划分为大小相等的区域，称为内存块（又叫物理页面，页框）。内存分配：以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻，通过页表把作业的各个页面与内存块对应起来。页面变换表列出了作业的逻辑地址与主存中的物理地址间的对应关系。页面大小:页面的大小应适中，且页面大小应是2的幂一个页表中包含若干个表目，自然序号对应于用户程序中的页号，块号是该页对应的物理块号。页面变换表的每一个表目除了包含指向页框的指针外，还包括一个存取控制字段。请求式分页存储管理

与纯分页存储管理不同，请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。缺页中断当要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺的页面调入内存。页面置换算法先进先出置换算法最近最久未用置换算法(LRU)近似的LRU算法（NRU算法）先进先出(FIFO)页面置换算法基本思想：置换时首先淘汰在内存中驻留时间最长的页面，即最早进入主存的页面。时刻123456789101112P432143543215M4+3+42+3④1+2③4+1②3+4①5+3453453④2+5③1+25125F+++++++++FIFOM=3缺页中断次数：F=9缺页率：f=9/12=75%最近最久未用(LRU)置换算法

基本思想：当需要置换一页时，选择在最近一段时间最久未用的页予以淘汰。时刻123456789101112P432143543215M4+3+42+3④1+2③4+1②3+4①5+3445334⑤2+3④1+2③5+12F++++++++++LRUM=3缺页中断次数：F=10缺页率：f=10/12=83%分段存储管理原理：按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。内存划分内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定。内存分配以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。段表

记录了段号，段的首（地）址和长度之间的关系。每一个程序设置一个段表，放在内存，属于进程的现场信息。分页与分段的主要区别段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。页的大小固定不变，由系统决定。段的大小是不固定的，它由其完成的功能决定。段式向用户提供的是二维地址空间，页式向用户提供的是一维地址空间，其页号和页内偏移是机器硬件的功能。由于段是信息的逻辑单位，因此便于存贮保护和信息的共享，页的保护和共享受到限制。

段页式存储管理

段页式管理吸收了分段的地址空间按逻辑意义分段的优点和分页在存储空间管理上的优点，不把段看成一个单一的连续整体来实现，而是将每个段分成若干页面来管理。进程的逻辑地址由三个部分组成：即段号s，页号p，和页内相对地址w。段号段内地址页号页内地址段表长度段表控制寄存器段号页表长度(页数)内外标志页表始址0L111L202L313段表…内存起始地址页号内外页面01121119215。。。第0段页表页号内外页面012010216。。。

第2段页表56…12…1920…段页式地址映像段表长度指某个作业进程所含段的数量；页表长度指一个段所占用的页的数量。设备管理设备的分类:按照功能、数据组织、资源分配和数据传输速率设备的独立性设备的统一性设备控制器的组成程序直接控制方式。(2)程序中断I/O方式。(3)DMA方式。(4)通道方式。I/O控制方式DMA方式下的数据传输

通道分类:字节多路通道选择通道数组多路通道

通道通道工作原理：CPU、通道I／O软件的层次中断处理程序设备驱动程序与设备无关的I/O软件用户层的输入/输出软件设备管理中的四种控制块

表目1┇表目i┇设备类型设备标识获得设备的进程DCT指针

系统设备表STD控制器标识控制忙/闲标记CHCT指针控制器等待队列首控制器等待队列尾┇COCT

通道标识通道忙/闲标记通道等待队列首通道等待队列尾┇CHCT

设备类型设备标识设备忙/闲标记COCT指针设备等待队列首设备等待队列尾驱动程序地址DCT

I/O系统的设备分配按如下步骤实施设备分配：分配设备。(2)分配控制器。(3)分配通道。I/O控制中断