操作系统原理ppt课件

1、l 操作系统概述l 进程管理l 存储管理l 文件系统与I/O操作系统给计算机一个灵活的大脑、一个强健的心脏和突出的个性 孰优？q(quoting Linus Torvalds):q . message passing as the fundamental operation of the OS is just an exercise in computer science masturbation. It may feel good, but you dont actually get anything DONE.qMonolithic：内核中所有的子系统运行在相同的特权级(privilege

2、d mode），拥有相同的地址空间，通信采用常规C函数调用的形式。系统调用是一个复杂的过程系统调用往往通过软中断的方式实现系统调用在为应用程序提供操作系统服务的同时，也实现了对计算机资源和应用程序的保护nProcess - a program in executionn text section, data section, stack, current activity n进程是资源拥有的基本单位进程是资源拥有的基本单位(unit of resource ownership)nCPU、存储空间，及其他资源、存储空间，及其他资源I/O设备、文件等）设备、文件等）n进程控制块进程控制块PCB及其

3、管理及其管理n进程的状态：进程的状态：running,ready,blocked,stopped,zombien qThread an execution path in a processqThread the unit of dispatchingq 进程中的线程共享进程资源，但拥有私有堆栈及进程中的线程共享进程资源，但拥有私有堆栈及线程控制块线程控制块(TCB，存储寄存器值、优先级及其他线，存储寄存器值、优先级及其他线程状态信息程状态信息)q核心级线程核心级线程KLT：kernel-level thread）q应用程序通过应用程序通过API调用核心线程管理例程调用核心线程管理例程(ker

4、nel thread facility)来管理：来管理：q 需要进行模式切换需要进行模式切换q是是OS调度的基本单位调度的基本单位q线程阻塞不会导致整个进程的阻塞线程阻塞不会导致整个进程的阻塞q在多处理器环境下，内核可使线程在不同的处理器上在多处理器环境下，内核可使线程在不同的处理器上运行运行qE.g. windows threadq用户级线程用户级线程ULT：user-level thread）q由应用程序自己通过线程库由应用程序自己通过线程库(thread library)来管理来管理：线程创建、终止、线程间通信，线程调度与切换：线程创建、终止、线程间通信，线程调度与切换qOS感知不到感知

5、不到ULT的存在的存在q线程阻塞会导致整个进程的阻塞线程阻塞会导致整个进程的阻塞q理论上讲，在任何理论上讲，在任何OS下都可以实现下都可以实现q无法利用多处理器无法利用多处理器#include #include int sum;void *runner(void *param);main(int argc, char *argv) pthread_t tid; pthread_attr_t attr; pthread_attr_init(&attr); /初始化线程属性为缺省属性 pthread_create(&tid,&attr,runner,argv1); /创建线

6、程 pthread_join(tid,NULL); /等待线程tid结束 printf(“sum=%dn”,sum);void *runner(void *param) int upper=atoi(param); int i; sum = 0; if (upper 0) for ( i = 1; i =upper; i+) sum +=i; pthread_exit(0);三、并发控制：互斥与同步三、并发控制：互斥与同步并发并发Concurrent） 与并行与并行Parallel） q临界资源临界资源(critical resource)q一次只能由一个进程访问的资源一次只能由一个进程访问的

7、资源q临界区临界区(critical section)q访问临界资源的代码段称为临界区访问临界资源的代码段称为临界区CS）q互斥互斥(mutual exclusion)q在一个时刻最多只有一个进程在临界区在一个时刻最多只有一个进程在临界区q同步同步(synchronization)q协调需要访问临界资源的进程，否则会导致协调需要访问临界资源的进程，否则会导致race condition竞争条件）竞争条件）q如：两进程如：两进程 p0,p1，都通过下面的代码访问一个共享的存储单，都通过下面的代码访问一个共享的存储单元元:qShared variable:int total : = 0 ;qp0,

8、p1:qq int count;qfor (count=1; count =50; count+)q total = total + 1 ;qqtotal可能的结果？可能的结果？q最大值？最小值？最大值？最小值？q注意注意total是两个进程都可以访问的共享存储单元，不同于一是两个进程都可以访问的共享存储单元，不同于一般程序中的全局变量般程序中的全局变量q两个前提：两个前提：q对处理器数及各进程的相对运行速度不会是零速度不应该对处理器数及各进程的相对运行速度不会是零速度不应该有任何假设有任何假设q进程在临界区停留的时间是有限的进程在临界区停留的时间是有限的q三个必须：三个必须：q互斥互斥(mu

9、tual exclusion)q有空让进有空让进(progress)，若没有进程在临界区，则应该让申请进入，若没有进程在临界区，则应该让申请进入临界区的进程中的一个立即进入临界区的进程中的一个立即进入q有限等待有限等待(bounded waiting)，申请进入临界区的进程不会无止，申请进入临界区的进程不会无止境的等待即不会有饥饿现象）境的等待即不会有饥饿现象）1.软件方法忙等待）软件方法忙等待）Shared variablesboolean flag2; /initially flag 0 = flag 1 = turn; /initially turn=i;Proces

10、s Pido flagi := true;while (turn i) while (flag j ) ; turn := i ;flag i = false; while (1);此算法正确吗？此算法正确吗？Peterson算法：算法直观，只能解决二个进程同步 P0: do flag0:=true; /希望进入 turn := 1; /给对方一次机会 while flag1 and turn = 1 donothing; /如果对方先申请则等待 flag0:= false; while (1)2. 利用硬件支持利用硬件支持中断屏蔽中断屏蔽(interrupt disable)代价大，无法做到

11、程序的交叉执行代价大，无法做到程序的交叉执行interleave)多处理环境下无法实现多处理环境下无法实现特殊机器指令特殊机器指令Test and Set InstructionExchange Instruction优点：适合多处理器环境、简单优点：适合多处理器环境、简单缺点：必须忙等待缺点：必须忙等待(busy waiting)、可能导致饥饿、可能导致饥饿qOS提供的装置，用于进行进程提供的装置，用于进行进程/线程的同步与互斥线程的同步与互斥q数据结构数据结构(s)qcount:integer;=0表示可用资源数，表示可用资源数，0，其绝对值表示挂起进程，其绝对值表示挂起进程数，初始化非负

