操作系统--算法总结

￡神魔★判官ぃ 2022-08-07 09:58 124阅读 0赞

操作系统中各个算法的运用使计算机系统的各个部件协调工作，使资源利用，程序执行更加合理高效。对比我们的生活，操作系统就像是一个百货商店，而算法就实现了让商店的利润尽可能达到最大。

## 【处理器两级调度】 ##

这里的两级调度说的是：**作业调度、进程调度**。

我们知道程序和数据存在外部存储器，执行前要先输送到内存，然后进程从就绪状态到运行结束；磁盘上的输入井传入主存的过程就是作业调度；一直到执行结束称为进程调度。

作业调度的算法：

![Center][]

首先是**先来先服务**，就好比是我们打饭排队一样，先来的先能买到饭，这体现了时间上的公平性。看一个简单例子：

在一个多道程序系统中，设用户空间为100K，主存空间管理采用最先适应分配策略，并采用先来先服务算法管理作业。请列出各个作业的开始执行时间、完成时间、周转时间 。

![Center 1][]

解析：

![Center 2][]

首先，题目给出用户可以使用主存为100k，因此作业放入主存的过程要注意内存不够用的情况，对上图的步骤进行解析：

1.确定开始、完成时间，以及装入主存的时间，因为单核系统一次只能出入一个作业，因此上一个作业的完成时间是下一个作业开始执行的时间。

2.按照先来先服务，job3本该先于job4，但job1，job2最先执行完也要到9时，从8--9时之间内存只有20K不能放下job3，因此跳过job3，先放入job4，它进入内存的时间=进入输入井的时间。

3.确定job3的进入内存时间，9时job1虽然已经完成，但是job2和job4仍然占用80K内存，因此，只能等job2完成，即9.6时，job3才能放入内存。

4.特别注意：周转时间=执行结束时间-进入输入井时间。

**时间短优先算法**，当内存仍然可以同时装入多个作业时，按照先来先服务算法执行，如果碰到两个像上题中job3的情况就考虑计算时间短的先执行：

例如上题，添加job5：装入时间 8.7时，需计算0.4小时，主存需求量25k，那执行完job4，接下来应该执行job5了而不是job3.

**      响应比高者优先算法：响应比=等待时间/计算时间**

**                                              等待时间=最后进入输入井时间-最初进入输入井时间**

**       **由响应比可以很方便的知道，程序的执行取决于等待时间和计算时间两个参量，可以避免执行事件非常短的程序等待过长的情况。

## 【进程调度算法】 ##

![Center 3][]

进程调度，是对内存中程序执行时就绪队列中的进程的调度。

对比于作业调度，先来先服务算法不用再考虑内存的事，因为作业已经从内存中形成进程形成队列，完全按照先来后到的顺序执行即可。

最高优先级调度，事先约定好进程的等级，让高优先级的先执行。它又分为抢占式和非抢占式，指的是高优先级进程到来时，会不会前占现有进程占用的处理器。

时间片轮转调度，事先规定了进程一次执行最多占用处理器时间，如果超出了就必须让出处理器。

## 【页面调度】 ##

![Center 4][]

**  页面调度的算法就像一个个接龙游戏：**

**      先进先出：**

**         例：在页式存储管理系统中，某进程依次访问的页面为2,3,2,1,5,2,4,5,3,2,5,2，分配三块主存块，此阿勇先进先出算法：**

**解析：**

**首先理解什么是缺页，每一次重新占用主存块就叫缺页。**

**                                           ![Center 5][]**

**   **  例如，第一列和第二列数字占用主存前是没有放东西的，因此是缺页，到第三列时，队列中已经存在2了，所以不缺页，队列中就不会有改变。这张表里面我们看到队首时间最短，先进先出是替换掉对尾（时间最长）。

其他算法类似，不做赘述。

【总结】

算法应用于计算机让我们的程序执行的越来越高效，只要我们联系生活，这些都是非常简单而有趣的。

**   **

[Center]: /images/20220805/dc99dafa3f944780a750b24e41be520b.png
[Center 1]: /images/20220805/a82e942aaec64f34badbde256f306c1f.png
[Center 2]: /images/20220805/f2d45137d4974e9488d86fb18d00a2cd.png
[Center 3]: /images/20220805/d795646a0b7c44d6b8b1923f038f23b8.png
[Center 4]: /images/20220805/606e48e193d94b948ed8ccca6d81efa5.png
[Center 5]: /images/20220805/eb45d639ee9144baa43fda9382ebab19.png