操作系统【十二】

6、缓冲管理

为了缓和CPU和I/O设备速度不匹配的矛盾,提高CPU和I/O设备的并行性,在现代OS中,几乎所有的I/O设备与处理机交换数据时,都用了缓冲区。

引入缓冲区的原因有很多,可归结为以下几点:

(1) 缓和CPU与I/O设备间速度不匹配的矛盾。

(2) 减少对CPU的中断频率,放宽对CPU中断响应时间的限制。

(3) 解决数据粒度不匹配的问题。

(4) 提高CPU和I/O设备之间的并行性。

(1)单缓冲

每当用户进程发出一个I/O请求时,操作系统便在主存中为之分配一个缓冲区,假定从磁盘把一块数据输入到缓冲区的时间为T,操作系统将该缓冲区中的数据传送到用户区的时间为M,而CPU对这一块数据处理(计算)的时间为C,由于T和C是可以并行的,当T>C时,系统对每一块数据的处理时间为M+T,反之,为M+C,系统对每一块数据的处理时间为Max(C,T) + M

在字符设备输入时,缓冲区用于暂存用户输入的一行数据,在输入期间,用户进程被挂起以等待数据输入完毕,在输出时,用户进程将一行数据输入到缓冲区后,继续进行处理,当用户进程已有第二行数据输出时,如果第一行数据尚未被提取完毕,则此时用户进程应该阻塞。

(2)双缓冲

为了加快输入和输出的速度,提高设备利用率,人们又引入了双缓冲区机制,称为缓冲对换,在设备输入时,先将数据送入第一个缓冲区,装满后便转向第二个缓冲区,此时操作系统可以从第一缓冲区中移出数据,并送入用户进程,接着由CPU对数据进行计算,在双缓冲时,系统处理一块数据的时间可以粗略地认为是Max(C,T),如果C<T,可使块设备连续输入,如果C>T,则可使CPU不必等待设备输入。

对于字符设备,若采用行输入方式,则采用双缓冲通常能消除用户的等待时间,即用户在输入完第一行后,在CPU执行第一行中的命令时,用户可继续向第二缓冲区输入下一行数据。

双机通讯时缓冲区的设置

§若我们在实现两台机器之间的通信时,仅为它们配置了单缓冲,那么它们之间任意时刻都只能实现单方向的数据传输,而绝不允许双方同时向对方发送数据。

§为了实现双向数据传输,必须在两台机器中都设置两个缓冲区,一个用作发送缓冲区,另一个用作接收缓冲区。

(3)循环缓冲

当输入与输出或生产者与消费者的速度基本相匹配时,采用双缓冲能获得较好的效果,可使生产者和消费者基本上能并行操作,但若两者速度相差甚远,双缓冲的效果则不够理想,因此,引入了多缓冲机制,可将多个缓冲组织成循环缓冲形式。对于用作输入的循环缓冲,通常是提供给输入进程或计算进程使用,输入进程不断向空缓冲去输入数据,而计算进程则从中提取数据进行计算。

循环缓冲区的组成如下

① 多个缓冲区,在循环缓冲区中包括多个缓冲区,每个缓冲区的大小相同,作为输入的多缓冲区可分为三种类型,用于装输入数据的空缓冲区R已装满数据的缓冲区G以及计算进程正在使用的先行工作缓冲区C

② 多个指针,作为输入的缓冲区可设置三个指针,用于指示计算进程下一个可用缓冲区G的指针Nextg指示输入进程下次可用的空缓冲区R的指针Nexti以及用于指示计算进程正在使用的缓冲区C的指针Current

计算进程和输入进程可以利用下述两个过程来使用循环缓冲区(循环缓冲的使用)。

① Getbuf过程,当计算进程要使用缓冲区中的数据时,可调用Getbuf过程,该过程将由指针Nextg所指示的缓冲区提供给进程使用,相应的,须把它改为现行工作缓冲区,并将Current指针指向该缓冲区的第一个单元,同时将Nextg移向下一个G缓冲区,类似地,当输入进程要使用空缓冲区来装入数据时,调用Getbuf过程,由该过程将指针Nexti所指示的缓冲区提供给输入进程使用,同时将Nexti指针移向下一个R缓冲区。

② Releasebuf过程,当计算进程把C缓冲区中的数据提取完毕时,便调用Releasebuf过程,将缓冲区C释放,此时,把该缓冲区由当前(现行)工作缓冲区C改为空缓冲区R,类似地,当输入进程把缓冲区装满时,也应该调用Releasebuf过程,将该缓冲区释放,并改为G缓冲区。

使用输入循环缓冲,可使输入进程和计算进程并行执行(进程同步),相应地,指针Nexti和指针Nextg将不断地沿着顺时针方向移动,这样就会出现如下两种情况。

