操作系统总结2005

1、操作系统总结林树宽第一章 绪论操作系统的概念定义从科普、功能、用户、管理员、软件的观点理解操作系统操作系统发展历史手工、批处理、多道程序、分时、实时操作系统的基本类型批处理、分时、实时、个人计算机、网络、分布式、嵌入式第一章 绪论操作系统的功能处理机管理、存储管理、设备管理、文件管理、用户接口操作系统的特征并发、共享、虚拟、异步现代操作系统特征微内核、多线程、对称多处理、分布式、面向对象第二章 用户接口与作业管理程序的启动和结束程序的启动（命令方式、批处理方式、EXEC方式、硬件装入程序、自启程序）程序的结束（正常结束、异常结束）作业的基本概念作业（用户角度、系统角度）作业组织（作业、说明书、

2、控制语言）第二章 用户接口与作业管理作业的建立包括：作业的输入、作业控制块的建立作业输入方式联机输入、脱机输入、直接耦合、Spooling、网络作业控制块的建立用户接口程序级接口、操作级接口、图形用户接口系统调用（类、功能、实现过程）第三章 进程管理进程的概念程序的顺序执行和并发执行定义、条件、特点进程的定义、特性、与程序的区别进程的描述进程的组成（程序+数据+PCB）进程控制块PCB（作用、所包含信息）进程上下文（用户级、寄存器级、系统级）第三章 进程管理进程的描述PCB的组织方式（链表、索引表）进程的状态及转换核心态和用户态内存中3种基本状态（转换、条件）扩展：3状态、5状态、7状态（状态

3、、转换、条件、数据结构等）进程控制功能、原语、UNIX进程管理第三章 进程管理线程进程与线程的关系线程引入的作用线程的应用线程的状态及转换操作系统对线程的实现方式进程与线程的比较线程举例第三章 进程管理进程的互斥与同步进程间的关系（同步、互斥）互斥算法（临界资源的使用）信号量（信号量和P、V原语）经典进程同步问题（特别复杂的互斥与同步）管程（定义、例子、实现、结构、与进程的异同）第三章 进程管理进程间通信进程间通信类型消息缓冲共享存储区管道消息套接字第三章 进程管理死锁死锁的定义、现象、发生原因、发生条件死锁的预防、避免、死锁的检测与恢复解决死锁的综合方法第四章 处理机调度分级调度调度层次（与

4、状态转换、与时间周期、操作系统类型联系）作业与进程的关系（从调度的角度）作业调度作业调度功能作页调度中状态的转换目标与性能第四章 处理机调度进程调度进程调度的功能、时机、上下文切换、性能评价调度算法先来先服务（FCFS）短作业优先（SJF）最高响应比优先（HRR）时间片轮转（RR）多级队列第四章 处理机调度调度算法优先级静态、动态优先级线性优先级（SRR）多级反馈队列调度算法性能指标调度算法应用举例第四章 处理机调度实时调度实时调度任务分类实时调度特点实时调度算法静态表驱动静态优先级驱动的可剥夺调度动态分析调度无保障动态调度第四章 处理机调度多处理机调度与单处理机调度的区别对称式多处理系统的调

5、度非对称式多处理系统的调度成组调度专用处理机的调度第五章 存储管理存储管理的功能和目标虚拟存储器存储管理的功能地址变换内外存数据传输的控制内存的分配与回收内存信息的共享与保护第五章 存储管理分区存储管理原理固定分区动态分区分配、释放最先匹配下次匹配最佳匹配最坏匹配碎片及解决第五章 存储管理覆盖与交换原理、实现、特点页式和段式存储管理简单页式（原理、数据结构、地址变换、特点）简单段式（原理、数据结构、地址变换、特点）简单页式、段是管理的比较第五章 存储管理虚拟存储器原理虚拟页式与简单页式管理的关系缺页中断请求调入和预调入虚拟段式与简单段式的关系特点第五章 存储管理虚拟存储器段页式地址变换高速联想

6、寄存器调入、分配策略置换算法（最佳OPT、最近最久未使用LRU、先进先出FIFO、轮转、最不常用LFU）第六章 文件系统引言文件管理的目的基本概念（文件、目录、文件分类）文件系统的结构和功能元素文件的组织文件的组织逻辑结构物理结构第六章 文件系统文件目录内容结构别名的实现（硬链接、符号链接）文件和目录的使用文件的访问文件的控制目录管理伪文件第六章 文件系统文件共享和访问控制存取控制共享访问权限并发访问安全、可靠性第六章 文件系统文件存储空间管理存储设备空间分配磁盘空闲空间管理文件卷文件系统层次模型文件系统举例（DOS、Windows、UNIX）第七章 设备管理引言外设管理的重要性外设的类型和特

7、征外设管理的目的和功能外设管理结构I/O控制技术程序控制方式（查询、中断）DMA方式（工作原理、与中断的区别）通道方式（定义、原理、3种通道、）第七章 设备管理缓冲技术缓冲技术的作用和目的单方向缓冲I/OCPU （单缓冲、双缓冲、环形缓冲）缓冲池（3种队列、4种操作）设备分配数据结构分配原则分配方式假脱机第七章 设备管理设备控制设备控制过程设备控制实现方式I/O软件的组成磁盘设备管理访问时间调度策略（先进先出、优先级、后进先出、短查找时间优先、各种扫描算法）置换算法 生产者/消费者问题 (the producer/consumer problem)问题描述：若干进程通过有限的共享缓冲区交换数据

8、。其中，生产者进程不断写入，而消费者进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。共享缓冲区生产指针消费指针Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consumer N满空指针移动方向 设信号量： full是“满”数目，初值为0， empty是“空”数目，初值为N。实际上，full和 empty是同一个含义：full + empty = N mutex用于访问缓冲区时的互斥，初值是1 ProducerP(empty);P(mutex);/进入区 one unit - buffer;V(mutex)

