计算题总结

作业调度算法

1、FCFS算法(先来先服务算法):算法每次从后备作业队列中选择最先进入该队列的一个或几个作业,将它们调入内存,分配必要的资源,创建进程并放入就绪队列。FCFS调度算法的特点是算法简单,但效率低;对长作业比较有利,但对短作业不利(相对SJF和高响应比);有利于CPU繁忙型作业,而不利于I/O繁忙型作业。

2、SJF算法(短作业优先算法):从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。SJF调度算法的平均等待时间、平均周转时间最少;但对长作业非常不利。

3、HRN算法(最高响应比优先算法):该算法是对FCFS调度算法和SJF调度算法的一种综合平衡,同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时,先计算后备作业队列中每个作业的响应比,从中选出响应比最高的作业投入运行。

响应比R计算公式: 响应比R = 作业周转时间/作业处理时间 = 1+(作业等待时间/作业处理时间)

4、HPF算法(优先数调度算法):每次从后备作业队列中选择优先级最髙的一个或几个作业,将它们调入内存,分配必要的资源,创建进程并放入就绪队列。

根据新的更高优先级进程能否抢占正在执行的进程,可将该调度算法分为:

  • 非剥夺式优先级调度算法。当某一个进程正在处理机上运行时,即使有某个更为重要或紧迫的进程进入就绪队列,仍然让正在运行的进程继续运行,直到由于其自身的原因而主动让出处理机时(任务完成或等待事件),才把处理机分配给更为重要或紧迫的进程。
  • 剥夺式优先级调度算法。当一个进程正在处理机上运行时,若有某个更为重要或紧迫的进程进入就绪队列,则立即暂停正在运行的进程,将处理机分配给更重要或紧迫的进程。

而根据进程创建后其优先级是否可以改变,可以将进程优先级分为以下两种:

  • 静态优先级。优先级是在创建进程时确定的,且在进程的整个运行期间保持不变。
  • 动态优先级。在进程运行过程中,根据进程情况的变化动态调整优先级。

5、均衡调度算法:基本思想是首先根据系统运行情况和作业属性将作业分类,轮流从不同的作业类中挑选作业;目的是力求均衡地利用各种系统资源,发挥资源利用效率。

页面置换算法

1、最佳置换算法(OPT):算法所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的,因而该算法无法实现。

2、先进先出置换算法(FIFO):优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应,因为在进程中,有的页面经常被访问。

3、最近最久未使用置换算法(LRU):选择最近最长时间未访问过的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段,来记录页面自上次被访问以来所经历的时间,淘汰页面时选择现有页面中值最大的予以淘汰。

磁盘驱动调度算法

先来先服务算法:根据进程请求访问磁盘的先后顺序进行调度。

  • 优点:公平,简单。
  • 缺点:未对寻道进行优化,平均寻道时间可能较长。

最短寻道时间优先算法:总是执行查找时间最短的那个磁盘请求。

  • 优点:平均寻道时间最短。
  • 缺点:存在“饥饿”现象。随着源源不断靠近当前磁头的读写请求到来,使得早来但距离磁头位置偏远的读写请求一直得不到满足。

扫描算法:每次总是选择沿臂的移动方向最近的那个柱面。如果这个方向没有访问请求,就改变移动方向,然后处理所遇到的最近的I/O请求。非常类似电梯的调度规则。

  • 优点:杜绝“饥饿”问题,平均寻道时间较好。
  • 缺点:在磁盘请求平均的情况下,磁头到头转向时,靠近磁头一端的请求特别少,许多请求集中分布在另一端。

循环扫描算法:移动臂总是从0号页面至最大页面顺序扫描,然后直接返回0号柱面重复执行。

银行家算法

银行家算法是一种用于死锁的避免的经典算法,算法描述如下:

  1. 将每个进程总需资源数减去已分配资源数,查找结果中是否有一行,其未被满足的资源数均小于等于系统剩余资源数。如果找不到,系统将死锁,任何进程都无法运行结束;
  2. 若找到这样一行,可以假设它获得所需资源并运行结束,将该进程标记为结束并将资源加到系统所剩资源数上;
  3. 重复以上两步,直到所有进程都标记为结束,则状态是安全的,否则将发生死锁。

