운영 체제의 페이지 교체 알고리즘


난이도 중급
자주 묻는 질문 아마존 인식하고있는 팩트 셋 Microsoft 페이팔
운영체제 이론

페이지 교체 란 무엇입니까?

최신 운영 체제는 메모리 관리를 위해 페이징을 사용하며 페이지 교체가 필요한 경우가 많습니다. 페이지 교체는 현재 메모리에있는 페이지를 필요하지만 메모리에없는 페이지로 교체하는 프로세스입니다. 이러한 조건을 페이지 폴트라고합니다.

페이지 교체 알고리즘의 목표는 전체 성능을 높이기 위해 페이지 오류 수를 줄이는 것입니다. 페이지 교체를위한 많은 알고리즘이 있습니다. 여기서 몇 가지를 논의하고 있습니다.

선입 선출 (FIFO)

선입 선출 페이지 교체 알고리즘 페이지 교체를위한 가장 간단한 알고리즘입니다. 모든 페이지를 추적하기 위해 대기열을 유지합니다. 우리는 항상 대기열 끝에 새 페이지를 추가합니다. 때 변발 가득 차고 페이지 폴트가있는 경우 큐 맨 앞에있는 페이지를 제거하고 큐 끝에 새 페이지를 추가합니다.
이러한 방식으로 우리는 선입 선출 기술을 유지합니다. 즉, 메모리에 먼저 삽입 된 페이지가 먼저 메모리에서 제거됩니다.

페이지 참조 문자열은 {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}이고 총 4 개의 페이지 슬롯이 있습니다. 그때,

운영 체제의 페이지 교체 알고리즘

벨라 디의 변칙

Belady는 일부 페이지 참조 문자열에서 페이지 슬롯을 늘리면 더 많은 페이지 오류가 발생할 수 있음을 증명했습니다.


3 개의 페이지 슬롯과 2 개의 페이지 슬롯이있는 페이지 참조 문자열 {1, 0, 3, 2, 4, 3, 2, 1, 0, 4, 3, 4}를 고려하십시오.
페이지 슬롯이 3 개인 페이지 폴트 = 3
페이지 슬롯이 4 개인 페이지 폴트 = 4

최적의 페이지 교체

이 알고리즘은 앞으로 사용할 페이지를 안다면 페이지 교체 기술을 최적화 할 수 있다고 말합니다.
Optimal Page Replacement 알고리즘에 따르면 앞으로 가장 적게 사용되는 페이지를 교체하는 것이 항상 최적입니다.

페이지 참조 문자열은 {2, 3, 4, 2, 1, 3, 7, 5, 4, 3}이고 총 3 개의 페이지 슬롯이 있습니다. 그때,

운영 체제의 페이지 교체 알고리즘

최근에 가장 적게 사용됨

이 알고리즘은 캐싱 기술을 기반으로합니다. 알고리즘은 최근에 가장 적게 사용 된 페이지를 대체한다고 말합니다.

페이지 참조 문자열은 {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4}이고 총 3 개의 페이지 슬롯이 있습니다. 그때,

운영 체제의 페이지 교체 알고리즘

선입 선출 구현

운영 체제의 페이지 교체 알고리즘을위한 Java 코드

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

class FirstInFirstOutPageReplacement {
    private static int pageFaults(int[] pageString, int pageSlots) {
        int faults = 0;

        // Set to store the elements present in queue, used to check if a page is present or not
        HashSet<Integer> set = new HashSet<>();
        // Queue to maintain the order of insertion
        Queue<Integer> queue = new LinkedList<>();

        // traverse the page string
        for (int i = 0; i < pageString.length; i++) {
            // if there are some empty slots
            if (queue.size() < pageSlots) {
                if (!set.contains(pageString[i])) {
                    // and the current page is missing
                    // add the page to set
                    set.add(pageString[i]);
                    // add the page to queue
                    queue.add(pageString[i]);
                    // it is a page fault, increment faults
                    faults++;
                }
            } else {
                // there are no empty slots and if current page is absent
                if (!set.contains(pageString[i])) {
                    // remove the first page in queue
                    int removedPage = queue.poll();
                    // remove the page from set
                    set.remove(removedPage);

                    // add the new page to set
                    set.add(pageString[i]);
                    // add the new page to queue
                    queue.add(pageString[i]);

                    // it is page fault, increment faults
                    faults++;
                }
            }
        }

        // return total number of page faults
        return faults;
    }

    public static void main(String[] args) {
        // Example
        int pageString[] = new int[] {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1};
        int pageSlots = 4;
        System.out.println(pageFaults(pageString, pageSlots));
    }
}
Page String = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}
Page Slots = 4
8

운영 체제의 페이지 교체 알고리즘을위한 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 

int pageFaults(int *pageString, int pageSlots, int n) {
    int faults = 0;
    
    // Set to store the elements present in queue, used to check if a page is present or not
    unordered_set<int> set;
    // Queue to maintain the order of insertion
    queue<int> q;
    
    // traverse the page string
    for (int i = 0; i < n; i++) {
        // if there are some empty slots
        if (q.size() < pageSlots) {
            if (set.find(pageString[i]) == set.end()) {
                // and the current page is missing
                // add the page to set
                set.insert(pageString[i]);
                // add the page to queue
                q.push(pageString[i]);
                // it is a page fault, increment faults
                faults++;
            }
        } else {
            // there are no empty slots and if current page is absent
            if (set.find(pageString[i]) == set.end()) {
                // remove the first page in queue
                int removedPage = q.front();
                q.pop();
                // remove the page from set
                set.erase(removedPage);
                
                // add the new page to set
                set.insert(pageString[i]);
                // add the new page to queue
                q.push(pageString[i]);
                
                // it is page fault, increment faults
                faults++;
            }
        }
    }
    
    return faults;
}

int main() {
    // Example
    int pageString[] = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1};
    int pageSlots = 4;
    cout<<pageFaults(pageString, pageSlots, sizeof(pageString) / sizeof(pageString[0]))<<endl;
    
    return 0;
}
Page String = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}
Page Slots = 4
8

복잡성 분석

시간 복잡성

HashSet을 사용하면 주어진 알고리즘을 선형 시간으로 실행할 수 있습니다. 따라서 알고리즘은 선형 시간 복잡도를 갖습니다. 의 위에).

공간 복잡성

O (페이지 슬롯), 우리는 대기열에 pageSlots 수의 페이지 만 유지했습니다. 따라서 공간 복잡성은 pageSlot에 따라 다릅니다.