개요(Overview)
[운영체제] 가상 기억장치의 구성과 관리 - 페이징과 세그먼테이션
개요(Overview) 오늘은 가상 기억장치의 구성과 관리에 대해 알아보도록 하겠습니다.지난 포스팅에서는 컴퓨터의 기억장치 즉, 우리가 통상적으로 메모리(Memory)라고 부르는 하드웨어 장치의 관리
1-hee.tistory.com
오늘은 지난 포스팅에 이어 가상 기억 장치의 페이지 교체 기법과 그 전략에 대해 알아보도록 하겠습니다.
1.6. 페이지 교체 기법
가상기억 장치의 운영, 특히 페이징 기법에 있어서 실 기억장치에 적재되어 있는
모든 페이지 프레임들은 프로세스에 의해 과거에 참조되었거나, 현재 참조되고 있거나, 또는 앞으로 참조될 페이지들 입니다.
이때, 주 기억장치에 미리 적재되지 않은 어떤 페이지를 필요로 하면, 보조기억장치로부터 주기억장치로 그 데이터를 읽어들여야 하는데, 만일 현재 주 기억장치 내에 비어 있는 프레임이 없는 경우에는 기존의 페이지 프레임중 하나를 선택하여 비워야 합니다.
이와 같이 기존에 적재되어 있는 페이지 프레임 중 실 기억장치로부터 제거되어야할 페이지를 결정하는 방법을 페이지 교체 기법이라고 합니다.
1.6.1. 최적화 원칙과 무작위 페이지 교체
최적화 원칙은 최적의 성과를 얻기 위해 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방법입니다.
이 기법은 매우 좋은 방법으로 여겨지나, 앞으로 사용될 것에 대한 ‘예측’을 필요로 하므로 실현하기 매우 어려운 기법입니다.
그러나 최적화 원칙에 근사한 교체기법을 사용해서 최적화 원칙에 접근할 수는 있습니다.
이에 비해 무작위 원칙 페이지 교체 기법은 제거될 페이지를 선택하는데 있어서 특별한 원칙 없이 무작위로 선택하는 방법입니다.
따라서, 이 방법은 모든 주 기억장치 내의 페이지들에 대해 교체될 가능성을 동일하게 합니다.
어느 페이지도 교체될 수 있음을 의미하며, 최악의 경우에는 바로 뒤에 사용될 페이지도 교체될 수 있습니다.
이 방법은 구현하기 간단하나 거의 사용되지 않는 방법입니다.
1.6.2. FIFO (First In First Out) 페이지 교체
FIFO 페이지 교체 기법은 각 페이지가 주 기억장치에 적재될 때마다
그 시간을 기억하여 가장 오래 주 기억장치에 있었떤 페이지를 교체시킵니다.
즉, 주 기억장치에 가장 먼저 들어간 페이지를 제거하는 방법을 말합니다.
아래의 그림에서는 3개의 페이지 프레임을 가진 가상 기억장치의 FIFO 교체 예시입니다.
위 그림처럼FIFO 방식은 이해하기 쉽고 설계가 간단하다는 장점이 있으나,
계속 사용되고 있는 페이지가 오랫동안 페이지 프레임을 차지하였다는 이유 하나만으로
교체되어야 하는 불합리성을 발생시킬 수 있습니다.
일반적으로 프로세스 당 더 많은 페이지 프레임이 할당될수록 더 적은 페이지 부재가 발생하는 것이 상식적입니다.
하지만, FIFO 방식에서는 아래의 그림과 같이 프레임이 더 많이 할당되어도 페이지 부재가 더 많이 발생하는 경우가 발생할 수 있는데, 이러한 현상을 FIFO 기법의 모순이라고 합니다.
1.6.3. LRU(Least Recently Used) 페이지 교체
LRU(Least Recently Used) 기법은 최근에 가장 오랫동안 사용되지 않은 페이지를 교체하는 기법입니다.
LRU 기법에서 각 페이지들이 호출될 때마다 그때의 시간을 테이블에 기억시킵니다.
이 작업은 필연적으로 시간의 기록을 위한 막대한 오버헤드를 초래하게 되며,
LRU 기법 자체는 좋은 방법이긴 하지만 많이 사용되지 않습니다.
LRU를 구현하는 방법으로는 카운터에 의한 방법과 스택에 의한 방법이 있습니다.
카운터 의한 방법은 어떤 페이지에 대한 참조가 있을 때마다,
그 시간을 기억하여 페이지 테이블 내의 사용 시간 레지스트에 저장합니다.
즉, 새로운 페이지가 호출되면 각 페이지 테이블 항목과 연관된
사용시간 레지스터 값을 탐색하고 가장 적은 값을 가진 페이지와 교체하는 방식입니다.
한편, 스택에 의한 방법은 스택에 페이지 번호를 수록하여 어떤 페이지가 호출 때마다 스택의 top으로 이동되며 스택의 top에 있는 페이지가 가장 최근에 사용된 페이지임을 나타내고 바닥에 있는 것이 가장 오랫동안 사용되지 않은 페이지임을 나타냅니다.
이때, 각 스택의 항목들이 가운데에서 제거되어야 하기 때문에, 이중 연결 리스트(doubly-linked list)로 구현되는 것이 일반적입니다.
1.6.4. LFU(Least Frequently Used) 페이지 교체
이 방법은 각 페이지들이 얼마나 사용되었는지를 확인하여, 호출된 횟수가 가장 적은 페이지를 교체하는 방식입니다.
이 방법도 직관적으로 보여 좋아 보이지만, 종종 나쁜 결과를 가져올 수 있습니다.
예컨데, 최근 주 기억장치에 들어온 페이지는 호출 횟수가 오랫동안 주 기억장치에 있었던 다른 페이지이 비해 적을 가능성이 크므로 최근의 페이지를 자주 교체시켜 불필요한 오버헤드를 발생시킬 수 있습니다.
1.6.3. NUR(Not Used Recently) 페이지 교체
NUR 기법은 적은 오버헤드로 LRU에 근사하며 실제로 자주 쓰일 수 있는 기법으로
최근에 쓰이지 않은 페이지들은 가까운 미래에도 쓰이지 않을 것이라 판정하고 새로 들어온 페이지들과 교체하는 기법입니다.
즉, 최근에 사용되지 않은 페이지들을 교체하는 기법을 의미합니다.
NUR기법은 다음과 같이 각 페이지당 2개의 하드웨어 비트를 필요로 합니다.
처음에는 모든 페이지들의 참조 비트를 0으로하고,
어떤 페이지가 참조되면 그 페이지의 참조비트를 1로 바꿉니다.
또한, 변형 비트의 초기치도 0으로 주어지며 어떤 페이지의 내용이 변형되면 비트를 1로 바꿉니다.
| 구분 | 값 | 설명 |
| 참조비트 | 0 | 페이지가 참조되지 않았을 때 |
| 1 | 페이지가 참조된 적이 있을 때 | |
| 변형 비트 | 0 | 페이지 내용이 변형되지 않았을 때 |
| 1 | 페이지 내용이 변형되었을 때 |
이러한 상태에서 하나의 페이지가 교체되어야 할 때는 다음과 같은 순 서로 페이지를 찾습니다.
- 참조된 적이 없는 페이지를 찾는다. 만일 찾으면 이 페이지를 교체시킨다.
- 참조 비트가 0인 페이지가 없으면, 변형 비트가 0인 페이지를 찾아 교체시킨다.
(변형비트가 0인 페이지를 교체시키는 경우는 변형비트가 1인 페이지를 교체시키면,
그 페이지가 변형되었으므로 다시 보조기억 장치를 써야 하는 번거로움을 발생시키기 때문)
다중 사용자 시스템에서 주 기억장치는 여러 사용자가 공유해야 하므로 조만간 대부분의 참조비트는 1이 됩니다.
그렇게 되면, 교체에 가장 적합한 페이지를 찾기 어려워지므로
주기적으로 모든 참조비트로 0으로 하여 다시 참조될 때 1로 바꾸는 방법도 있습니다.
NUR 기법에서는 이에 따라 다음과 같이 4가지 그룹으로 나뉘게 됩니다.
| 그룹 | 참조 비트 | 변형 비트 |
| 그룹 1 | 0 | 0 |
| 그룹 2 | 0 | 1 |
| 그룹 3 | 1 | 0 |
| 그룹 4 | 1 | 1 |
이때 그룹 1이 가장 우선적으로 교체되며, 그룹 2는 호출되지 않고 변형된 페이지를 나타내는데
실제 상황에서 이는 없는 경우에 해당합니다.
그러나, 정기적으로 참조비트를 초기화하는 과정으로 인해 그룹 2가 발생할 수 있는 것입니다.
1.7. Working Set과 지역성(Locality)
지역성(Locality)란 의미는 프로세스들이 기억장치 내의 정보를 균일하게 접근한다는 것이 아니라,
국부적인 부분을 집중적으로 참조한다는 것을 의미합니다.
예컨데, 어떤 프로그램이 수행 중일 때 현재 100번지를 참조하고 있다면
500번지나 800번지보다 101번지를 참조할 가능성이 훨씬 높다는 것을 의미합니다.
이와 같이 어떤 시간 내에 기억장치의 국부적인 부분을 많이 참조하는 현상을 ‘지역성’이라고 일컬으며,
이러한 지역성은 시간과 공간에 밀접한 관계가 있습니다.
1. 시간 구역성(temporal locality) : 최초 참조된 기억장소가 가까운 미래에도 계속 참조될 가능성이 높은 것.
ex)
- 순환(looping)
- 서브 루틴(subroutine)
- 스택(stack)
2. 공간 지역성(spatial locality) : 어떤 기억장소가 참조되면 그 근처의 기억장소가 계속 참조되는 경향성
ex)
- 배열의 접근
- 순차적인 코드 실행
기억장치에서 이러한 지역성의 가장 중요한 의미는 각 프로그램이 많이 참조하는 페이지들이
주 기억장치에 있다면, 프로그램이 보다 효율적으로 실행될 수 있다는 점입니다.
이러한, 지역성을 이용하여 Denning은 프로글매 행동에 대한 Working set 이론을 정립했습니다.
Working set이란 하나의 프로세스가 자주 참조하는 페이지들의 집합을 의미하는데,
하나의 프로그램이 효율적으로 실행되기 위해서는 그들의 Working set이 주 기억장치 내에 유지되어야 하며,
그렇지 않으면 그 프로그램이 보조 기억장치로부터 계속 페이지들을 요구하게 되므로,
*스레싱(thrashing)이라는 바람직하지 못한 현상을 발생시킨다는 것을 의미합니다.
스레싱(thrashing) : 특정 프로그램을 실행하기 위해 페이지 부재(Page Fault)가 자주 발생하는 상황
따라서, 실행중인 프로그램이 주 기억장치(실 기억장치)에 자신의 필요로 하는 Working set을 유지하고 있다면
매우 효율적으로 기억장치를 관리할 수 있으며, 이를 원칙으로 하는 기억장치 관리 방법론입니다.
Working set 방법에서 기억장치에 새로운 프로세스를 더 추가시킬지 여부를 판정하는 기준은
그 프로세스의 Working set(=수행 작업 단위에 따라 필요한 총 메모리 사용량)의
크기를 모두 수용할 수 있는 가에 대한 여부로 판정합니다.
처음 시작하는 프로세스는 시스템이 그 프로세스의 Working set을 알 수 없으므로, 대충 짐작하여 책정합니다.
그리고, 프로세스가 실행되는 동안에는 페이지들이 삭제기도하고 추가되기도 할 뿐 아니라
거의 다른 Working set으로 전이가 일어나기도 합니다.
이처럼 Working set 기법에 따른 메모리 사용량의 추이는 아래와 같은 그림처럼 표현할 수 있습니다.
위 그림을 참조하면 하나의 프로세스가 어떻게 시간이 지남에 따라 주 기억장치를 사용하는지,
즉 Working set의 크기가 어떻게 변화하는 지를 나타내며,
이처럼 Working set은 시간이 지남에 따라 매우 유동적이고
앞에서의 Working set과 다음 번의 Working set이 현저히 다를 수 있음을 보여줍니다.
1. 8. 요구 페이징 기법과 예측 페이징 기법
페이징 환경에서 어떤 프로세스가 수행되기 위해서는
그 프로세스에 해당하는 모든 페이지들을 보조 기억장치에서 주 기억장치로 최소 한 번 이상은 옮겨져야 합니다.
다중 사용자 환경에서 모든 페이지들을 동시에 주 기억장치에 위치시키는 것은 불가능 합니다.
따라서, 현재 수행에 필요한 일부 페이지들(Working set)만 주 기억장치에 위치되어 있습니다.
이러한 환경에서 각 페이지들을 보조 기억장치에서 주 기억장치로 옮기는 기법에는
크게 요구 페이징 기법과 예측 페이징 기법 두 가지가 있습니다.
요구 페이징 기법(demand paging)은 어떤 프로세스를 수행하다가 페이지 부재가 발생했을 때,
해당 페이지를 보조 기억 장치에서 주 기억장치로 옮기는 기법을 말합니다.
이 기법은 다음과 같은 특징이 있습니다.
- 실 기억장치에 옮겨진 모든 페이지 들이 프로세스에 의해 실제로 참조되는 것임을 확신할 수 있다.
- 프로그램의 실행 순서는 정확히 예측할 수 없으므로, 새로운 페이지를 통해 짐작하여 주 기억장치에 미리 옮기는 것은 잘못된 결과를 초래할 수 있다.
- 어느 페이지를 주 기억장치에 옮길 것인가를 결정하는 데 필요한 오버헤드는 최소화한다.
요구 페이징 방법에는 몇 가지 문제점이 있는데, 그 중 하나는
프로세스의 페이지 부재가 발생할 때마다 해당하는 하나의 페이지만 주 기억장치로 가져온다는 점입니다.
이러한 상황에서 프로세스는 그 페이지가 주 기억장치에 적재될 때까지
아무 일도 하지 못하고 대기해야 하는 문제가 발생할 수 있습니다.
이 대기하는 구간마다 이미 기억장치에 할당된 그 프로세스의 페이지들은 유휴 상태로 머물게 되는 것이고,
이 프로세스에 할당된 페이지가 많을수록 대기로 낭비되는 기억장치의 희생이 커지게 됩니다.
반면에, 예측 페이징 기법에서는 프로세스가 필요로 할 때마다,
페이지들을 운영체제가 예측하여 주 기억장치에 여유가 있을 때 미리 적재시킵니다.
만약 이 결정이 옳았다면, 그 프로세스는 최소의 페이지 부재율을 가지고 실행되어 실행시간을 상당히 줄일 수 있습니다.
프로세스가 현재 주 기억장치에 있는 페이지들로 실행되는 동안
시스템은 추후 사용될 새로운 페이지들을 예측하여 주 기억장치로 옮기는데,
에측 페이징 기법은 이러한 원리로 인해 다음 같은 장점을 가질 수 있습니다.
- 예측이 옳았을 경우, 프로세스의 수행시간을 매우 감소시킬 수 있다.
(이는 지역성을 이용하여 예측하게 된다면 어느 정도 적중할 수 있다.) - 미리 예측하는 방법이 적은 오버헤드를 갖는다면 다른 실행중인 프로세스에 영향을 주지 않고도 속도를 가속화할 수 있다.
- 컴퓨터 하드웨어 값이 계속 내려감에 따라 예상 페이지 기법이 주 기억장치에 적재할 초과량의 페이지들을 수용할 수 있을 정도로 실 기억장치의 용량 확장이 가능할 수 있다.
1.9. 페이지 크기
페이징 시스템에서 주 기억장치(실 기억장치)는 고정된 크기의 페이지 프레임들로 구성됩니다.
이러한 페이지 프레임들은 과연 얼마나 커야 효과적일지 의문이 들 수 있습니다.
또한, 이러한 페이지 크기는 모든 페이지에서 같은 크기로 통일할 지
아니면 서로 다른 크기를 갖게 할 지 고려해야 할 부분이 많이 존재합니다.
이러한 질문에 대한 해결 방안을 마련하기 위해서는
소프트웨어 ,하드웨어 그리고 특정 시스템에 대한 이해와 같이 넓은 분야의 지식을 필요로 할 수 있습니다.
여기에는 하나의 보편적인 해결책은 존재할 수 없으며,
그 문제에 대해 모든 컴퓨터 시스템이 같은 방식을 채택해야 할 필요도 없습니다.
따라서 이러한 페이지의 크기를 결정할 때에는 아래와 같은 내용을 고려하여 판단하는 것이 바람직합니다.
- 페이지 크기가 작으면 작을수록 보다 많은 페이지 프레임이 생기고, 이들을 관리하기 위한 기억 공간으로 인해 공간적인 비효율성이 발생하게 된다. 그리고 이러한 기억 장소의 낭비 현상을 테이블 단편화(table fragmentation)라고 한다.
- 페이지 크기가 큰 경우에는 참조되는 정보와 무관한 많은 양의 정보가 함께 주 기억장치에 적재하게 되므로, 이러한 면에서는 좀더 페이지를 작은 단위로 나누어야 할 필요가 생길 수 있다.
- 프로그램들은 지역성을 가지므로 비교적 작은 크기로 페이지를 만들 수 있다.
- 디스크 I/O 작업은 많은 시간을 필요로하므로 프로그램 실행중 I/O의 횟수를 줄이기 위해서는 페이지의 크기가 클수록 좋다.
- 페이지 내의 내부 단편화를 줄이기 위해서는 페이지의 크기를 줄일수록 좋다.
아래의 테이블은 널리 보급된 컴퓨터 시스템에서의 페이지 크기를 나타낸 표입니다.
| 제조사 | 모델 | 페이지 크기 | 단위 |
| Honeywell | Multics | 1024 | 32-bit word |
| IBM | 370/168 | 1024 or 512 | 32-bit word |
| DEC | PDP-10 PDP-20 |
512 | 32-bit word |
| DEC | VAX 8800 | 512 | 8-bit word |
| Intel | 80386 | 4096 | 8-bit word |
참고 자료
- 김완규, 고정국, 진광윤, 최신형, 하성권, 허덕행 | 핵심 운영 체제론 | 두양사
'CS BASIC > 운영체제(Operation System)' 카테고리의 다른 글
| [운영체제] 병행 프로세스와 Dekker 알고리즘 (0) | 2024.12.23 |
|---|---|
| [운영체제] 파일 시스템(File System) (2) | 2024.12.01 |
| [운영체제] 가상 기억장치의 구성과 관리 - 페이징과 세그먼테이션 (0) | 2024.11.24 |
| [운영체제] 기억장치 (記憶裝置, Memory , Computer Data Storage) (1) | 2024.11.16 |
| [운영체제] 디스크 스케줄링 (0) | 2024.04.01 |
