操作系统每章总结 第1篇

、线程的引入

、进程的两个基本属性

、引入线程的好处

、线程的属性

这就先总结到第二章，后面的内容在下一篇博文中。

总结重点：

第一章 操作系统引论 1.操作系统的作用 2.操作系统的发展过程 （包括解决的问题和优缺点） 3.操作系统的基本特征 第二章 进程的描述与控制 1.进程的定义和特征 2.进程和程序的比较 3.进程的三种基本状态及转换 是什么及其作用 5.进程间的两种制约关系 6.临界资源 临界区的概念 7.同步机制应遵循的规则 8.信号量机制-整型信号量 （Ps:书上的经典同步问题不会考你） 9.进程通信的类型 10.线程

操作系统每章总结 第2篇

只会阻塞引起阻塞的线程

线程的四个应用场景

l 前后台运算：即有UI和后台运算的程序，你总不希望后台数据运算时前面的UI界面就对用户没响应了吧?所以这里应该分开线程，后台启动单独的线程运算，界面在不同的线程了所有能时时相应用户的操作(哪怕只是提示计算中)。

l 异步计算：比如应对电路故障的实时备份功能，通过线程无论是在代码量上还是开销上都要比你编写定时调度的功能要高效。

l 速度敏感的运算：多线程的计算机可以在计算一组数据的同时读入下一组数据(当然弄几个进程干这事儿也可以，但是开销明显更大)。

l 模块化的程序架构：对于包含多个活动或者多个源头和目标的输入输出程序，也许更容易使用多线程来设计和实现(就是每个线程干一摊子事儿，大家数据在一起自己取谁也别干涉谁)。

l 另外的比如Java程序，每个程序就是一个JVM的进程，至于这里面你起多少线程操作系统是不关心的。

并发性

竞争条件

竞争条件发生在多进程或者多线程同时修改同一个数据项的情况下，这时数据的最终结果依赖于各个进程(线程)执行的顺序(也就是结果不是唯一确定的了，比如同时修改变量b，P1执行b = 1， P2执行b = 2结果有竞争失败者决定)。

临界区

类似于b的这种资源称为临界资源(critical resource)，程序中操作临界资源的程序段称为临界区(critical section)。就是说事儿肯定是出在临界区里的。

互斥(multual exclusion)

多个进程尝试进入同一个不可共享的资源的时候进程间需要是互斥的。这个不可共享的资源就是上面说的临界资源，进入的程序段即临界区。

互斥的要求：

l 互斥是系统强制的。

l 在临界区外挂起的进程不能够干涉其他进程。

l 请求临界资源的进程不能被无限期的延迟，即不能有死锁。

l 当没有进程处于临界区时，对临界资源的请求必须立即分配。

l 互斥不能建立在任何关于进程相对速度或执行顺序的假设上。

l 一个进程在临界区的时间应该是有限的。

进程交互

进程交互分三种情况：

l 进程间互不相认：比如多道程序设计，这些进程间存在共享资源但是彼此不知道，操作系统需要保证进程间的安全。

l 进程间简介知道彼此：进程不知道彼此的ID，但是知道存在共享资源，进程间表现为合作。

l 进程间直接知道彼此：进程知道彼此的ID，存在共享资源，进程间表现为合作。

并发性的硬件支持

Interrupt disable

进程声明自己的某一段程序是不可被中断的，这招只在单个处理器的情况下有用，因为多个处理器则存在进程并行运行。

Compare & swap instruction

由CPU提供的原子指令，用测试值(test value)检查内存单元(_ord)，如果相等就用给定的值设置内存单元(newvalue)，最终返回替换前的内存单元值。

使用：内存单元的初始值是0，多个进程执行用0去测试并替换为1的指令，只有获取到0的返回值的进程获得了进入临界区的资格，在离开临界区前进程要重置内存单元值为0。

Exchange Instruction

有CPU提供的原子指令，用内存区域的值和一个寄存器的值交换。也就是只有换到寄存器初始值(换完以后检查内存区域的值)的那个进程可以进入临界区并在离开时重置寄存器。

硬件支持存在的弊端：

1，采用的是忙等待(busy waiting)的方式，CPU一直在进程间切换，效率低。

2，可能发生饥饿：总有一个二活人品差，抢不到而又没有任何办法干预。

3，可能存在死锁：P1获得了临界资源但是同时P1被P2中断了(P2优先级高)，P2却无法获得被P1占有的临界资源，P1同时得不到CPU的计算周期。

并发性的软件支持

信号量(semaphore)

用于进程间传递信号的一个整数值。提供了三种操作初始化、信号加和信号减。只有0和1的信号量称为二元信号量。减操作semwait用于阻塞一个进程(当信号量为0的时候阻塞)，加操作semsignal用于激活被阻塞的进程。、

生产者与消费者

生产者负责生产资源并加入到指定的缓存中，加入过程如果缓存已满要阻塞生产者;消费者负责消费资源，如果缓存已空要避免消费者消费不存在的资源。

const int bufferSize = n1;

semaphore s = 1, n = 0, e = bufferSize;

producer

while(true)

produce();

semwait(e);

semwait(s);//s信号量用于控制每次只有一个进入critical section

append();

semsignal(s);

semsignal(n);

consumer

while(true)

semwait(n);

semwait(s);

taken();

semsignal(s);

semsignal(e);

consume();

监听者(管程)

信号量的麻烦在于分布在程序的各个地方，一处错误就可能导致并发同步的错误。监听者提供了更完善的机制用于并发同步。参考监听者子图。

监听者包括局部数据、条件变量和若干过程和等待队列等，局部变量是被监听者机制保存的处于外部进程不能访问或影响局部变量。

进程可以通过调用监听者的某一过程来进入监听者，但是同一时间只有一个进程处于监听者中(其它的在外面排队，也就是进入队列)。

监听者包含若干个条件变量，可以视条件变量为指向某一等待队列的指针。

监听者提供了cwait和csignal方法，调用cwait(c)将在条件变量c上阻塞当前进程并使监听者可用，当前进程加入到条件变量c的等待队列，调用csignal(c)将激活条件变量c的等待队列上的进程并重新尝试获得监听者(一般是激活一个，也有可能是signalAll<对于条件变量不明确的情况激活所有的进程，使正确的进程运行其它的进程则因为未获得条件变量再次阻塞>)。

除此监听者还提供了紧急队列(也可能没有)，对于进入到过程中的但最后没有调用csignal的进程(它可能是在过程中阻塞了或者怎么完蛋了)有两种处理方式：1，踢出去重新回到进入队列和大家竞争。2，考虑到这个进程已经执行了过程的部分逻辑有必要把它加入到紧急队列中，监听者会在空闲后重新激活紧急队列中的进程。

注意与信号量不同的是，在调用csignal(c)的时候如果条件变量c的等待队列上没有任何进程，那这个动作将不产生任何效果也不会累计下去。

生产者/消费者问题中Monitor的实现：

monitor

int size, nextin, nextout

appand(node)

if(nextin == size) cwait(notFull);

buffer[nextin] = node;

nextin = (nextin + 1) % size;

count++;

csignal(notEmpty);

take(char x)

if(count == 0)cwait(notEmpty);

x = buffer[nextout];

nextout = (next + 1) % size;

count--;

csignal(notFull);

消息传递

消息传递是进程间通信的另一个手段，其一个优点是除了进程间还可以适应分布式、共享的系统。消息传递最典型的两个原语：send(source, message)和receive(destination, message)，其中可以是阻塞send、阻塞receive的也可以是不阻塞send阻塞receive的或者两者都不阻塞。

消息的组成包括消息头和消息体，消息头包括目的地Id、消息格式、源Id、消息长度等信息，消息体则是消息内容。

寻址：消息可以是一对一的也可以是一对多、多对一或者多对多。

消息的排队原则：默认情况下消息的接收应该是先进先出的对了，除此还要考虑紧急程度的优先级设置。

生产者消费者的消息实现：

producer

while(true)

receive(mayproduce, pmsg);

pmsg = produce();

send(mayconsume, pmsg);

consumer

while(true)

