三.处理机调度与死锁
思维导图：
作业的状态及其转换
1.概念：一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、收容、执行和完成等4个状态。
2.处理机调度可以分为4级：(1)作业调度：又称高级调度。(2)交换调度：又称中级调度。(3) 进程调度：又称低级调度。(4) 线程调度
下图可以展现出作业的处理流程：
归纳一些问题：
1.作业的调度性能如何衡量？
- 周转时间 = 运行时间 + 等待时间 = 作业完成时刻 - 作业到达时刻
- 等待时间 = 上一个周转时间 - 距离上一个的到达时间 = 上一个的等待时间 + 上一个运行时间 - 距离上一个的到达时间
- 带权周转时间 = 周转时间 / 服务时间（运行时间）
- 平均带权周转时间 = 带权周转总时间 / 作业个数
- 平均周转时间 = 作业周转总时间 / 作业个数
特别注意：作业到达时间不是作业进内存的时间，而是发出请求，提交就开始计时，如果无法安排进内存，那么就等待，等待的这部分时间也要计数
2. 调度算法实例
-
FCFS（先来先服务）算法：JOB1-JOB2-JOB3-JOB4
-
SJF（短作业优先）算法：JOB1-JOB3-JOB4-JOB2
- HRRN（高响应比调度）算法：JOB1-JOB3-JOB2-JOB4
需要根据公式将每个作业的响应度进行排序
3.如何避免死锁？
- 银行家算法
银行家算法是在资源动态分配时来对每个进程的所占有资源以及空闲资源和进程最大所需资源这三个进行比较验证本次分配的资源是否合理，这便是避免死锁的方法。
核心算法思路：
从流程图可以看出主要是进行了两次判断来保证资源的分配需求从而避免死锁
void banktest::safe()
{
while(1)
{
while(1)
{
vector<int> work = _avail;
vector<bool> Finish(_pcNum,false);
int flag1 = 0;
int routine = 0;
int *route = new int[_pcNum ];
for(int i = 0;i < _pcNum;++i)
{
for(int p = 0;p < _pcNum;++p)
{
if(Finish[p] == true) continue;
flag1 = 0;
for(int k = 0;k < _wkNum;++k)
{
// 如果需要的大于空闲的则分配失败
if(work[k] < _need[p][k]) continue;
flag1 += 1;
}
if(flag1 == _wkNum)
{
Finish[p] = true;
for(int f = 0;f < _wkNum;++f)
{
work[f] += _allocation[p][f];
_allocation[p][f] = 0;
_need[p][f] = 0;
}
}
route[routine] = p;
routine += 1;
}
}
int flag2 = 0;
for(int i = 0;i < _pcNum;++i)
{
if(Finish[i] == false)
{
cout << "not safe" << endl;
break;
}
flag2 += 1;
}
if(flag2 == _pcNum)
{
cout << "is safe" << endl;
cout << "the routine is :" <<endl;
for(int i = 0;i < _pcNum;++i)
{
if(i == _pcNum - 1)
{
cout << route[i] << endl;
break;
}
cout << route[i] << "---->";
}
}
int num;
cout << "请输入要申请的资源进程号（小于零结束）" << endl;
cin >> num;
if(num < 0 || num >= _pcNum)
{
break;
}
cout << "依次输入各个资源的数量(" << _wkNum << ")" << endl;
for(int i = 0;i < _wkNum;++i)
{
cin >> _need[num][i];
}
}
string jd = "yes";
cout << "是否再次分配yes/no" << endl;
cin >> jd;
if(jd == "no" || jd == "NO")
{
break;
}
}
}
四.存储器管理
思维导图
归纳一些问题
三种算法示例
1 例：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按三种算法组成的空闲区队列;
2.作业1有2页分别装入内存的第5、6块；作业2有3页装入内存的第2、4、7块；作业3有1页装入内存的第8块
笔试题型需要的概念
->页号 = 程序地址 / 页长(4KB)
->业内偏移 = 程序地址 % 页长(4KB)
3.某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下
问:则逻辑地址0A5C（H）所对应的物理地址是什么？
由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。
逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100，根据上面的分析，下划线部分为页内地址，编码“000 10”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00 ，拼接块内地址10 0101 1100，得01 0010 0101 1100，即125C（H）。
解逻辑地址0A5C（H）所对应的物理地址是125C（H）
4.关于死锁的问题，主要是通过一些工具来查找死锁位置，具体在下面的博客中有介绍：
死锁现象以及调试实践
五.虚拟存储器
思维导图
归纳的一些问题
1.有一虚拟存储系统，采用先进先出的页面淘汰算法。在内存中为每个进程分配3块。进程执行时使用页号的顺序为 4 3 2 1 4 3 5 4 3 2 1 5
(1) 该进程运行时总共出现几次缺页。
(2) 若每个进程在内存有4块，又将产生几次缺页。
(3) 如何解释所出现的现象。
（1）m=3
（2）、m=4
（3）、FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加
2.某程序在内存中分配三个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、 LRU、OPT算法分别计算缺页次数
假设开始时所有页均不在内存。
3.某程序在内存中分配四个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按LRU、OPT算法分别计算缺页次数
假设开始时所有页均不在内存
4.有一页式系统，其页表存放在主存中。
(1) 如果对主存的一次存取要3us，问实现一次页面访问要多长时间。
2*3=6us
(2) 如系统有快表，平均命中率为97%，假设访问快表的时间忽略为0，问此时一次页面访问要多长时间。
0.97*3+0.03*6=3.09us
5.在分页存储管理系统中，有一作业大小为4页，页长为2K，页表如下
6.如果内存划分为100KB、500KB、200KB、300KB、600KB首次适应、最佳适应和最差适应算法各自将如何放置大小分别为212KB、417KB、112KB、426KB的进程？哪种算法的内存利用率最高？
答：
（1）首次适应：212KB放在500KB分区（剩余288KB）；417KB放在600KB分区；112KB放在剩余的288KB分区；而426KB进程必须等待。
（2）最佳适应：212KB放在300KB分区；417KB放在500KB分区；112KB放在200KB分区；426KB放在600KB分区。
（3）最差适应：212KB放在600KB分区（剩余388KB）；417KB放在500KB分区；112KB放在剩余388KB分区；而426KB进程必须等待
综上可以看出，最佳适应算法的内存利用率最高。
7.一个32位地址的计算机使用两级页表，虚地址被分为9位的顶级页表域，11位的二级页表域和偏移，请问，页面长度是多少？在地址空间中，共存在多少页？
答：9位作顶级页表域，11位作二级页表域，所以剩余32-(9+11)=12位作偏移，所以页面长度是212=4K，在地址空间中共存在220个页面
8.请解释什么是重定位？为什么要重定位？
将虚拟的逻辑地址映射为真实存在的物理地址。
进程中的地址都是从0开始的虚拟地址，在多道程序环境中必须依靠重定位寄存器将逻辑地址映射为物理地址
9.动态重定位的实现方式有几种？
（1）基于重定位寄存器且连续分配的动态重定位。
（2）基于段或页离散分配的动态重定位
10.可采用那几种方式将程序装入内存？它们分别适用于哪种场合？
（1）绝对装入：单道批系统。
（2）可重定位装入（装入时进行地址映射）：多道环境且装入后进程的位置不能变
（3）动态运行时装入（运行的时候进行地址映射）：需要重定位寄存器的支持
11.何谓静态链接？静态链接时要解决那两个问题？
静态链接：程序运行前将编译后的模块与库函数进行链接，链接后不分开。
问题1:修改相对地址：将各模块的相对地址修改为整体相对地址。
问题2:修改调用符号：将外部调用模块的起始地址修改为相对地址
12.编写程序时必须经过编译链接生成目标代码，请问什么是链接？链接主要解决哪些问题？简述链接的主要类型及其优缺点？
链接：将编译后的目标模块与库函数链接为一个可装入的模块。
解决问题：将目标模块与库函数链接起来，目标函数中只有调用的库函数名，参数等，并没有实际内容，链接后便形成完整的函数。
静态链接：已经拥有所有需要的库函数，运行速度快但体积大，有很多冗余代码。
装入时动态链接：装入内存时一边装入一边链接,若装入时发生调用，在将被调用的模块装入并修改地址。便于修改与更新，便于模块共享，但是运行时性能会有损失
动态运行时链接：体积小，装入速度快。运行时性能会有损失
13.为什么要引入对换技术？对换可分为哪几种类型？
为了腾出内存，将具备运行条件的作业调入内存。
换入，换出
14.对换技术对文件区管理的目标和对对换区管理的目标有何不同？
文件区为了提升空间利用率。
对换区为了提高进行调入调出速度
15.为什么说分段系统较分页系统更容易实现信息共享和保护？
分段系统段内内容基本一致，只需要一个标志位便可对整个段进行保护。
16.分页系统，文件存放更分散，需要的标识太多
提高内存利用率途径有哪些？
内存利用率低主要由这几个方面造成：
（1）内存碎片多：将连续分配变为离散分配
（2）冗余信息多，重复拷贝：储存器共享机制
（2）大进程阻塞 ：虚拟技术，动态链接技术
（4）长期不用的资源占据内存：对换技术
17.储存器管理的基本任务，是为多道程序的并发执行提供良好的储存器环境。请问：“良好的储存器环境”应包含哪些方面？
（1）独立性：各进程应拥有独立的地址空间，运行不会相互干扰。
（2）容量足够：储存器空间大小应满足进程的需求。
（3）储存器管理能够为进程对新信息的访问，共享，链接，安全，动态增长提供便利。
（4）储存器利用率高