信号量与PV操作

信号量是用来解决进程同步的,不是用来解决死锁问题的。

P原语操作的主要动作是:

  1. s.value减一;
  2. 若s.value减一后仍大于或等于0,则进程继续进行;
  3. 若s.value减一后小于0,则该进程被阻塞后与该信号相对于的队列中,然后转进程调度。

V原语操作的主要动作是:

  1. s.value加一;
  2. 若s.value加一后大于或等于0,则进程继续进行;
  3. 若s.value加一后小于或等于0,则从该信号的等待队列中唤醒一个进程,然后返回原进程继续执行或转进程调度。

分页式/分段式地址转换

分页式例题:

某虚存的用户空间有24个页面,每页1KB,内存16KB。假设某时刻系统为用户的第0,1,2和3页分配的物理快号为5,10,4,7,试将虚拟地址0A5C变化为物理地址。

0A5C:0000 1010 0101 1100  ->     因为每页1KB,所以前6位是页号,后10位是页内地址。页号为2转换为物理块号为4,页内地址不变。答案:0001 0010 0101 1100

分段式例题:

根据下面段表,写出对应的物理内存地址:

段号

段首址

段长

0

400

600

1

1300

400

2

100

200

  1. [0,430]    物理地址:830
  2. [1,200]    物理地址:1500
  3. [2,400]    越界。
  4. [3,100]    越界。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android相关

处理器结构--分支预测(Branch Prediction)

条件分支指令通常具有两路后续执行分支。即不采取(not taken)跳转,顺序执行后面紧挨JMP的指令;以及采取(taken)跳转到另一块程序内存去执行那里的指...

35740
来自专栏大数据挖掘DT机器学习

使用Python绘制点击图、热图

via: http://blog.csdn.net/wenyusuran/article pyHeatMap是一个使用Python生成热图的库,基本代码是我一年...

63640
来自专栏人工智能LeadAI

TensorFlow从0到1 | 第十八章: 升级手记:TensorFlow 1.3.0

《TensorFlow从0到1》写到现在,TensorFlow的版本也从当时的1.1.0迭代到了8月初发布的1.3.0。可以预见在未来很长一段时间里,它仍会持续...

31870
来自专栏PaddlePaddle

【进阶篇】安装与编译C-API预测库

编写|PaddlePaddle 排版|wangp 1 概述 使用 C-API 进行预测依赖于将 PaddlePaddle 核心代码编译成链接库,只需在编译时...

382100
来自专栏Golang语言社区

一致性hash算法原理及golang实现

这里存在一种场景, 当一个缓存服务由多个服务器组共同提供时, key应该路由到哪一个服务.这里假如采用最通用的方式key%N(N为服务器数目), 这里乍一看没什...

18520
来自专栏计算机视觉

为stackGan一个工程创建一个虚拟环境,python 2.7 tensorflow0.12-tensorflow 1.01

安装conda 下载地址:https://repo.continuum.io/miniconda/Miniconda2-latest-Linux-x86_64...

368100
来自专栏听雨堂

Flash背景透明的代码

      我觉得这个应该不是太难,结果DW中死活设置不成功,网上搜索到的都是一些互相抄了抄去的不知所云的东西,懒得去学习研究,还不如在自己原来做过的网站中找代...

21360
来自专栏自然语言处理

深度学习环境搭建

本文作者的专题《目标检测》链接:https://www.jianshu.com/c/fd1d6f784c1f 此专题的宗旨是让基础较为薄弱的新手能够顺利实现目标...

56110
来自专栏AI2ML人工智能to机器学习

TF Boy 之初筵 - 机器簇

在 "TF Boy 之初筵 - 分布十三式", 里面,我们提到参数服务器PS+Worker。 我们基本上是在Client里面定义好了TF模型(网络图),然后提交...

8310
来自专栏专知

Python网络爬虫与信息抽取笔记06 爬虫实战2

17320

扫码关注云+社区

领取腾讯云代金券