操作系统概述。
第二章进程管理
一、进程与线程。
二、处理机调度。
三、进程同步。
四、死锁。第三章内存管理。
第四章文件管理。
第五章设备管理。
操作系统》算法总结。
一、进程(作业)调度算法（p91）
先来先服务调度算法（fcfs）：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。
特点：利于长进程，而不利于短进程。
短进程（作业）优先调度算法(spf)：它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。
时间片轮转调度算法 ：系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把cpu分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。
优先权调度算法 ：它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并执行。
高响应比优先调度算法：它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。特点：
既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。
多级队列调度算法。
基本概念：作业周转时间（ti）＝完成时间－提交时间。
作业平均周转时间(t)＝周转时间/作业个数。
作业带权周转时间（wi）＝周转时间/运行时间。
响应比＝（等待时间＋运行时间）/运行时间。
二、存储器连续分配方式中分区分配算法(p123)
首次适应分配算法（ff）：对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。保留了高址部分的大空闲区。
循环首次适应算法：每次分配均从上次分配的位置之后开始查找。 使内存中的空闲区分布得更均匀。
最佳适应分配算法(bf)：是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。
最坏适应分配算法（wf）：将作业申请大小与内存中所有未分配区的大小进行比较，直到找到最大的或等于作业空间的区分配给作业。要求按空闲区大小从大到小的次序组成空闲区链。
优先使用大的自由空间，在进行分割后剩余空间还可以被使用。大的自由空间无法保留给需要大空间的作业。
三、页面置换算法(p149)
最佳置换算法（opt) ：选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。
先进先出置换算法（fifo）：选择最先进入内存的页面予以淘汰。
最近最久未使用算法（lru）：选择在最近一段时间内最久没有使用过的页，把它淘汰。
最少使用算法（lfu）：选择到当前时间为止被访问次数最少的页转换。
四、磁盘调度(p194)
先来先服务（fcfs）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置。
最短寻道时间优先（sstf）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题，但容易造成进程饥饿现象。
扫描算法（scan）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。
在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。
循环扫描算法（cscan）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。
当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。
五、信号量问题（解题思路）（p53）
分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。
对互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，通常只设置一个互斥信号量，且初值为1，代表一次只允许一个进程对临界资源访问。
对同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关，即同步关系涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。
在每个进程中用于实现互斥的pv操作必须成对出现；用于实现同步的pv操作也必须成对出现，但可以分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的p操作，则其顺序不能颠倒，必须先执行对同步信号量的p操作，再执行对互斥信号量的p操作，但v操作的顺序没有严格要求。
六、银行家算法（p108）
七、地址变换（内存管理一章）
1.操作系统的定义是什么？它的五大主要功能是什么？
操作系统是控制和管理计算机系统内各种硬件和软件资源、有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。
操作系统的主要功能包括：存储器管理，处理机管理，设备管理，文件管理以及用户接口管理。
1． 在操作系统中为什么要引入进程的概念？它与程序的区别和联系是怎样的？
答：由于多道程序设计的引入，各程序在执行过程中就出现了相互制约的心关系，程序的执行出现“走走。
停停”的新状态。这些都是在程序的动态过程中发生的。用程序这个静态的概念已不能如实地反映程序并。
发执行过程中的这些特征。为此，人们引入“进程”这一概念来描述程序动态执行过程的性质。
区别：①进程是动态的，程序是静态的；②进程有独立性，能并发执行，程序不。
能；③二者无一一对应关系；④进程异步运行，会相互制约；程序不具备此特征；
但进程与程序又有密切联系，进程不能脱离具体程序而虚设，程序规定了相应。
进程所要完成的动作。
2． 什么是进程的互斥与同步？
答：互斥：在逻辑上本来完全独立的若干进程，由于竞争同一个资源而产生的相互制约关系。
同步：进程间共同完成一项任务时直接发生相互作用的关系，在执行时间次序上必须遵循确定的规律。
3、一个进程进入临界区的调度原则是什么？
一进程进入临界区的调度原则是：
①如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。
②任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。
③进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。
④如果进程不能进入自己的临界区，则应让出cpu，避免进程出现“忙等”现象。
4、在操作系统中，p操作和v操作各自的动作是如何定义的？
p操作顺序执行下述两个动作：
①信号量的值减1，即s=s-1；
②如果s≥0，则该进程继续执行；
如果s＜0，则把该进程的状态置为阻塞态，把相应的pcb连入该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在s上执行v操作，把它释放出来为止）。
v操作顺序执行下述两个动作：
①s值加1，即s=s+1；
②如果s＞0，则该进程继续运行；
如果s≤0，则释放信号量队列上的第一个pcb（即信号量指针项所指向的pcb）所对应的进程（把阻塞态改为就绪态），执行v操作的进程继续运行。
5、作业调度和进程调度各自的主要功能是什么？
作业调度的主要功能是：
记录系统中各个作业的情况；
按照某种调度算法从后备作业队列中挑选作业；
为选中的作业分配内存和外设等资源；
为选中的作业建立相应的进程；
作业结束后进行善后处理工作。
进程调度的主要功能是：
保存当前运行进程的现场；
从就绪队列中挑选一个合适进程；
为选中的进程恢复现场。
1 解释下列概念：逻辑地址，物理地址，重定位。
答：逻辑地址：用户程序经编译之后的每个目标模块都以0 为基地址顺序编址，这种地址称为相对地址或。
逻辑地址。物理地址：内存中各物理存储单元的地址是从统一的基地址顺序编址，这种地址称为绝对地址或物理地址。
重定位：程序和数据转入内存时需对目标程序中的地址进行修改，这中把逻辑地址转变为内存的物理地址的过程为重定位。
2 什么是虚拟存储器，它有哪些特征。
答：是用户能作为可编址内存对待的存储空间，在这种计算机系统中虚地址被映象为实地址。简单地说，虚拟存储器是由操作系统提供的一个假想的特大存储器。
具有以下基本特征：
虚拟扩充：不是物理上，而是逻辑上扩充了内存容量；② 部分装入：每个作业不是全部一次性而是一部分的装入内存；③ 离散分配：不必占用连续的内存空间，而是“见缝插针”；
多次对换：所需的全部程序和数据要分成多次调入内存。
中断响应主要做的工作是： ①中止当前程序的执行；
②保存原程序的断点信息（主要是程序计数器pc和程序状态寄存器ps的内容）；
③转到相应的处理程序。
2、一般中断处理的主要步骤是：保存被中断程序的现场，分析中断原因，转入相应处理程序进行处理，恢复被中断程序现场（即中断返回）。
页号物理块号。
所对应的页号是： 2 （十进制）
查页表，得到物理块号是： 11 （十进制）
高级操作系统讲义
北京邮电大学计算机。学院 一上课基础。学习过本科操作系统课程。熟悉一种程序设计语言。二参考书 1 何炎祥等高级操作系统。科学出版社，1999年。2 何炎祥分布式操作系统。高等教育出版社，2005年。3 andrew s.tanenbaumdistributed operating systems.中...
高级操作系统讲义
1.网络操作系统 具有网络功能的操作系统，无严格定义。ms dos 1 网络通信能力。2 提供网络服务 网络上各节点的主机运行自身的操作系统，它不仅要保证本机的系统进程或用户进程能简便 有效地使用网络中各种资源 同时，也为网中其它用户使用本机资源提供服务。os 网络协议。2 分布式操作系统。每台计算...
高级操作系统讲义g
第十一章恢复与容错。11 1 具有容错能力的应用程序。基于事务型 基于进程控制型 11 2 事务恢复。事务的原子化特征要求 所有已提。交的事务对数据项的影响都。已反应到数据项中，所有未提交或。异常终止的事务对数据项的。影响应全部撤消。假定 服务器运行时，将所有的数。据项都保存在易失性存储器。中，并把...