操作系统期末复习总结

进程的状态与转换

进程调度

调度算法的评价指标

CPU利用率

CPU忙碌的时间占总时间的比例

系统吞吐量

单位时间内完成作业的数量

总共完成了多少道作业/总共花了多少时间

周转时间

从作业被提交给系统开始，到作业完成为止的这段时间间隔

作业完成时间-作业提交时间

平均周转时间

各作业周转时间之和/作业数

带权周转时间

作业周转时间/作业实际运行时间

平均带权周转时间

各作业带权周转时间之和/作业数

等待时间

指进程/作业处于等待处理机状态时间之和，等待I/O完成的时间不计入等待时间

周转时间-运行时间（-I/O操作时间）

响应时间

指从用户提交请求到首次产生响应所用的时间

调度算法

FCFS先来先服务（非抢占式）

对长作业有利，对短作业不利

有利于受CPU限制的进程，不利于受I/O限制的进程

SJF短作业优先（非抢占式）

SRTN最短剩余时间优先（抢占式）

每当有进程加入就绪队列时就需要调度，还有当一个进程完成时也需要调度

对短作业有利，对长作业不利，会产生“饥饿”现象

HRRN高响应比优先算法（非抢占式）

响应比=（等待时间+要求服务时间）/要求服务时间

只有当前运行的进程主动放弃CPU时(正常/异常完成，或主动阻塞)，才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机

RR时间片轮转调度算法（抢占式）

默认新到达的进程先进入就绪队列

更有利于CPU密集型的进程

优先级调度算法

多级反馈队列调度算法（抢占式）

多级队列调度算法

进程互斥

软件实现方法

单标志法

int turn = 0; // turn 表示当前运训进行临界区的进程号，可以把turn看作是“谦让”的意思
// P0 进程
while(turn != 0);
critical section;
turn = 1;
remainder section;
// P1 进程
while(turn != 1);
critical section;
turn = 0;
remainder section;

违背了“空闲让进”的原则

双标志先检查法

违背了“忙则等待”的原则

双标志后检查法

先上锁，后检查

违背了“空闲让进”和“有限等待”的原则

Peterson算法

硬件实现方法

中断屏蔽方法

利用“开/关中断指令”实现

TestAndSet指令（TSL）

Swap指令

信号量机制

通过操作系统提供的一对原语来对信号量进行操作

wait(S)，signal(S) => P(S)，V(S)

对信号量的操作只有三种，即初始化、P操作、V操作

整型信号量不满足让权等待，会发生“忙等”

记录型信号量（semaphore）

/*记录型信号量的定义*/
typedef struct {
	int value;			//剩余资源数
	Struct process *L;	 //等待队列
} semaphore;
/*某进程需要使用资源时，通过 wait 原语申请*/
void wait(semaphore S) {
	S.value--;
	if (S.value < 0){
        block(S.L)
    }
};
/*进程使用完资源后，通过 signal 原语释放*/
void signal(semaphore S) {
    S.value++;
    if(S.value <= 0) {
        wakeup(S.L)
    }
};

实现进程互斥

划定临界区
设置互斥信号量mutex，初值为1（semaphore mutex = 1;）
在进入区P(mutex)——申请资源
在退出去V(mutex)——释放资源

P、V必须同步出现

实现进程同步

分析什么地方需要实现“同步关系”
设置同步信号量S，初始为0
在“前操作”之后执行V(S)
在“后操作”之前执行P(S)

实现进程的前驱关系

生产者-消费者问题

生产者、消费者共享一个初始为空、大小为n的缓冲区

缓冲区是临界资源
缓冲区没满=>生产者生产
缓冲区没空=>消费者消费

semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;
producer() {
    while(1) {
        // 生产一个产品
        P(empty);
        P(mutex);
        // 把产品放入缓冲区
        V(mutex);
        V(full);
    }
}
consumer() {
    while(1) {
        P(full);
        P(mutex);
        // 从缓冲区取出一个产品
        V(mutex);
        V(empty);
        // 使用产品
    }
}

实现互斥的P操作一定要在实现同步的P操作之后，两个V操作的顺序可以交换

多生产者-多消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程

读者-写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:①允许多个读者可以同时对文件执行读操作;②只允许一个写者往文件中写信息;③任一写者在完成写操作之前不允许其他读者或写者工作;④写者执行写操作前，应让已有的读者和写者全部退出

哲学家就餐问题

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考

两个临界资源

可以最多允许四个哲学家进餐
可以要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻寒。这就避免了占有一支后再等待另一只的情况
只有一个哲学家左右筷子都可用的时候，才允许拿起筷子

死锁

死锁避免

银行家算法

内存管理

连续分配管理方式

单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据;用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间

有内部碎片，无外部碎片

固定分区分配

将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业

分区大小可以相等，也可以不相等

