磁盘调度算法,内存调度,内存分配策略_电气自动化网
首页 资讯 应用 高压 设计 行业 低压 电路图 关于

嵌入式

旗下栏目: PLC 嵌入式 单片机 DCS

磁盘调度算法,内存调度,内存分配策略

嵌入式 | 发布时间:2018-06-02 | 人气: | #评论# | 本文关键字:内存,算法,磁盘,磁盘调度算法,内存调度,内存分配
摘要:磁盘是可供多个进程共享的设备,当有多个进程都要求访问磁盘时,应采用一种最佳调度算法,以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中,主要是寻道时间。因此:磁

磁盘是可供多个进程共享的设备,当有多个进程都要求访问磁盘时,应采用一种最佳调度算法,以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中,主要是寻道时间。因此:磁盘调度算法的目标是使磁盘的平均寻道时间最少

1,先来先服务(FIFS,first come first served) 
  根据进程请求访问磁盘的先后顺序进行调度。公平,简单,每个进程都能依次得到处理,不会出现某一进程的请求长期得不到满足的情况。但算法由于未对寻道进行优化,致使平均寻道时间可能很长

2,最短寻道时间优先(SSTF,shortest seek time first) 
  要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短。但是这种算法不能保证平均寻道时间最短。

  虽然能获得较好的性能,但却可能导致某个进程发生“饥饿”现象。只要不断有新进程的请求到达,且其所要访问的磁道与磁头当前的距离较近,这种新进程的I/O请求必然优先得到满足

3,电梯算法(SCAN) 
不仅考虑到预访问的磁头与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。例如:当磁头正在自里向外移动时,SCAN算法所考虑的下一个访问对象应该是在当前磁道之外,又是距离最近的。这样的自里向外的访问,直至再无更外的磁道需要访问时,才将磁臂换为自外向里移动。这样“避免了饥饿现象”。

局部性原理

时间局限性: 
如果程序中某条指令一旦执行,则不久后该指令可能再次执行;如果某数据被访问过,则不久后该数据可能再次被访问。产生时间局限性的典型原因是由于存在着大量的循环操作 
空间局限性: 
一旦程序访问某个存储单元,在不久后,其附近的存储单元也将被访问,即一段时间内所访问的地址,可能集中在一定的范围。程序的顺序执行和顺序存储

虚拟存储器:具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统 
每个页表:

页号,物理块号,状态位p,访问字段A,修改位M,外存地址

如果系统的页大小为4KB(2^12B),那么页表可以拥有2^(32-12)个 
状态位p:是不是已经调入了内存 
访问字段A:记录被访问的次数,供换出页面时参考 
修改位M:该页在调入内存后是不是被修改过,若修改,则需要重写到外存

分页系统中的地址变换过程:

1,检索块表(若找到,修改页表项中的访问位) 
2,没有找到,到内存中去查找页表(查找状态位p,已调入,则将页表写入快表,当快表满时,应先按照某种算法换出,写入) 
3,若未调入,则产生缺页中断,请求OS从外存把该页调入内存

内存分配策略和分配算法

在为进程分配内存时,将涉及到三个问题 
1,最小物理块数的确定 
2,物理块的分配策略 
3,物理块的分配算法

1,这里的最小物理块数,是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值的时候,进程将无法进行。如果过多的话,那么将可能造成内存的浪费。 
对于某些功能较强的机器,其指令长度可能要两个或多于两个字节,因而其指令本身有可能跨两个页面,且源地址和目的地址所涉及的区域也有可能跨2个页面。所以要至少分配6个页面 
2,物理块分配策略 
  1,固定分配局部置换:(基于进程的类型)或根据程序员,管理员的建议,为每个进程分配一定数目的物理块,在整个运行期间都不再改变。采用该策略,如果进程在运行中发现缺页,则只能从进程在内存n个页面中选出一个页换出,然后再调入一个页,以保证分配给该进程的内存空间不变。但是:为某个进程分配的物理块难以确定

  2,可变分配全局变量:这可能是最易于实现的一种物理块分配和置换策略,已用于若干OS。在采用这种策略时,先为系统中的每个进程分配一定数目的物理块,而OS中也保持一个空闲物理块队列。当某进程发现缺页时,由系统从空闲物理块队列中取出一个物理块分配给该进程,并将欲调入的页装入其中。这样,凡是产生缺页中断,都将获得新的物理块。仅当空闲物理块队列中的物理块用完时,OS才能从内存中选择一页调出。(随机调出)

  3,可变分配局部置换:为每个进程分配一定数目的物理块,但当某进程发现缺页时,只允许从该进程在内存的页面中选出一页换出。这样,就不会影响其它进程的运行。如果进程在运行中频繁的发生缺页中断,则系统必须为该进程分配若干附加的物理块,直至该进程的缺页率减少到合适的程度为止。同样,若一个进程的运行过程中的缺页率特别低,则此时可适当减少分配给该进程的物理块数

3,物理块分配算法

 1,平均分配算法(可供分配的物理块平均分配给各个进程) 
 2,按比例分配算法(根据进程的大小按比例分配物理块算法) 
 3,考虑优先权的分配算法(为了重要的,紧迫的作业能尽快完成,应为他分配较多的内存空间。通常采取的方法把内存中供分配的所有物理块分为两部分:一部分按比例分配给各进程;另一部分根据各进程的优先权,适当的增加其相应份额,分配给各进程)

内存调度

在进程运行过程中,若所要访问的页面不在内存而需要把它们调入内存,但内存已没有空间,系统必须从内存中调出一页。 
置换算法的好坏,直接影响系统的性能。

1,最佳置换算法(理想化的算法,难于实现) (淘汰的页面将是以后永不使用的,或许是最长(未来时间不再被访问的)),可以获得最低的缺页率

2,先进先出页面置换算法(总是淘汰最先进入内存的页面)

3,最近最久未使用 
  比较好的算法,但要求系统中有较多的支持硬件 ,为了了解一个进程在内存中的各个页面各有多少时间未被进程访问,以及如何快速的直到那一页是最近最久未使用的页面。必须有两类硬件的支持:栈和寄存器。

责任编辑:内存调度
首页 | 电气资讯 | 应用技术 | 高压电器 | 电气设计 | 行业应用 | 低压电器 | 电路图 | 关于我们 | 版权声明

Copyright 2017-2018 电气自动化网 版权所有 辽ICP备17010593号-1

电脑版 | 移动版 原创声明:本站大部分内容为原创,转载请注明电气自动化网转载;部分内容来源网络,如侵犯您的权益请发送邮件到[email protected]联系我们删除。