1、操作系统课程期末复习,第一章,操作系统作用中断：在计算机执行期间，系统内发生任何非寻常的或非预期的急需处理事件使得CPU暂时中断当前正在执行的程序而，转去执行相应的时间处理程序。待处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。直接内存访问：Direct Memory Access(DMA)允许外围设备和主内存之间直接传输它们的I/O数据，而不需要系统处理器的参与。,多CPU、多核多道程序系统分时系统操作系统双重模式用户模式内核模式,第二章：操作系统概述,对于用户来说 操作系统是个“黑盒子”,要打开这个盒子 先得找到“盒子的入口”系统接口,接口:连接两个设备并转换数据 系统接口连
2、接用户和OS,学习转换 转换之前:用户如何使用计算机?,命令、GUI、Apps 都是应用OS提供的函数接口编程序,系统调用有哪些?POSIX,OS提供的函数 系统调用 系统调用有哪些?怎么做?,第二章：操作系统概述,系统调用系统调用类型微内核VS强内核,第三章：进程,计算机解决问题 执行程序,执行中的程序和静止程序存在很大区别 引出进程,CPU太快 引出并发 进一步深化了进程,进程走走停停 状态转化 现场切换 进程调度,进程相互干扰 进程保护 地址空间 线程,进程相互协作 进程同步 进程通信消息,用户希望操纵进程 进程创建等,第三章：进程,进程定义运行中的程序资源分配的最小单位CPU调度的一个
3、单位进程状态图,进程与线程,进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。线程有时称轻量级进程，进程中的一个运行实体，是一个CPU调度单位。进程和线程的不同之处可从以下四个方面比较：(1)调度：线程作为调度的基本单位，同进程中线程切换不引起进程，当不同进程的线程切换才引起进程切换；进程作为拥有资源的基本单位。(2)并发性：一个进程间的多个线程可并发。(3)拥有资源：线程仅拥有隶属进程的资源；进程是拥有资源的独立单位。(4)系统开销：进程大；线程小。,进程控制块 PCB进程切换长期调度、中期调度、短期调度,进程调度,在许多进程或线程都准备使用CPU
4、进行任务处理时，就会存在资源竞争和分配的问题。一般都会将进程或线程先放在一个缓冲池中，等待合适的时机调度程序从中选择一个进程或线程进行交给CPU进行处理。,长期调度、中期调度、短期调度,(1)长期调度，又称为作业调度或高级调度，这种调度将已进入系统并处于后备状态的作业按算法选择一个或一批，为其建立进程，并进入主机，当该作业执行完毕时，还负责回收系统资源，在批处理系统中，需要有作业调度的过程，以便将它们分批地装入内存，在分时系统和实时系统中，通常不需要长期调度。它的频率比较低，主要用来控制内存进程的数量。(2)中期调度，又称为交换调度。它的核心思想是能将进程从内存或从CPU竞争中移出，从而降低多
5、道程序设计的程度，之后进程能被重新调入内存，并从中断处继续执行，这种交换的操作可以调整进程在内存中的存在数量和时机。其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。(3)短期调度，又称为进程调度、低级调度或微观调度。这也是通常所说的调度，一般情况下使用最多的就是短期调度。它的主要任务是按照某种策略和算法将处理机分配给一个处于就绪状态的进程，分为抢占式和非抢占式。三级调度的区别在于频率不同，长期调度频率较低，短期调度频率较高。,进程创建fork函数 父子函数返回的值不一样exec函数进程通信两种模型
6、并发与并行,第四章：线程,进程=地址空间+指令执行序列,一个地址空间+多个指令执行序列 引出线程,线程具有并发的优点，却比进程的代价低得多,WebExplorer表明线程简单实用 线程怎么实现,线程在同一地址空间中 线程库可以用户级实现,用户级线程，核心级线程，两者都有,各类线程的实现细节，其中上下文切换是核心,第四章：线程,线程定义多线程优势多线程模型,第五章：CPU调度,并发能提高效率 并发的核心是进程能让出CPU,进程让出CPU 下一个进程使用CPU 这个选择就是调度,进程、线程(内核级、用户级)都能调度 任务调度,调度任务分类:交互式，批处理,CPU调度算法:FCFS,SJF,Prio
7、rity(批处理);RR(交互式),CPU调度算法:多级队列,多级反馈队列(混合),调度时机分类:抢占式、非抢占式,第五章：CPU调度,FCFSSJFSRTFPriorityRR,掌握每种算法 各自特点 周转时间、等待时间、响应时间,第六章：进程同步,并发 多个进程同时存在 相互影响,非原子操作共享变量 出现语义错误 竞争条件,竞争条件 临界区 互斥 临界区进入方法,复杂的peterson算法强硬的关中断硬件支持的TestAndSet,都不适合用户实现 封装成锁,一般的锁会盲等 引入睡眠 将锁一般化为信号量,所有一切都是为了使用户更容易、使系统更好用(不出错),第六章：进程同步,进程的关系：同
8、步、互斥并发进程竞争条件：和时间有关的共享数据语义错误多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关,临界资源与临界区 critical section临界资源：一次仅允许一个进程使用的共享资源临界区：不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。临界区是每个进程中访问临界资源的那段程序。临界区访问原则：每次只允许一个进程进入临界区，进入后不允许其他进程进入。,解决临界区问题的三个条件,1.Mutual Exclusion(互斥)-If process Pi is executing in its critical section,then no ot
9、her processes can be executing in their critical sections2.Progress(前进)-If no process is executing in its critical section and some processes that wish to enter their critical sections,then only those processes that are not executing in their reminder sections can particulate in the decision on whic
10、h will enter its critical section next,and this selection cannot be postponed indefinitely3.Bounded Waiting(有限等待)-A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before th
11、at request is granted,解决临界区问题的方法,Software:Petersons SolutionHardware:Synchronization HardwareSemaphores:PV 信号量,它们的本质就是：上锁 进入临界区 解锁,还记得我们银行家算法的那个实验吗？里面有一个mutex的互斥这个就是典型的多线程对同一变量操作的访问问题。,do acquire lock critical section release lock remainder section while(TRUE);,如何用PV原语解决问题？观察一件案例，首先判断属于：进程同步？互斥？两者都有
12、的混合问题？互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。确定信号量，信号量可能有多个：有几个等待互斥：判断进程间是否互斥,关键是看进程间是否共享某一公有资源,一个公有资源与一个信号量相对应同步：进程同步时的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关,所以称该信号量为私有信号量确定信号量的值可用资源实体数
13、用PV原语实现同步或互斥,PV Semaphore,挑水的小和尚,某寺庙，有小、老和尚若干，有一水缸，由小和尚提水入缸（向缸中倒水）供老和尚饮用。水缸可容30桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为5个。每次入、取缸水仅为1桶，且不可同时进行。试给出有关从缸中取水和向缸中倒水的算法描述,几个进程：从井中取水后向缸中倒水为连续动作，可算同一进程从缸中取水为另一进程 同步还是互斥问题：互斥：水井、水缸、水桶同步：水缸的水信号量：互斥：水井 mutex1互斥：水缸mutex2同步：水缸能放的水-有没有觉得很像生产者消费者问题？,你想想小和尚怎么开始打水的？是一开始就去拿一个桶
14、到井里去吗？（宿舍有一瓶刚送来的桶装水，你会不会马上把它装到饮水机上？）,当然不是！要先看看饮水机上那个桶里还有没有水。同理，小和尚也要先看看缸里还能不能容得下一桶水。,算法描述：小和尚先到缸里看看能不能还装一桶水。相当于申请一个空位。小和尚到去申请一个桶拿到桶之后，小和尚到井里去打水（这个动作是互斥的）打好水，小和尚把水倒到缸里（这个动作是互斥的），缸里又多了一桶水，相当于释放一个满位小和尚把桶还回去。,小和尚先到缸里看看能不能还装一桶水。相当于申请一个空位。,小和尚到去申请一个桶,拿到桶之后，小和尚到井里去打水（这个动作是互斥的）,打好水，小和尚把水倒到缸里（这个动作是互斥的），,缸里又多
15、了一桶水，相当于释放一个满位,小和尚把桶还回去。,第七章：死锁,进程竞争资源 有可能形成循环竞争 死锁,死锁需要处理 死锁分析 死锁的必要条件,死锁处理 预防、避免、检测+恢复、忽略,死锁预防:破除必要条件 引入了不合理因素,死锁避免:用银行家算法找安全序列 效率太低,死锁检测恢复:银行家算法找死锁进程组并恢复 实现较难,死锁忽略:就好像没有死锁 现在用的最多,第七章：死锁,什么是死锁？多个进程因循环等待资源而造成无法执行的现象发生死锁的必要条件Mutual exclusion:only one process at a time can use a resourceHold and wait
16、(占有并等待):a process holding at least one resource is waiting to acquire additional resources held by other processesNo preemption:a resource can be released only voluntarily by the process holding it,after that process has completed its taskCircular wait(循环等待):there exists a set P0,P1,Pn of waiting pr
17、ocesses such that P0 is waiting for a resource that is held by P1,P1 is waiting for a resource that is held by P2,Pn1 is waiting for a resource that is held by Pn,and Pn is waiting for a resource that is held by P0.资源分配图：有环、无环,注意步骤！,第八章：内存,内存的根本目的 把程序放在内存并让其执行,程序执行需要重定位 编译、载入和运行三种定位时刻,运行时重定位最成熟 从逻辑地
18、址到物理地址的翻译,内存如何管理 连续内存分配(分区)最直观,程序由若干段组成 以段为单位的内存分区策略 分段,分段对程序员自然，但会造成内存碎片 分页 段页结合,第八章：内存,重定位bind什么是重定位重定位的时机动态链接、静态链接,内存分配方案,最简单最直接：连续分配：动态内存分配连续分配：分段典型：首次适应、最佳适应、最差适应问题：碎片-紧缩不连续分配：分页：逻辑地址转物理地址段页结合,An Example,Given five memory partitions of 100 KB,500 KB,200 KB,300 KB,and 600 KB(in order),how would
19、each of the first-fit,best-fit,and worst-fit algorithms place processes of 212 KB,417 KB,112 KB,and 426 KB(in order)?Which algorithm makes the most efficient use of memory?,first-fit212KB选中分区2，这时分区2还剩288KB。417KB选中分区5，这时分区5还剩183KB。112KB选中分区2，这时分区2还剩176KB。426KB无分区能满足，应该等待。,best-fit212KB选中分区4，这时分区4还剩88
20、KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区3，这时分区3还剩88KB。426KB选中分区5，这时分区5还剩174KB。,worst-fit212KB选中分区5，这时分区5还剩388KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区5，这时分区5还剩176KB。426KB无分区能满足，应该等待。,分区：1.100 KB,2.500 KB,3.200 KB,4.300 KB,5.600 KB,页表很大怎么办？,Hierarchical Paging(层次页表/多级页表)地址翻译效率很低，要提高效率TLB(Translation Look-aside
21、Buffer)是一组相联快速内存：快表Hashed Page Tables(哈希页表)Inverted Page Tables(反向页表),TLB得以发挥作用的原因,TLB命中时效率会很高，未命中效率会降低，平均后仍表现良好。用数字来说明:,有效访问时间=HitR(TLB+MA)+(1-HitR)(TLB+2MA),命中率!,内存访问时间!,TLB时间!,有效访问时间=80%(20ns+100ns)+20%(20ns+200ns)=144ns,有效访问时间=98%(20ns+100ns)+2%(20ns+200ns)=122ns,慢了22%!,TLB要想发挥作用，命中率应尽量高,TLB越大越好
22、，但TLB价格昂贵，通常64,1024,第九章：虚拟内存,内存的根本目的 把程序放在内存并让其执行,只要将部分程序放进内存即可执行 内存利用率高,可编写比内存大的程序 使用一个大地址空间(虚拟内存),部分程序在内存 其他部分在磁盘 需要的时候调入内存,页表项存在P位 缺页产生中断 中断处理完成页面调入,调入页面需要一个空闲页框 如果没有空闲页框 置换,置换方法 FIFOMINLRUClock,第九章：虚拟内存,优点1:地址空间物理内存,用户可以编写比内存大的程序,4G空间可以使用，简化编程,优点2:部分程序放入物理内存,内存中可以放更多进程，并发度好，效率高,将需要的部分放入内存，有些用不到的
23、部分从来不放入内存，内存利用率高,如一些处理异常的代码!,程序开始执行、响应时间等更快,请求调页过程,当访问没有映射的线性地址时,load addr,页错误处理程序,但完成这个过程很费时间(有时候一条指令会引起几次调页)!,显然是一个很好理解的过程,如何选一个空闲页框?,没有空闲页框怎么办?分配的页框数是有限的,页面淘汰(置换),需要选择一页淘汰,有多种淘汰选择。如果某页刚淘汰出去马上又要用,FIFO，最容易想到，怎么评价?,有没有最优的淘汰方法，OPT,最优淘汰方法能不能实现，能否借鉴思想，LRU,考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为3时（或者说是页框数是3，或者说帧数是3），试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少，淘汰的页面是哪些？缺页中断率是多少？,FIFO页面置换,1,2,5,4,1,3,Belady异常,来看一个例子!,引用序列1，2，3，4，1，2，5，1，2，3，4，5,FIFO页置换,3frame,9faults,4frame,10faults,