需要建立一个数据结构——分区说明表

有内部碎片，无外部碎片

动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要

没有内部碎片，有外部碎片

可以采用紧凑技术来解决外部碎片

动态分区分配算法

首次适应算法（First Fit）

每次都从低地址开始查找，找到第一个能满足大小的空闲分区

空闲分区以地址递增的次序排序

最佳适应算法（Best Fit）

空闲分区按容量递增次序链接

找到的一定是能够满足且大小最小的

会产生很多的外部碎片

最坏适应算法（Worst Fit）

空闲分区按容量递减次序链接

邻近适应算法（Next Fit）

空闲分区以地址递增的次序排序，每次分配内存时从上次查找结束的位置开始查找

页面置换算法

最佳置换算法（OPT）

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面

先进先出置换算法（FIFO）

每次选择淘汰的页面时最早进入内存的页面

会出现Belady异常（当为进程分配的物理块数增大时，缺页次数不减反增的异常现象）

最近最久未使用置换算法（LRU）

每次淘汰的页面是最近最久未使用的页面

是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大

时钟置换算法（CLOCK）

为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列

当某页被访问时，其访问位置为1

当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描

改进型的时钟置换算法

在其他条件都相同的时候，应优先淘汰没有修改过的页面（访问位，修改位）

第一轮:从当前位置开始扫描到第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
第二轮:若第一轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮:若第二轮扫描失败，则重新扫描，查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
第四轮:若第三轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换

例题

例1

下图所示分别给出了页式或段式两种地址变换示意(假定段式变换对每一段不进行段长越界检查，即段表中无段长信息)

指出这两种变换各属于何种存储管理
计算出这两种变换所对应的物理地址

页式存储:物理地址=页始址+页内偏移量

页始址=内存块号×页面大小=12×2^11=24576

物理地址=24576+586=25162

段式存储:物理地址=段始址+段内偏移量

物理地址=4000+586=4586

例2

在某页式管理系统中，假定主存为64KB，分成16块，块号为0、1、2、…、15。设某进程有4页，其页号为0、1、2、3，被分别装入主存的 9、0、1、14块

该进程的总长度是多大
写出该进程每一页在主存中的起始地址
若给出逻辑地址(0,0)、(1,72)、(2,1023)、(3,99)，请计算出相应的内存地址(括号内的第一个数为十进制页号，第二个数为十进制页内地址)

例3

在页式、段式和段页式存储管理中，当访问一条指令或数据时，各需要访问内存几次?其过程如何?假设一个页式存储系统具有快表，多数活动页表项都可以存在其中。如果页表存放在内存中，内存访问时间是1us，检索快表的时间为0.2us，若快表的命中率是85%，则有效存取时间是多少?若快表的命中率为50%,那么有效存取时间是多少

页式存储管理:根据页号查页表->访问内存地址(物理地址=物理页号×页面大小+页内偏移量)
段式存储管理:根据段号查段表->访问内存地址(物理地址=段始址+段内偏移量)
段页式存储管理:根据段号查段表(可确定该段对应的页表始址)->根据页号查页表访问内存地址(物理地址=物理页号页面大小+页内偏移量)

快表命中率 85%:平均存取时间=(0.2+1)×0.85+(0.2+1+1)×0.15 =1.35 μS

快表命中率50%:平均存取时间=(0.2+1)×0.5+(0.2+1+1)×0.5=1.7 μS

例4

某分页式虚拟存储系统，用于页面交换的磁盘的平均访问及传输时间是20ms。页表保存在主存，访问时间为1us，即每引用一次指令或数据，需要访问两次内存。为改善性能，可以增设一个关联寄存器，如果页表项在关联寄存器里，则只要访问一次内存就可以。假设80%的访问其页表项在关联寄存器中，剩下的20%中，10%的访问(即总数的2%)会产生缺页。请计算有效访问时间

例5

已知系统为32位实地址，采用48位虚拟地址，页面大小4KB，页表项大小为8B;每段最大为4GB

假设系统使用纯页式存储，则要采用多少级页表，页内偏移多少位
假设系统采用一级页表，TLB命中率为98%，TLB访问时间10ns，内存访问时间100ns，并假设当TLB访问失败时才开始访问内存，问平均页面访问时间是多少
如果是二级页表，页面平均访问时间是多少
上题中，如果要满足访问时间小于120ns，那么命中率需要至少多少
若系统采用段页式存储，则每用户最多可以有多少个段?段内采用几级页表

页面大小4KB=2^12B->12位页内偏移量

32位实地址->物理内存大小为2^32B=4GB

48位虚拟地址->支持最大虚拟内存大小2^48B；逻辑地址为48位

纯页式存储，各级页表大小不能超过一页

每页可以存4KB/8B=2^9个页表项