① Nexti指针追赶上Nextg指针,这意味着输入进程的速度大于计算进程处理数据的速度,已把全部可用的空缓冲区装满,再无缓冲区可用,此时,输入进程应该阻塞,直到计算进程把某个缓冲区中的数据全部提取完,使之成为空缓冲区R,并调用Releasebuf过程将它释放时,才将输入进程唤醒,这种情况称为系统受计算限制

② Nextg指针追赶上Nexti指针,这意味着输入数据的速度低于计算进程处理数据的速度,使全部装有输入数据的缓冲区都被抽空,再无装有数据的缓冲区供计算进程提取数据,这时,计算进程应该阻塞,直至输入进程又装满某个缓冲区,并调用Releasebuf过程将它释放时,才去唤醒计算进程,这种情况称为系统受I/O限制

(4)缓冲池

上述的缓冲区仅适用于某特定的I/O进程和计算进程,因而它们属于专用缓冲,当系统较大时,将会有许多这样的循环缓冲,这样会消耗大量的内存空间,而且利用率不高,为了提高缓冲区的利用率,引入缓冲池,在池中设置了多个可供若干个进程共享的缓冲区。缓冲池中的各缓冲区是系统的公共资源,可供各进程共享,并由操作系统统一分配和管理。

对于既可以用于输出的共用缓冲池,其中至少包含有一下三种类型的缓冲区。

① 空(闲)缓冲区。

② 装满输入数据的缓冲区。

③ 装满输出数据的缓冲区。

为了管理方便,将相同类型的缓冲区链成一个队列,形成了空缓冲队列emq、输入队列inq、输出队列outq。

还具有四种工作缓冲区:

  • 用于收容输入数据的工作缓冲区
  • 用于提取输入数据的工作缓冲区
  • 用于收容输出数据的工作缓冲区
  • 用于提取输出数据的工作缓冲区。

缓冲区可以工作在收容输入、提取输入、收容输出、提取输出四种工作方式下。

收容输入,在输入进程需要输入数据时,便调用Getbuf(emp)过程,从空缓冲队列的队首取出一个空缓冲区,把它作为收容输入工作缓冲hin,然后,把数据输入其中,装满后再调用Putbuf(inq,hin)过程,将该缓冲区挂在输入队列上。

提取输入,当计算进程需要输入数据时,调用Getbuf(inq)过程,从输入队列队首取出一个缓冲区,作为提取输入工作缓冲区sin,计算进程从中提取数据,计算进程用完该数据后,再调用Putbuf(emq,sin)过程,将该缓冲区挂到空缓冲队列emq上。

收容输出,当计算进程需要输出时,调用Getbuf(emq)过程从空缓冲区队列emq的队首取出一个空缓冲区,作为收容输出工作缓冲区hout,当其中装满输出数据后,又调用Putbuf(outq,hout)过程,将该缓冲区挂在outq末尾。

提取输出,由输出进程调用Getbuf(outq)过程,从输出队列队首取出一个装满输出数据的缓冲区,作为提取输出工作缓冲区sout,在数据提取完后,再调用Putbuf(emq,sout)过程,将该缓冲区挂在空缓冲队列末尾。

7、磁盘存储器的管理

(1)磁盘性能简述

磁盘设备包括一个或多个物理盘片,每个盘片分一个或两个存储面,每个磁盘面被组织成若干个同心环,这种环称为磁道,各磁道之间留有必要的缝隙。每条磁道上可存储相同数目的二进制位,这样,磁盘密度即每英寸中所存储的位数,显然是内层磁道密度较外层磁道的密度高,每条磁道又被逻辑上划分成若干个扇区,一个扇区称为一个盘块(数据块)或称为磁盘扇区。一个物理记录存储在一个扇区上,磁盘上存储的物理记录块数目是由扇区数、磁道数以及盘面数决定的。

磁盘可以从不同的角度进行分类:硬盘和软盘、单片盘和多片盘、固定头磁盘和活动头磁盘等。

固定头磁盘:每条磁道都有一个读/写磁头,可对磁道并行读/写,I/O速度快,适用于大容量磁盘。

移动头磁盘:每个盘面一个磁头,该磁头能移动以进行寻道。只能进行串行读/写, I/O速度较慢,但结构简单,曾经广泛用于中、小型磁盘设备中。

  • 寻道时间Ts:是把磁臂从当前位置移动到指定磁道上所经历的时间。
    • 该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和, 即Ts=m×n+s
  • 旋转延迟时间Tr:是指定扇区移动到磁头下面所经历的时间。
    • Tr=1/2r
    • r为磁盘每秒钟的转数
    • 如:硬盘转速为15000r/min (15000转/分钟) 每转=60000ms/15000r=4ms,平均延迟2 ms
  • 传输时间Tt:指数据从磁盘读出,或向磁盘写入数据所经历的时间。
    • Tt = b/rN
    • 每次所读/写的字节数b;
    • r为磁盘每秒钟的转数;
    • N为一条磁道上的字节数
  • 则访问时间Ta =Ts + Tτ+ Tt
    • Ta = Ts + b/rN + 1/2r
    • 其中Ts=m×n+s