9、;V(full);/退出区ConsumerP(full);P(mutex);/进入区 one unit n时因此，如果在设计系统时，能预测到进程并发执行和申请资源量的情况，只要每个进程所需资源的最大量不超过x,则可不必受任何的资源分配策略的限制，只要有空闲资源就可分配给申请者，系统不会有死锁现象。习题有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存共有8个存储块，问：逻辑地址至少应为多少位？内存空间多大？有8页的逻辑空间，每页有1024字节，它们被映射到32块的物理存储区中，则逻辑地址的有效位（ ）位，物理地址至少是（ ）位。习题一分页存储管理系统，逻辑地址长

10、度为16位，页面大小为2048字节，对应的页表如下，逻辑地址0A5CH和2F6AH经地址变换后的物理地址各是多少？习题物理地址8页表长度页表地址控制寄存器页号页面号021328有效地址21C41C4页式地址变换举例250010000111000100给出段号和段内地址，完成段式管理中的地址变换过程对于段号，段内地址形式，计算0,430 1,10 2,500 3,400的内存地址存取主存中的一条指令或数据至少要访问几次主存？段号段长度主存起始地址01234660142005809621933009012371952段表起始地址段表地址寄存器虚拟地址11C4段号段内地址段表段号始址01500134

11、0035C4内存第2段页表段地址寄存器段表长度 段表始址页号 其它 页面 1 12 2 19 3 21 4 8 5 10第0段页表页号 其它 页面 1 29 2段号 其它 页表长度 页表始址 0 5 1024 1 7 1029 2 9 1036段表某进程在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。堆栈第五章 存储管理第五章 存储管理某os采用可变分区分配方法管理，用户区主存512KB(0-511KB),自由区由空闲分区表管理。假设分配时采用分配自由区的低地址部分的方案，假设初始时全为空。对于下述申请次序：req(300KB),req(100KB),

12、release(300KB),req(150KB),req(30KB),req(40KB),req(60KB),release(30KB)1.采用首次适应法，用户区状态。写出空闲分区表。2.采用最佳适应法，用户区状态。写出空闲分区表。3.如再申请100KB，各有什么结果？编程实现 P203-8。设索引表数组为index, 每个物理块的块号用m个字节表示，物理块长为PBL, 文件结构为流式文件。给定字节偏移OFF,计算其所在的物理块地址。解：令 k = int(PBL/m)Int Off2PBN(Off) k = int(PBL/m);lbn = Off / PBL;if lbn10 then

13、return indexlbn;Else I = (lbn-10) div k; J = (lbn-10) mod k; 读文件的第 Index10+I 号块的内容 buf; return bufj; 40962284542031111150101367142891568241011109954952331452.33003333083274104289156757601331假定盘块的大小为1KB，每个盘块号占4个字节，文件索引节点中的磁盘地址明细表如图所示，如何将下列文件的字节偏移量转换为物理地址？1 9000 2 14000 3 350000解：（1） 字节偏移量为9000，此时逻辑块号

14、为：9000/10248块内偏移量为：900081024808因逻辑块号小于10，因此该块为直接块。其物理盘块号为367，该块中的第808字节即为文件的第9000字节（2） 字节偏移量为14000，此时逻辑块号为：14000/102413块内偏移量为：14000131024688因逻辑块号1013266，因此该块为一次间接块。 由图可知，一次间接的盘块号为428，从一次间接块中读出盘块号表，查得其物块号为952，该块中的第688字节即为文件的第14000字节。(3)字节偏移量为350000，此时逻辑块号为：350000/1024341块内偏移量为：3500003411024816因逻辑块号26

15、634165802，因此该块为二次间接块。由图可知，二次间接块的盘块号为9156。由于一个一次间接块中可容纳256个块号，341-10-25675 因此，字节偏移量350000在二次间接块的第0个一次间接块的第75个表项中，其盘块号为333，该块中的第816字节即为文件的第350000字节。某磁盘有40个磁道，磁头从一个磁道移至另一个磁道需要6ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均距离为13道，每块的旋转延迟时间及传输时间分别为100ms、25ms,问读取一个100块的文件需多少时间？一个树形结构的文件系统如图所示，框为目录，园为文件。可否进行下列操作在目录D中建立一个文件，命名

16、为A；将目录C改名为A若E和G分别为两个用户的目录用户E欲共享文件Q，应有什么条件，如何操作？在一段时间内，用户G主要使用文件S和T。为简便操作和提高速度，应如何处理？用户E欲对文件I加以保护，不许别人使用，能否实现？如何实现？根目录ABCDEFGHIJKLMNOPQRST作业P202 7.1, 7.2, 7.3, 7.7, 7.8, 7.10, 7.11, 7.12, 7.13一个存储与磁盘上的文件系统，其中的文件由大小512B的块组成。假定每一个文件有一个文件目录项，该目录项包含此文件的名字、文件长度以及第一块（或第一索引块）和最后一块的位置，而且该目录项位于内存。对于索引结构文件，该目录项指明第一索引块、该索引块又依次指向511个文件块且有一个指向下一个索引块的指针。针对连续、链接、索引结构的每一种，如果当前位于逻辑块10（即最后一个访问的块是逻辑块10）且希望访问逻辑块4，那么，必须分别从磁盘上读多少个物理块？ 若磁头的当前位置为100磁道，磁头正向磁道号增加的方向移动。现有一磁盘读写请求队列：23，376，205，132，19，61，190，398，29，4，18，40。分别采用先来先服务、最短寻道时间优先和扫描算法，平均寻道长度各是多少？ 下一磁道 移动磁道数 最少寻道优先 扫描 23