12、数，初始化非负qqueue:list of process；正在等待该类资源的进程；正在等待该类资源的进程q进程只能通过进程只能通过OS提供的提供的wait和和signal两个操作原语访问信号量两个操作原语访问信号量qWait(s):等待资源等待资源q s.count = s.count 1;q if s.count 0 then beginq place this process in s.queue;q block this process;q end;qSignal(s):释放资源释放资源q s.count = s.count +1;q if s.count =0 then beginq

13、 remove a process P from s.queue;q place process P on ready list;q end;信号量信号量full，初始化为，初始化为0,表示缓冲区中可消费的资源数表示缓冲区中可消费的资源数mutex，初始化为，初始化为1,用于对缓冲区的互斥操作用于对缓冲区的互斥操作empty, 初始化为缓冲区的长度初始化为缓冲区的长度N，表示缓冲区中空闲单元，表示缓冲区中空闲单元数数Producer: repeat produce; wait(empty);wait(mutex); append; signal(mutex) ;signal(full); fo

14、reverConsumer: repeat wait(full); wait(mutex); take; signal(mutex);signal(empty);consume forever例：有n个进程P1，P2，Pn向容量为M的缓冲区写数据，每个进程一次写1个数据，当缓冲区写满时，另一个读进程Pr一次将M个数据全部读完，如此反复。请用信号量解决这些进程的同步互斥问题。答：本题中需要定义下述变量和信号量：data_type bufferM; /* data_type对应于所需要的数据类型，如int、float等 */int in=0； /* 用来指示下一个可存放数据的缓冲区 */semap

15、hore empty=M; /* 对应空闲的缓冲区 */semaphore full=0; /* 对应缓冲区中的数据 */semaphore mutex=1; /* 用来实现Pi进程对变量in的互斥访问 */进程Pi可描述为：Pi() while(1) wait(empty); wait(mutex); 向缓冲区bufferin中写数据； in=(in+1)%M; signal(mutex); signal(full); 进程Pr可描述为：Pr() int i; while(1) for(i=0;iM;i+) wait(full); wait(mutex); 取出缓冲buffer0到buffe

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

17、描述为：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*/ n四、并发控制：死锁问题四、并发控制：死锁问题1.死锁死锁deadlock）系统中存在一个进程集合，该集合中的每个进程都占用系统中存在一个进程集合，该集合中的每个进程都占用了一定数量的资源，并且在等待被集合中的其他进

18、程占了一定数量的资源，并且在等待被集合中的其他进程占用的资源用的资源例：某系统由相同类型的例：某系统由相同类型的8个资源组成，若资源可被个资源组成，若资源可被3个进个进程共享，每个进程最多可申请程共享，每个进程最多可申请3个资源，问该系统是否会个资源，问该系统是否会发生死锁？发生死锁？ nMutual exclusion：互斥nHold and wait：保持等待，申请资源时拥有其他资源nNo preemption：非剥夺，进程占有的资源只能由进程自己释放，不会被别的进程剥夺nCircular wait：循环等待(若各类资源的资源数为1，则一定死锁)n间接预防：阻止Mutual exclusi

