2023. 5. 23. 20:51 1차 수정
가상 메모리 관리
가상 메모리는 메모리와 디스크를 같이 사용한다.
만약에 메모리 프레임에 접근할 페이지가 없으면 디스크 영역에서 페이지를 가져와 메모리 프레임에 페이지를 넣어야 한다.
이럴 때 페이지 대치의 필요성을 느낄 수 있다.
즉 할당할 메인 메모리 공간이 부족하면 대치가 필요하다.
페이지 대치란 페이지 부재(메모리에 접근할 페이지가 없다. fault)가 발생하면
메인 메모리에서 사용되지 않는 페이지(victim)를 없애고 새로운 페이지로 바꾸는 기법이다.
순서를 간단하게 알아보자.
- 희생자 페이지를 메모리에서 디스크로 내보낸다.
- 페이지 테이블의 타당, 비 타다 비트를 수정한다.
- 디스크에서 원하는 페이지를 프레임으로 가져온다.
- 새로운 페이지를 위한 페이지 테이블을 재설정한다.
희생 프레임(victim)을 찾는 것은 매우 중요하다. 즉, 효율적인 페이지 대치 알고리즘이 필요하다.
보통 프레임 수가 증가하면 페이지 부재수가 감소한다. 즉 반비례 관계다.
페이지 대치 알고리즘
이제 페이지 몇 가지 페이지 대치 알고리즘에 대해 알아보겠다.
FIFO
먼저 선입선출 대치 알고리즘이다. FCFS, FIFO라고 한다. 간단한 페이지 대치 알고리즘이다.
페이지의 메모리 도착시간을 이용한다. 오래된 페이지를 대치한다.
선입선출 큐에 의해 관리된다. 큐의 머리 부분에 있는 페이지를 먼저 대치한다.
즉 먼저 들어온 게 희생 프레임이다.
벨레디의 변이는 할당되는 프레임의 수가 증가함에 따라 페이지 부재율이 증가하는 것이다.
프레임을 더 많이 할당했으나 page fault가 오히려 증가한다. 즉 최적 페이지 대치 알고리즘이 필요하다.
최적 페이지 대치 알고리즘
먼저 최적 페이지 대치 알고리즘이다.
이 알고리즘은 페이지 부재율이 가장 낮다. OPT(Optional Algorithm) 또는 MIN 알고리즘이라고 한다.
앞으로 가장 오랜 기간 동안 사용되지 않을 페이지로 대치한다.
참조 열에 대한 미래의 지식(정보)이 요구된다. 미리 알기 어렵기 때문에 구현의 문제가 있다.
LRU 알고리즘
이제 현실에서 자주 사용하는 LRU 알고리즘이다. Least Recently Used의 약어다. 최근 최소 사용 알고리즘이다.
가까운 미래의 근사치로서 가장 최근의 과거 사용. (오랜 기간 동안 사용하지 않은 페이지로 대치하는 효과다)
미래의 예측을 과거의 자료로 해결하려는 통계적 개념이다. 메모리의 지역성을 이용한 알고리즘이다. 각 페이지와 그 페이지가 최후로 사용된 시간 연관. 즉 페이지가 대치되어야 할 때는 오랫동안 사용되지 않은 페이지를 선택한다.
LRU 구현 방법은 계수기, 스택이 있다.
계수기는 각 페이지 테이블 항목과 사용시간 레지스터와 연관이 있다.
클럭은 메모리 참조마다 증가한다. 이 클럭을 이용해 시간 정보를 얻는다.
사용시간 레지스터는 페이지의 최후 참조에 대한 시간을 유지한다. 가장 작은 시간 값을 가진 페이지를 대치한다.
즉 페이지 테이블의 시간 정보를 보고 뭐가 제일 안 쓰였는지 확인한다. 단점이 존재하는데 페이지 탐색 시간과 페이지 테이블의 변화 과정 유지 부담이다.
스택 방식을 이용한 것은 먼저 들어온 것이 나중에 나가고 나중에 들어온 것이 먼저 나간다.
참조될 때마다 탑으로 추가 또는 이동한다.
만약 최근에 참조한 것이 스택 아래에 있으면 그것을 pop 한 후 다시 push 해야 하는데 이러면 낭비가 발생한다.
즉 중간에서 이동할 경우는 오버헤드다.
이 경우를 막기 위해 Doubly Linked List Stack으로 구현한다.
LRU 근접 대치 알고리즘에는 부가된 참조 비트 알고리즘과 시계(2차적 기회 대치) 알고리즘, 최소 사용빈도 알고리즘, 최대 사용빈도 알고리즘, 페이지 버퍼링이다. 페이지 버퍼링 알고리즘만 빼고 살펴보겠다.
먼저 부가된 참조 비트 알고리즘이다.
페이지 대치 대상은 가장 낮은 참조 비트를 가진 페이지 프레임이다.
이 알고리즘은 페이지 테이블에 참조 비트가 존재한다.
참조 비트의 초기 값은 0이며 해당 페이지가 참조되면 왼쪽 끝, 즉 최상위 비트에 1이 들어간다. 이후 shift right을 진행한다.
만약 참조가 되면 1이 들어가고 참조가 안되면 0이 들어간다. clock 이 있어 주기적으로 체크를 한다.
가장 낮은 참조 비트를 가지면 희생 프레임이 된다. (참조 비트에서 1이 적으면 희생 프레임)
시계 알고리즘
다음은 시계 알고리즘이다.
2차적 기회 대치 알고리즘이라고 이해하는 게 편하다.
먼저 원형 버퍼로 구성되어있으며, FIFO 스타일이다.
참조 비트가 존재한다. 페이지가 프레임에 적재되면 1 또는 페이지가 참조되면 값이 1로 변한다. 초기 값은 0이다.
즉 아직 참조되지 않은 상태다. 참조 비트는 페이지 대치 필요시 2차적 기회를 제공하는 기준이다.
참조 비트를 가리키는 포인터가 존재한다. 페이지 대치 대상은 참조 비트가 0인 프레임의 페이지다. 1
인 경우에는 어떻게 되는가? 먼저 참조가 되면 1 값으로 변한다.
이러면 다음에 FIFO로 순서가 돌아올 때 1인 경우에는 한번 더 희생 프레임이 되지 않을 기회를 준다.
대신 참조 비트 1이 0으로 바뀐다.
이래서 2차적 기회 대치 알고리즘이라고 하는 것이다. 0으로 바뀌면 포인터는 다음 프레임으로 이동한다.
최소 사용 빈도 알고리즘
페이지 대치 대상은 참조 횟수가 적은 프레임의 페이지다. 참조 횟수가 적은 것은 활발하게 사용되지 않을 것이라는 판단하에 이루어진 것이다. 페이지가 참조될 때마다 해당 페이지의 참조 횟수가 증가한다.
최대 사용빈도수 알고리즘
페이지 대치 대상은 참조 횟수가 많은 프레임의 페이지다. 참조 횟수가 적은 것은 향후에 사용될 가능성이 높다는 판단 때문이다. 페이지가 참조될 때마다 해당 페이지의 참조 횟수가 증가한다.
배르의 발표에 따르면 효율성은 차례로 OPT> LRU> 시계> FIFO 순이다.
가상 메모리의 효율성에 대한 이야기다
페이지 부재율 감소를 위해 페이지 대치와 페이지 할당은 매우 중요하다.
n개 프레임중 최적의 할당 알고리즘으로 효율성을 증대시켜야 한다.
단독 사용자는 프로세스 1개가 메모리를 다 쓰는 경우다.
128K 메모리를 1K 프레임으로 나누면 128개의 프레임이 생긴다. OS 영역의 프레임을 35개, 단독 사용자 영역(93개 프레임)으로 구분한다. 93번째 프레임 할당을 요청하면 다음번 94번째 프레임 할당 요청에서 페이지 대치가 필요하다.
다음은 다중 사용자다. 여러 프로세스에게 93개 프레임을 어떻게 효율적으로 할당할 수 있는가?
각 프로세스마다 최소로 할당되어야 할 프레임수가 다를 것이다. 즉 프로세스마다 요구하는 프레임의 크기가 다른 것이다. 프레임 수가 적으면 페이지 부재율이 증가한다. 이 때는 2가지 경우가 존재한다. 균일 할당과 비례 할당이다.
균일 할당은 모든 프레임이 m개라면 n개의 프로세스에 대해 m/n개로 프레임을 할당한다. 비례 할당은 각 프로세스의 크기에 비례하여 프레임을 할당하는 것이다. 앞에 언급했던 것처럼 각 프로세스가 요구하는 메모리 양이 다르다. 큰 프로세스는 프레임을 많이 요구하고, 작은 프로세스는 프레임을 적게 요구한다.
만약 3개의 프로세스가 있고, 총 98개 프레임의 경우를 균일 할당하면 32 32 32 2 일 것이다.
2개 프로세스가 10K, 127K고 총 62개 프레임이라면, 균일 할당은 31 31 이렇게 나눌 것이다.
비례 할당의 경우는 10K(10+127)*62 = 약 4개 프레임이고 127(10+127)*62 = 약 57개 프레임으로 나올 것이다.
스레싱
페이지 부재가 연속적으로 발생하면 프로세스는 페이지 교환을 위하여 시간을 낭비한다.
계속적으로 페이지 교환이 일어나는 현상이 발생한다.
메모리 공간은
한정되어 있다. 실행시킬 프로세스가 증가하면 어느 순간 존재하지 않는 페이지를 가져와 배치하고 대치하며 부재 처리를 해야 한다.
CPU가 프로세스 수행 시간보다 페이지 교환에 시간을 더 보내게 될 수 있다.
이게 스레싱이다. 즉 프로세스 수행 시간 < 페이지 교환에 보내는 시간 이런 상황이다.
스레싱의 원인은 이용률 감소, 페이지 부재 일으킴, 필요한 프레임 미배당 등이 있다.
이 스레싱을 해결하기 위해 워킹 셋 모델 즉 적재 정책이 등장한다.
적재 정책은 지역성을 근거로 가지고 있다.
지역성이란 무엇인가?
지역성은 프로세스 실행 과정에서 지역성 또는 국부성 특징이 나타나는 것이다.
메모리 내의 정보를 균일하게 액세스 하지 않고 페이지 중 일부를 선호하여 지역적인 부분을 집중적으로 참조하는 것이다.
- 시간 지역성 - 참조된 기억장소가 가까운 미래에도 계속 참조될 가능성이 높다.
- 공간 지역성 - 프로세스가 어떤 기억 장소를 참조하면 그 근처의 기억 장소가 그 후에도 계속 참조될 가능성이 높다.
작업 설정 모델 (Working Set Model)은 Denning, 지역성을 설명하기 위한 목적으로 개발되었다.
참조가 많은 페이지들의 집합 -> 메모리에 지속적으로 상주한다. 페이지 fault를 줄이는 것이 목적이다. 즉 페이지를 메모리에서 최대한 많이 hit 하도록 만드는 것이다. Working-set 작업 설정은 윈도라는 델타 모양의 변수를 이용한다.
t-w에서 t까지 동안에 참조된 페이지번호들의 집합과 W는 델타 변수로 이용하며 진행한 시간의 값이다. 표현방식은 예를 들어 10초 동안 참조한 페이지가 2615777751이라면 WS(t1)={1,2,5,6,7}이다.
작업 설정 모델은 델타 모습의 변수인 Working-Set Window 즉, WSSI 가 지역성과 연관 있다. 프로세스의 Working Set Size다.
델타가 작게 설정된다면 지역성을 커버하지 못한다. 델타가 크게 설정된다면, 몇 개 정도의 지역성을 커버한다. 델타가 매우 크게 무한대 정도라면, 전체 프로세스를 커버한다.
만약 프로세스가 5개의 프레임(D)을 요구하는데 유효한 프로세스가 3개(M) 라면 드레싱이 발생한다. D와 M을 잘 다루어야 페이지의 부재를 줄일 수 있다. D> M일 경우는 프로세스 실행을 연기시켜야 한다.
작업 설정 모델에서 작업 설정의 크기는 안정기와 과도기가 반복되는 현상을 보인다.
작업 설정 모델은 페이지 부재를 줄이기 위해 등장했다. 스레싱을 줄이기 위해 등장한 것이다. 페이지 부재를 줄이기 위한 방법으로는 프리페이징이라는 것이 있다. 요구 페이징과는 다르게 요청하지 않아도 페이지를 미리 가져오는 것이다. 장점은 fault 발생을 줄이지만 스레싱 조절이 어렵다.
부재율에 대한 상한 값을 정하고, 하한 값을 정하고 이를 모니터링한다.
페이지 부재율이 더 높으면 프로세스가 더 많은 프레임이 필요하다. 다른 프레임을 더 할당한다. 페이지 부재율이 낮으면 프로세스가 많은 프레임을 가지고 있는 것이다. 이러면 프레임을 회수한다. 이렇게 부재율을 관리하면 스레싱도 방지가 가능하다.
다음은 대치 범위다. 지역 대치와 전역 대치가 있다.
지역 대치는 해당 프로세스 프래임에서 선택해서 대치한다. 프로세스 간 영향을 주지 않고, 프로세스의 프레임 수는 변화가 없다. 전역 대치는 프로세스와 상관없이 선택이 가능하며 구현이 간단하지만 타 프로세스에 영향을 준다.
프리 페이징은 미리 여러 페이지를 가져온 뒤에 실행하면 page Fault가 준다는 근거를 바탕으로 만들어졌다. 프로세스의 초기 실행에는 많은 page Fault가 발생하기 때문이다. 프리페이징 시점은 프로그램 실행 직전, I/O waiting, 유효 프레임이 없어 이를 처리하는 경 우디. 이 경우에는 요구 페이지 말고 추가 페이지도 더 가져온다.
프리 페이징의 사용률이다. 일단 메모리에 돌어온 페이지들 중에서 일부 페이지는 미사용한다. s페이지만큼 프리페이징을 한다. 그러나 실제 사용률은 0<a<1이다. 불필요한 (1-a)*s 개의 프리페이징 비용이 발생한다.
a 가 0에 가까우면 프리 페이징은 좋지 않고, a가 1에 가까우면 프리 페이징의 효과가 좋다.
페이지 크기는 일반적으로 4k, 8k다. 페이지 사이즈가 크면 페이지 개수가 적어지며, 페이지 테이블 크기가 적어진다. 또한 페이지 부재수가 감소하며 페이지 교체가 줄어든다. 처리속도가 증가하며 디스크 처리 시간도 증가한다. 단 내부 단편화는 많아지고 메모리 효율성은 떨어진다.
CPU와 메모리 사이에서 성능을 높이기 위해 캐시 메모리를 사용한다. 분산적인 구조로 이용!
댓글