在访问时间中,寻道时间和旋转延迟时间,基本上都与所读/写数据的多少无关,而且它通常是占据了访问时间的大头,尤其是寻道时间。因而,适当地集中数据(不要太零散)传输,将有利于提高传输效率。

(2)磁盘调度

磁盘是多个进程共享的设备,当有多个进程都要求访问磁盘时,应采用一种最佳的调度算法,使各进程对磁盘的平均访问时间最小。由于在访问磁盘中,主要是寻道时间,因此,磁盘调度的目标是使磁盘的平均寻道时间最少。目前常用的磁盘调度算法有先来先服务、最短寻道时间优先及扫描等算法。

先来先服务(FCFS, First Come First Service),这是一种最简单的磁盘调度算法,其根据进程请求访问磁盘的先后顺序进行调度.

优点:公平、简单,每个进程的请求都能得到依次处理,不会出现某个进程的请求长期得不到满足的情况。

缺点:未对寻道进行优化,致使平均寻道时间可能较长。仅适用于请求磁盘I/O的进程数目较少的场合

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

优点:使每次寻道时间最短

缺点:不能保证平均寻道时间最短;可能导致距离远的进程总也得不到服务

扫描(SCAN)算法,SSTF算法虽然能获得较好的寻道性能,但可能会导致某个进程发生饥饿现象,因为只要有新进程的请求到达,且其所要访问的磁道与磁头当前所在磁道的距离较近,这种新进程的I/O请求必然先满足,对SSTF算法修改后形成SCAN算法,可防止老进程出现饥饿现象。该算法不仅考虑到欲访问的磁盘与当前磁道之间的距离,更优先考虑的是磁头当前的移动方向。例如,当磁头正在自里向外移动时,SCAN算法所考虑的下一个访问对象,应是其欲访问的磁道既在当前磁道之外,又是距离最近的。其类似电梯的运行,也称为电梯调度算法。

缺点:刚移过的磁道的等待时间长

循环扫描(CSCAN)算法,SCAN算法既能够获得较好的寻道性能,又能防止饥饿现象,但是,当磁头刚从里向外移动而越过了某个磁道时,恰好又有一进程请求访问此磁道,这时,该进程必须等待,待磁头继续从里向外,然后再从外向里扫描完所有要访问的磁道后,才处理该进程的请求,致使该进程的请求被大大地推迟。为了减少这种延迟,CSCAN算法规定磁头单向移动,例如,致使自里向外移动,当磁头移到最外的磁道访问后,磁头立即返回最里的欲访问的磁道,即将最小的磁道号紧接着最大的磁道号构成循环,进行循环扫描

NStepSCAN算法,在SSTF、SCAN、CSCAN几种调度算法中,都可能会出现磁臂停留在某处不动的情况,例如,有一个或几个进程对某个磁道具有较高的访问频率,即这些进程反复请求对某一磁道的I/O操作,从而垄断了整个磁盘设备,这一现象称为磁臂粘着。

NStepSCAN算法将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按FCFS算法一次处理这些子队列,当正在处理某子队列时,如果又出现了新的磁盘请求,便将新的请求进程放入其他队列,这样就避免了出现粘着现象。当N很大时,会使N步扫描算法性能接近于SCAN算法,当N=1时,退化为FCFS算法。

FSCAN算法,其是NStepSCAN的简化,即FSCAN只将磁盘请求队列分成两个子队列,一个是由当前所有请求磁盘I/O的进程所形成的队列,由磁盘调度按SCAN算法进行处理,在扫描期间,将新出现的请求磁盘I/O的进程放入另一个等待处理的请求队列。这样,所有的新请求都被推迟到下一次扫描时处理。

(3)磁盘高速缓存

利用内存中的存储空间来暂存从磁盘上读出的一系列盘块中的信息,这里的高速缓存是一组在逻辑上属于磁盘,物理上是驻留在内存中的盘块,高速缓存在内存中可以分成两种形式,第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存,其大小是固定的,不会受到应用程序的影响。第二种是把所有未利用的内存空间变为一个缓冲池,供请求分页系统和磁盘I/O时(作为磁盘高速缓存)共享。此时的高速缓存大小不再固定。

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~