《16年-操作系统复习提要课件.ppt》由会员分享，可在线阅读，更多相关《16年-操作系统复习提要课件.ppt（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、操作系统复习提要2016年题型（往年的）1.是非题（20分，每题2分）注意，错题要纠错！2.单项选择题（30分，每题3分）3.简答题（20分，每题5分）4.计算、设计题（30分）考试范围n前15章（第七版第七版）n重点113章1.4Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Jan 12,2005Part 1:Overview 1.Introduction 2.Operating-System Structures Part 2:Process Management 3.Processes 4.
2、Threads 5.CPU Scheduling 6.Process Synchronization 7.Deadlocks Part 3:Memory Management 8.Main Memory 9.Virtual Memory 1.5Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Jan 12,2005Part 4:Storage Management 10.File-System Interface 11.File-System Implementation 12.Mass-Storag
3、e Structure 13.I/O Systems 14.Protection15.Security1 绪论nComputer System StructureApplication programsOperating systemHardwareUsers1 绪论n存储结构n程序方式/中断/DMAnMultiprogramming/Timesharing(multitasking)1 绪论例题n名词辨析：分时（time-sharing）与多道程序（multi-programming）n核心态和用户态n判断：分时（time-sharing）是为了在操作系统中支持同时运行多个程序，从而提高CP
4、U的利用率而提出的。2 操作系统结构n从三个角度l用户角度用户角度、l程序员角度程序员角度l操作系统设计人员角度操作系统设计人员角度2 操作系统结构nOperating System ServiceslUser Operating System InterfacelSystem CallslSystem ProgramsnOperating System Design and ImplementationlOperating System StructurelVirtual MachineslOperating System GenerationlSystem Bootlmicrokernel
5、n进入操作系统的三种场景l1.中断 Interruptl2.异常 Exceptionl3.系统调用，System Call，Trap2 操作系统结构例题n名词辨析：微内核和模块化内核n在微内核结构的操作系统中，进程间通讯可以不在微内核内。l错。进程通讯是内核的核心功能，对微内核系错。进程通讯是内核的核心功能，对微内核系统，也在微内核内实现。统，也在微内核内实现。n以下对操作系统内核的运行方式的描述，正确的是：DlA.操作系统是一个以内核态运行的独立的进程；lB.操作系统内核运行时不能访问其它进程的地址空间；lC.只有在硬件中断发生时，操作系统内核才会运行；lD.操作系统内核可以以内核态在用户进
6、程上下文中运行。3 进程n进程概念n进程调度n进程操作n进程协作n进程间通信3 进程3 进程n数据结构：lPCBl调度用的queuen基本进程编程方法3 进程n长程调度长程调度（或作业调度）从作业池中选择进程，并将它们装入内存以执行。n短程调度短程调度（或CPU调度）从就绪可执行的进程中选择进程，并为其中之一分配CPU。n中程调度调度3 进程例题n名词辨析：长程调度（long-term scheduling）与中程调度（mid-term scheduling）4.线程n概述n多线程模型n若干线程问题4.线程n基本概念n特点n与进程的关系，比较4.线程例题n1）是非：线程都保存有各自的栈信息和C
7、PU状态（寄存器、指令计数器等）。n2）是非：在多进程多线程操作系统中，每个进程只需要维护一个栈（stack）；n3）名词辨析：进程和线程5.CPU调度n基本概念n调度准则/评估n几种调度算法lFCFS，lSJF（SRTF）l优先级调度lRR5.CPU调度例题是非题：在微内核结构的操作系统中，CPU调度必然在微内核内。名词辨析：最短作业优先调度和最短剩余时间优先调度6进程同步n概念n生产者-消费者问题n哲学家问题n信号量6进程同步例题n1）是非：单CPU环境下由于任何时刻只有一个进程（线程）能够运行，因此操作系统不需要实现同步与互斥支持。n2）选择：多CPU共享内存环境下，以下哪种实现临界区的
8、方法无效？lA.使用test_and_set机器指令实现“忙等”（busy waiting）lB.Peterson算法lC.关中断lD.使用swap机器指令实现“忙等”7死锁n系统模型n死锁特点l死锁的4个条件l资源分配图l死锁？饥饿？n死锁处理办法l死锁预防l死锁避免l死锁检测l死锁恢复n安全状态/死锁n银行家算法（矩阵）7死锁例题1）选择：以下哪种情况仍然可能会发生死锁？lA.资源都是可共享的；lB.每一种资源的数量都超过单个进程所需这类资源的最大值；lC.空闲资源能够满足任意一个进程还需要的资源需求；lD.每个进程必须一次申请、获得所需的所有资源7死锁例题2）辨析：死锁（deadlock
9、）与饥饿（starvation）3)在抢占式（preemptive）操作系统中，进程不会因为申请、使用资源发生死锁。4）不安全状态未必会导致死锁的发生；始终处于安全状态也不能保证死锁一定不会发生。5）问答：7死锁例题.（10分）现有以下实现有界缓存（bounded buffer）问题的伪代码1.semaphore mutex=1;2.semaphore full=0;3.semaphore empty=3;/buffer中允许3个item4.producer()5./produce an item6.wait(empty);7.wait(mutex);8./add it to the buff
10、er9.signal(mutex);10.signal(full);11.12.consumer()13.wait(mutex);14.wait(full);15./remove one from buffer16.signal(mutex);17.signal(empty);18./consume the removed item19.a)请问该代码是否会引起死锁？（3分）b)如果不会引起死锁，请证明死锁（证明死锁的四个必要条件中有一个不成立）；如果可能引起死锁，请画出资源分配图（信号量作为资源），指出代码发生死锁的原因，并进行改正。（7分）8主存管理n背景n交换n连续内存分配n分页n分段n
11、带有分页的分段8主存管理例题n是非：段表由各个进程自己管理，进程可在用户态对段表进行更新。n名词辨析：段式内存管理和页式内存管理9虚存管理n背景n按需（demanding）页面调度n进程创建n页面置换l算法：FIFO（Beladys）；LRU，LFU，MFUn帧分配n系统颠簸（Thrashing）9虚存管理例题n1）是非：微内核操作系统中，CPU调度和虚存管理功能必须在微内核中实现；n2）是非：在虚存管理时，采用先进先出（FIFO）页面替换策略，必然会发生Belady异常（即分配页框越多，缺页率反而越高）；n3）选择：当发生抖动（或称为颠簸，thrashing）时，以下哪种现象不会出现？lA.
12、处于等待（waiting）状态的进程数增多lB.CPU利用率增高lC.磁盘I/O增多lD.长程调度（long-term scheduling）允许更多的进程进入就绪（ready）状态9虚存管理例题n4）计算：采用按需调页（demand paging），现有3个页框，分别存储着页面号2,3,4三个页面。已知接下来的页面访问顺序为1,2,3,4,1,2,5,1,2,3,4,5。使用时钟算法（clock algorithm）作为页面替换算法。（10分）l请计算会发生的缺页次数（假设初始时在页框内的页面的引用位（reference bit）都是1，2/3/4三个页面按序存放，初始时指针指向页面2）？（
13、7分）l请写出这一访问序列所对应的工作集。（3分）n试简述缺页中断处理的详细过程（从发生缺页中断开始至页面调度结束，进程继续执行为止），并指明每一个步骤中，处理所处的上下文环境和模式。10文件系统接口n文件概念n访问方法n目录结构n文件系统安装n文件共享n保护10文件系统接口例题n1）简答：请简述在一个支持有向无环图目录结构的文件系统中，删除一个普通文件（非目录文件）时操作系统需要执行哪些操作。（5分）11文件系统实现n文件系统结构n文件系统实现lFCBn目录实现n分配方法l连续分配l链接分配l索引分配n空闲空间管理n恢复11文件系统实现例题n1）是非：在目录文件中，必须保存文件名和文件控制块
14、信息。n2）选择：以下哪种数据结构必须存放在持久存储介质上？lA.进程控制块lB.页表lC.文件控制块lD.打开文件列表11文件系统实现例题n3）以下对于目录及其实现的描述，错误的是：lA.目录是文件的集合，是一种逻辑概念，通常用文件实现lB.目录文件中存放的就是目录中文件的文件控制块（file control block）lC.目录中可以有子目录，形成嵌套结构lD.目录中的“.”和“.”通常分别代表该目录本身和其父目录11文件系统实现例题4）（15）假设有文件系统使用i-node如图所示。其中一个磁盘块大小为4KB，一个磁盘块指针大小为32位（4B），直接块（direct block）大小为
15、2KB，其它索引块大小和一个磁盘块一样大小。假设有一个4MB大小的文件，其i-node已在内存中（direct block也在内存中），文件的其它部分都在磁盘上，不考虑缓存。请问：a)访问其第一个字节，第1K个字节，第1M个字节，第2M个字节，第3M个字节，和最后一个字节分别需要访问几个磁盘块（2x5=10）？b)该文件系统最大能支持多大的文件(5)？11文件系统实现例题n5）计算、设计题（15）n设有一个文件系统，文件数据块（磁盘块）大小为4KB，每个文件数据块指针大小为4B（32位）。该文件系统需要支持以下操作：nint read(int fd,int pos,int len,int*bu
16、f);nint write(int fd,int pos,int len,int*buf);nint insert(int fd,int pos,int len,int*buf);n其中，fd为文件句柄（handle），pos为读写插入位置，以上三个函数会按照pos x 4KB为实际位置读写插入buf中len x 4KB的数据，即每次数据操作必然读写插入一个磁盘块大小的数据，且插入位置的偏移量正好是4KB的整数倍。na)请分别详细描述如何在连续磁盘块分配、链接分配、索引分配情况下实现插入操作（3x3）；nb)不考虑缓存，不考虑连续分配时空间不够的情况，请详细分析以上三种实现每次读写插入操作需要
17、访问多少次磁盘（2x3）；nc)请问以上哪种方式最不适合这一场景？哪种方式最适合这一场景？为什么？（2x2）nd)假设在FCB中，还剩余256B的空间，请参考UNIX文件系统的i-node结构，设计一个多级的包含直接块和间接索引的块管理方式，并分析该方式与以上三种方式相比的优缺点。（3）n现有如下代码int pos10;/*和用户交互，为posi赋值*/int fd=open(“/home/us001/test.txt”,O_WRONLY);/*以只写方式打开文件*/for(int i=0;i 10;i+)fseek(fd,posi,SEEK_CUR);/*文件指针定位到当前位置+posi*/
18、fprint(fd,“pos%dn”,i);/*写文件*/close(fd);/*关闭文件*/na）请解释第2、第4、第5、第6行代码执行时，操作系统分别需要进行哪些操作？（8分）nb）请问第4、第5行代码的写操作属于顺序访问还是随机访问？（2分）nc）请问对于这种访问方式，采用何种文件块组织方式较合适？为什么？（5分）。11文件系统实现例题12 海量存储n磁盘调度n多级存储12 海量存储例题n1）.以下哪个操作不是磁盘格式化进行的？lA.划分扇区和磁道lB.建立空闲FCB列表lC.建立空闲块列表lD.设定根目录文件n2）辨析：二级存储（secondary storage）与三级存储（tert
19、iary storage）n3）简答:请简述磁盘访问效率由哪些部分决定，并分析如何提高文件系统中顺序访问文件的效率。（5）12 海量存储例题n已知磁盘访问队列98,183,37,122,14,124,65,67（标号为柱面号），当前磁头位置为53。（10分）la)请写出一种最优的磁头移动序列，并计算磁头移动距离。（5分）lb)请问这一序列和哪种调度算法的结果是一致的？（2分）lc)请问这种调度算法能否保证在任意情况下是最优的？为什么？（3分）12 海量存储例题n（10）设现有磁头访问请求队列98，83，137，122，14，124，67，65，当前磁头位置为50。请：la)分别计算最短寻道时间
20、优先（SSTF）算法和SCAN算法所需的磁头移动距离（3x2）lb)请比较以上两种方法的优缺点（4）。12 海量存储例题n假设磁盘磁头当前在磁道100，磁道请求队列为：:l1.请计算FIFO（先进先出）策略下的寻道总长度(包括过程)（4分）l2.请计算SSTF（最近寻道时间优先）策略下的寻道总长度(包括过程)（4分）l3.请问：SSTF是否一定是总寻道长度最短的，为什么？（2分）13 I/O系统nPolling/Interrupt/DMA13 I/O系统1）是非：对于键盘这样的低速字符设备，采用DMA方式进行数据交换是不合适的；2)是非：块设备一定是快速设备，且一定既能支持顺序访问又能支持随机
21、访问。3）辨析：程序控制输入输出（programmed I/O）与直接内存访问（DMA）n选择：以下哪种设备常用假脱机方式（spooling）进行IO操作：la.磁带lb.磁盘lc.网络ld.打印机n2.试简述采用DMA方式进行I/O操作的整个过程，并说明DMA方式适合哪种类型的I/O操作，并解释原因。14/15.Protection&Securityn.在一个教师与学生共享使用的Linux系统中，已知任课教师wnqian有目录：/home/wnqian/os/exam/，用于存放试题和答案。该目录的所有者是wnqian，所属的组中包括wnqian和历年的助教（每年不同）。该目录下还有/hom
22、e/wnqian/os/exam/2013，/home/wnqian/os/exam/2014等目录，分别存放各年的试题。助教应只能访问担任助教当年的目录。请问，对于/home/wnqian/os/exam/目录，以下哪种权限设置是最合理的，符合最小权限原则？lA.rwxrwx-；lB.rwxr-xr-x；lC.rwx-x-；lD.rw-；复习n概念间的比较l各类辨析n数据结构的比较l如 PCB/TCB/FCBn算法间的比较l相似性，联系，区别，不同场合lTrade-off流程图nPagingnInterrupt，Exception，DMA，综合题-算法n进程调度（FCFS，RR，SRTF）n页替换（FIFO，Optimal，LRU，LRU-A.，LFU/MFU）n磁盘调度（FCFS，SSTF，SCAN，C-SCAN，LOOK，C-LOOK）综合题-程序n信号量l生产者，消费者，。综合题-数据结构nInodenPCB、TCB、FCB