19、on, Hold and wait及No preemption都满足n直接预防：阻止circular wait的发生。n一种可行的方法：有序申请法对所有资源类别编号，进程申请资源按序进行）。n例：哲学家就餐问题，筷子编号，先拿编号小的、再拿大的。n进程申请资源时，决定是否应该满足n必须预先知道每个进程需要的各类资源数nBankers algorithm，银行家算法n基本思想，若新的状态是安全的safe），则满足它nSafe state：从此状态出发，存在某种执行顺序安全序列,safe sequence），可以使所有进程执行完毕。n安全状态只是暂时安全，如果以后资源分配不当，也会导致死锁；不安全

20、状态不一定就死锁。状态状态a是安全的是安全的(a) (b) (c) (d) (e)(a) (b) (c) (d) 状态状态b）是不安全的）是不安全的nP4 没有获得资源，打上标记没有获得资源，打上标记n置置 W = (0,0,0,0,1)nP3请求的资源请求的资源 = W. 给给P3打标记，并置打标记，并置 W = W + (0,0,0,1,0) = (0,0,0,1,1)n算法无法找到满足条件的进程，终止。所以系统发生死锁，算法无法找到满足条件的进程，终止。所以系统发生死锁，P1和和P2 是死锁进程是死锁进程R1 R2 R3 R4 R5P1P2P3P4Request Allocated Av

21、ailableR1 R2 R3 R4 R5R1 R2 R3 R4 R50 1 0 0 10 0 1 0 10 0 0 0 11 0 1 0 11 0 1 1 01 1 0 0 00 0 0 1 00 0 0 0 00 0 0 0 1n当发生死锁时，如何恢复死锁n Abort all deadlocked processes. Abort one process at a time until the deadlock cycle is eliminated. In which order should we choose to abort?n Priority of the process.n

22、 How long process has computed, and how much longer to completion.nResources the process has used.nResources process needs to complete.nHow many processes will need to be terminated. nIs process interactive or batch? nSelecting a victim minimize costn Rollback return to some safe state, restart proc

23、ess for that state.Starvation same process may always be picked as victim, include number of rollback in cost factor.1. CPU约束进程与约束进程与I/O约束进程约束进程进程的执行是进程的执行是CPU burst与与I/O burst交替的过程交替的过程CPU约束进程：大量时间作计算，少量约束进程：大量时间作计算，少量I/OI/O 约束进程：大量的约束进程：大量的I/O，少量时间作计算，少量时间作计算2. 调度准则调度准则(criteria)3. 调度模式调度模式(decisi

24、on mode)Non-preemptive非抢占式）非抢占式）进程一旦被调度，则执行至结束或不能继续执行进程一旦被调度，则执行至结束或不能继续执行如因为发起如因为发起I/O操作而等待）操作而等待）Preemptive抢占式）抢占式）当一个新的进程到达时当一个新的进程到达时当有进程从阻塞变为就绪时当有进程从阻塞变为就绪时进程从核心态返回到用户态时如中断、系统调进程从核心态返回到用户态时如中断、系统调用返回时）用返回时）注：此抢占非指内核抢占注：此抢占非指内核抢占4. 常用调度算法常用调度算法FCFS(first come first served)先来先服务，直至结束先来先服务，直至结束(no

25、npreemptive)RR:Round robin时间片轮转时间片轮转(time slice,preemptive)时间片到时，将进程放入就绪队列的末尾，然后从时间片到时，将进程放入就绪队列的末尾，然后从队列头部取出一个进程运行队列头部取出一个进程运行公平的调度策略，不会导致进程饥饿公平的调度策略，不会导致进程饥饿Priority scheduling：基于优先级的调度：基于优先级的调度存在问题：饥饿低优先级进程可能永远得不到执存在问题：饥饿低优先级进程可能永远得不到执行行解决办法：老化（解决办法：老化（ Aging） 随着时间的推移，进随着时间的推移，进程的优先级可以提升程的优先级可以提升

26、(即进程的优先级可以是动态即进程的优先级可以是动态的的)n分区：将内存划分为若干个分区，每个分区存放一个进程，以支分区：将内存划分为若干个分区，每个分区存放一个进程，以支持多道程序持多道程序(multi-programming)，nFixed partitioning:固定大小的分区，分区内部会出现碎块固定大小的分区，分区内部会出现碎块(internal fragment)nDynamic partitioning:动态分区，按照进程大小决定分区大小，动态分区，按照进程大小决定分区大小，不存在内部碎块，但有外部碎块不存在内部碎块，但有外部碎块external fragment)，涉及放，涉及放

