2016-2017第一学期操作系统复习提纲

1、操作系统课程 期末复习,第一章,操作系统作用 中断： 在计算机执行期间，系统内发生任何非寻常的或非预期的急需处理事件使得CPU暂时中断当前正在执行的程序而，转去执行相应的时间处理程序。待处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。 直接内存访问： Direct Memory Access (DMA) 允许外围设备和主内存之间直接传输它们的I/O数据，而不需要系统处理器的参与。,多CPU、多核 多道程序系统 分时系统 操作系统双重模式 用户模式 内核模式,第二章：操作系统概述,对于用户来说 操作系统是个“黑盒子”,要打开这个盒子 先得找到“盒子的入口” 系统接口,接口: 连接两个设备并转换数据 系统接口连接用户和OS,学习转换 转换之前:用户如何使用计算机?,命令、GUI、Apps 都是应用OS提供的函数接口编程序,系统调用有哪些? POSIX,OS提供的函数 系统调用 系统调用有哪些?怎么做?,第二章：操作系统概述,系统调用 系统调用类型 微内核VS强内核,第三章：进程,计算机解决问题 执行程序,执行中的程序和静止程序存在很大区别 引出进程,CPU太快 引出并发 进一

2、步深化了进程,进程走走停停 状态转化 现场切换 进程调度,进程相互干扰 进程保护 地址空间 线程,进程相互协作 进程同步 进程通信消息,用户希望操纵进程 进程创建等,第三章：进程,进程定义 运行中的程序 资源分配的最小单位 CPU调度的一个单位 进程状态图,进程与线程,进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。 线程有时称轻量级进程，进程中的一个运行实体，是一个CPU调度单位。 进程和线程的不同之处可从以下四个方面比较： (1) 调度：线程作为调度的基本单位，同进程中线程切换不引起进程，当不同进程的线程切换才引起进程切换；进程作为拥有资源的基本单位。 (2) 并发性：一个进程间的多个线程可并发。 (3) 拥有资源：线程仅拥有隶属进程的资源；进程是拥有资源的独立单位。 (4) 系统开销：进程大；线程小。,进程控制块 PCB 进程切换 长期调度、中期调度、短期调度,进程调度,在许多进程或线程都准备使用CPU进行任务处理时，就会存在资源竞争和分配的问题。一般都会将进程或线程先放在一个缓冲池中，等待合适的时机调度程序从中选择一个进程或线程进行

3、交给CPU进行处理。,长期调度、中期调度、短期调度,(1)长期调度，又称为作业调度或高级调度，这种调度将已进入系统并处于后备状态的作业按算法选择一个或一批，为其建立进程，并进入主机，当该作业执行完毕时，还负责回收系统资源，在批处理系统中，需要有作业调度的过程，以便将它们分批地装入内存，在分时系统和实时系统中，通常不需要长期调度。它的频率比较低，主要用来控制内存进程的数量。 (2)中期调度，又称为交换调度。它的核心思想是能将进程从内存或从CPU竞争中移出，从而降低多道程序设计的程度，之后进程能被重新调入内存，并从中断处继续执行，这种交换的操作可以调整进程在内存中的存在数量和时机。其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。 (3)短期调度，又称为进程调度、低级调度或微观调度。这也是通常所说的调度，一般情况下使用最多的就是短期调度。它的主要任务是按照某种策略和算法将处理机分配给一个处于就绪状态的进程，分为抢占式和非抢占式。 三级调度的区别在于频率不同，长期调度频率较低，短期调度频率较高。,

4、进程创建 fork函数 父子函数返回的值不一样 exec函数 进程通信 两种模型 并发与并行,第四章：线程,进程 = 地址空间 + 指令执行序列,一个地址空间+多个指令执行序列 引出线程,线程具有并发的优点，却比进程的代价低得多,WebExplorer表明线程简单实用 线程怎么实现,线程在同一地址空间中 线程库可以用户级实现,用户级线程，核心级线程，两者都有,各类线程的实现细节，其中上下文切换是核心,第四章：线程,线程定义 多线程优势 多线程模型,第五章：CPU调度,并发能提高效率 并发的核心是进程能让出CPU,进程让出CPU 下一个进程使用CPU 这个选择就是调度,进程、线程(内核级、用户级)都能调度 任务调度,调度任务分类: 交互式，批处理,CPU调度算法: FCFS, SJF, Priority(批处理); RR(交互式),CPU调度算法: 多级队列, 多级反馈队列(混合),调度时机分类: 抢占式、非抢占式,第五章：CPU调度,FCFS SJF SRTF Priority RR, 掌握每种算法 各自特点 周转时间、等待时间、响应时间,第六章：进程同步,并发 多个进程同时存在 相互

