首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 互联网 >

百度口试(磁盘操作)

2012-08-10 
百度面试(磁盘操作)在处理磁盘数据时,需要首先将其读入内存才能进行处理。如果要读取的数据已经在内存中,则

百度面试(磁盘操作)
在处理磁盘数据时,需要首先将其读入内存才能进行处理。如果要读取的数据已经在内存中,则可以直接 访问内存。通常来说内存是有限的,因此要读取新的数据时必须覆盖内存中一部分原有的数据。假设现在有n块同样大小的数据,内存一共可以容纳m块数据。现在给出 一系列对这些数据的读取请求,要求它们必须按照给定的顺序被读取,同时要求读取磁盘 的次数尽可能地少。请简述一个策略满足这样的要求。



整个系统分为三部分:

1.内存,可以存放m块数据

2.外存磁盘,有n块数据

3.数据队列,存放了数据读取的顺序 (一系列对数据的读取请求)

   例如n为3 (1,2,3) 此时 数据队列可能是 (1,2,1,3,2,2)等等



内存呢,可以有两种状态

1.内存未满

2.内存已满



策略:



一、如果内存未满,对于要读取的数据,首先查找内存中是否已经存在,如果存在则直接从内存中读取,如果不存在则从硬盘中读取,这样既可以防止内存中有重复数据出现,又能尽可能少的读取磁盘数据

二、如果内存已经满,就是n>m时呗,这时候对于读取的数据,首先查找内存中是否已经存在,如果存在则直接读取内存中的数据,如果不存在,则要替换内存中的数据,即旧的被移走,新的数据移进。



其中替换算法有:

内存中的m个数据,依次检查待读的n-m个数据,是否在内存中存在,如果存在则内存中的相应数据不能替换,对于内存中的数据没有对应的n-m个数据的可以替换。

只可以保证尽可能少的读取磁盘数据。



这个题,按照数据队列读数据时,内存中有的就直接从内存中读取,没有的就从磁盘中读取,其中还涉及到内存是否已满时操作的差异,如果内存已满则要用旧的替换新的。

热点排行