操作系统原理20110905课件

OperatingSystemPrinciples操作系统概述进程管理存储管理文件系统与I/O1第一部分操作系统概述一、操作系统的功能实现对计算机资源的管理(CPU,存储器，I/O设备）控制应用程序的执行提供应用程序访问计算机资源的接口（系统调用）实现对操作系统内核及应用程序的保护操作系统给计算机一个灵活的大脑、一个强健的心脏和突出的个性2二、OS的分类批系统（batchsystem）成批提交作业，作业完成或无法继续执行时发生切换交互（分时）系统（interactive,Time-sharingsystem)多个用户（应用程序）分享计算机资源 Windows,Linux,…实时系统（Real-timesystem）满足应用的时间约束要求

VxWorks,QNX,…3Monolithicvs.micro-kernel(quotingLinusTorvalds):...messagepassingasthefundamentaloperationoftheOSisjustanexerciseincomputersciencemasturbation.Itmayfeelgood,butyoudon'tactuallygetanythingDONE.Monolithic：内核中所有的子系统运行在相同的特权级(privilegedmode），拥有相同的地址空间，通信采用常规C函数调用的形式。5四、操作系统的硬件支持特权级（区分OS与应用程序的权限）MMUCache中断6五、系统调用操作系统提供给应用程序的一个接口，使得应用程序能够获得操作系统的服务进程管理、文件管理、存储管理、系统管理等系统调用是一个复杂的过程系统调用往往通过软中断的方式实现系统调用在为应用程序提供操作系统服务的同时，也实现了对计算机资源和应用程序的保护7二、线程（thread）Thread–anexecutionpathinaprocessThread–theunitofdispatching

进程中的线程共享进程资源，但拥有私有堆栈及线程控制块(TCB，存储寄存器值、优先级及其他线程状态信息)核心级线程（KLT：kernel-levelthread）应用程序通过API调用核心线程管理例程(kernelthreadfacility)来管理：需要进行模式切换是OS调度的基本单位线程阻塞不会导致整个进程的阻塞在多处理器环境下，内核可使线程在不同的处理器上运行E.g.windowsthread9用户级线程（ULT：user-levelthread）由应用程序自己通过线程库(threadlibrary)来管理：线程创建、终止、线程间通信，线程调度与切换OS感知不到ULT的存在线程阻塞会导致整个进程的阻塞理论上讲，在任何OS下都可以实现无法利用多处理器1011三、并发控制：互斥与同步并发（Concurrent）与并行（Parallel）临界资源(criticalresource)一次只能由一个进程访问的资源临界区(criticalsection)访问临界资源的代码段称为临界区（CS）13互斥(mutualexclusion)在一个时刻最多只有一个进程在临界区同步(synchronization)协调需要访问临界资源的进程，否则会导致racecondition（竞争条件）如：两进程p0,p1，都通过下面的代码访问一个共享的存储单元:Sharedvariable: inttotal:=0;p0,p1:{

intcount; for(count=1;count<=50;count++) total=total+1;}total可能的结果？最大值？最小值？注意total是两个进程都可以访问的共享存储单元，不同于一般程序中的全局变量14临界区问题解决方法正确性的准则两个前提：对处理器数及各进程的相对运行速度（不会是零速度）不应该有任何假设进程在临界区停留的时间是有限的三个必须：互斥(mutualexclusion)有空让进(progress)，若没有进程在临界区，则应该让申请进入临界区的进程中的一个立即进入有限等待(boundedwaiting)，申请进入临界区的进程不会无止境的等待（即不会有饥饿现象）15Peterson算法：算法直观，只能解决二个进程同步

