×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,101,837명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

페이징(Paging) 기법


보조기억장치를 이용하여 가상 메모리를 같은 크기의 블록으로 나눈것을 페이지라 하고 

RAM을 페이지와 같은 크기로 나눈 것을 프레임이라 할 때


페이징 기법이란 사용하지 않는 프레임을 페이지에 옮기고 필요한 데이터를 페이지 단위로 프레임에 옮기는 기법이다.

이때 페이지와 프레임을 매핑 시키기 위해 Paging Table을 사용한다.


페이징 기법을 사용하면 연속적이지 않은 공간을 활용 할 수 있기에 메모리 외부 단편화 문제를 해결 할 수 있다.

하지만 하나의 페이지의 limit가 4kb인데 3kb짜리 데이터가 페이지에 담기면 내부 단편화는 여전히 생길 수 있다.


이때 이를 해결하기 위해 페이지를 엄청 작은 단위로 나누어도 되지만, 너무 많이 페이지를 나누면 매핑하는데 비용이 너무 많이 들기 때문에 적절히 페이지 크기를 조절해야한다.


이러한 페이징은 물리 메모리(RAM)에서 사용되지 않고 있는 메모리 영역이 보조 기억장치에 일시적으로 저장되는 과정을 말한다.

이미 페이징 된 페이지(물리 메모리에서 보조 기억장치에 옮겨진 페이지)에 접근이 발생하면 프로세서는 페이지 폴트(Page Fault)를 발생시키고 OS는 페이징된 메모리 내용이 존재하는 파일(페이징 파일)에서 해당 페이지 내용을 읽어 메모리에 적재 시킨다.





페이징 알고리즘(paging algorithm)


페이지 부재(Page Fault)가 발생했을 때, 주기억장치의 모든 페이지 프레임이 사용 중이라면 어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 것을 말한다.


(1) OPT(Optimal Replacement, 최적 교체)

- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법

- 각 페이지의 호출순서와 참조상황을 미리 예측해야하므로 실현 가능성이 희박


(2) FIFO(First In First Out)

- 각 페이지가 주기억장치에 적재될 때마다 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법

- 이해하기 쉽고, 프로그래밍 및 설계가 간단하며, 벨레이디의 모순현상이 발생함

Belady's Anomaly : FIFO 알고리즘에서 기존 페이지 프레임의 개수를 늘리면 Page Fault 발생이 감소해야하나, 오히려 늘어나는 현상


FIFO :: 5번 Page Fault


실행

3

1

2

4

1

2

6

프레임

번호

3

3

3

4

4

4

4

1

1

1

1

1

6

2

2

2

2

2



Time

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Page

1

2

6

1

4

5

1

2

1

4

5

6

4

5

Main Memory

1

1

1

1

1

2

6

4

4

4

4

5

1

2

 

2

2

2

2

6

4

5

5

5

5

1

2

6

 

 

6

6

6

4

5

1

1

1

1

2

6

4

 

 

 

 

4

5

1

2

2

2

2

6

4

5

Page fault

*

*

*

 

*

*

*

*

 

 

 

*

*

*


이때 Belady's Anomaly가 무엇인지 알아보자.


4개의 페이지 프레임

Time

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Page

0

1

2

3

0

1

4

0

1

2

3

4

4

4

Main Memory

0

0

0

0

0

0

1

2

3

4

0

1

1

1

 

1

1

1

1

1

2

3

4

0

1

2

2

2

 

 

2

2

2

2

3

4

0

1

2

3

3

3

 

 

 

3

3

3

4

0

1

2

3

4

4

4

Page fault

*

*

*

*

 

 

*

*

*

*

*

*

 

 


3개의 페이지 프레임

Time

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Page

0

1

2

3

0

1

4

0

1

2

3

4

4

4

Main Memory

0

0

0

1

2

3

0

0

0

1

4

4

4

4

 

1

1

2

3

0

1

1

1

4

2

2

2

2

 

 

2

3

0

1

4

4

4

2

3

3

3

3

Page fault

*

*

*

*

*

*

*

 

 

*

*

 

 

 


위의 표에서 보면 알 수 있는 것은 페이지 프레임수가 1개 많음에도 불구하고 4개의 페이지 프레임에서는 10번의 Page Fault가,

3개의 페이지 프레임에서는 9번의 Page Fault가 일어났다. 즉, FIFO에서는 모순이 발생한다.


따라서 중요한 페이지가 계속 사용될 가능성이 있음에도 불구하고 오랫동안 있었다는 이유만으로 교체되는 것은 불합리하다.



(3) LRU(Least Recently Used)

- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법

- 각 페이지마다 계수기나 스택을 두어 현시점에서 가장 오랫동안 사용하지 않은(가장 오래전에 사용된 페이지) 페이지를 교체함


LRU :: 5번 Page Fault


실행

3

1

2

4

1

2

6

프레임

번호

3

3

3

4

4

4

6

1

1

1

1

1

1

2

2

2

2

2



Time

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Page

1

2

6

1

4

5

1

2

1

4

5

6

4

5

Main Memory

1

1

1

1

1

1

1

1

1

1

1

1

1

1

 

2

2

2

2

6

6

2

2

2

2

6

6

6

 

 

6

6

6

4

4

4

4

4

4

4

4

4

 

 

 

 

4

5

5

5

5

5

5

5

5

5

Page fault

*

*

*

 

*

*

 

*

 

 

 

*

 

 



(4) LFU(Least Frequently Used)

- 사용빈도가 가장 적은 페이지를 교체하는 기법

- 프로그램 실행 초기에 많이 사용된 페이지가 그 후로 사용되지 않을 경우에도 프레임을 계속 차지하는 단점이 존재


Time

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Page

1

2

6

1

4

5

1

2

1

4

5

6

4

5

Main Memory

1

1

1

1

1

1

1

1

1

1

1

1

1

1

 

2

2

2

2

5

5

5

5

5

5

5

5

5

 

 

6

6

6

6

6

2

2

2

2

6

6

6

 

 

 

 

4

4

4

4

4

4

4

4

4

4

Page fault

*

*

*

 

*

*

 

*

 

 

 

*

 

 


(5) NUR(Not Used Recently)

- 최근에 사용하지 않은 페이지를 교체하는 기법

- 사용 여부를 확인하기 위하여 각 페이지마다 참조비트와 변형비트가 사용됨


(6) SCR(Second Chance Replacement)

- 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 기법

- FIFO 알고리즘 기법의 단점을 보완하는 기법


출처: http://server-engineer.tistory.com/126







반응형