36/9=4，需要分为4级页表
(10+100)×98%+(10+100+100)×2%=112
一级页号（27位）| 二级页号（9号）| 页内偏移量（12位）

每个物理页框只能存4KB/8B=2^9个页表项

快表中的页号是复合页号，即可以直接计算出最终目标的物理地址，不需要再查更低级的页表

(10+100)×98%+(10+100+100+100)×2%=114 ns
(10+100)P+(10+100+100+100)(1-P)<=120 ns

P>=95 %
先考虑纯段式的逻辑地址结构

每段最大为4GB=2^32B->段内偏移量要32位->最多支持2^16个段

段页式（把各段段内再分页）

32位可以划分为20+12位

20/9=2.222->要分三级页表

文件管理

例题

例1

简述文件的外存分配中的连续分配、链接分配和索引分配各自主要的优缺点

连续分配

优点：可以随机访问，访问速度快

缺点：要求有连续的存储空间，容易产生碎片，降低磁盘空间利用率，不利于文件的增长扩充
链接分配

优点：不要求连续的存储空间，更有效地利用磁盘空间，并且有利于扩充文件

缺点：只适合顺序访问，不适合随机访问；另外，链接指针占用一定空间，降低了存储效率，可靠性也差
索引分配

优点：既支持顺序访问也支持随机访问，查找效率高，便于文件删除

缺点：索引表会占用一定的存储空间

例2

在实现文件系统时，为加快文件目录的检索速度，可利用“FCB分解法”。假设目录文件存放在磁盘上，每个盘块512B。FCB占64B，其中文件名占8B。通常将FCB分解成两部分，第一部分占10B(包括文件名和文件内部号)，第二部分占56B(包括文件内部号和文件其他描述信息)

假设某一目录文件共有254个FCB，试分别给出采用分解法前和分解法后，查找该目录文件的某一个FCB的平均访问磁盘次数
一般地，若目录文件分解前占用n个盘块，分解后改用m个盘块存放文件名和文件内部号，请给出访问磁盘次数减少的条件

512B/64B=8->每个磁盘块只能存8个FCB

254/8=31.75(32)->32个磁盘块
- 分解前：(1+2+3+…+32)/32=16.5
10×254/512=4.96->5个磁盘块
- 分解后：(2+3+4+5+6)/5=4
分解前是(1+2+3+…+n)/n=n×(n+1)/2/n=(n+1)/2；分解后是(2+3+4+…+(m+1))/m=(m+3)/2

m<n-2

例3

假定磁盘块的大小为1KB，对于540MB的硬盘，其文件分配表FAT最少需要占用多少存储空间

对于540MB的硬盘，硬盘总块数为540MB/1K=540K个

磁盘块号范围:0~540K-1，刚好小于2^20，可用20bit表示块号->文件分配表的每个表目至少要20位

即20/8=2.5字节，这样FAT占用的存储空间大小为2.5B×540K=1350KB

例4

在UNIX操作系统中，给文件分配外存空间采用的是混合索引分配方式，如下图所示。UNIX系统中的某个文件的索引结点指示出了为该文件分配的外存的物理块的寻找方法。在该索引结点中，有10个直接块(每个直接块都直接指向一个数据块)，有1个一级间接块，1个二级间接块以及1个三级间接块，间接块指向的是一个索引块，每个索引块和数据块的大小均为4KB，而UNIX系统中地址所占空间为4B(指针大小为4B)，假设以下问题都建立在该索引结点已经在内存中的前提下。现请回答:

文件的大小为多大时可以只用到索引结点的直接块
该索引结点能访问到的地址空间大小总共为多大?(小数点后保留2位)
若要读取一个文件的第10000B的内容，需要访问磁盘多少次
若要读取一个文件的第10MB的内容，需要访问磁盘多少次
一个2GB大小的文件，在这个文件系统中实际占用多少空间

解：

4KB×10=40KB
每个索引块可存储4KB/4B=1K=2^10个索引项

该索引结点最大可包含10+2^10+2^20+2^30个数据块

单个文件最大长度为(10+2^10+2^20+2^30)×4KB≈4.00TB
10000B/4KB=2.44，放在第三个直接块，需要访问1次
10MB/4KB=2.5×1024

直接块和一级间接块可以指向10+(4KB/4B)=1034块

直接块和一级间接块以及二级间接块可以指向10+(4KB/4B)+(4KB/4B)^2>1×1024^2块

需要访问3次
该文件占用2GB/4KB=512×1024个数据块

直接索引指向10个数据块

一级间接指向1024个数据块，需要1个索引块

二级间接指向512×1024-10-1024个数据块

共需1+[(512×1024-10-1024)/1024]=512个索引块

索引块共占空间大小(1+512)×4KB=2MB+4KB

另外每个文件使用的iNode数据结构占13×4B=52B

该文件实际占用磁盘空间大小为2GB+2MB+4KB+52B