운영체제 강의노트
교재 : 운영체제(개정판)
출판사 : 한빛미디어(2010년 11월 발행)
저자 : 구현회
8장 가상 메모리
소프트웨어학과 원성현 교수
1. 가상 메모리의 개념
• 가상 메모리(virtual memory)란?
• 실제 주기억장치보다 훨씬 더 크게 주기억장치를 인식하고 사용할 수 있도록 하는 기술
• 프로세스의 덩치가 매우 크지만 실행에 필요한 부분은 극히 일부라 는 것에 착안하여 현재 또는 가까운 미래에 필요하지 않은 부분은 모 두 디스크에 두고 필요할 때만 주기억장치로 적재(swap in)했다가 필요없으면 디스크로 내보내는(swap out) 방식의 메모리 관리 기법 가상 메모리의 등장 배경
0 1 2 3 4 5 6
0
1
2
5 3
6
4 0
2
3
소프트웨어학과 원성현 교수
1. 가상 메모리의 개념
• 디스크를 이용한 가상 메모리 관리의 문제점
• 메모리와 디스크 사이의 데이터 이동량이 많아져서 시간 지연 발생
• 어느 시기에 페이지를 주기억장치에 넣었다가 다시 디스크로 복귀 시킬 것인지에 대한 결정
• 요구하는 페이지가 주기억장치에 없을 때, 즉 페이지 부재시에 대 한 처리 방안
• 논리 주소와 물리 주소 사이의 적절한 주소 변환이 필수적임
논리주소 (가상주소)
물리주소 (실제주소) 변환
함수
1. 가상 메모리의 개념
• 동적 주소 변환(DAT : Dynamic Address Translation)
• 가상주소와 실제주소를 연관시키기 위한 방법으로 프로세스가 수 행 중에 실제주소를 배정하는 방법
• 블록 사상
• 동적 주소 변환을 위해서는 주소 사상 테이블(Address Mapping Table)을 유지해야 함
• 사상이 바이트 또는 워드 단위로 이루어지면 주소 사상 테이블을 위한 정보량이 커지므로 사상 정보의 양을 줄이는 방법으로 블록 단 위로 사상을 하는 방법이 등장함
블록 사상
블록 0 블록 1 블록 2
블록 n
…
가상메모리
주소사상테이블
물리적메모리 보조기억장치
2. 요구 페이징
• 요구 페이징(Demanded Paging) 기법이란?
• 프로세스를 위해 몇 개의 페이지 프레임을 할당한 후, 시스템이 필 요로 하는 페이지만 페이지 프레임을 할당하고, 필요로 하지 않는 나머지 페이지는 디스크에 보관
• 페이지 프레임을 할당받은 페이지가 필요하지 않게 되고 새로운 페이지가 필요하게 되면 페이지 프레임을 할당받은 페이지를 디스 크로 교체해서 내보내고 디스크에 있는 페이지를 대체함
요구 페이징의 기본 개념
메인 메모리
4 8 12 16 20
0 1 2 3
프로세스 A
프로세스 B
교체되어 나감 교체되어 들어옴
2. 요구 페이징
• 타당/비타당 비트가 추가된 페이지 테이블
• 페이지 테이블에서 각 페이지가 주기억장치에 있는지(v), 없는지(i) 를 관리
B A C D E G F H
0 1 2 3 4 5 6 7
논리적 메모리
4 6
9
0 1 2 3 4 5 6 7
페이지 테이블
i v v i i i v
i
프레임 타당/비타당 비트
A C
F
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
물리적 메모리
B
D E
G H
보조기억장치
2. 요구 페이징
• 페이지 부재 해결 과정
• 시스템이 원하는 페이지가 주기억장치에 없는 상황을 해결하는 과 정
보조기억장치
운영체제
Load M i
Free frame
물리적 메모리 1. 참조
2. 트랩
3. 트랩페이지가 보조기억장치에 있음
4. 부재 중인 페이지를 가져옴
페이지 테이블
5. 페이지 테이블 재설정
6. 명령어 재시작
• 페이지 대치(page replacement)는 왜 필요한가?
• 요구 페이징 기법은 기본적으로 프로세스마다 주기억장치 중 몇 개의 페이지 프레임만을 사용할 수 있도록 하는 기법임
• 사용할 수 있는 페이지 프레임의 수가 3~5개 정도밖에 안되기 때문에 프로세스의 대부분의 페이지들은 디스크에서 대기하고 있 어야 함
• 시스템이 필요로 하는 페이지가 주기억장치에 없다면(이런걸 page fault : 페이지 부재라고 함) 디스크에서 가져와야 하는데 가 져올 때 빈 페이지 프레임이 있다면 다행이지만, 없다면 어떤 페이 지든 디스크로 퇴출되어야만 빈 페이지 프레임을 확보할 수 있음
• 주기억장치에 있는 페이지를 디스크로 내보내고 디스크에 있던 페이지를 주기억장치로 반입하는 것을 페이지 대치라고 함
• 페이지 대치를 얼마나 적게 하는가가 관건임
• 일반적으로 사용 가능한 페이지 프레임이 많을 수록 페이지 대치는 적게 일어난다고 보면 됨
페이지 대치
3. 페이지 대치 알고리즘
3. 페이지 대치 알고리즘
2 4 6 8 10 12 14 16
1 2 3 4 5 6
Number of frames Number of
page faults
• 선입선출(FIFO : First In First Out) 알고리즘
• 주기억장치에 적재된 것이 가장 오래된 페이지부터 대치
• 간단하지만 불합리할 수 있음 페이지 대치 알고리즘
3. 페이지 대치 알고리즘
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7
0
7 0 1
2 0 1
2 3 1
2 3 0
4 3 0
4 2 0
4 2 3
0 2 3
0 1 3
0 1 2
7 1 2
7 0 2
7 0 1
f f f f f f f f f f f f f f f
총 페이지 부재 회수 : 15회
• 선입선출(FIFO : First In First Out)의 모순
• Belady’s Anomaly라고도 하는데 할당되는 페이지 프레임의 수가 늘어나는데 페이지 부재는 더 늘어나는 이상 현상
3. 페이지 대치 알고리즘
0 1 2 3 0 1 4 0 1 2 3 4 0 0
1
0 1 2
3 1 2
3 0 2
3 0 1
4 0 1
4 2 1
4 2 3
f f f f f f f f f
총 페이지 부재 회수 : 9회
0 3 프레임
4 프레임
0 1
0 1 2
0 1 2 3
4 1 2 3
4 0 2 3
4 0 1 3
4 0 1 2
3 0 1 2
3 4 1 2
총 페이지 부재 회수 : 10회
f f f f f f f f f f
• 최적(Optimal) 페이지 대치 알고리즘
• 향후 사용될 가능성이 가장 낮은 페이지부터 대치
• 향후 사용될 가능성이 가장 낮다는 것을 아는 것이 어렵기 때문에 현실적으로 적용하기는 어려운 방법
• 이론적으로 최소의 페이지 부재를 가져오기 때문에 다른 방법 들과 비교하기 위해 사용함
3. 페이지 대치 알고리즘
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7
0
7 0 1
2 0 1
2 0 3
2 4 3
2 0 3
2 0 1
7 0 1
f f f f f f f f f
총 페이지 부재 회수 : 9회
• 최근 최소 사용(LRU : Least Recently Used) 알고리즘
• 미래를 알 수 없다면 과거를 이용
• 가장 최근에 사용한 적이 없는 페이지는 향후에도 사용될 가능성 이 가장 낮은 것으로 판단하여 가장 최근에 사용한 적이 없는 페이 지부터 대치
• 어떤 페이지가 가장 최근에 사용되었고, 어떤 페이지가 가장 오래 전에 사용되었는지를 아는 방법
• 계수기를 이용한 순서 결정
• 스택을 이용한 순서 결정
3. 페이지 대치 알고리즘
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7
0
7 0 1
2 0 1
2 0 3
4 0 3
0 3 2
1 3 2
1 0 7
f f f f f f f f f
총 페이지 부재 회수 : 12회
4 0 2
4 3 2
1 0 2
f f f
• 최근 최소 사용 근접 알고리즘
• 부가된 참조 비트 알고리즘
• 각 페이지에 8비트 길이의 참조 비트 부여
• 페이지가 사용될 때마다 최상위 비트를 1로 바꾸고 오른쪽 으로 한자리씩 시프트
• 값이 00000000이면 한번도 사용된 적이 없는 페이지
• 값이 11111111이면 매번 사용된 페이지
• 값 11000100은 01110111보다 최근에 사용된 페이지
• 이를 통해서 어떤 페이지를 내보낼 것인가를 결정
• 시계(Second Chance) 알고리즘
• 모든 페이지에 1비트의 참조 비트 부여
• 페이지가 사용될 때마다 참조 비트를 0에서 1로 전환
• 참조 비트가 0인 페이지를 내보낼 페이지로 결정
• 참조 비트가 1인 페이지는 참조비트를 0으로 바꾸고 한번 의 기회를 더 줌
• 다음 검사에서 참조 비트가 0이면 대치 대상이 되고 그 동안 또 사용되어 1로 되어 있으면 다시 0으로 바꿈
3. 페이지 대치 알고리즘
• 프로세스들에게 페이지 프레임을 할당하는 것은 가용 프레임 수에 전 적으로 의존
• 프로세스들에게 할당되는 프레임 수가 줄어들면 페이지 부재율 상승
• 페이지 부재는 페이지 대치 알고리즘의 실행을 유도하고 페이지 교체를 수반하므로 프로그램 실행 속도 저하 유발
• 프로세스들에게 많은 페이지 프레임을 할당할 수도 없음
• 프로세스들이 많은 페이지 프레임을 갖고 있으면 다중 프로그밍 의 정도가 떨어져서 이 또한 시스템 성능 하락의 요인이 됨
• 프로세스별로 반드시 확보해야 할 페이지 프레임의 수가 보장되어야 함
• 균일 알고리즘
• 프로세스의 길이와 무관하게 일정한 수의 프레임 할당
• 비례 할당 할고리즘
• 전체 프레임 수와 프로세스들의 길이를 고려하여 프레임 차 등 할당
4. 프레임 할당 알고리즘
최소 프레임 수
• 스레싱(Thrashing)이란?
• 프로세스가 기본적으로 확보해야 할 페이지 프레임의 수가 충분하 지 못하여 빈번하게 페이지 부재(page fault)가 발생하는 현상
• 스레싱 발생 원인
• 부족한 페이지 프레임, 과도한 페이지 부재, 과도한 페이지 대치
• 스레싱 예방
• 최적의 페이지 프레임 수 제공
5. 프로세스 적재 정책
스레싱
프로세서 이용률
다중 프로그래밍 정도 스레싱 발생
• 지역성(Locality)이란?
• 국부성이라고도 함
• 실행 중인 프로세스에 의해 나타나는 특성으로, 프로세스들은 실 행 기간 동안 메모리 내의 정보를 균일하게 액세스하는 것이 아니 라 페이지 중 일부를 선호하여 지역적인 부분만을 집중적으로 참 조하는 현상
• 지역성의 예
• 함수 하나가 새롭게 호출
• 반복문이 실행되기 시작
• 배열이 참조되기 시작
• 지역성의 종류
• 시간적 지역성 : 참조된 기억장소는 가까운 미래에 다시 참조
• 공간적 지역성 : 참조된 기억장소 인근 주소를 계속 참조
• 지역성이 왜 중요한가?
• 몇 개의 페이지 프레임을 할당할 것인가를 결정하는 단초가 됨
5. 프로세스 적재 정책
지역성
