Introduction
Operating System
Machine-Independent Operating System Features
Machine-Independent Operating System Features
Interrupt Processing
Process Scheduling
I/O Supervision
Management of Real Memory
Management of Virtual Memory
Management of Real Memory
동시에 한 명 이상의 사용자를 지원하는 모든 운영체제는 병행 프로세스들간에 주기억장치를 분할하는 방식을 제공해야 한다. 많은 다중 프로그래밍 시스템은 각각의 프로세스에 서로 다른 분할(partition)이 할당되도록 메모리를 분할 단위로 나눈다. 나뉘어진 분할들은 위치와 크기가 고정분할(fixed partition)에서와 같이 미리 정의되거나 가변 분할(variable partition)에서와 같이 실행되는 작업의 요구에 따라 동적으로 할당될 수 있다.
고정 분할의 메모리 할당은 각 작업들을 충분히 수용할 수 있고 미사용 중인 가장 작은 분할(작업을 실행할 수 있는 최소한의 메모리)에 작업을 로드하는 것이다. 분할이 작업이 요구하는 크기보다 클 경우 분할 내의 남은 메모리는 사용되지 않는다. (남은 공간은 메모리 낭비)
작업이 한번 분할에 로드되면 수행이 완료될 때까지 남아있게 된다. 작업이 종료된 후에, 분할된 메모리의 재사용이 가능해진다.
고정 분할 방식에서 분할 크기의 초기 선택은 매우 중요하다. 크기가 큰 작업이 시간의 지연 없이 수행될 수 있도록 충분한 크기의 분할이 존재해야 한다. 그러나 만일 너무 많은 수의 큰 분할들이 존재한다면 상대적으로 크기가 작은 작업이 실행될 때는 많은 양의 메모리를 낭비하게 된다.
작업의 크기가 공통적으로 특정한 크기에 근접하거나, 작업 크기의 분포가 자주 바뀌지 않는다면 고정 분할 기법이 가장 효율적이다.
각 작업이 로드될 때마다 새로운 분할이 생성된다. 새로 생성된 분할의 크기는 작업을 로드하는 데 요구되는 크기와 정확하게 같다. 작업이 종료되면 그 작업에 할당된 메모리는 반환되고, 반환된 메모리는 그 후 다른 분할을 할당하는 데 재사용될 수 있다.
가변 분할을 이용할 때는 미리 분할의 크기를 선택할 필요가 없다. 그러나 운영체제는 메모리의 어떤 부분이 할당되었고 어떤 부분이 비어있는가를 계속해서 추적해야 하므로 부하가 가중된다. 그러한 작업을 위해서 일반적으로 운영 체제는 비어있는 메모리 영역의 링크드 리스트를 유지한다. 이 링크드 리스트는 새로운 분할이 할당될 때 스캔된다.
분할은 로드가 가능한 가장 처음 영역에 위치하거나(first-fit 할당), 로드가 가능한 가장 작은 영역에 위치한다(best-fit 할당). 분할이 해제될 때 할당되었던 메모리는 가용 리스트(free list)로 반환되고 인접한 가용 영역(free area)과 결합된다.
가변 분할을 할지 고정 분할을 할지는 수행할 작업의 크기와 특징에 따라 달라진다.
사용되는 분할 기법에 관계없이 운영체제와 하드웨어는 메모리 보호를 제공해야 한다. 어떤 작업이 하나의 분할에서 수행 중일 때 그 작업이 다른 분할들이나 운영 체제 내의 메모리 위치를 수정하지 못하도록 해야 한다. 효과적인 메모리 보호를 위해서는 하드웨어적 지원이 필요하다. 작업에 해당하는 분할의 시작 주소와 끝 주소를 포함하는 한쌍의 한계 레지스터(bounds register)를 두는 것이 방법이다.
한계 레지스터는 사용자 프로그램이 직접 액세스할 수 없고 단지 cpu가 감독자 모드일 때에만 사용된다. 운영 체제는 사용자 작업에 분할이 할당될 때 한계 레지스터들을 설정한다. 한계 레지스터의 값은 인터럽트나 LPS 명령에 의한 문맥 전환 연산 동안에 자동적으로 저장되고 복구된다.
모든 메모리 참조에 대해서 하드웨어가 참조된 주소를 한계 레지스터와 비교 검사한다. 만일 주소가 현재 분할 밖의 값이라면 메모리 참조가 수행되지 않고 프로그램 인터럽트가 발생한다.
cpu가 감독자 모드일 때 운영체제는 모든 위치의 메모리 참조가 허용된다.
동적 할당의 공통적인 문제점은 메모리 조각화(memory fragmentation)이다. 조각화는 사용 가능한 메모리가 여러 개의 분리된 블록으로 나뉘어 있고 각 블록이 사용하기에 너무 작을 때 발생한다.
메모리 조각화의 해결 방안인 재배치 가능 분할(relocatable partition)이 있다. 작업이 종료된 후 남아 있는 분할들은 가능한 한 메모리의 끝으로 이동한다. 이러한 이동은 모든 사용 가능한 메모리를 새로운 분할을 할당하는 데 유용한 하나의 연속된 블록으로 결합시킨다. 이 방법은 재배치 불가능한 분할을 사용하는 것보다 더 효과적인 메모리 활용을 할 수 있게 한다.
그러나 사용자 작업을 하나의 메모리 위치에서 다른 곳으로 복사하는 데는 상당한 시간이 필요하다. 이러한 단점에 의한 손실은 증가된 메모리 활용의 이득을 초과할 수 있다.
재배치 가능 분할의 사용은 또한 프로그램 재배치에 대한 문제를 발생시킨다. 실제적으로는 재배치 가능 분할의 구현은 하드웨어의 지원을 필요로 한다.
운영 체제에 의해 현재 실행되고 있는 프로그램의 시작 주소를 가지도록 설정된 특별한 재배치 레지스터가 있다. 재배치 레지스터는 자동적으로 문맥 전환 연산이 수행 동안에 저장되고 복원되며 변경된다. 레지스터의 값은 프로그램이 새로운 위치로 이동될 때 운영 체제에 의해 변경된다. 재배치 레지스터의 값은 사용자 프로그램이 행하는 모든 메모리 참조의 주소값에 자동적으로 더해진다.
STA 명령은 08108 번지를 참조한다. 재배치 레지스터에 의해 실제로 참조되는 주소는 36108이다. 만일 프로그램이 1A000번지로 이동된다면 운영체제는 P3의 재배치 레지스터 값을 1A000으로 변경시킨다. 그래서 STA 명령에 의해 실제로 참조되는 주소는 22108이다.
Management of Virtual Memory
가상 자원이란, 실제 구현된 것과는 다른 특성으로 사용자 프로그램이 사용할 수 있게 하는 것을 의미한다. 가상 메모리는 일반적으로 컴퓨터에서 사용 가능한 실제 메모리의 총량보다 훨씬 더 크다. 사용자 프로그램에 의해 사용되는 가상 메모리는 외부 장치인 예비 기억 장치(backing store)에 저장된다. 가상 메모리의 각 부분들은 사용자 프로그램에 의해 요구되면 실제 메모리로 mapping 된다. backing store과 가상 메모리로부터 실제 메모리로의 매핑(virtual-to-real mapping)에 관련된 내용은 사용자 프로그램에게는 완전히 은폐된다. 즉 프로그램은 가상 메모리가 실제로 존재하는 것처럼 작성된다.
요구 페이징(demand paging) 시스템에서는 프로세스의 가상 메모리는 고정 길이의 페이지 단위로 분할된다. 컴퓨터의 실제 메모리는 페이지와 동일한 길이의 페이지 프레임(page frame)으로 분할된다. 프로세스의 임의의 페이지는 실제 메모리의 페이지 프레임으로 로드될 수 있다.
가상 주소 0000부터 0FFF는 페이지 0에 포함되고, 1000부터 1FFF는 페이지 1에 포함된다. 프로그램의 실행이 시작되면 운영 체제는 실행 가능한 첫 번째 명령을 포함하는 페이지 0을 실제 메모리의 페이지 프레임으로 로드한다. 다른 페이지들은 필요할 때마다 로드된다.
가상 메모리의 페이지로부터 실제 메모리의 페이지 프레임으로의 매핑은 페이지 맵 테이블(PMT: page map table)로 표현된다.
시스템 내에서는 각 프로세스마다 1개의 PMT를 둔다. 페이지 맵 테이블(PMT)은 하드웨어가 프로그램의 가상 메모리 주소를 해당되는 실제 메모리의 주소로 변환시킬 때 사용된다. 가상 주소를 실제 주소로 변환하는 것을 동적 주소 변환(dynamic address translation)이라 한다.
(a) 페이지 0이 페이지 PMT를 거쳐 프레임 1D(실제 메모리 주소)로 로드되었다. 가상 주소 0103번지에 위치한 첫 번째 JEQ 명령의 경우 피연산자의 주소는 가상 주소 0420번지이다. 피연산자 주소 0420번지는 페이지 0에 위치하고 페이지의 시작으로부터 오프셋 420번지에 있다. 페이지 맵 테이블은 이 프로그램의 페이지 0이 페이지 프레임 1D(1D000부터 시작)에 로드 되었음을 나타낸다. 그러므로 동적 주소 변환에 의해 계산되는 실제 주소는 1D420이 된다.
(b) 가상 주소 0420 번지의 LDA 명령의 경우 명령어의 피연산자는 가상 주소 6FFA(페이지 6, 오프셋 FFA)번지이다. 그러나 페이지 6은 아직 실제 메모리에 로드되지 않았기 때문에 동적 주소 변환 하드웨어가 실제 주소를 계산할 수 없다. 때문에 페이지 부재라 불리는 특수한 형태의 프로그램 인터럽트를 발생시킨다.
(c) 인터럽트 처리 루틴은 요구된 페이지를 프레임에 로드함으로써 이 인터럽트를 처리한다. 페이지 프레임 29가 선택되어 동적 주소 변환이 성공적으로 수행된다.
P3의 페이지 맵 테이블은 0, 1, 2, 4, 6, 7, 8 페이지가 현재 로드되었다는 것을 나타내고, 각 페이지에 해당하는 페이지 프레임의 번호를 보여준다. 시스템 내의 모든 프로그램에 대해 그림과 유사한 페이지 맵 테이블이 존재한다.
동적 주소 변환 알고리즘
가상 메모리 주소를 page number, offset으로 분리 한 뒤 PMT 에서 해당 페이지를 찾는다.
해당 페이지가 메모리에 있으면 page frame address, offset를 결합하여 실제 주소 형태로 만든다.
이 때 store 명령이 있으면, PMT entry에 페이지가 변경되었음을 표시한다.
해당 페이지가 메모리에 없으면 페이지 결함 인터럽트를 발생시킨다.
페이지 부재 인터럽트 처리 알고리즘
만약 요구된 페이지가 아직 실제 메모리에 로드되지 않았다면, 하드웨어는 동적 주소 변환 계산을 수행하지 못하고 페이지 부재(page fault)라 불리는 특수한 형태의 프로그램 인터럽트를 발생시킨다.
운영체제는 모든 페이지 프레임의 상태를 나타내는 테이블을 관리한다. 페이지 부재 인터럽트를 처리하는 첫 번째 단계는 비어있는 페이지 프레임을 찾기 위해 이 표를 검색하는 것이다.
비어있는 페이지 프레임이 발견되면 요구된 페이지는 즉시 로드된다. 비어있는 페이지 프레임이 발견되지 않으면 로드될 페이지의 공간을 확보하기 위해 현재 메모리에 있는 어느 한 페이지를 제거해야 한다. 제거될 페이지가 실제 메모리로 로드된 후 수정되었다면 변경된 페이지는 backing store에 다시 기록되어야 한다. 제거될 페이지가 수정되지 않았다면 메모리 내의 페이지는 무시된다.
인터럽트 핸들러는 요구된 페이지를 로드할 페이지 프레임을 선택하고, 이후에 페이지 부재에 의해 이 프레임이 다시 선택되지 않도록 마크한다. 만약 페이지가 제거되려면, 이 페이지를 사용하고 있던 프로세스의 PMT는 그 페이지의 제거를 반영하기 위해 갱신된다. 이런 갱신은 페이지가 제거되는 동안에 프로세스가 제거되는 페이지를 참조하는 것을 방지한다.
페이지 처리 연산이 완료된 후, 인터럽트 핸들러는 저장된 상태 정보를 사용하여 페이지 부재를 발생시킨 명령으로 제어를 반환한다. 그 후 제어가 반환된 명령의 동적 주소 변환은 계속된다.
알고리즘 설명에서는 몇 가지 해결되지 않은 중요한 의문점이 있다.
어떤 페이지를 제거해야 할까?
시스템은 메모리 내의 각각의 페이지가 언제 마지막으로 참조되었는지를 기록하여 가장 오랫동안 사용되지 않은 페이지를 교체한다. 이것이 LRU(Least recently used)라고 불리는 방식이다.
다른 시스템들은 프로세스에 의해 자주 사용되는 페이지들의 집합을 결정한다. 이 집합을 프로세스의 작업 세트(working set)이라고 한다. 각각의 프로세스는 항상 메모리 내에 자신의 작업 세트를 유지한다.
페이지 맵 테이블은 어떻게 구현할까?
페이지 맵 테이블을 중앙 메모리 내에 배열로써 구현하는 방법이 있는데 이 방식은 각 주소 변환에 있어서 추가적인 메모리 액세스를 요구하므로 비효율적이다. 그러나 어떤 시스템들은 평균 액세스 시간을 개선하기 위해 고속 버퍼와 함께 이 방법을 사용한다.
특수한 고속의 연상 메모리에 페이지 맵 테이블을 구현하는 것은 매우 효율적이지만 거대한 크기의 실제 메모리를 갖는 시스템에는 많은 비용이 든다.
요구 페이징 시스템은 분할 기법에서 자주 발생하는 조각화로 인한 메모리 낭비의 대부분을 피할 수 있다. 요구 페이징 시스템은 또한 실행 동안 사용되지 않는 프로그램의 일부는 로드하지 않음으로써 메모리를 절약한다.
그러나 요구 페이징 시스템에서는 심각한 문제점이 있다. 페이지 요구로 인해 페이지 교체에 많은 시간을 쓰고 유용한 작업 시간은 얼마 되지 않는다.
높은 페이지 요구율 때문에 발생하는 서비스의 전체 손실을 스래싱(thrashing)이라 한다. 스래싱을 피하기 위해서는 페이지 부재율을 훨씬 낮추어야 한다.
대부분의 실제 프로그램에서는 참조 국부성이라 불리는 특성 때문에 메모리 참조가 프로그램의 가상 주소 공간 전체에 임의로 분포되지 않는다. (a)와 같이 메모리 참조는 주소 영역 내에서 군집을 이룬다. 이러한 참조 국부성(locality of reference) 때문에, 프로그램의 모든 주소 영역을 메모리 내에 두지 않고도 페이지 부재율을 저하시키는 것이 가능하다.
만일 메모리 내에 W보다 작은 개수의 페이지가 존재한다면 스래싱이 발생하게 된다. 메모리 내에 W 이상의 페이지가 존재한다면 만족할만한 성능을 가질 것이다. 이러한 임계점 W는 프로그램의 페이지 작업 세트(working set)의 크기가 된다.
가상 메모리 주소와 실제 메모리 주소와의 연계는 메모리 참조가 수행될 때까지는 이루어지지 않는다.
또 다른 형태의 가상 메모리는 세그먼트(segmentation) 기법이라 불리는 방식으로 구현될 수 있다. 세그먼트화된 가상 메모리 시스템에서 주소는 지정되는 세그먼트 번호와 세그먼트 내의 오프셋 값으로 구성된다.
그러나 세그먼트의 길이는 고정적이지 않다.(이에 반해 페이지는 전체 시스템에서 고정 길이를 갖는다.) 또한 세그먼트는 일반적으로 프로시져나 자료 영역들과 같은 논리적인 프로그램 단위와 관계가 있다.(이에 반해 페이지는 주소 공간의 임의적인 분할일 뿐이다.)
세그먼트 기법은 특정한 세그먼트에 읽기 전용이나 실행 전용등의 보호 속성을 설정하는 것이 가능하다. 또한 서로 다른 사용자 작업이 한 세그먼트를 공유할 수 있게 한다.
세그먼트 기법은 종종 요구 페이징 방식과 결합하여 사용되는데, 이 결합에서는 두 단계의 매핑 주소 변환 과정이 필요하다.
자료 출처
- "System Software: An Introduction to Systems Programming" by Leland L. Beck
- 동국대학교 엄진영 교수님 시스템 소프트웨어와 실습 강의 교안
'computer science > System software || OS' 카테고리의 다른 글
| Operating system (1) (0) | 2022.11.22 |
|---|---|
| Macro Processors (0) | 2022.11.20 |
| Linkers and Loaders (1) (0) | 2022.11.01 |
| Linkers and Loaders (2) (0) | 2022.10.30 |