receive(mayconsume, pmsg);

pmsg = consume();

send(mayproduce, pmsg);

main()

create_messagebox(mayconsume);

create_messagebox(mayproduce);

for(int i = 0; i < N; i++) send(mayproduce, null);

parbegin(producer, consumer);

读者和写者问题

读者/写者问题不同于生产者消费者，一个资源可以同时有多个读者但是同一时间只能有一个写者。写者和读者不能同时获取资源。

可以存在两种类型的锁

1，读者优先：文件未被占用或存在读者时可以继续加入读者。

2，写者优先：文件被读者占用后一旦出现写者后续不能加入读者。

可以基于信号量或者消息发送来解决，个人觉得能通过信号量的一定能通过Monitor解决。

死锁和饥饿

死锁：两个或多个进程间都需要几个临界资源，但是各个进程持有其中一个临界资源而尝试获取另外的临界资源。

饥饿：可能是优先级或者调度算法本身的原因导致某个进程始终无法获取到临界资源(竞争激烈)，虽然不存在死锁但是这个进程做不了任何事情。

联合进程图(Join Process Diagram)

资源类型

可重用资源：比如I/O设备、文件等等，它们在同一时间只可以被一个进程使用，但是使用之后并不会因此而销毁。

可消耗资源：比如存在I/O中的一段流数据，一旦被使用就不在存在了，但是可以被制造出来。除此以外还有信号、中断、消息等等。

死锁形成的条件

1.互斥

2.不存在抢占

3.持有和等待

4.形成了等待的环路

1~3：有可能产生死锁但是并没死锁。只有4发生的时候死锁才是真的产生了。

死锁预防(protection)

死锁的预防不同于死锁避免，死锁预防的目的在于干涉死锁形成的条件1~4使得死锁无法形成，往往导致的成本很高并且不很实用。

1.互斥：无法消除，有并发就有互斥。

2.抢占：这个可以做到有几种途径：a，当进程资源请求被拒绝时强制其释放已占有的资源，在后续需要时可以重新申请。b，当进程申请已被其它进程占有的资源时系统允许其抢占。这两种方法都有一个大前提就是资源状态必须是容易保存和恢复的，否则就啥都没了。

3.持有和等待：可以让进程一次申请所有需要的资源，这将不会出现持有并等待的情况。但是这是在进程能够预测它所使用的所有资源的前提下才成立的，并且效率很低。进程会在没有用到资源前先占用资源。

4.形成环路：可以将各个资源类型定义成线性顺序，只有占有了前面资源的进程才能进一步申请后续资源——同样效率是硬伤。

死锁避免(avoidance)

死锁的避免是运行时发现进程的启动或者请求会导致死锁，从而采取不启动或阻塞的措施。

1，如果进程的请求导致死锁，则不启动进程。这个比较难做到，因为它要求进程提前预知自己要用到的所有资源。

2，如果进程请求的资源可能导致死锁，则不分配资源给进程(塞你一会儿)。这个是更可行的办法。

方法2的运算如下：

OS中始终维护下列数据：

1，矩阵C(claim)为各个进程声明的需要用到资源。

2，矩阵A(allocation)现在以分配给各个进程的情况。

3，向量R当前系统拥有的资源

当一个进程申请起源是，OS假设分配资源给它并更下上面的数据，之后查看是否会产生死锁：

1，C - A得到矩阵P描述每个进程顺利完成时要得到的剩余资源。

2，向量R - A中各个资源的合计值等到向量V当前可用的资源。

3，如果向量V中的资源不足以使P中任何一个进程得到满足，那么即将发生死锁，这时候拒绝进程的请求。

4，如果存在可完成的进程，把进程的资源加入到向量V中重复3步骤直到所有进程可完成或出现死锁。

矩阵C

矩阵A

矩阵C - A

系统资源向量R

当前可用资源向量V

由于当前可用资源可以满足P2，所以可以加回P2的资源并重复步骤3。

死锁的检测和恢复

死锁的检测其实和上面的步骤是一样的需要两个矩阵：Q——进程请求资源(是排除已分配资源后)、A——进程已经分配的资源，一个向量V当前可用资源。

1，标记A中所有资源占用都为0的进程行。

2，初始化临时的向量W是它等于V。

3，查找Q中为标记的i行，其中i行小于向量W。如果找不到i则种植算法。

4，如果找到i行，将i标记并把A中i行数据加回到W中。重复步骤3。

当算法结束时如果存在为标记的行则已经发生死锁。

死锁的恢复有点野蛮：

1，取消所有死锁的进程。这是现代操作系统最常用的办法。

2，回滚进程到之前一个检查点(checkpoint)，重新启动。操作系统需要具备回滚和恢复的能力，这样仍然有死锁的风险，但是并发的不确定性能保证死锁最终不再发生。

3，连续取消死锁进程直到最终不再出现死锁。取消进程的顺序依赖某种成本的原则，取消后重新调用死锁检测，如果仍然存在死锁继续取消。

4，连续抢占资源直到死锁不再发生。同样基于某些成本选择的方法，资源抢占后重新调用死锁检测，一个被抢占资源的进程需要回滚到获取该资源前的检查点。

3、4步骤可以考虑一下原则：

l 目前消耗处理器时间最少。

l 目前为止产生的输出最少

l 预计剩下的时间最长。

l 目前位置分配的资源总量最少。

l 优先级最低。

哲学家就餐问题

一个屋子里有5个哲学家他们一天中除了睡觉只做思考和吃饭两件事情，屋子里有一个桌子提供了哲学家喜欢的意大利粉，但是由于哲学家每天至思考导致身体退化他们需要用两个叉子才能够进食，他们坐下后会先拿起左手的叉子，然后拿起右手的叉子，之后进食吃饱以后放下两把叉子。桌子周围一共提供了五把椅子在每个椅子间提供了一把叉子，请为哲学家设计吃饭的算法。

如果5个哲学家同时饿了那么每个人都会拿到左手的叉子而死锁。

哲学家吃饭问题可以通过信号量或者Monitor来处理。

内存管理

内存管理的目的：

l 重定位

l 保护

l 共享

l 逻辑组织

l 物理组织

内存分区

固定分区

分为大小相等和大小不等的固定分区策略。内存预先被划分为固定大小的内存区域，进程可以安装到大于等于自身的内存区域中。

存在内部碎片、大于最大内存区域的进程无法加载、内存利用不充分。

动态分区

动态的根据进程大小进行内存区域划分，从而使得每个进程可以装进和自己大小相等的内存区域。

存在外部碎片、需要定时压缩外部碎片否则内存被割裂成很多小区域。

伙伴系统

采用二分法把内存等大小的两块区域(2^1)，再将其中一块区域继续二分为2^2层，逐次分配下去直到进程所需的大小M在2^(N+1) < M <2^(N)时保存进程。在进程释放后再进行合并为较大的块。

伙伴系统弥补了固定分区和动态分区的缺点，但是分页和分段提供了更高级的分区方式。

重定位

因为进程换入换出后不一定仍加载到原来的内存位置，所以在程序中不可能确切的写出实际的内存地址，而是通过偏移量来描述位置。

内存被划分成许多等大小的帧，程序被划分成与帧大小相等的若干页。进程加载时需要将所有页加载到内存中不一定连续的帧中。系统维护了页表描述程序占用的页和空闲页表。

分页没有外部碎片，由于每个帧很小只有最后一帧是可能存在内部碎片的，所以只会出现很小的内部碎片。

页的大小将直接影响性能。页太小时：页数多开始时页面错误率很高，一段时间后由于页面都已加入趋于平稳，但是过小的页将使每次读写的区块很小。页增大时：每一页所包含的单元和相关单元越来越远，局部性被削弱错误率增加，不断增大时错误率又减小当页大小等于进程P时不再有也错误，整个进程都在内存中。由此导致的问题是主存中能存入的进程越来越少。

操作系统为每个进程维护一个页表描述进程中页与帧的对应，逻辑地址分为了页号和偏移量两部分。一般情况下页表的大小位页的大小，页表中每条记录称为页表实体(PTE，page table entry)。

