操作系统教学复习讲义操作系统复习资料赖国勇一、教学内容、要求、重点和难点：第一章操作系统引论教学内容：操作系统的定义，特征，功能，分类及其发展简史等。

教学要求：1、了解：操作系统的发展简史，分时和实时操作系统的特点。

2、理解：操作系统的分类，分时概念。

3、掌握：操作系统的定义，特征和主要功能。

4、重点：操作系统的定义、特征、功能及其分类。

5、难点：操作系统的特征和主要功能。

第二章进程管理教学内容：进程、线程的基本概念，进程状态，进程控制，进程同步和互斥，进程通信等。

教学要求：1、了解：经典进程同步问题，进程通信方式，线程的类型、特征、创建和终止。

2、理解：引入进程的原因，进程控制块的作用，信号量的物理意义，用信号量实现互斥与同步（P、V操作），引入线程的原因。

3、掌握：进程的定义与特征，进程与程序的异同，进程基本状态变化，临界资源，临界区，同步机制应遵循的原则，信号量的含义。

4、重点：进程基本状态转换，用信号量实现互斥与同步（P、V操作），经典进程同步算法。

5、难点：进程基本状态转换，用信号量实现互斥与同步（P、V操作），经典进程同步算法。

第三章处理机管理教学内容：进程（作业）调度，死锁的概念，产生死锁的原因和必要条件，处理死锁的方法等。

教学要求：1、了解：高响应比优先调度算法，多级队列调度算法，多级反馈队列调度算法，预防死锁的方法。

2、理解：调度层次，FIFO调度算法，短进程（作业）优先调度算法，时间片轮转调度算法，优先权调度算法，银行家算法。

3、掌握：死锁的概念，产生死锁的原因和必要条件。

4、重点：进程（作业）调度算法，死锁的概念，银行家算法。

5、难点：进程（作业）调度算法，产生死锁的原因，银行家算法。

第四章存储管理教学内容：内存的各种管理方式，包括分区式、页式、段式、段页式存储管理方式，以及虚拟存储器的基本概念和请求调页、请求调段存储管理方式等内容。

教学要求：1、了解：引入重定位的原因；连续分配方式的类型；动态分区分配方式下，如何提高内存利用率，采用何种分配算法，如何管理空闲分区表或空闲分区链，如何进行分区的保护；内存管理方式变化的原因；分段系统比分页系统更容易实现信息共享和保护的原因。

2、理解：地址重定位，分页、分段、段页式存储管理模式；引入虚拟存储器的原因；虚拟存储器的特征和实现。

3、掌握：分页、分段系统的地址转换；实现虚拟存储器的页表机制，地址变化过程，页面置换算法。

4、重点：地址重定位，分页、分段存储分配和淘汰算法，虚拟存储器的实现。

5、难点：三种存储空间的划分，页面淘汰算法，虚拟存储技术。

第五章设备管理教学内容：I/O设备分类，4种I/O控制方式，I/O硬件组成，I/O软件分层思想，设备独立性，设备驱动程序，I/O中断处理程序，I/O处理过程，设备分配算法，缓冲技术，SPOOLING技术（虚拟设备）等。

教学要求：1、了解：I/O硬件组成，I/O软件分层思想，设备驱动程序、I/O中断处理程序，I/O处理过程。

2、理解：缓冲技术，DMA，通道技术，设备独立性。

3、掌握：I/O设备分类，4种I/O控制方式，SPOOLING技术（虚拟设备），设备分配算法。

4、重点：设备分类，SPOOLING技术（虚拟设备），设备独立性，设备分配算法。

5、难点：I/O软件分层思想，I/O处理过程，SPOOLING技术（虚拟设备）。

第六章文件管理教学内容：文件和文件系统的基本概念，文件的逻辑结构和物理结构，文件存取方式，文件目录及目录管理，文件共享及保护，文件存储空间管理，磁盘调度算法（FCFS、SSTF、SCAN）等。

教学要求：1、了解：文件系统的功能，文件共享，文件系统性能的改善。

2、理解：文件保护，磁盘调度的目的。

3、掌握：文件和文件系统的基本概念，文件的逻辑结构和物理结构，文件目录及目录管理，文件存储空间管理，磁盘调度算法（FCFS、SSTF、SCAN）。

4、重点：文件和文件系统的基本概念，文件的逻辑结构和物理结构，磁盘调度算法（FCFS、SSTF、SCAN）。

5、难点：文件目录及目录管理，文件存储空间管理，磁盘调度算法（FCFS、SSTF、SCAN）。

二、重点举例：第一章操作系统引论1.1、主要基本概念操作系统，分时操作系统，用户接口，命令接口，系统调用，图形接口。

第二章进程管理2.1、主要基本概念多道程序设计，并发性-并行性，进程，进程控制块，进程映像，内核，进程状态，进程同步和互斥，临界资源，临界区，可再入程序，管道，线程。

2.2、有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。

（1）说明A、B进程之间存在什么样的制约关系？（2）为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。

要求给出信号量的含义和初值。

解：(1)A、B两个进程之间存在互斥的制约关系。

因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。

（2）iMutex：用于互斥的信号量，初值为1。

（注：信号量名称可变，下面的伪代码相应变化。

