【操作系统专题】其他问题：调度算法，文件系统等

共以下 1 个回答

• 秊 永久会员 2023年9月5日 下午2:27

  1、页面调度算法介绍一下

  由于虚拟内存的存在，如果某个进程所需要访问的页面不在物理内存中，而是在磁盘空间上，此时 CPU 就会产生一个缺页中断，请求操作系统将所缺页调到物理内存中，如果此时刚好内存里装的页面满了，操作系统就带根据一定的算法来选取将哪些页换出，将缺页换入。具体的页面置换算法大约有五种，基本目标都是尽可能的在一段时间内减少页面的换入换出次数。

  理想情况下效率最高的的置换算法是“最佳页面置换算法”，思想是，置换在「未来」时间内最长时间不访问的页面。这个算法在实际系统中无法实现，因为程序访问页面是动态的，我们无法预测在以后的时间需要访问哪个页面。但它像是一个标准，我们可以用它来跟我们自己的算法效率作比较，越接近就代表我们的算法越好。

  既然我们无法预知页面在下一次访问时的时间，那我们可以通过选择在内存中驻留时间最长的页面进行置换，这是“先进先出算法 FIFO”的思路，在实践中效率不是很高，因为某些页面可能需要持续使用，自然驻留的时间就长，一不小心换出就还带花时间换入。

  再改进一下就是使用最近最久未使用 LRU 算法，思路是发生缺页时，选择到目前为止，最长时间没有被访问的页面，由此推断它以后被访问的概率也很小。这种算法的效率还不错，但代价有点高，因为需要在内存中维护一个所有页面的链表，最近最多使用的在表头，最近最少使用的在表尾。如果某个时刻需要访问的页面在链表中的某个位置，就需要遍历整个链表然后放到表头，遍历这个过程是$O(N)$ 很耗费时间。实践中也很少使用。

  那有没有同时结合 FIFO 和 LRU 优点的算法，有，就是“时钟页面置换算法”，它将所有的页面都保存在一个类似钟表的环形链表中，并将每一个页面都附加一个标志位 0 或 1，用来表示最近是否有使用，同时用一个指针指向最老的页面。当发生缺页中断时，看指针所指向的页面，如果它的标志位为 0，则就将它置换出去，再将新页插到现在这个位置。如果标志位为 1，就将它改为 0 但不置换，继续看下一个页面。

  clock 算法改进

  也可以单独对 LRU 算法进行改进，使用 LFU 最不常使用算法。它的思路是将每个页面设置一个「访问计数器」，每当一个页面被访问时，它的计数器就 + 1，发生缺页中断时，淘汰计数器值最小的那个。思路还是比较好理解的，但其中有很多问题。首先就是每个页面都要加一个计数器，这个硬件成本比较高。其次是如果在所有页面中快速找到计数值最小那个？以及怎么只根据计数值来判断某个页面在最近一段时间内的访问频率？还有计数值超了咋办？（参考 Redis 淘汰键值对的 LFU 算法实现）。

  2、操作系统读写磁盘，影响磁盘读写时间的因素有哪些？

  首先是“读写方式”，传统的机械硬盘需要磁头和磁头臂与磁盘配合，先找到对应的磁道才能读取数据。而固态硬盘则是通过电学信号的传输完成对闪存芯片的读写，主要依靠的是电学信号，没有寻道时间，速度很快。

  对于机械硬盘来说，影响读写时间的因素主要有硬盘段转速，是连续 IO 还是随机 IO，以及硬盘中的内置缓存大小。硬盘的转速越快，磁头寻道的速度就越快，读写就越快。连续 IO 的话，磁盘只需寻一次道，接着顺序读写即可，随机 IO 则需要多次寻道。磁盘缓存的话就是利用时间局部性原理，一旦某个数据被访问，它在不久的将来可能再次被访问。将它放在缓存中可以方便以后快速读取。

  3、操作系统的原子操作是怎么实现的？

  见【并发专题】CAS连环炮

  0 赞同 0 条回复

  登录以回复