页表可以是多级页表，受制于页大小的限制页表的大小不能大于一页(也不可能把巨大的页表存放在主存中)，因此页表做多级处理，根页表始终在主存中，当次级页表不在主存中时从辅存加载对应的页表进主存。

根据页表寻址

l 根据虚拟地址的页号查找根页表对应的帧号。

l 帧号+次级页号合成次级页表的地址找到对应的主存中帧号(如果存在的话)。

l 帧号+偏移量获得实地址。

l 如果页表中页表实体的标志位标志当前页没有加载到主存中，发生页错误中断交给操作系统加载，进程被中断处于Block状态。

反向页表(Inverter Page Table)

这是另一个可行的从虚地址获取实地址的方案。

针对虚拟内存中页表大小和虚拟地址范围成比例的缺点(太大了)，反向页表大小是固定的取决于主存中实际帧数。反响列表对虚拟地址的页号做Hash运算取得Hash值，每一个Hash值对应一个数据项。数据项中记录了进程ID和主存中帧号，通过帧号和偏移量就可以得到实地址了。由于多个虚拟地址可能映射到同一个Hash值，反向页表需要维持链结构(当前项连接到同值的其它项)，所以进程ID和Hash值共同决定了虚拟地址对应的数据项。

反响的含义是指使用帧号而不是页号来索引页表项。

转移后备缓冲器(TLB，Translation Lookside Buffer)

这是(虚拟内存地址转换)硬件设备的一部分，相当于高速缓存。因为正常情况下虚拟地址的访问要经过两次主存——一次查找帧地址，一次取数据，转移后备缓冲器缓存了页号和帧地址的对应关系，只有在未命中的情况下采取访问页表查找帧号。

简单分段类似于简单分页，是将主存换分成大小不等的若干段，一个进程可以存储在不连续的段中。分段的大小受限于分段最大长度。分段对程序员是可见的，它具有处理不断增长的数据结构的能力以及支持共享和保护的能力。操作系统为每个进程维护一个段表。

分段存在外部碎片。

段页结合

段页结构是将程序划分成段，每段保存在主存中对应的段里，在主存中段是由等大小的多个页组成，当段最后不足一个页时占用一个页。

段页结合的方式结合了分段和分页的长处。在分段系统中由于每段有长度属性，避免了程序不经意的越界访问。进程间存在共享时多个进程可能持有同一个段的引用，页结构也可以是实现类似的结构。

虚拟内存

当程序太大超过主存时就需要虚拟内存了，另外多道程序设计希望同时有尽可能多的进程加载到内存中，由于局部性的原理进程不需要全部加载进内存而是加载频繁是用的区块(称为驻留集)，进程的其它部分保存着专门的辅存区域中。这个机制称为虚拟内存。

系统抖动

当系统换出一块内存区域后紧接着它有需要调用它，当这种情况频繁发生的时候就导致了系统抖动。

读取策略

分为请求式分页和预约式分页。请求式分页是指当确实需要访问到某页时才把它加载进主存，预约式分页是利用局部性原理将可能访问到的当前请求的后续页面加载到主存中。显然预约式分页更可取，但是会造成一定的浪费，在首次加载页面和发生页错误时适合采取预约式分页。

放置策略

替换策略

替换策略是在加载新的页时主存已满需要替换出页时决定那些页将被替换的算法。

最佳(OPT，Optimal)

最少发生页错误的算法，是优先替换那些距离访问最远的页面，需要预知页的请求顺序，本身是不可能实现的，但是可以作为参考比对其它策略。

最近最少使用

实际上是性能上最接近最佳的，但是仍难以实现。一种实现方式是给每个页定义最近访问的时间标签，并在每次访问后更新标签，即使通过硬件支持成本和开销仍然很高。

先进先出

依赖的理论是一个在很久以前加载的页现在很可能已经不再访问了，但是结果往往并非如此，这种策略很容易实现。

环形的结构，通过指针指示当前所在位置，每个页有一个使用为在访问后标记其值为1。在需要替换时移动指针找到第一个标记位等于0的页，指针每移动过一个页就将这个页的使用位清零。这样如果没有使用位为0的页，当移动一圈以后最初的位置就会被清理。

一个改进是增加修改位——这也是必须的因为被修改的内存必然要写入辅存。现在有两个指示位(访问u，修改m)，算法如下：

1，查找u=0,m=0的页，如果存在替换。这一步不清零访问位。

2，如果1失败，查找u=0，m=1的页，并且这个过程中把访问位清零。

3，如果2失败，重复1，必要时重复2。

这样好处是尽量不去替换发生数据修改的页，少了写回辅存的动作。

页缓冲

也是避免系统抖动的一个策略，在主存中划分出一定的缓存，用于保存那些被替换出的页，根据局部性原理他们很可能近期会被访问到。这个缓存是一个先入先出的队列，一般页面被访问则直接从缓存中取回，如果一直没有被访问则最终会被挤出缓存。

驻留集管理(Resident Set)

虚拟内存中并非一个进程的所有部分都加载到主存中，程序运行过程中常驻内存的部分称为驻留集。

驻留集的讨论包括两部分：驻留集分配(大小)和替换范围。其中驻留集不可变的情况下替换算法已经在替换侧路讨论过了，驻留集可变的情况下将有所不同。

固定分配，局部范围：每个进程的驻留集大小固定，每个进程一旦有一个页换进来就要有一个页换出去。需要根据程序的类型、优先级等预先分配固定的大小，一旦过小则会保持较高的也错误率，如果较大则会占用资源，系统运行缓慢。

动态分配，全局范围：根据进程运行的状态调整驻留集的大小，如果页错误率较高就适当加大驻留集，如果进程错误率一直保持较低水平说明程序的驻留集足够大，可以适当削减一些也不会危及程序。全局范围则可在所有进程间选择要被替换出的页，难点在于没办法确定该从哪里换出页(即很可能换了不该换的)，解决办法是页缓冲。

动态分配，局部范围：动态分配的效果同上，同时限制在进程自己的范围内换出页。在这个策略中要求对增加或减少驻留集大小进行评估并且要预估将来进程的情况，因此比简单全局替换要复杂得多，但会提供更好的性能。

驻留集的替换策略

工作集策略(Working Set)

W(t，r)是关于t和r的函数，t是单位时间，r是窗口的宽度定义最近的r个单位时间中用到的页的集合。即始终有W(t, r+1) 包含 W(t, r)。

工作集如下工作：

1，监视每个进程的工作集。

2，周期性的从一个进程的驻留集中移除那些不在工作集中的页，可以使用LRU策略。

3，只有当一个进程的工作集在主存时才可以执行该进程(也就是驻留集包含了工作集)。

首先工作集是有效的，它利用率局部性原理，并未该原理设计了一个可以减少页错误的内存管理策略。遗憾的是工作集存在很多问题：

1，现在不总是代表未来。

2，开销太大，实现监视每个进程不现实。

3，r最优值未知。

但是工作集提供了参考，以下方案都是基于工作集思想的：

页错误频率(Page Fault Frequency，PFF)

主存中每个页都有一个使用位(和时钟的一样作用)，操作系统记录每个进程上一次页错误的时间戳，如果发生了页错误查看两次页错误的时间间隔如果小于阈值F，则加入新的页(扩大驻留集)，否则清除所有使用位为0的页，并把当前驻留集的页使用位清零(缩小驻留集)。一个改进时加入使用两个阈值——一个是驻留集增加的最高阈值，一个是驻留集减小的最低阈值(指频率)。

页面错误频率是工作集的一个折衷，使用页缓冲则可以达到相当好的效率。但是一个缺点是如果要转移到新的局部性，会导致暂时的驻留集猛增。转移到新的局部性是指，进程运行一段时间会切换到不同的逻辑指令部分，这时候局部性发生偏移，之前的驻留集不再需要。

采样间隔可变工作集(Variable-interval Simple Working Set，VSWS)

针对PFF在内存高峰是来不及淘汰就得驻留集而导致进程频繁换入换出等开销(频率不够快)，采用动态的采样率以期望尽快淘汰不需要的页。

