操作系统_2013new.

操作系统OperatingSystems费翔林《操作系统教程(4)》高教社，2008葛季栋[e-mail]多道程序设计程序的动态概念内存管理提高性能和利用率—提高CPU与I/O，I/O之间的并行度固定/动态分区、分页/分段处理器管理/进程抽象I/O设备管理设备抽象,I/O软件的分层虚存抽象处理器调度虚拟分页虚拟段页式文件抽象单/多线程结构进程中断技术虚拟分段并发进程,同步与互斥(PV,管程,进程通信)磁盘管理/调度死锁问题,必要条件,预防,避免,检测和解除文件逻辑结构文件物理结构文件目录,共享与保护虚拟文件系统I/O控制方式,缓冲技术设备分配,虚拟设备Spooling文件管理文件系统文件抽象Chap3Chap4Chap6Chap2Chap5Roadmap安全与保护Chap7，网络和分布式Chap8主要内容第一章、操作系统概述第二/三章、进程和处理机管理、进程同步、互斥、通信与死锁第四章、存储管理第五章、设备管理和I/O系统第六章、文件管理第一章、操作系统概述操作系统的定义操作系统的特征操作系统的功能操作系统的分类第二/三章、进程和处理机管理，进程同步、互斥、通信与死锁进程–定义–特征–组成进程管理–五状态模型进程协作–互斥、同步–死锁处理机调度（作业管理）–调度算法第四章、存储管理内存管理–基本原理–分区调度虚存管理–页面调度磁盘管理–磁盘调度第五章、设备管理和I/O系统I/O设备数据传送控制方式中断技术虚拟设备Spooling技术第六章、文件管理文件–概念–实现目录–实现FAT32文件系统物理设备微程序机器语言O.S.命令解释器编译编辑银行系统，飞机订票硬件系统软件应用程序图1.2OSdos.应用程序裸机(硬件)第一章、操作系统概述操作系统的定义–操作系统是计算机系统的一个系统软件，它是这样的一些程序模块的集合：它们能有效的组织和管理计算机系统中的硬件及软件资源，合理的组织计算机工作流程，控制程序的执行，并向用户提供各种服务功能，使得用户能够灵活、方便、有效的使用计算机，使整个计算机系统能高效地运行。两方面作用–管理系统中的各种资源，包括硬件及软件资源–为用户提供良好的接口普通用户界面编程接口API操作系统的特征并发性--指若干事件在同一时间间隔内发生共享性随机性操作系统的功能进程管理–对处理机进行管理作业管理–OS向用户提供使用它自己的手段存储管理–管理存储资源操作系统的功能文件管理–有效的支持文件的存储、检索和修改等操作，解决文件的共享、保密和保护问题，以便用户方便安全地访问文件。设备管理–对计算机系统中的所有输入/输出设备的管理。其他功能–系统安全、网络通信等操作系统的分类批处理操作系统分时操作系统实时操作系统嵌入式操作系统网络操作系统分布式操作系统个人计算机操作系统智能卡操作系统第二、三章进程进程定义和描述进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。作为描述程序执行过程的概念，进程具有动态性、独立性、并发性和结构化等特征。进程与程序的区别和联系进程是动态的，程序是静态的。进程是暂时的，程序是永久的。进程和程序的组成不同。进程包括程序、数据和进程控制块。进程和程序是密切相关的。通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可以包括多个程序。进程可以创建其他进程，而程序不能形成新的程序。进程控制块进程由代码、数据和进程控制块PCB组成PCB是由操作系统维护的用来记录进程相关信息的数据结构。进程控制块的内容分为进程描述信息、进程控制信息、资源占用信息和处理机现场保护结构4个部分。五状态进程模型创建阻塞退出就绪运行创建新进程提交超时释放事件出现等待事件调度作业调度算法先来先服务算法（FirstComeFirstService）–基本思想是按照进程到达的先后顺序进行调度最短作业优先算法（ShortestJobFirst）–要求作业在开始执行时预计执行时间，给预计执行时间短的作业优先分派处理机。后来的短作业不抢现正在执行的作业。优先级算法（PriorityScheduling）–是多级队列的改进，协调各进程队列中进程的响应时间要求。分为抢占式和非抢占式。作业调度计算各种调度算法下作业队列的–平均周转时间调度的类型长程调度:决定加入到等待执行的进程池中中程调度：决定加入到部分或全部在主存中的进程集合中。短程调度：决定哪一个可用进程将保持处理器执行。I/O调度：决定哪一个进程挂起的I/O请求将被可用的I/O设备处理。调度的决策模式非抢占：–在这种情况下，一旦进程处于运行态，它就不断执行直到终止，或者为等待I/O或请求某些操作系统服务而阻塞自己。调度的决策模式抢占：–当前正在运行的进程可能被操作系统中断，并转移到就绪态。关于抢占的决策可能是在一个新进程到达时，或者在一个中断发生后把一个被阻塞的进程置为就绪态时，或者基于周期性的时间中断。–与非抢占策略相比，抢占策略可能会导致较大的开销，但是可能对所有进程会提供较好的服务，因为它们避免了任何一个进程独占处理器太长时间。此外，通过使用有效的进程切换机制(尽可能地获得硬件的帮助)，以及提供比较大的主存，使得大部分程序都在主存中，可使抢占的代价相对比较低。习题--作业调度先来先服务算法(FCFS)最简单的调度策略是先来先服务，也称为先进先出或者严格排队方案。当每个进程就绪后，它加入就绪队列。当当前正在运行的进程停止执行时，选择在就绪队列中存在时间最长的进程运行。非抢占FCFS最短作业优先算法最短进程优先是一个非抢占的策略，其原则是下一次选择所需处理时间最短的进程。短进程将会越过长作业，跳到队列头。非抢占最短作业优先算法进程的协作进程的调度–并发协作关系–同步竞争关系–互斥互斥算法临界资源是指计算机系统中需要互斥使用的硬件或软件资源，如外设、共享代码段、共享数据结构等。–(在一段时间内，只允许一个进程访问的资源)临界区是指进程中访问临界资源的一段代码。信号量信号量：由操作系统提供的管理公有资源的有效手段。信号量代表可用资源实体的数量，–0表示还有可用的资源，新来的进程可以直接执行，–0表示已经没有可用的资源，有进程因此而阻塞，–＝0表示已经没有可用的资源，也没有进程在等待该资源。–P原语P(s)：把信号量s减去1，如果计算后的信号量s小于0，则阻塞该进程–V原语V(s)：把信号量s加1，如果计算后的信号量s小于或等于0，则从阻塞队列中激活一个等待的进程生产者-消费者问题解决若干进程通过有限的共享缓冲区交换数据时的缓冲区资源使用问题。OneProducer,OneConsumer,NBuffersOneProducer，NConsumer,NBuffersNProducer,OneConsumer,NBuffersNProducer,NConsumer,NBuffersB:ARRAY[0..k-1]OFinteger;empty:semaphore；/*可以使用的空缓冲区数*/full:semaphore;/*缓冲区内可以使用的产品数*/mutex:semaphore;mutex:=1;empty:=k;/*缓冲区内允许放入k件产品*/full:=0;/*缓冲区内没有产品*/putptr,getptr:integer;putptr:=0;getptr:=0;processproducerbeginL1:produceaproduct；P(empty);P(mutex);B[putptr]:=product；putptr:=(putptr+1)modk;V(mutex);V(full);gotoL1;end;processconsumerbeginL2:P(full);P(mutex);Product:=B[getptr]；getptr:=(getptr+1)modk;V(mutex);V(empty);consumeaproduct；gotoL2;end;一个生产者,一个消费者,缓冲区容量为Nreadcount:=0semaphoreRmutex，Wmutex；Rmutex=1;Wmutex=1;Cobeginprocessreader_i(){P(Rmutex);if(readcount==0)P(Wmutex);readcount++;V(Rmutex);{读文件};P(Rmutex);readcount--;if(readcount==0)V(Wmutex);V(Rmutex);}processwriter_j(){P(Wmutex);{写文件};V(Wmutex);}coend信号量解决读者写者问题-读者优先哲学家吃通心粉问题有五个哲学家围坐在一圆桌旁，桌子中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后，欲吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。错误的解法出现死锁semaphorefork[5];for(inti=0;i5;i++)fork[i]=1;cobeginprocessphilosopher_i(){/*i=0,1,2,3*/while(true){think()；P(fork[i]；/*i=4,P(fork[0])*/P(fork[(i+1)%5])；/*i=4,P(fork[4])*/eat()；V(fork[i])；V(fork([i+1]%5)；}}coend哲学家吃通心面问题的一种正确解哲学家吃通心粉问题-死锁非死锁的解法死锁问题死锁（deadlock）是指系统中多个进程无限制的等待永远不会发生的条件。产生条件–互斥：任意时刻只允许一个进程使用资源–请求和保持：进程在请求其他资源的时候，不主动释放已经占用的资源–非剥夺：进程已经占用的资源，不会被强制剥夺–环路等待：环路中的每一进程在请求另一进程已经占有的资源。(银行家算法)处理死锁的基本方法死锁的预防–预防死锁是指通过某种策略来限制并发进程对资源的请求，使系统在任何时候都不满足死锁的必要条件。–预先静态分配法和有序资源使用法。死锁的检测–基本思路是在操作系统中保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。–资源分配图死锁的避免–最合理做法应该是在分配资源时判断是否出现死锁，只有确信不会导致死锁时才分配资源。–银行家算法第四章、存储管理内存管理的基本原理–内存管理主要包括内存分配和回收、地址变换、内存扩充、内存共享和保护等功能。内存的管理–分区(固定分区，可变分区)–分页–分段–段页式固定分区可变分区存储管理可变分区存储管理是按作业的实际大小来划分分区，且分区个数也是随机的,实现多个作业对主存的共享，进一步提高主存资源利用率。特点:1)分区的个数动态变化，每个分区的长度也是可变的。2)在分区外围会形成碎片，成为外部碎片。3)在转载进程的时候需要找到一个容量大于该进程内存需求的空闲分区，如果找不到，需要进行内存的移动。常用的动态分区分配算法（1）最先适配法–按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端，但是随着低端分区不断划分，会产生较多小分区，每次分配时，查找时间开销便会增大。下次适配法(邻近适配)–按分区在内存的先后次序，从上次分配的分区起查找（到最后分区时，再从头开始），找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。常用的动态分区分配算法（2）最佳适配法–按分区在内存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进行分配。从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。这种方法的优点是较大的空闲分区可以被保留下来。最坏适配法–按分区在内存的先后次序从头查找，找到最大