）各进程代码如下：2.3、试画出下面5条语句的前趋图：S1：a=5-x；S2：b=a*x；S3：c=4*x；S4：d=b+c；S5：e=d+3。

参考答案：2.4、有两个程序，A程序按顺序使用CPU10秒，使用设备甲5秒，使用CPU5秒，使用设备乙10秒，最后使用CPU10秒。

B程序按顺序使用设备甲10秒，使用CPU10秒，使用设备乙5秒，使用CPU5秒，使用设备乙10秒。

在顺序环境下先执行A程序再执行B 程序，CPU的利用率是多少？（要求写出详细计算过程）参考答案：由题目所给条件可知，两个程序顺序执行，先执行程序A，再执行程序B。

A程序的执行时间为：10+5+5+10+10=40秒其中使用CPU时间为：10+5+10=25秒（3分）B程序的执行时间为：10+10+5+5+10=40秒其中使用CPU时间为：10+5=15秒（3分）两个程序的总执行时间为：40+40=80秒其中使用CPU时间为：15+25=40秒故CPU利用率为40／80=50%（3分）2.5、有一个系统有内存32KB，OS占用2KB，每一个用户进程占用10KB。

用户进程80%时间进行I/O，问CPU利用率是多少？如果增加30KB内存，CPU利用率又是多少？（要求写出详细计算过程）参考答案：（1）用户进程数为：（32-2）/10=3。

CPU利用率为：1-P n=1-(80%)3=48.8%。

（2）用户进程数为：（32+30-2）/10=6。

CPU利用率为：1-P n=1-(80%)6=73.79%。

注：CPU空闲等价于所有用户进程均在进行I/O。

第三章处理机管理3.1、主要基本概念分级调度，作业，作业控制块，作业调度，进程调度，抢占式进程调度，周转时间，平均周转时间，带权周转时间，平均带权周转时间，响应比，死锁，中断，中断源，中断请求，中断响应，中断屏蔽。

3.2、分别用先来先服务、短作业优先和响应比高者优先三种算法填写下表（时间单位：小时）。

（要求：写出必要的计算步骤）答：FCFSSJF响应比高者优先3.3、表1给出10个进程的相关信息：进程名称、进程状态(1就绪2等待3运行)、运行时间和优先级(0级最高)。

请采用短进程优先调度算法完成表2的进程调度执行流。

表1进程的相关信息参考答案：表2短进程优先调度执行流3.4、在银行家算法中，某时刻出现下述资源分配情况：试问：此时，如果进程P3提出请求：Request3（1，4，3，5）后，系统能否将资源分配给它？请详细描述算法过程。

解：①、Request3（1，4，3，5）≤Need3(1，8，8，6)②、Request3（1，4，3，5）≤Available(2，8，5，6)③、预分配资源，有：Available:=Available(2，8，5，6)-Request3（1，4，3，5）=(1，4，2，1);Allocation3():=Allocation3(2，3，5，2)+Request3（1，4，3，5）=(3，7，8，7);Need3():=Need3(1，8，8，6)-Request3（1，4，3，5）=(0，4，5，1)④、安全性检测：（注：安全序列不唯一。

）⑤、结论：存在安全序列：P0、P2、P1、P3、P4，故预分配资源后的状态是安全状态，可以将资源分配给进程P3。

第四章存储管理4.1、主要基本概念逻辑空间，物理空间，地址重定位（地址映射），内碎片，外碎片，内存紧缩(compaction)，可重定位装入(relocatableloading)，动态装入(dynamicrun-timeloading)，最先匹配法(first-fit)，下次匹配法(next-fit)，最佳匹配法(best-fit)，最坏匹配法(worst-fit)，局部性原理，虚存，联想存储器，OPT算法(OPT，optimal)，先进先出算法(FIFO)，LRU算法(LRU，LeastRecentlyUsed)，最不常用算法(LFU，LeastFrequentlyUsed)，最近未使用算法(NRU，NotRecentlyUsed轮转算法)，页面缓冲算法(pagebuffering)，抖动。

4.2、某系统主存容量为512KB，采用动态分区存储管理技术。

某时刻t主存中有三个空闲区，它们的首地址和大小分别是：空闲区1（30KB，100KB）、空闲区2（180KB，36KB）、空闲区3（260KB，60KB）1、画出该系统在时刻t的内存分布图；2、用首次适应算法和最佳适应算法画出时刻t的空闲区队列结构；解：1、2、4.3、某系统采用分页存储管理，设计如下：页面大小为4KB，允许用户虚地址空间最大为16页，允许系统物理内存最多为512个内存块。

试问该系统虚地址寄存器和物理地址寄存器的长度各是多少位？作必要的说明。

解：页面大小为4KB4KB=21212位允许用户虚地址空间最大为16页16=244位允许系统物理内存最多为512个内存块512=299位虚地址寄存器位数：12+4=16物理地址寄存器位数12+9=214.4、某虚拟存储器的用户编程空间共64KB，每页为1KB，内存为16KB。

假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：则逻辑地址0A5C（H）所对应的物理地址是什么？答：0A5C(H)：00001010010111002查表得：10001010拼接得：00101010010111002A5C(H)4.5、在一基本分页存储管理系统中，某进程的页表如表2所示。

已知页面大小为1024字节，试将逻辑地址1011，2148，3000，4000，5012（十进制）转化为相应的物理地址。