Demand Paging은 말그대로 프로세스의 필요한 page만 요청해서 사용하는 벙법이다. 현재 사용되지 않는 페이지는 가상 메모리에서 있게되며, 요청이 있을 경우 실제 메모리에 Swap in 되고, 사용이 끝나면 다시 가상 메모리로 Swap out 된다. 이때 어떤 페이지가 실제 메모리에 있고, 어떤 페이지가 swap out되어 가상 메모리에 있는지를 알기 위해서 Valid/Invalid bit set을 추가한다
우선 프로세스가 요구한 페이지가 Frame에 있는지 확인한다. Frame에 없을 경우 Frame이 꽉 찼을 경우 어떤 프레임에 있는 페이지를 쫓아내고 요청된 페이지를 올려야 한다. Frame에 있는 페이지를 쫓아내는 방법을 Replacement Algorithm이라고 한다.
FIFO 기법
FIFO(First-In First-Out) 기법은 주기억 장치에 가장 먼저 적재된 페이지를 교체합니다. 이를 위해서는 페이지들의 주기억 장치 적재 시간을 기록해두어야 하는데, 사용 빈도가 높은 프로그램의 페이지들이 교체될 가능성이 높습니다.
time |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
w |
|
c |
a |
d |
b |
e |
b |
a |
b |
c |
d |
frame 0 |
a- |
a- |
a- |
a- |
a- |
e |
e |
e |
e |
e- |
d |
frame 1 |
b |
b |
b |
b |
b |
b- |
b- |
a |
a |
a |
a- |
frame 2 |
c |
c |
c |
c |
c |
c |
c |
c- |
b |
b |
b |
frame 3 |
d |
d |
d |
d |
d |
d |
d |
d |
d* |
c |
c |
page fault |
|
|
|
|
|
1 |
|
2 |
3 |
4 |
5 |
page(s) loaded |
|
|
|
|
|
e |
|
a |
b |
c |
d |
page(s) removed |
|
|
|
|
|
a |
|
b |
c |
d |
e |
FIFO with Second Chance(CLOCK, Sencd Chance)
FIFO방식에 referece bit을 추가한 방식이다. FIFO를 생각해보면 Queue에서 head부분을 victim으로 선택해서 replace했다. 여기에 각각의 페이지에 reference bit을 추가한다. 즉, 페이지가 한번이라도 호출이 되었다면 reference bit을 1로 만든다. 0은 한번도 호출이 안되었다는 말이다. FIFO방식에서 Queue의 head를 victim으로 선택할때 그 페이지의 reference bit을 체크해서 만약에 0이라면 그냥 replace한다. 왜냐하면 한번도 호출되지 않았다. (즉, 잘 사용 빈도가 적다는 말이다.) 그리고 reference bit이 1이라면 replace하지 않고 다음 페이지로 건너뛴다. 이때, 1이었던 reference bit을 0으로 만든다. 이것이 second-chance다. 즉, 한번의 기회를 더 주겠다는 말이다.
(- Check the reference-bit of the oldest page
- If it is 0, then replace it
- If it is 1, clear the reference-bit, move it to end of list, and continue searching
- Fast and does not replace a heavily used page, The worst case may take a long time)
This policy is similar to LRU and FIFO. Whenever a page is referenced, the use bit is set. When a page must be replaced, the algorithm begins with the page frame pointed to. If the frame's use bit is set, it is cleared and the pointer advanced. If not, the page in that frame is replaced. Here the number after the page is the use bit; we'll assume all pages have been referenced initially
time |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
w |
|
c |
a |
d |
b |
e |
b |
a |
b |
c |
d |
frame 0 |
a |
a/1- |
a/1- |
a/1- |
a/1- |
e/1 |
e/1 |
e/1 |
e/1 |
e/1- |
d/1 |
frame 1 |
b |
b/1 |
b/1 |
b/1 |
b/1 |
b/0- |
b/1- |
b/0 |
b/1 |
b/1 |
b/0 |
frame 2 |
c |
c/1 |
c/1 |
c/1 |
c/1 |
c/0 |
c/0 |
a/1 |
a/1 |
a/1 |
a/0 |
frame 3 |
d |
d/1 |
d/1 |
d/1 |
d/1 |
d/0 |
d/0 |
d/0- |
d/0- |
c/1 |
c/0 |
page fault |
|
|
|
|
|
1 |
|
2 |
|
3 |
4 |
page(s) loaded |
|
|
|
|
|
e |
|
a |
|
c |
d |
page(s) removed |
|
|
|
|
|
a |
|
c |
|
d |
e |
무작위 기법
무작위(Random) 기법은 원칙없이 임의로 교체 대상 페이지를 선정하는 기법으로, 교체될 페이지를 선정하는 오버헤드는 적지만 페이지 부재 횟수를 줄이려는 어떠한 시도도 하지 않습니다.
NRU or NUR(Not-Recently-Used or Not Used Recently) 기법
NUR(Not Used Recently) 기법은 적은 오버헤드로 LRU 기법의 성능을 내기 위한기법으로, 이 기법에서는 근래에 쓰이지 않은 페이지는 가까운 미래에도 쓰이지 않을 가능성이 많기 때문에 이러한 페이지를 호출되는 페이지와 교체합니다. NUR 기법에서는 참조 비트와 갱신 비트의 조합을 검사하여 페이지를 교체합니다. 참조 비트는 일정 주기마다 '0' 으로 재설정되며, 이후 해당 페이지가 참조되면'1' 로 설정됩니다. 갱신 비트는 내용이 갱신되었을 경우 '1'로 설정되어 해당 페이지의 내용을 디스크로 옮겨야 함을 나타냅니다.
(-Randomly pick a page from the following (in order)
1)Not referenced and not modified
2)Not referenced and modified
3)Referenced and not modified
4)Referenced and modified
- Easy to implement, Not very good performance, takes time to classify)
This policy selects for replacement a random page from the following classes (in the order given): not used or modified, not used but modified, used and not modified, used and modified. In the following, assume references 2, 4, and 7 are writes. The two numbers written after each page are the use and modified bits, respectively.)
time |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
w |
|
c |
a* |
d |
b* |
e |
b |
a* |
b |
c |
d |
frame 0 |
a |
a/00 |
a/11 |
a/11 |
a/11 |
a/01 |
a/01 |
a/11 |
a/11 |
a/01 |
a/01 |
frame 1 |
b |
b/00 |
b/00 |
b/00 |
b/11 |
b/01 |
b/11 |
b/11 |
b/11 |
b/01 |
b/01 |
frame 2 |
c |
c/10 |
c/10 |
c/10 |
c/10 |
e/10 |
e/10 |
e/10 |
e/10 |
e/00 |
d/10 |
frame 3 |
d |
d/00 |
d/00 |
d/10 |
d/10 |
d/00 |
d/00 |
d/00 |
d/00 |
c/10 |
c/10 |
page fault |
|
|
|
|
|
1 |
|
|
|
2 |
3 |
page(s) loaded |
|
|
|
|
|
e |
|
|
|
c |
d |
page(s) removed |
|
|
|
|
|
c |
|
|
|
d |
e |
LRU 기법
LRU(Least Recently Used) 기법은 참조된 시간을 기준으로 교체될 페이지를 선정하는 기법으로, 가장 오랫동안 참조되지 않은 페이지를 교체합니다. 이를 위해서는 적재되어 있는 페이지가 참조될 때마다 참조 시간을 기록해두어야 하기 때문에 그 오버헤드가 단점입니다. 하지만 LRU 기법은 최적의 기법인 MIN 기법의 성능에 가장 근사하게 접근한 기법으로, 실제로도 가장 많이 사용되고 있는 기법입니다
(어떤 시간값을 캐쉬Data마다 적제해서 구분하지는 않고 position을 변경해서 사용함, 물론 구현은 가능함)
This policy selects for replacement the page that has not been used for the longest period of time
time |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
w |
|
c |
a |
d |
b |
e |
b |
a |
b |
c |
d |
frame 0 |
a |
a |
a |
a |
a |
a |
a |
a |
a |
a |
a |
frame 1 |
b |
b |
b |
b |
b |
b |
b |
b |
b |
b |
b |
frame 2 |
c |
c |
c |
c |
c |
e |
e |
e |
e |
e |
d |
frame 3 |
d |
d |
d |
d |
d |
d |
d |
d |
d |
c |
c |
page fault |
|
|
|
|
|
1 |
|
|
|
2 |
3 |
page(s) loaded |
|
|
|
|
e |
|
|
|
c |
d |
|
page(s) removed |
|
|
|
|
c |
|
|
|
d |
e |
|
stack (top) |
|
c |
a |
d |
b |
e |
b |
a |
b |
c |
d |
|
|
-- |
c |
a |
d |
b |
e |
b |
a |
b |
c |
|
|
-- |
-- |
c |
a |
d |
d |
e |
e |
a |
b |
stack (bottom) |
|
-- |
-- |
-- |
c |
a |
a |
d |
d |
e |
a |
LFU or MFU 기법
LFU(Least Frequently Used) 기법은 참조된 횟수를 기준으로 교체될 페이지를 선정하는 기법으로, 가장 참조 횟수가 적은 페이지를 교체합니다. 이를 위해서는 페이지들이 참조될 때마다 참조 횟수를 누적시켜야 하기 때문에, 그 오버헤드가 단점입니다. 또한 최근에 적재된 페이지가 이후 참조될 가능성이 많음에도 불구하고 참조 횟수가 적어 교체될 가능성이 있습니다.
Least Frequently Used (LFU): ``replace page with smallest count''
Most Frequently Used (MFU): ``replace page with largest count''
LRU 알고리즘의 구현 예
public class LRUCache<K,V> {
private static final float hashTableLoadFactor = 0.75f;
private LinkedHashMap<K,V> map;
private int cacheSize;
/**
* Creates a new LRU cache.
* @param cacheSize the maximum number of entries that will be kept in this cache.
*/
public LRUCache (int cacheSize) {
this.cacheSize = cacheSize;
int hashTableCapacity = (int)Math.ceil(cacheSize / hashTableLoadFactor) + 1;
map = new LinkedHashMap<K,V>(hashTableCapacity, hashTableLoadFactor, true) {
// (an anonymous inner class)
private static final long serialVersionUID = 1;
@Override protected boolean removeEldestEntry (Map.Entry<K,V> eldest) {
return size() > LRUCache.this.cacheSize; }}; }
public synchronized V get (K key) {
return map.get(key); }
public synchronized void put (K key, V value) {
map.put (key,value); }
public synchronized void clear() {
map.clear(); }
public synchronized int usedEntries() {
return map.size(); }
public synchronized Collection<Map.Entry<K,V>> getAll() {
return new ArrayList<Map.Entry<K,V>>(map.entrySet()); }
} // end class LRUCache
public static void main (String[] args) {
LRUCache<String,String> c = new LRUCache<String,String>(3);
c.put ("1","one"); // 1
c.put ("2","two"); // 2 1
c.put ("3","three"); // 3 2 1
c.put ("4","four"); // 4 3 2
if (c.get("2")==null) throw new Error(); // 2 4 3
c.put ("5","five"); // 5 2 4
c.put ("4","second four"); // 4 5 2
// Verify cache content.
if (c.usedEntries() != 3) throw new Error();
if (!c.get("4").equals("second four")) throw new Error();
if (!c.get("5").equals("five")) throw new Error();
if (!c.get("2").equals("two")) throw new Error();
// List cache content.
for (Map.Entry<String,String> e : c.getAll())
System.out.println (e.getKey() + " : " + e.getValue());
}
관련 URL 및 출처
- replacement algorithm관련
http://www.sci.csuhayward.edu/~billard/cs4560/node15.html
http://people.msoe.edu/~mccrawt/resume/papers/CS384/mccrawt_cs384_virtual.pdf
http://bcook.cs.georgiasouthern.edu/cs523/lectureb.htm
http://nob.cs.ucdavis.edu/classes/ecs150-1999-02/mm-pagexample.html
http://www.javastudy.co.kr/docs/jhan/javaadvance/8-6.htm#one
http://www.source-code.biz/snippets/java/6.htm
http://cherrykyun.tistory.com/146
http://jakarta.apache.org/jcs/