采用三个参数：L采样区间最长宽度、M采样区间最短快读、Q采样区间允许发生的页错误数。VSWS和PFF一样使用了页的使用位，不同之处在于频率的调整：

1，如果采样时间超过了最长时间L，挂起进程并扫描使用位。

2，未达到最长时间，但是页错误数超过了Q：

，如果采样间隔超过了M则挂起进程并扫描使用位。

，如果采样间隔没有超过M，则一直等待采样时间到达M进行扫描。

清除策略

清除策略目的在于确定何时讲一个被修改的页写回辅存，分为请求式清除和预约式清除。

请求式清除采取动作的时间比较慢，影响性能。

预约式清除把需要修改的页在需要用到它们的页帧之前批量的写回辅存。但是预约式清除写回的页在替换策略确定移除它之前仍有驻留在主存中，这期间可能再次发生修改导致清除无意义。

改进办法是使用页缓冲，分为两个表存储替换策略淘汰的页。一个表寸修改的页，一个表存未修改的页，修改表中的页被批量的写回辅存，然后移动到未修改表中，未修改的表准备被挤出或者拿回。

加载控制

加载控制是关注多道程序设计的控制，系统中多道程序的数量称为多道程序设计级。当多道程序数量过少时系统会比较空闲，过多时则会导致较高的页错误率和抖动。

一个方案称为L=S，L是页错误间隔的平均时间，S是页错误的平均处理时间，实验表明当两者接近时处理器使用率达到最大。

另一个方案是50%方案，即始终报纸分页设备的使用率保持在50%左右，此时的处理器使用率也是最大。

另外策略是监视时钟(Clock)替换策略的环形缓存区指针移动速度，当移动速度低于某个阈值时可能是以下两种情况之一：

1，很少发生页错误，指针很少移动。

2，未被使用的驻留页太多，指针不需要移动太多就可以找到可清除页。

这两种情况都表明进程的驻留集分配太大，可以增加多道程序设计级。另外还可以包括一个高阈值，如果指针移动速度超过这个阈值，则表明多道程序设计级太高，导致频繁的页错误，则要挂起进程以减少多道程序设计级。挂起进程的策略可以是：

l 最低优先级

l 正在发生页错误的进程(Faulting process)：原因是该进程很肯能驻留集还没有形成，因此暂停它的代价很低。

l 最后被激活的进程：同样很可能有最小的驻留集。

l 拥有最小驻留集的进程：重新装入的代价最小，但是不利于驻留集较小的程序。

l 最大的进程：释放较大的空间，不用很快又去取活其它的进程。

l 具有最大剩余执行窗口的进程：类似于最少剩余时间策略，把已运行时间最短的挂起。

处理器调度

单处理器调度

调度类型

长程调度：决定是否将任务加入到待执行的进程池中。

中程调度：决定进程的部分或全部加入到内存中(从Suspended到Ready)。

短程调度：决定哪一个就绪的进程将被执行。

I/O调度：决定哪一个挂起的I/O请求将被可用的I/O设备执行。

处理器调度关注的是短程调度。

调度准则

面向用户

响应时间：从任务提交到开始有响应输出的时间，一般的当处理器开始处理任务时即开始有输出。

周转时间：从任务提交到任务完成的时间。

最后期限：当可以指定最后期限时，操作系统降低其它目标，是满足最后期限的作业数目的百分比达到最高。

可预测性：无论系统当前负载情况是繁重还是空闲，一个给定工作完成的总时间和总代价应该是相等的。

面向系统

吞吐量：单位时间内完成的进程数。

处理器利用率：处理器处于忙状态的时间百分比。对于昂贵的共享系统来说这是一个重要的准则，对于个人系统则显得不那么重要。

公平性：没有来自用户或其它系统的指导时操作系统应该公平的对待所有进程，没有一个进程会处于饥饿状态。

强制优先级：当指定了优先级后调度策略应优先响应高优先级的进程。

平衡资源：调度策略应是系统的所有资源保持忙碌的状态，较少使用紧缺系统资源的进程应该得到照顾。

调度算法

归一化周转时间：它是指进程周转时间与服务时间的比率，最小值是.该值表示进程的相对延迟，典型的进程的执行时间越长可容忍的延迟越长。

先来先服务(FCFS)：没有优先级和抢占，所有进程按照加入的顺序执行。这样的调度偏向于执行时间长的进程。FCFS策略本身对操作系统不是很有吸引力，但是它经常和优先级系统配合使用产生有价值的调度策略。

轮转(Round Robin)：对处理器资源进行时间分片，依次分配相同的时间资源给每个就绪的进程。轮转的时间片最好略大于一次典型交互的时间，当时间片足够大时退化为FCFS策略。

轮转增加了处理时钟中断、进程切换和分配函数的开销，因此时间片不应该过短。该策略对短执行时间的进程有所改善，但是一个问题是进程分为I/O密集型和处理器密集型，由于I/O密集型进程经常被I/O中断，所以轮转策略倾向于处理器密集型。

一个改善的策略是虚拟轮转法(Virtual Round Robin)，它增加了一个I/O队列，当一个进程被I/O阻塞后它加入到I/O队列，在就绪后它I/O队列有高于就绪队列的优先级，该进程后续的执行时间与已执行时间的和不会超过时间片。

最短进程优先(SPN，shortest process Next)：具有最短执行时间的进程有更高的优先级，它依赖于系统估计进程的执行时间，在批处理系统中任务加入时程序员给出任务的估计时间，如果任务执行时间远远超过给出的估计时间它将被废弃。在生产环境中有大量的重复任务，系统将监控每次任务执行的时间以估计执行时间，最简单的公式是s=(各次时间和)/n，一个避免每次求和的优化是s=S(n-1) + Tn/n，上述公式每次执行的权值是相同的，典型情况下我们希望最近的执行情况有更大的权值Sn+1 = aTn + (1-a)Sn。

最少剩余时间(SRT，shortest remain time)：是SPN的改进版本增加了抢占机制，在不断有短进程加入的情况下长进程可能处于饥饿状态。

最高相应比优先(HRRN，Highest Response Rapid Next)：使用公式(w+s)/s，其中w是等待时间，s是服务时间。操作系统始终选择具有最高相应比的进程，同样需要估计和记录进程的服务时间。该策略非常具有吸引力，当偏向短进程时，长进程由于得不到处理响应比不断增加。

反馈：不想SPN、STR、HRRN策略那样需要估计时间，反馈策略倾向于短进程，它具备多个队列Q1~Qn，当进程加入时处于Q1队列中，采用FCFS的顺序服务队列中的每个进程，当进程允许超过时间阈值时中断并加入到下一级队列中Q2，依次类推。Q1具有最高的优先级，只有Q1中不存在进程是才执行下一级的队列。这样可能导致的问题是过长的队列可能加入到Qn队列后处于饥饿状态，因此要见识进程的等待时间，如果超过一定长度则重新调入到Q1中。

多处理器调度

多处理器调度关注的类型

无约束并行性：进程之间没有显示的同步，每个进程都是一个单独的程序。无约束并行可能达到每个用户都像是使用单独的计算机或工作站。

粗粒度和非常粗粒度并行性：进程之间存在这同步，但是在一个非常粗浅的级别上，这种情况可以简单的处理成一组运行在多道程序单处理器的并发进程，在多处理器系统是允许的软件进行很少或者不进行改动就可以支持。

中等粒度并行性：应用程序可以被进程中一组线程有效的实现，这种情况下程序员需要显示的指定潜在的同步性，应用程序之间需要高程度的合作与交互。

细粒度并行性：代表着比线程间更加复杂的同步情况，迄今为止仍是特殊的未被分割的领域。

进程调度

集中调度or对等调度：

集中调度即调度中存在主处理器，所有的任务分发由主处理器来完成，这种情况下主处理器可能成为系统的瓶颈。

单处理器使用多道程序设计：

与单处理器性能的不同：

多个处理器系统中由于一个长进程在单个处理器上执行时，其它的进程可以分配到另外的处理器上因此复杂的调度策略不再显得非常重要，调度策略的开销可能成为性能损失。FCFS策略变得可接受。