P0:do{flag[0]:=true;//希望进入

turn:=1;//给对方一次机会whileflag[1]andturn=1do{nothing};//如果对方先申请则等待<CS>flag[0]:=false;<RS>}while(1)172.利用硬件支持中断屏蔽(interruptdisable)代价大，无法做到程序的交叉执行（interleave)多处理环境下无法实现特殊机器指令TestandSetInstructionExchangeInstruction优点：适合多处理器环境、简单缺点：必须忙等待(busywaiting)、可能导致饥饿183.信号量(semaphore，无忙等待)OS提供的装置，用于进行进程/线程的同步与互斥数据结构(s)count:integer;>=0表示可用资源数，<0，其绝对值表示挂起进程数，初始化非负queue:listofprocess；正在等待该类资源的进程进程只能通过OS提供的wait和signal两个操作原语访问信号量Wait(s):等待资源s.count=s.count–1;ifs.count<0thenbeginplacethisprocessins.queue;blockthisprocess;end;Signal(s):释放资源s.count=s.count+1;ifs.count<=0thenbeginremoveaprocessPfroms.queue;placeprocessPonreadylist;end;19例：有n个进程（P1，P2，…，Pn）向容量为M的缓冲区写数据，每个进程一次写1个数据，当缓冲区写满时，另一个读进程Pr一次将M个数据全部读完，如此反复。请用信号量解决这些进程的同步互斥问题。答：本题中需要定义下述变量和信号量：data_typebuffer[M];/*data_type对应于所需要的数据类型，如int、float等*/intin=0；/*用来指示下一个可存放数据的缓冲区*/semaphoreempty=M;/*对应空闲的缓冲区*/semaphorefull=0;/*对应缓冲区中的数据*/semaphoremutex=1;/*用来实现Pi进程对变量in的互斥访问*/进程Pi可描述为：Pi(){while(1){wait(empty);wait(mutex);向缓冲区buffer[in]中写数据；

in=(in+1)%M;signal(mutex);signal(full);}}进程Pr可描述为：Pr(){inti;while(1){for(i=0;i<M;i++)wait(full);wait(mutex);

取出缓冲buffer[0]到buffer[M-1]中的数据；signal(mutex);

for(i=0;i<M;i++)signal(empty);}}21例：有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）；（2）-N<A产品数量-B产品数量<M。其中，N和M是正整数。试用信号量来同步产品A与产品B的入库过程。答：本题中，首先需要设置一个初值为1的互斥信号量mutex，以保证每次只存入一种产品。另外，为了保证“-N<A产品数量-B产品数量<M”，还需设置信号量SA，表示仓库中目前可再存放的A产品的数量，其初值为M-1；SB，表示目前还可再存放的B产品的数量，其初值为N-1。A产品入库的过程可描述为：B产品入库的过程可描述为：while(1){while(1){wait(SA);/*还可放A产品？*/wait(SB);/*还可放B产品？*/wait(mutex);wait(mutex);将A产品放入仓库；将B产品放入仓库；signal(mutex);signal(mutex);signal(SB);/*可放B产品数增1*/signal(SA);/*可放A产品数增1*/}}

22四、并发控制：死锁问题1.死锁（deadlock）

系统中存在一个进程集合，该集合中的每个进程都占用了一定数量的资源，并且在等待被集合中的其他进程占用的资源例：某系统由相同类型的8个资源组成，若资源可被3个进程共享，每个进程最多可申请3个资源，问该系统是否会发生死锁？

233.deadlockprevention死锁预防间接预防：阻止Mutualexclusion,Holdandwait及Nopreemption都满足直接预防：阻止circularwait的发生。 一种可行的方法：有序申请法（对所有资源类别编号，进程申请资源按序进行）。 例：哲学家就餐问题，筷子编号，先拿编号小的、再拿大的。254.deadlockavoidance死锁避免进程申请资源时，决定是否应该满足必须预先知道每个进程需要的各类资源数Banker’salgorithm，银行家算法基本思想，若新的状态是安全的（safe），则满足它Safestate：从此状态出发，存在某种执行顺序（安全序列,safesequence），可以使所有进程执行完毕。安全状态只是暂时安全，如果以后资源分配不当，也会导致死锁；不安全状态不一定就死锁。266.死锁恢复当发生死锁时，如何恢复死锁

Abortalldeadlockedprocesses.

Abortoneprocessatatimeuntilthedeadlockcycleiseliminated.

Inwhichordershouldwechoosetoabort?Priorityoftheprocess. Howlongprocesshascomputed,andhowmuchlongertocompletion. Resourcestheprocesshasused. Resourcesprocessneedstocomplete. Howmanyprocesseswillneedtobeterminated. Isprocessinteractiveorbatch?

Selectingavictim–minimizecostRollback–returntosomesafestate,restartprocessforthatstate.