5、影响,非原子操作共享变量 出现语义错误 竞争条件,竞争条件 临界区 互斥 临界区进入方法,复杂的peterson算法强硬的关中断硬件支持的TestAndSet,都不适合用户实现 封装成锁,一般的锁会盲等 引入睡眠 将锁一般化为信号量,所有一切都是为了使用户更容易、使系统更好用(不出错),第六章：进程同步,进程的关系：同步、互斥 并发进程 竞争条件： 和时间有关的共享数据语义错误 多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关,临界资源与临界区 critical section 临界资源：一次仅允许一个进程使用的共享资源 临界区：不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。临界区是每个进程中访问临界资源的那段程序。 临界区访问原则：每次只允许一个进程进入临界区，进入后不允许其他进程进入。,解决临界区问题的三个条件,1. Mutual Exclusion (互斥)- If process Pi is executing in its critical section, then no other processes can be executin

6、g in their critical sections 2. 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 which will enter its critical section next, and this selection cannot be postponed indefinitely 3. Bounded Waiting (有限等待) - A bound must exist on the number of times that other processes are allowed to enter their critical sect

7、ions after a process has made a request to enter its critical section and before that request is granted,解决临界区问题的方法,Software: Petersons Solution Hardware: Synchronization Hardware Semaphores: PV 信号量,它们的本质就是：上锁 进入临界区 解锁,还记得我们银行家算法的那个实验吗？ 里面有一个mutex的互斥 这个就是典型的多线程对同一变量操作的访问问题。,do acquire lock critical section release lock remainder section while (TRUE);,如何用PV原语解决问题？ 观察一件案例，首先判断属于：进程同步？互斥？两者都有的混合问题？ 互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。 同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序

8、访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。 确定信号量，信号量可能有多个：有几个等待 互斥：判断进程间是否互斥,关键是看进程间是否共享某一公有资源,一个公有资源与一个信号量相对应 同步：进程同步时的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关,所以称该信号量为私有信号量 确定信号量的值 可用资源实体数 用PV原语实现同步或互斥,PV Semaphore,挑水的小和尚,某寺庙，有小、老和尚若干，有一水缸，由小和尚提水入缸（向缸中倒水）供老和尚饮用。水缸可容30桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为5个。每次入、取缸水仅为1桶，且不可同时进行。 试给出有关从缸中取水和向缸中倒水的算法描述,几个进程： 从井中取水后向缸中倒水为连续动作，可算同一进程 从缸中取水为另一进程 同步还是互斥问题： 互斥：水井、水缸、水桶 同步：水缸的水 信号量： 互斥：水井 mutex1 互斥：水缸mutex2 同步：水缸能放的水 - 有没有觉得很像生产者消费者问题？,你想想小和尚怎么开始打水的

9、？是一开始就去拿一个桶到井里去吗？（宿舍有一瓶刚送来的桶装水，你会不会马上把它装到饮水机上？）,当然不是！要先看看饮水机上那个桶里还有没有水。 同理，小和尚也要先看看缸里还能不能容得下一桶水。,算法描述： 小和尚先到缸里看看能不能还装一桶水。相当于申请一个空位。 小和尚到去申请一个桶 拿到桶之后，小和尚到井里去打水（这个动作是互斥的） 打好水，小和尚把水倒到缸里（这个动作是互斥的）， 缸里又多了一桶水，相当于释放一个满位 小和尚把桶还回去。,小和尚先到缸里看看能不能还装一桶水。相当于申请一个空位。,小和尚到去申请一个桶,拿到桶之后，小和尚到井里去打水（这个动作是互斥的）,打好水，小和尚把水倒到缸里（这个动作是互斥的），,缸里又多了一桶水，相当于释放一个满位,小和尚把桶还回去。,第七章：死锁,进程竞争资源 有可能形成循环竞争 死锁,死锁需要处理 死锁分析 死锁的必要条件,死锁处理 预防、避免、检测+恢复、忽略,死锁预防: 破除必要条件 引入了不合理因素,死锁避免: 用银行家算法找安全序列 效率太低,死锁检测恢复: 银行家算法找死锁进程组并恢复 实现较难,死锁忽略: 就好像没有死锁 现在用的最多,第七章：死锁,什么是死锁？ 多个进程因循环等待资源而造成无法执行的现象 发生死锁的必要条件 Mutual exclusion: only one process at a time can use a resource Hold and wait(占有并等待): a process holding at least one resource is waiting to acquire additional resources held by other processes No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task Circular

《2016-2017第一学期操作系统复习提纲》由会员繁星分享，可在线阅读，更多相关《2016-2017第一学期操作系统复习提纲》请在金锄头文库上搜索。