操作系统复习

Chap.1概述操作系统的定义、功能、特征操作系统是一种系统软件，是假设干程序模块所的集合； 它负责管理和控制计算机系统的硬件、软件资源的分配、调度和管理，使系统高效、平安地运行；为用户提供简单、直观、灵活的用户接口和使用环境，以方便用户对计算机系统的使用。 操作系统的主要功能：处理机管理、进程管理、存储管理、设备管理、文件管理、作业管理、用户接口操作系统的类型及特点，操作系统的构成及各模块功能三种用户接口处理机的2种工作状态及设置原因，系统调用的机制处理机的工作状态主要有内核态和用户态两种。设置这两种状态主要是为了保护操作系统内核不受用户程序的干扰和影响，使计算机系统具有稳定性、可靠性、平安性等特点。因为设置这两种工作状态后，用户编写的程序都运行在用户态，只能执行非特权指令，不能直接读写影响系统状态的CPU存放器、外部设备存放器的指令、不能直接访问和使用系统资源，而只能通过操作系统才能访问这些资源；而操作系统程序运行在核心态，可以执行CPU的任何指令，实施资源管理。术语：多道程序设计、并发、吞吐量、分时、实时硬件：构成计算机的各种有形的物理装置、部件或设备软件：与计算机进行数据处理有关的计算机程序、数据、过程、规那么、文档资料的总称多道程序设计：可以支持多道程序同时在内存中并发执行的计算机系统并发：多个活动同时处于执行状态，每个活动都已开始执行，却都尚未完成，这种执行方式称为并发吞吐量：计算机系统在单位时间内完成的作业数分时：操作系统将CPU执行时间划分成一个个时间片，轮流分配给各个进程使用，各个进程执行完一个时间片，排到等待队列，等待分配下一个时间片。时间片的大小使系统对每个进程的响应保持在用户能够忍耐的限度内实时：能够在规定的时间内对外部发生的事件给予响应和处理的计算机系统称为分时系统Chap.2进程管理术语：进程、程序、线程、进程互斥、进程同步、临界区、临界资源、原语进程组成，进程的三种根本状态及其转换〔习题第3题〕进程控制原语：创立、退出、等待、唤醒，这些原语完成的主要工作，进程控制块的主要内容〔列举几项〕线程的概念及与进程的关系，进程间通信的主要技术：管道、消息通信、共享内存用P、V操作及信号量的方法解决同步互斥问题〔作业11、12、13题〕11.设系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算结果。设每个用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用P、V操作写出这些进程使用打印机的算法。答：(1)三个进程间的关系是互斥关系。(2)进程间同步算法如下：设置一个互斥信号量mutex来协调各进程对打印机的使用，初值为1。用户进程1：…P(mutex);打印计算结果1；V(mutex);…用户进程2：…P(mutex);打印计算结果2；V(mutex);…用户进程3：…P(mutex);打印计算结果3；V(mutex);…12.(1)有错(2)有错13.(1)可用3个进程完成：Pa：从卡片机读信息，并逐一输入到缓冲区B1中Pb：从缓冲区B1读信息，加工处理后再搬到缓冲区B2中P3：从缓冲区B2读信息，并在打印机上印出(2)这些进程间为同步关系(3)同步算法：初值：empty1=empty2=1;full1=full2=0;Pa：While(1){从卡片机读数据；P(Empty1);将数据写入缓冲区B1；V(Full1);}Pb：While(1){P(Full1);从缓冲区B1读数据；V(Empty1)加工数据P(Empty2);将加工后的数据写缓冲区B2；V(Full2);}Pc：While(1){P(Full2);从缓冲区2读数据；V(Empty2);打印信息；}P、V原语的作用，信号量的含义C三级调度及功能、含义，作业调度与进程调度的关系，计算作业及进程周转时间，常用调度算法：FCFS、短作业优先、轮转法、响应比高优先，算法的特点(习题2、3、7、10)10.〔1〕RRRR123420468101214165FCFS182012342046810121416518201234204681012141651820非抢占优先级(2)作业名12345平均周转时间FCFS1010111115RR1915110非抢占式优先级101811814〔3〕作业名12345平均带权周转时间FCFS110115RR112非抢占式优先级118872.高级调度与低级调度的主要功能是什么?为什么要引入中级调度?3.处理机调度一般可分为哪三级?其中哪一级调度必不可少?为什么?7.作业调度与进程调度之间有什么差异?二者间如何协调工作?C1、术语：程序地址、物理地址、地址重定位、快表、碎片、内碎片、外碎片、存储抖动与工作集2、分区式内存管理的思想〔3种适应算法〕3、分页式内存管理〔学会手工查页表，计算物理地址〕，可从程序地址、物理地址中提取页号、页内偏移量；地址位数确实定〔习题7，8，14，15，16，17，19，21〕7.设一个逻辑地址空间有8页，每页1024个字节，映像到有32块的物理内存上。〔1〕逻辑地址需要用多少位表示？〔2〕物理地址需要用多少位表示？答：(1)log28+log21024=13位(2)log232+log21024=15位8.假设一个分页系统的页表存放在内存中：〔1〕如果一次内存访问需要花费1.2μs，那么存取一次数据至少要多少时间？〔2〕如果我们增加8个联想存储器，其命中率可达75%，那么有效内存访问时间是多少〔假设在联想存储器中找到该页表项，那么认为在联想存储器中查找时间为0〕？答：2×1.2us=2.4us××1.2+1.2=1.6us14.假定分页存储系统中有快表，多数活动页表项都可收在其中。如果页表还是放在内存中，内存访问时间是1μs，假设快表的命中率是85%，那么有效存取时间是多少？假设命中率降为50%，那么有效存取时间为多少？答：如果快表命中率为85%，那么有效存取时间为：(1-0.85)×1us+1us=1.15us(1-0.5)×1＋1＝1.5us17.什么时候会发生缺页？说明缺页出现时操作系统所做的事情。答：缺页时机：CPU发现要访问的内存页面不在内存时缺页时操作系统所作的工作：(1)转缺页中断效劳程序(2)取得缺页内存地址和页面所在辅存地址(3)在内存中找到一个空闲物理块(4)从辅存调入所需页面(5)填修改引起缺页指令内存地址所在页面在页表：物理块号为空闲物理块号，页面状态位为存在21.一个操作系统支持分页虚存，所用处理机的周期时间是1μs，页面大小是1000字，分页设备是磁鼓，它每分钟转3000圈，传输速率是每秒1000000字。由系统测得下述统计结果：〔1〕所执行的全部指令中有0.1%存取的页面不是当前的页面。〔2〕存取另外页面的指令，它们所存取的页面有80%已在内存。〔3〕当请求一个新页面时，所置换页面有50%在此期间修改正。设系统中只运行这一个程序，当磁鼓进行传送时，处理机空转等待。在上述条件下计算这个系统的有效指令时间〔执行一条指令所需的平均时间〕答：1个页面从外存传到内存的时间：1000÷10-6＝10-3s＝1ms存取当前页面中内存单元的时间：1us×99.9%≈10-6s存取不在当前页面中内存单元〔但单元已在内存〕的时间：1us×0.1%×80%≈10-9s存取不在当前页面中内存单元〔但单元不在内存，被置换页面不需写回〕的时间：1ms×0.1%×20%×50%=10-7s存取不在当前页面中内存单元〔但单元不在内存，被置换页面需写回〕的时间：2ms×0.1%×20%×50%=2×10-7s有效存取时间为:10-6s+10-9s+10-7s+2×10-7s=1.3us16.考虑下面存储访问序列，该程序有460字：10，11，104，170，73，309，185，245，246，434，458，364设页面大小是100字，请给出访问顺序。又设该程序根本可用内存是200字，采用FIFO置换算法，找出其缺页率。如果我们采用LRU置换算法，缺页率是多少？如果采用最优置换算法，其缺页率又是多少？19.考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块分别为1，2，3，4，5，6或7时，试问LRU、FIFO、OPT这三种置换算法的缺页各出现多少次？注意，所有内存块最初都是空的，所以但凡第一次用到的页面都产生一次缺页4、分段式内存管理〔习题24〕24.考虑如下段表：下述逻辑地址的物理地址是什么？〔1〕0，430；〔2〕1，10；〔3〕1，11；〔4〕2，500；〔5〕3，400；〔6〕4，112。答：219+430=6492300+10=23102300+11=2311∵500>100，∴发生地址越界1327＋400＝1727∵112>96，∴发生地址越界5页面替换〔淘汰算法〕〔OPT、LRU、FIFO、NUR〕，缺页中断处理过程，计算内存访问时间；Chap.5文件系统1．文件系统的功能2.术语：文件逻辑结构、文件的物理结构文件的逻辑组织有几种形式及特点，文件的物理组织形式主要有哪几种及优缺点3.什么是文件控制块?有哪些内容？它与文件有何关系？4．习题16、1716.有些文件系统中采用“文件控制块分解法”，即文件目录与其控制信息分开存放。假设目录文件存放在磁盘上，每个盘块为512字节。文件控制块占64字节，其中文件名占8字节。通常将文件控制块分解为两个局部，第一局部占10字节〔包括文件名和文件内部号〕，第二局部占56字节〔包括文件内部号和文件其他描述信息〕。〔1〕假设某一目录文件共有254个文件控制块，试分别给出采用分解法前和分解法后，查找该目录文件的某个文件控制块的平均访问磁盘次数。〔2〕一般情况，假设目录文件分解前占用n个盘块，分解后改用m个盘块存放文件名和文件内部号局部，请给出访问磁盘次数减少的条件。答：〔1〕分解前：目录大小：64×254＝16256字节查找目录文件的某个文件控制块的平均访问磁盘次数：分解后：目录大小：10×254＝2540查找文件目录的平均访盘次数：根据文件目录的文件控制块号〔索引节点号〕访存次数为1总共访盘次数：3＋1＝4次〔2〕分解前访盘次数：(1＋n)/2分解后访盘次数：(1+m)/2+1访问磁盘次数减少的条件：(1＋n)/2>(1+m)/2+1即：n>m+217.在UNIX系统中，试问：〔1〕有哪几种常用类型的文件？〔2〕试描述“翻开文件”和“关闭文件”系统调用的作用及主要实现过程。〔3〕假设盘块为1KB，每块可放256个地址，如何将以下文件的字节偏移量转换为物理地址？〔要求写出计算过程。〕①9000②18000③420000答：普通文件、目录文件、设备文件翻开文件的作用：实现系统对文件的检索、权限验证、读/写指针共享等操作，改善文件系统的性能，翻开文件的过程：1〕查找文件目录。如找到，那么把对应的文件控制块调入内存的活动文件控制块区。2〕检查翻开文件的合法性。如果flags与文件使用属性不符，那么不能翻开该文件，返回fd为-1，表示不成功；如果权限相符，那么建立内部控制结构〔如UNIX系统中的用户翻开文件表、系统翻开文件表和活动Ⅰ节点表等〕之间的通路联系，返回fd值关闭文件的作用：一个是防止对翻开文件的非法操作，起保护文件的作用；为了有效地使用系统资源。因为一个进程能够同时翻开的文件数是受限制的，当它不再使用某个翻开文件时，那么应关闭它，腾出其内部控制结构所占用的内存空间，关闭文件的过程：将尚存在于缓冲区的数据写入文件更新将内存文件控制块的内容写入磁盘文件控制块，更新文件的长度、修改日期等信息回收文件控制块所占用的内存(3)偏移量为9000的物理地址计算方法：物理块号的计算方法是：计算逻辑块号：因为9000/1024=8….808逻辑块号为82〕计算在物理块号由于8<10，所以可从直接块8处查到物理块号偏移量为1800的物理地址计算方法：1〕计算逻辑块号：因为18000/1024=17….592逻辑块号为172〕检查在几次间接指针下由于17－10<255，所以在一次间接指针的索引下3〕计算在一次间接索引块中的指针号17－10＝7在一次间接索引块的第7个指针元素中查到其物理块号偏移量为420000的物理地址计算方法：1〕计算逻辑块号：因为420000/1024=410….160逻辑块号为4102〕检查在几次间接指针下由于410－10－256＝144<2562，所以在二次间接指针的索引下3〕计算在二次间接索引块中的指针号144÷256＝0…144在二次间接索引块的第0个指针指向的索引块的第144个指针处查到物理块号C设备I/O控制方式(3种:直接I/O，中断控制、DMA控制)，术语：SPOOLING技术，通道、控制器、设备SPOOLing技术是在计算机控制下通过联机的外围设备同时操作，其实质是用多个磁盘文件来代替独占的输入输出设备，当进程申请使用独占设备时，就分配一个文件代替设备给其使用，可以防止因竞争独占设备而引起死锁或阻塞等待等问题。设备驱动程序的结构框架与功能、接口，磁盘调度〔FCFS、电梯调度〕〔习题11，12〕SPOOLing系统是怎样实现虚拟设备的？采用SPOOLing技术时，SPOOLing系统将进程需要处理的数据预先输入到磁盘文件中，当进程需要从输入设备输入信息时，就改从磁盘文件读取数据；进程需要输出信息时，先将输出信息写入一个磁盘文件，然后SPOOLing系统在后台将各个进程的输出信息从磁盘文件一一输出到外部设备。在这里，SPOOLing系统用磁盘文件代替设备分配给进程使用，而进程却感觉到自己分配到独占的外部设备，而这种设备不是真实的独占设备，而是一个磁盘文件，所以称为虚拟设备。12.假定一个动头盘有200道，编号从0～199。当前磁头正在143道上效劳，并且刚刚完成了125道的请求。如果请求队列的先后顺序是：86，147，91，177，94，150，102，175，130问：为完成上述请求，以下算法各自磁头移动的总量是多少？〔1〕FCFS；〔3〕电梯法；答：(1)(143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(175-102)+(175-130)=565(2)147-143+150-147+175-150+177-150+177-130+130-102+102-91+91-86=30+91=121C死锁的四个必要条件，死锁预防的方法：有序资源分配法、静态资源分配法、虚拟设备法死锁防止的根本思想：银行家算法死锁检测与恢复方法，死锁与饥饿，习题14、1514.设有三个进程p1、p2、p3，各按如下所示顺序执行程序代码：

进程p1进程p2进程p3↓↓↓p(s1)p(s3)p(s2)p(s2)p(s1)p(s3)v(s1)v(s3)v(s2)v(s2)v(s1)v(s3)↓↓↓在执行时能否产生死锁？如可能死锁，请说明在什么情况下会产生死锁？并给出一个防止死锁产生的修改方法。其中