Starvation–sameprocessmayalwaysbepickedasvictim,includenumberofrollbackincostfactor.29五、CPU调度(CPUscheduling)1.CPU约束进程与I/O约束进程进程的执行是CPUburst与I/Oburst交替的过程CPU约束进程：大量时间作计算，少量I/OI/O约束进程：大量的I/O，少量时间作计算302.调度准则(criteria)313.调度模式(decisionmode)Non-preemptive（非抢占式）进程一旦被调度，则执行至结束或不能继续执行（如因为发起I/O操作而等待）Preemptive（抢占式）当一个新的进程到达时当有进程从阻塞变为就绪时进程从核心态返回到用户态时（如中断、系统调用返回时）注：此抢占非指内核抢占324.常用调度算法FCFS(firstcomefirstserved)先来先服务，直至结束(nonpreemptive)RR:Roundrobin时间片轮转(timeslice,preemptive)时间片到时，将进程放入就绪队列的末尾，然后从队列头部取出一个进程运行公平的调度策略，不会导致进程饥饿Priorityscheduling：基于优先级的调度存在问题：饥饿－低优先级进程可能永远得不到执行解决办法：老化（Aging）–随着时间的推移，进程的优先级可以提升(即进程的优先级可以是动态的)33第三部分存储管理一、基本概念Relocation(重定位)：程序只有在执行时才能确定其在内存中的位置Protection(保护)：进程在未被允许时不能访问其他进程的地址空间Sharing(共享)：应该提供机制允许进程访问共享地址空间中的信息Logicaladdress(逻辑地址)：用户进程访问的地址，即虚地址Physicaladdress(物理地址)：物理存储器的地址3435二、物理内存管理分区：将内存划分为若干个分区，每个分区存放一个进程，以支持多道程序(multi-programming)，Fixedpartitioning:固定大小的分区，分区内部会出现碎块(internalfragment)Dynamicpartitioning:动态分区，按照进程大小决定分区大小，不存在内部碎块，但有外部碎块（externalfragment)，涉及放置算法(placementalgorithm)：firstfit,bestfit,nextfitOSprocess5process8process2OSprocess5process2OSprocess5process2OSprocess5process9process2process9process1036Buddysystem（常用于空闲内存管理）37三、分页、分段及段页式存储管理若一次TLB访问时间为

,一次存储器访问时间为1

TLB命中率为，则平均存取时间EAT为： EAT=(1+)+(2+)(1–) =2+–页表的实现方式：页表分级Hash页表倒置页表38分段（segmentation）39段页式存储管理(e.g.Pentium)40四、虚拟存储进程的虚地址空间(virtualaddressspace)由进程的逻辑地址组成的地址空间。虚地址空间可以远大于系统的物理内存。虚拟存储器(virtualmemory)：逻辑地址访问的存储器4142五、页装入策略(pagefetchpolicy)决定何时将进程的逻辑页面装入内存Demandpaging（按需调页）：发生缺页时，才将页面装入。Prepaging（预取）：预先将某些页面装入内存。43六、页替换策略(pagereplacementpolicy)OS分配给进程的物理内存不够用时，需要页替换Optimal：最优化方法，选择将来最久不会被访问的页换出需要预先知道页访问序列不可能实现，只是作为一个评判标准FIFO：最先装入的被换出LRU:最久未使用的页被换出(基于locality现象，很有效)Clockpolicy，时钟算法。LRU算法不易实现，用时钟算法近似模拟每页设置一个referencebit，为1表示在时钟指针循环一周内被访问过；查找替换页：指针扫描，若referencebit=1,置为0,否则该页就是替换对象。Belady’s

Anomaly(belady异态):内存大，反而缺页率高4445进程执行时缺页率过高，使得系统忙于页面换进换出，因此执行效率低。提高效率的可行方法：优化页调入与替换算法；增加物理内存；减少进程数；提供更快速的交换设备。工作集（workingset,进程近期访问的页面的集合）为防止抖动，应该使得进程获得足够的内存以使进程的工作集在内存中计算工作集的算法七、抖动(thrashing)46八、交换区管理实现虚拟存储的重要手段扩大内存，使系统可以运行比物理内存大的程序。交换空间（s）交换文件，文件系统下的一个文件（如windows下的页面文件）交换设备（如linux的swap分区）后者比前者的读写效率高交换设备的管理数据结构交换设备上的空间信息；页表项上标识页面在交换区中的信息。Linux中的S：提高交换设备的存取效率47第四部分文件系统与I/O管理1.文件系统文件控制块（FCB）目录空闲磁盘空间管理文件系统性能48文件控制块（FCB)permissions,dates,ownershipsize,Datablocksindexes49UNIX/Linux文件控制块i-node(indexnode:索引节点）50目录：存储目录下文件名字及属性（如FCB信息）Twowaysofhandlinglongindirectory(a)In-line(b)Inaheap51TheWindows98DirectoryAnexampleofhowalongnameisstoredinWindows9852通过目录搜索文件Thestepsinlookingup/usr/ast/mbox53文件系统空闲磁盘空间管理(a)Storingthefreelistonalinkedlist(b)Abitmap54典型文件系统磁盘结构55文件系统性能－Blockcache56文件系统性能－inode布局I-nodesplacedatthestartofthediskDiskdividedintocylindergroupseachwithitsownblocksandi-nodes572.I/O子系统I/O设备分类：独占、共享I/O设备的工作方式及特点:程序查询（Programme