27、置算法置算法(placement algorithm)：first fit,best fit, next fitOSprocess 5process 8process 2OSprocess 5process 2OSprocess 5process 2OSprocess 5process 9process 2process 9process 10Buddy system常用于空闲内存管理）常用于空闲内存管理）n若一次TLB访问时间为 ,一次存储器访问时间为1n TLB命中率为，则平均存取时间EAT为：nEAT = (1 + ) + (2 + )(1 )n= 2 + 页表的实现方式：页表的实现方式

28、： 页表分级页表分级 Hash页表页表 倒置页表倒置页表n进程的虚地址空间进程的虚地址空间(virtual address space)n由进程的逻辑地址组成的地址空间。由进程的逻辑地址组成的地址空间。n虚地址空间可以远大于系统的物理内存。虚地址空间可以远大于系统的物理内存。n虚拟存储器虚拟存储器(virtual memory)：逻辑地址访问的：逻辑地址访问的存储器存储器n决定何时将进程的逻辑页面装入内存决定何时将进程的逻辑页面装入内存nDemand paging按需调页）：发生缺页时，才将页按需调页）：发生缺页时，才将页面装入。面装入。nPrepaging预取）：预先将某些页面装入内存。预取

29、）：预先将某些页面装入内存。nOS分配给进程的物理内存不够用时，需要页替换分配给进程的物理内存不够用时，需要页替换nOptimal：最优化方法，选择将来最久不会被访问的页换：最优化方法，选择将来最久不会被访问的页换出出n需要预先知道页访问序列需要预先知道页访问序列n不可能实现，只是作为一个评判标准不可能实现，只是作为一个评判标准nFIFO：最先装入的被换出：最先装入的被换出nLRU:最久未使用的页被换出最久未使用的页被换出(基于基于locality现象，很有效现象，很有效)nClock policy，时钟算法。，时钟算法。LRU算法不易实现，用时钟算算法不易实现，用时钟算法近似模拟法近似模拟n

30、每页设置一个每页设置一个reference bit，为，为1表示在时钟指针循环一表示在时钟指针循环一周内被访问过；周内被访问过；n查找替换页：查找替换页：n 指针扫描，若指针扫描，若reference bit =1,置为置为0,否则该页就是否则该页就是替换对象。替换对象。nBeladys Anomaly(belady异态异态):内存大，反而缺页率高内存大，反而缺页率高n进程执行时缺页率过高，使得系统忙于页面换进换进程执行时缺页率过高，使得系统忙于页面换进换出，因此执行效率低。提高效率的可行方法：出，因此执行效率低。提高效率的可行方法：n优化页调入与替换算法；优化页调入与替换算法；n增加物理内存

31、；增加物理内存；n减少进程数；减少进程数；n提供更快速的交换设备。提供更快速的交换设备。n工作集工作集working set,进程近期访问的页面的集合进程近期访问的页面的集合）n为防止抖动，应该使得进程获得足够的内存以使进为防止抖动，应该使得进程获得足够的内存以使进程的工作集在内存中程的工作集在内存中n计算工作集的算法计算工作集的算法七、抖动七、抖动(thrashing)n实现虚拟存储的重要手段实现虚拟存储的重要手段n扩大内存，使系统可以运行比物理内存大的程序。扩大内存，使系统可以运行比物理内存大的程序。n交换空间交换空间swap space）n交换文件，文件系统下的一个文件如交换文件，文件系

32、统下的一个文件如windows下的下的页面文件）页面文件）n交换设备如交换设备如linux的的swap分区）分区）n后者比前者的读写效率高后者比前者的读写效率高n交换设备的管理交换设备的管理n数据结构数据结构n交换设备上的空间信息；交换设备上的空间信息；n页表项上标识页面在交换区中的信息。页表项上标识页面在交换区中的信息。nLinux中的中的Swap cache：提高交换设备的存取效率：提高交换设备的存取效率 1.文件系统文件控制块FCB）目录空闲磁盘空间管理文件系统性能n文件控制块FCB)npermissions, dates, ownershipnsize, Data blocks indexesUNIX/Linux 文件控制块i-node(index node:索引节点）n目录：存储目录下文件名字及属性如FCB信息）qTwo ways of handling long file names in directoryq(a) In-lineq(b) In a heapAn example of how a lo