线程调度

负载分配：

提供全局队列，每个处理器只要空闲就从队列中取任务执行。

优点是：负载均匀的分配给处理器，不存在空闲的处理器;不需要集中调度;可以使用单处理的任何一种调度方案进行分配。

缺点是：中心队列占居了必须互斥访问的存储器区域，因此多处理器同时查找时会成为瓶颈，当只有几十个处理器时不是大问题，但是上百个处理器时就会出现瓶颈。被抢占的线程可能在不同的处理器上执行，如果每个处理器都配有高速缓存的话那么命中率将非常低。如果进程的所有线程都视为在公共线程池中那么进程的线程可能不会同时被处理，当线程间存在高度合作时则出现瓶颈。

组调度：

一组相关的线程基于一对一的原则，同时分配到一组处理器上去。

优点：如果紧密相关的进程并行执行那么同步阻塞可能减少，从进程推广到线程组调度把一个进程所有的线程视为相关的;调度开销可能减少，因为进程内线程间可能相关如果一个线程在高速允许，而它以来的线程没有运行就会出现阻塞和调度。

缺点：组调度同一时间调度一个进程中相关线程，某些进程的特性可能至适应单线程允许将会出现其它处理器空闲的情况，解决办法是把若干单线程的进程视为一组允许。

专用处理器分配：

每个程序执行时被分配给一组处理器，处理器个数与进程的线程数相等，当进程执行完后处理器返回到处理器池中等待处理其它任务。这个策略看似是极端浪费的，它会等到进程运行结束才将处理器分配给其它的进程使用，而一旦一个线程被I/O阻塞执行它的处理器将空闲。

采用这个策略的原因：

1，高度并行的系统中有数十或者数百个处理，每个处理器只占系统总代价的一小部分，处理器利用率不再是衡量有效性或性能的重要因素。

2，一个程序的生命周期里避免进程切换会加快程序运行。

动态调度：

执行期间进程的线程数可以改变。某些应用程序可能提供了语言和系统工具允许动态的改变进程中的线程数目。提供了一种操作系统和应用程序共同进行调度决策的方法。

当一个作业请求一个或多个处理器时：

1，如果有空闲处理器分配满足它们需求。

2，否则如果作业新到达，从当前已分配多个处理器的作业中分出一个处理器给它。

3，如果都不满足那么作业处于未完成状态直到有空闲的处理器或者改作业废除它的请求。

4，当释放一个或多个处理器时为这些处理器扫描当前未满足的请求队列，给每个没有分配处理器的作业分配一个处理器，如果还有空闲处理器再次扫描队列，按照FCFS原则分配处理器。

I/O设备调度

I/O功能的逻辑结构

逻辑I/O：逻辑I/O层将I/O设备视为逻辑资源，不关心底层的细节。逻辑I/O代表用户进程管理的一般I/O功能，允许它们根据设备标识符以及诸如打开、关闭、读取等操作与设备打交道。

设备I/O：请求的操作和数据(缓冲的数据、记录等)被转换成适当的I/O指令序列、通道命令和控制器指令。可以使用缓存技术以提高使用率。

调度和控制：关于I/O操作的排队、调度和控制发生在这一层，可以在这一次处理中断，收集和报告I/O状态。这一层是与I/O设备真正打交道的软件层。

I/O缓冲

I/O设备划分：

