59.페이지 교체기법 중 시간 오버헤드를 줄이기 위해 각 페이지 마다 참조 비트와 변형 비트를 두는 교체기법은?

해설

페이지 교체 알고리즘 페이지 부재가 발생하면 새로운 페이지를 주기억장치로 들여와야 한다. 이때 메모리에 공간이 없으면 이미 올라와 있던 페이지중 하나를 희생시키고 그곳으로 새페이지를 load해야 한다. 페이지 교체 알고리즘은 희생시킬 페이지를 고를 때 사용되는 알고리즘을 말한다. 이러한 알고리즘들의 주요한 평가 기준은 페이지 부재율이다. 1)Belady의 최적 알고리즘(OPT 알고리즘) Belady가 제안한 것으로 페이지 부재를 최소화하기 위해서 향후 가장 오랫동안 사용되지 않을 페이지를 교체시키는 알고리즘이다. 성능이 가장 좋지만 프로세스가 향후 어떤 페이지를 필요로 할지를 미리 알 수 없기 때문에 실제 구현은 불가능하다. 2)FIFO(First- in First-Out) 기법 FIFO페이지 대치기법은 주기억장치에 가장 먼저 들어온 페이지를 교체시킨다. FIFO의 모순 일반적으로 프로세스에게 더 많은 페이지 프레임을 할당할수록 더 적게 페이지 부재가 발생해야 한다. 그러나 실제 FIFO페이지 대치 기법에서는 프로세스에게 더 많은 수의 페이지 프레임을 할당함에도 오히려 페이지 부재가 더 많이 발생하는 경우가 생길 수 있는데 이러한 현상을 FIFO모순이라고 한다. 3) LRU(Least Recently Used) 기법 페이지 대치가 필요할 때마다 오랫동안 사용되지 않은 페이지를 희생시킨다. 이러한 LRU 페이지 대치 기법에서는 FIFO모순이 발생되지 않아 스택 알고리즘이라고도 한다. 4) LFU(least frequently used)기법 참조된 횟수가 가장 적은 페이지를 교체시키는 방법이다. 5)NUR(not used resently) 기법 NUR알고리즘은 최근 사용된 적이 있는지 여부를 알기 위해 참조 비트를 사용하며 참조 비트는 해당 페이지가 access될 때마다 set되고 주기적으로 reset된다. 또 희생시킬 그 페이지를 먼저 디스크에서 원래 읽어온 이후 내용이 변형됐다면 그 페이지를 먼저 디스크에 write시킨 후 빼앗아야 한다. 따라서 변형 페이지는 페이지 부재 발생시 디스크 write 한번, read 한번을 해야 하므로 오버헤드가크다. NUR은 이러한 점에 착안한 기법으로 희생시킬 페이지는 가급적 참조가 안된 페이지 변형된 적이 없는 페이지를 선택한다. [출처] 페이지 교체 및 할당 알고리즘|작성자 갤러리