I/O设备分为面向块(block oriented和面向流(stream oriented)的设备，面向块的设备将信息保存在块中，通常是固定大小的，传输过程中一次传送一块。面向流的设备以字节流的方式传输数据。

单缓冲：系统在发送I/O指令后给I/O设备分配一块位于主存中的缓冲区，传输数据被放在缓冲区中，当传输完成时立即尝试读取下一块。根据局部性原理有理由期望下一块被读取，这种机制称为超前读。

双缓冲：单缓冲时I/O设备必须等待读取缓冲区中数据被完全读出才能再次写入，双缓冲设置两块缓存区域以平滑这种趋势。设C为进程处理块的时间，T位读取块的时间，我们可以粗略估计块的执行时间位max(C，T)，当C>=T是进程将不需要等待I/O，当C

循环缓冲：当爆发性的执行大量的I/O操作时，则仅有双缓冲就不够了，这种情况下使用多于两个缓冲的方案来缓解，这种缓冲区域自身被当成循环区域使用。

需要指出的是缓存是一种技术旨在平缓I/O请求峰值的，当进程需求的I/O平均值大于I/O传输速度是再多的缓冲也不能解决问题。

磁盘调度

磁盘性能参数

寻道时间：机械臂移动到数据所在轨道的时间，现在典型磁盘的寻道时间Ts=10ms。

旋转延迟：磁盘旋转到要读取的数据位置的延迟，一般取平均时间即1/2r，其中r表示转速。

传送时间：磁头读取数据所花费的时间b/(Nr)，b表示要读取的字节数，N表示磁道上总字节数，r表示转速。

磁盘调度策略

先进先出

先来的请求先服务，由于数据的请求式随机的，会导致较高的寻址时间，效率差。

优先级

优先级是高优先级的请求先服务，一般是为了满足操作系统的特定目的，并没有改善磁盘性能的能力。

后进先出(LIFO)

令人惊讶的是这种选取最近请求的策略有许多优点。把设备资源提供给最近(使用系统)的用户时会导致磁头臂在一个顺序文件中移动时移动的很少，甚至不移动。利用这种局部性原理可以提高吞吐量减少队列长度，只要一个作业积极的使用磁盘它就能尽快得到处理。

当然如果有大量的请求就会导致最先的请求饿死。

最短服务时间优先(SSTF)

总是选择磁头臂移动最少的请求响应，对于移动距离相等的请求可以随机移动向一边。同样如果一个进程大量的请求临近的数据会导致其它请求饥饿。

SCAN：

SCAN要求磁头臂向一个方向移动，移动过程中响应在当前磁道的请求。当磁头臂到达最外(内)层磁道时，再反向扫描。这种算法并没有很好的利用局部性原理(对最近横跨过的区域不公平，不如SSTF和LIFO好)，由于两侧的数据被快速的扫描了两次因此它偏向于外围数据(局部性原理)。

C-SCAN

限定在一个方向扫描，当达到最后一个磁道时，磁头臂返回到相反方向的磁道末端重新开始扫描。

N-step-SCAN和FSCAN

为了克服进程的粘滞性，在SCAN和C-SCAN中一个或多个进程对一个磁道有较高的访问速度时可能会垄断这个磁道一段时间。N-step-SCAN设置若干个N个请求的队列，每次扫描只响应一个队列里的请求，当开始扫描时新的请求需要加入到下一个队列中。

RAID

RAID是一组磁盘系统把它们看为一个单个的逻辑驱动器。

数据分布在物理驱动器阵列中

使用冗余的磁盘容量保存奇偶检验信息，保障一个磁盘失败时，数据具有可恢复性。

磁盘高速缓冲

高速缓存是系统从主存中划分的一块区域，利用了局部性原理保存最近访问的数据块，用于提高更好的磁盘性能。

替换算法

LRU：最少访问，将缓冲区设置为一个栈，当一个块被访问后加入到栈中，如果再次得当访问则把该块从当前位置移动到栈顶，随着块的加入那些不被访问的将会挤出栈中。

LFU：最小频率访问，对缓存中的块增加计数特性，每次被访问到时计数加1。当访问辅存时，把计数最小的块移除，加入最近的块。由于局部性的问题，一个块可能短时间内多次访问使得计次很高，但是这之后并不意味着还会再次访问它，所以LFU并不是一个好的算法。

基于频率的替换算法：克服LFU的确定，在LRU的栈模型中划分出位于栈顶的若干帧为新区，当块位于新区是重复访问不增加访问次数。

文件管理

文件系统软件结构

基本文件系统：计算机与外部环境的接口，该层处理磁盘、磁带的交互数据。

基本I/O管理程序：负责所有文件I/O的初始和终止。

逻辑I/O：是用户和应用程序能够访问到记录。

访问方法层(堆、顺序文件、索引顺序文件、索引、散列)：距离用户和应用程序最近的层，在应用程序与保存数据的设备之间提供了标准接口。

文件结构：

域(Field)：基本的数据单元，一个域包含一个值，如雇员名字、日期等。

记录(Record)：一组相关域的集合，可以看做应用程序的一个单元。

文件(File)：一组相关记录的集合，它被用户或应用程序看做一个实体，并可以通过名字访问。

数据库(DB)：一组相关数据的集合，它的本质特征是数据之间存在着明确的关系，可供不同的应用程序使用。

文件组织和访问

最简单的文件系统。数据按它们到达的顺序被组织，通过特定的分隔符或特定的域指明。每个域应该是自描述的，数据之间不一定存在联系或相同的格式。

当数据在处理器采集并存储时或者当数据难以存储时会用到堆。只能穷举搜索，对大多数应用都不适用。

顺序文件：

文件具有固定的格式，所有的记录都有相同的格式，具有相同数目、长度固定的域按照顺序组成。每条记录第一个域称为关键域，唯一标识了这条记录。

交互的表现较差，需要顺序的搜索。一种情况下顺序文件按照顺序存储在磁盘上，在发生文件修改时需要移动数据，可能的处理方式是把数据存在临时堆上，定期的将数据批量写回顺序文件。另一种情况文件可能采用链式存储，该方法带来一些方便，但是是以额外的处理和开销为代价的。

索引顺序文件

弥补了顺序文件检索的问题。检索文件可以是简单的顺序文件，每条记录包括两个值一个关键域和指向文件的指针。简单的检索可以是一级的，也可以由多级检索。查找文件时找到相等的域或者关键域值之前最大的域。

索引文件

顺序文件和索引顺序文件只能是顺序检索或对关键域检索，索引文件对感兴趣的域提供了索引，索引文件本身可以是顺序的。索引文件分为完全索引和部分索引，差别在于被索引的域是全部域还仅仅是感兴趣的域。

索引文件一般只提供索引访问的方式，不再支持顺序访问，因此记录的组织也不必是顺序的，应用程序只能通过指针访问。

直接文件或散列文件

直接文件或散列文件开发直接访问磁盘中任何一个地址一致的块的能力，要求每条记录中都有一个关键域，但这里不存在顺序的概念。

记录组块

磁盘中数据保存在块中，块越大每次传输的数据越多，效率越高。当时大的块要求操作系统提供更大或者复杂的缓存，并且由于局部性的关系大块中的数据可能是应用程序不需要的造成浪费。

固定组块

使用固定长度的记录，并且若干条完整记录保存到一个块中，每个块末尾可能有未使用的空间称为内部碎片。

可变长度跨越式组块

块的长度可变，记录可以跨越块保存，如果一个块的末尾空间不足一条记录时，剩下的数据可以保存在下一个块中，通过后继指针指明。造成了更复杂的处理，并且当读取跨越块的数据时需要读取两次，消除了内部碎片。

可变长度非跨越式组块

和上面相同，但是记录不可以跨越块保存。

二级存储管理

文件分配

预分配：文件请求时声明需要的空间，一次性分配。

动态分配：根据文件的增长每次分配一定的空间，或者一块。

分配方法：

连续分配：始终给文件分配连续的空间。这种分配方式对于顺序文件非常高效，并且可以简单的检索到需要的文件块。但是会产生外部碎片，并且需要实时运行压缩程序以消除外部碎片。

链式分配：文件不需要顺序保存，每块尾部通过指针指向下一块数据，文件分配表中同样只要保存一个表项。

链式分配的一个后果是局部性不再被利用，如果要顺序的读取一个文件时需要一连串访问磁盘的不同部分，这对系统的影响很严重。一些系统周期性的的对文件进行合并。

索引分配：每个文件在文件分配表中有一个一级索引，分配给文件的每个分区在索引中都有一个表项，典型的文件索引在物理上并不保存在文件分配表上，而是保存在独立的一个块上，文件分配表中该文件索引指向这个块。

可以消除外部碎片，按大小可变的分区分配可以提高局部性，任何情况下(大小可变分区、按块保存)都需要不时的对文件进行合并。使用大小可变的分区情况下合并可以减少文件索引。索引分配支持顺序和直接读取数据，是最普遍的一种文件分配形式。

空闲空间管理

位表：使用一个向量，向量的每一位代表一块磁盘，0表示空闲，1表示使用。优点是容易找到一块或一组连续的空间，问题是需要穷举来找到合适大小的区域，当磁盘剩余很少空间时这个问题尤为严重，因此需要设置特殊的数据结构辅助查找。如位表可以在逻辑上划分为不同的区域，建立区域汇总表统计每个区域的使用情况，查找空闲位时可以先找到合适的区域在查找位表中这部分区域的使用情况。

位表需要加载在主存中，一个位表所需要的存储总量为【(磁盘大小)/(8_件系统块大小)】(计算的是占用的字节数)，因此一个16GB的磁盘，块大小位512字节时位表占用4MB，如果每次去数据都从硬盘加载4MB的位表的话这个速度是难以忍受的。

链式空闲区

空闲表可以使用指向每个空闲区的指针和他们的长度值被连接在一起，因为空闲表只需要一个指向第一个空闲区的指针，因此这种情况下空闲表的大小是可以忽略的。

这种分配法适合所有的文件分配方法，如果按块分配可以移动位于头部的指针，如果是按区域分配则可以顺序的找到合适的区域并更新指针。

存在的问题：1，使用一段时间磁盘会出现很多碎片，许多区变成只有一块大小。2，写时需要先读取该块以发现下一块的指针，如果进程请求大量的单个块这个效率是很差的，同意删除的时候也会导致很慢。

索引是把空闲空间看做文件，使用之前介绍的索引表的方式记录。基于效率的原因，索引适合使用在大小可变的分区分配的情况下。

空闲块列表

每个空闲块都有一个顺序号，把顺序号保存在磁盘的一个保留区中。根据磁盘的大小，存储一个块号需要24位或32位。这是一种令人满意的方法，空闲块列表部分保存在主存里：

1，磁盘空闲块列表占用空间小于磁盘空间的1%。

2，尽管空闲块太大了，不能保存在主存。但是两种有效技术把该表的一小部分保存在主存里：

a，这个表可以是一个下推栈，栈中靠前的数千元素保存在内存中，当分配一个新块时它从栈顶弹出，同样当一个块被接触时把它压入栈中。只有栈中部分满了或者空了时候才需要从磁盘传输数据，通常情况下它是零访问时间的。

b，这个表可以看所FIFO的队列，分配时从头部取走，取消分配时从队尾入队，只有队空了或者满了时才需要与磁盘传输。

看了“操作系统总结知识”还想看：

1.操作系统主要知识点

2.操作系统知识大全

3.操作系统基本知识 操作系统知识点

操作系统基础知识总结

5.系统与设计知识点归纳

操作系统每章总结 第3篇

目的：为了进一步提高资源利用率和系统吞吐量

该系统中，用户提交的作业都先存在外存中，在作业A在执行I/O请求时，CPU空闲，此时调用作业B，防止CPU空闲。同理按一定的算法调用作业，防止CPU空闲

PS:推动多道批处理系统形成和发展的动力是提高资源利用率和系统吞吐量。

优点：

缺点：

特点：

还需解决的问题：

操作系统每章总结 第4篇

SPOOLing技术又称“假脱机技术”，是在通道技术和多道程序设计基础上产生的，它是一种将独占设备改造成共享设备的技术。

将一_享的打印机改造成可供多个用户共享的打印机，是SPOOLing的典型应用。

具体做法是：系统对于用户的打印输出，先在输出井申请一个空闲盘块区，并将要打印的数据送入其中，然后将此作业挂在打印队列上。若打印机空闲，输出程序从打印队列中取出作业，将要打印的数据从输出井传送到内存缓冲区，再进行打印。

操作系统每章总结 第5篇

在程序执行过程中，需要将要访问的数据的逻辑地址转换成物理地址。

具体实现方法是增加一个重定位寄存器，装入程序在内存中的起始地址，真正的地址为相对地址与重定位寄存器中的起始地址相加之和，从而实现动态重定位。

优缺点：理解原理后，从碎片的产生、是否缺乏大空闲区、排序性能等考虑

抖动：是指在页面替换过程中，刚刚调入的页面又被调出，刚刚调出的页面很快又被调入，发生频繁的页面调度行为。

分页和分段、局部性原理、虚拟存储器

操作系统每章总结 第6篇

（1）、解决问题：

单道批处理系统是在解决人机矛盾和CPU与I/O设备速度不匹配矛盾的过程中形成的。批处理系统旨在提高系统资源的利用率和系统的吞吐量。（但单道批处理系统仍不能充分利用资源，故现在已很少用）

单道批处理分为：联机批处理、脱机批处理 联机批处理：CPU直接控制作业输入输出 脱机批处理：由外围机控制作业输入输出

（2）、缺点：

（3）、特征

操作系统每章总结 第7篇

 连续分配方式会形成很多碎片，为之进行紧凑操作的开销非常大，如果允许一个进程直接分散地装入到许多不相邻接的分区中，则无须进行紧凑操作，基于这一思想产生了离散分配方式，如果离散分配的基本单位是页，则称为分页存储管理方式，若为段，则为分段存储管理方式。

页面与页表

分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页进行编号，从0开始。相应地，把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或者页框，也同样为它们编号，如0#块，1#块等。在未进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻接的物理块中，由于进程的最后一页经常装不满一块而形成不可利用的碎片，称之为页内碎片。

在分页系统中的页面其大小应适中，页面若太大，一方面可以是内存碎片减少，有利于提供内存利用率，但是，每一个进程占用的页面较多，导致页表过长，占用太多内存，会降低页面换进换出的效率。页面若太大，可减少页表的长度，提供页面换进换出的速度，但是，内存碎片会增大，所以，也页面大小应适中，通常为512B~8K

分页地址中的地址结构如下

 说明：前一部分为页号P，后一部分为位移量W（或称为页内地址），总共32位，其中0~11位为页内地址，每页大小4KB，12~31位为页号，地址空间最多允许1M页。

为了能够保证在内存中找到每个页面所对应的物理块，系统为每个进程建立了一张页面映射表，简称为页表。页表项纪录了相应页在内存中对应的物理块号，在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号，页表实现了从页号到物理块号的地址映像。

 块内地址表每块的大小和每一页的大小相等

地址变换机构

为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须设置地址变换机构，分为基本的地址变换机构和具有快表的地址变换机构。

 当页号大于页表长度时，越界中断。

操作系统每章总结 第8篇

实时系统（Real－Time System）是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

特征：

对实时处理系统，系统按分时原则为多个终端服务； 对实时控制系统，系统经常对多路现场信息进行采集；以及对多个对象或多个执行机构进行控制。

实时处理系统，每个终端用户向实时系统提出服务请求时，彼此独立； 实时控制系统，对信息的采集和对对象的控制彼此不干扰。

操作系统每章总结 第9篇

 解：由题知逻辑地址为：

物理地址为：

 （1）逻辑地址1011（十进制）的二进制表示为：

    00  1111110011，由此可知逻辑地址1011的页号0，查页表知该页放在第2物理块中；

其物理地址的二进制表示为：010  1111110011，所以逻辑地址1011对应的物理地址为0BF3H。其地址转换图如后所示。

 （2）逻辑地址2148（十进制）的二进制为：

10  0001100100，由此可知逻辑地址2148的页号是2，查页表知该页放入物理块1中；

其物理地址的二进制是：001 0001100100，所以逻辑地址2148对应的物理地址是0464H。

（3）逻辑地址5012（十进制）的二进制表示为：

  100  1110010100，可知该逻辑地址的页号为4，查页表知该页为不合法页，则产生越界中断。

具有快表的地址变换机构

基本的地址变换机构存在的问题；地址变换速度降低（因页表放于内存中，CPU访问一个字节的数据需两次访问内存）

目的：为提高地址变换速度

快表（联想寄存器、联想存储器、TLB）

为一种特殊的高速缓冲存储器。内容-----页表中的一部分或全部内容。·CPU产生逻辑地址的页号，首先在快表中寻找，若找到(命中)就找出其对应的物理块；若未找到(未命中)，再到页表中找其对应的物理块，并将之复制到快表。若快表中内容满，则按某种算法淘汰某些页。

两级和多级页表

现代计算机系统中，可以支持非常大的逻辑地址空间（2^32~2^64），这样，页表就变得非常大，要占用非常大的内存空间，如，具有32位逻辑地址空间的分页系统，规定页面大小为4KB，则在每个进程页表中的页表项可达1M(2^20)个，又因为每个页表项占用一个字节，故每个进程仅仅页表就要占用1MB的内存空间，而且要求连续，这显然是不现实的，可以通过如下两个方法解决该问题。

① 采用离散分配方式来解决难以找到一块连续的大内存空间的问题。

② 只将当前需要的部分页表项调入内存，其余页表项仍驻留在磁盘上，需要时再调入。

对于要求连续的内存空间来存放页表的问题，可利用将页表进行分页，并离散地将各个页面分别存放在不同的物理块中的办法来解决，同样的，也要为离散分配在页表再建立一张页表，称为外层页表。在每个页表项中记录了页表页面的物理块号，以32位逻辑地址空间为例进行说明。

 说明：外层页号P1为10位，可以表示1024个物理块，外层页表中的外层也内地址P2为10位，可以表示1024个物理块，页内地址为12位，表示页面大小为4K。

​

说明：在页表的每一个表项中存放的是进程的某页在内存中的物理块号，如第0页的0页存放1#物理块，第1页存放4#物理块，而在外层页表的每个页表项中，所存放的是某页表分页的首址，如第0页页表存放在1011#物理块中，第1页页表存放在1078#物理块中。

为了实现地址变换，在地址变换机构中需要增设一个外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址，在利用P2作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号，用该块号和页内地址d即可构成访问的内存物理地址。

将页表施行离散分配的方法，虽然解决了对大页表无需大片存储空间的问题，但是并未解决用较少的内存空间去存放大页表的问题，换言之，只用离散分配空间的办法并未减少页表所占用的内存空间，解决办法是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。在采用两级页表结构的情况下，对于正在运行的进程，必须将其外层页表调入内存，而对页表则只需要调入一页或者几页，为了表征某页的页表是否已经调入内存，还应在外层页表项中增设一个状态位S，其值若为0，表示该页表分页尚未调入内存，否则，说明已经在内存，进程运行时，地址变换机构根据逻辑地址P1，去查找外层页表，若所找到的页表项中的状态位为0，则产生一中断信号，请求OS将该页表分页调入内存。

对于64位的机器而言，采用两级页表已经不太合适，如果页面大小仍采用4KB，那么剩下52位，若还是按照物理块的大小（2^12位）来划分页表，每个页表项4B，故一页中可存放2^10个页表项，则将余下的42位用于外层页号，此时，外层页表中可能有4096G个页表项，要占用16384GB的连续内存空间，显然是不行的。必须采用多级页表，即将外层页表再进行分页。若计算机的虚拟地址空间大小为2^64，页面大小为4KB，页表项为4B，则最少页表的级数为6级，首先总的页面个数为2^52（64 - 12），其次，每个物理块能装入的页表项为4KB/4B = 2^10个，10 * 6 > 52，即最少需要6级。

六、基本分段存储管理方式

 从固定分区到动态分区分配，再到分页存储管理方式，其主要动力为提高内存利用率，引入分段存储管理的目的在于满足用户在编程和使用上多方面的要求。如

① 方便编程，用户可以把自己的作业按照逻辑关系划分为若干段，每个段都是从0开始编址，并有自己的名字和长度。

② 信息共享，在实现对程序和数据的共享时，是以信息的逻辑单位为基础的，比如共享某个函数。

③ 信息保护，信息保护同样是对信息的逻辑单位进行保护。

④ 动态增长，在实际应用中，数据段在使用过程中往往会不断增长，而实现无法确切知道数据段会增长到多大，分段可以较好的解决这个问题。

⑤ 动态链接，再运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中有需要调用某段时，才将该段调入内存并进行链接。

分段系统的基本原理

在分段管理中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息，如有主程序段MAIN，子程序段X，数据段D及栈段S，每个段都有自己的名字，每个段从0开始编址，并采用一段连续的地址空间，段的长度由相应的逻辑信息组的长度决定，因而各段长度不等，整个作业的地址空间由于是分成多个段，因而是二维的，即其逻辑地址由段号和段内地址构成。

说明：一个作业允许最长有64K个段，每个段的最大长度为64KB。

在分段式存储管理系统中，为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区，为了使程序正常运行，能够物理内存中找出每个逻辑段所对应的位置，应该为每个进程建立一张段映射表，称为段表，每个段在表中有一个表项，其中记录了该段在内存中的起始地址和段的长度。段表可以存放在一组寄存器中，这样有利于提高地址转换速度，但通常将段表放在内存中。段表用于实现从逻辑段到物理内存区的映射。

为了实现从进程的逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址和段表TL，在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较，若S>TL，表示段号太大，访问越界，产生越界中断信号，若未越界，则根据段表的始址和该段的段号，计算该段对应段表项的位置，从中读出该段在内存中的起始地址，然后，再检查段内地址d是否超过该段的段长SL，若超过，同样发出越界中断信号，若为越界，则将该段的基址与段内地址d相加，即得到要访问的内存物理地址。

      每次访问一个数据时（需给出段号和段内地址），也需要访问两次内存，第一次根据段号获得基址，第二次根据基址与段内地址之和访问真实数据的物理地址。这降低了计算机的速率，也可以增设一个联想存储器，用来保存最近常用的段表项，用来加速存取数据的时间。

可以看到，分页与分段存在很大的相似性，如都采用离散分配方式，都需要通过地址映射机构实现地址变换，但两者的主要区别如下。

① 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率，或者说，分页仅仅是由于系统管理的需要而不是用户的需要，段则是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了能更好地满足用户的需要。

② 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，一个系统中，只存在一种大小的页面，段的长度则不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

③ 分页的作业的地址空间是一维的，即单一的线性的地址空间，程序员只利用一个记忆符即可表示一个地址，而分段的作业地址空间是二维的，程序员在标识一个地址是，需要给出段名和段内地址。

① 静态链接，在将目标模块装配成一个装入模块时，需要对相对地址进行修改（由于编译程序产生的所有目标模块中，使用的都是相对地址，其起始地址都为0，每个模块中的地址都是相对于起始地址计算的）。也需要变换外部调用符号（将每个模块中所用的外部调用符号都变换为相对地址），这种先进行链接所形成的一个完整的装入模块，又称为可执行文件，通常都不再拆开它，要运行时可直接将它装入内存，这种事先进行链接，以后不再拆开的链接方式，称为静态链接方式。

  段页式存储管理方式

分页系统能够有效的提高内存利用率（但是会存在页内碎片），分段系统则能够很好地满足用户需要。若能将两种方式结合起来，既具有分段系统的便于实现、分段可共享、易于保护、可动态链接等优点，又能像分页系统那样很好地解决内存的外部碎片问题，基于此，提出了段页式系统。

段页式系统先将用户程序分成若干个段，再把段分为若干个页，并为每一个段赋予一个段名。段页式系统中，地址结构由段号、段内页号、页内地址三部分构成。

在段页式系统中，为了便于实现地址转换，须配置一个段表寄存器，其中存放段表始址和段表长TL，进行地址变换时，首先利用段号S，将它与段表长TL进行比较，若S

​

在段页式系统中，为了获得一条指令或数据，需要访问内存三次，第一次访问时访问内存中的段表，从中取得页表始址，第二次访问是访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址，第三次访问才是真正的从第二次访问所得的地址中，取出指令或数据。同样，也可以增设高速缓冲寄存器用于加快访问速度。

操作系统每章总结 第10篇

所谓进程通信是指进程之间信息交换。

高级通信：用户可直接利用OS提供的一组通信命令高效传送大量数据。分为：

直接通信：发送进程直接把消息发送给接收者，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息。也称为消息缓冲通信

间接通信：发送进程将消息发送到某种中间实体中（信箱），接收进程从（信箱）中取得消息。也称信箱通信。在网络中称为电子邮件系统。

思考：直接通信与间接通信方式的主要区别？

前者需要两进程都存在，后者不需要。

习题： 进程A1、A2，…An1通过m个缓冲区向进程B1、B2、…Bn2不断发送消息。发送和接收工作遵循下列规则： （1）每个发送进程一次发送一个消息，写入一个缓冲区， 缓冲区大小等于消息长度 （2）对每个消息，B1，B2，…，Bn2都须各接收一次，读 入各自的数据区内 （3）m个缓冲区都满时，发送进程等待，没有可读消息 时，接收进程等待。 试用P、V操作组织正确的发送和接收工作。

提示：每个缓冲区只需写一次但要读n2次，因此，可以看成n2组缓冲区，每个发送者要同时写n2组缓冲区中相应的n2个缓冲区，而每个接收者只要读它自己对应的那组缓冲区的对应单元。 Sin[n2]=m，表示每组缓冲区中可放的（空的）缓冲区的数目，初值为m; Sout[n2]=0，表示每组缓冲区中可取的（已用的）缓冲区的数目，初值为0;

先将问题简化： 设缓冲区的大小为1 有一个发送进程A1 有二个接收进程B1、B2 设有信号量Sin[1] 、Sin[2] 初值为1

设有信号量Sout[1] 、Sout[2] 初值为0

向目标前进一步

设缓冲区的大小为m 有一个发送进程A1 有二个接收进程B1、B2 设有信号量Sin[1] 、Sin[2] 初值为m

设有信号量Sout[1] 、Sout[2] 初值为0

到达目标：

设缓冲区的大小为m 有n1个发送进程A1….An1 有n2个接收进程B1…Bn2 设有n2个信号量Sin[n2] 初值均为m

设有n2个信号量Sout[n2] 初值均为0

操作系统每章总结 第11篇

进程是系统资源分配的基本单位，线程是CPU调度的基本单位。

线程可看作一种“轻量级线程”。线程自己不拥有系统资源，只拥有一点儿在运行中必不可少的资源，它与所属进程的其他线程共享进程的系统资源。

引入线程的目的是为了减小程序在并发执行时的时空开销，提高操作系统的并发性能。

1）共享存储

2）消息传递

3）管道通信：使用特殊的pipe文件，一方写入，一方读取

分为高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）。

死锁产生的必要条件：

解决死锁的方法：

操作系统每章总结 第12篇

处理机管理、内存管理、文件管理和设备（I/O）管理。

并发是指多个事件在同一时间间隔内发生，并行是指多个事件在同一时刻发生。

例如你在9: 00到9: 30仅吃面包，9: 30到10: 00仅写字，那么在9: 00—10: 00这一时间段内，吃面包和写字就是并发的；如果你在9: 00—10: 00左手拿着面包吃，右手写字，那这两个动作就是并行的。

管态又叫系统态、核心态。CPU在管态下有权限执行计算机的任何指令，其资源访问不受限制。操作系统内核程序处于管态。

目态又叫用户态。CPU处于目态时，程序只能执行非特权指令，不能直接使用系统资源，并且只能访问用户程序自己的存储空间。用户编写的程序处于目态。

区分管态和目态是为了保护系统程序。

通过系统调用（使用访管指令），可以从目态切换到管态。此外，程序产生异常或中断时（如除以0，缺页，I/O中断），也会切换到内核态。

操作系统每章总结 第13篇

、处理机管理功能：进程控制、进程同步、进程通信、调度（作业调度、进程调度）

、存储器管理功能：内存分配、内存保护、存储扩充、地址映射

、设备管理功能：缓冲管理、设备分配、设备处理

、文件管理功能：文件存储空间的管理、目录管理、文件的读 /写管理和保护

、操作系统与用户之间的接口：命令接口、程序接口、图形接口

、现代OS的新功能：