- 다중 프로그래밍 시스템에서는 다수의 사용자 프로세스를 메모리에 적재하기 위하여 사용자 영역을 여러 개로 분할하여야 한다. 여기서 분할은 하나의 프로세스를 메모리에 적재하는데 필요한 메모리 영역을 의미하며 크기가 고정 혹은 가변적이다.
- 다수의 고정 혹은 가변 분할된 메모리 영역에 프로세스를 할당하는 방법에는 연속(contiguous) 할당과 불연속(non contiguous) 할당이 있다.
연속 할당
- 연속 할당은 하나의 사용자 프로세스를 임의의 분할에 연속적으로 할당하는 방법으로서 분할의 크기가 할당하려는 사용자 프로세스보다 반드시 크거나 같아야 한다.
- 연속 할당 기법은 고정 혹은 가변 분할에 따라 차이가 있다.
고정 분할
- 고정 분할은 다중 프로그래밍을 위하여 메모리 주소 공간을 임의의 크기로 분할하여 사용자 프로세스를 분할 단위로 할당하는 기법이다. 이때 각 분할의 크기는 서로 다를 수 있지만 그 분할의 크기는 고정되어 있다. 따라서 적재 가능한 사용자 프로세스의 크기는 분할의 크기에 제한되며 다중 프로그래밍 정도는 분할의 수에 결정된다.
- 크기가 서로 다른 임의의 분할에 사용자 프로세스를 적재시키는 방법에 적재 기법에 따라 다르다.
절대 적재 기법은 프로그램이 번역되는 과정에서 어셈블러 혹은 컴파일러에 의해 그 프로그램이 어느 분할에 적재될 것인지 결정된다. 이 경우 운영체제는 각각의 분할에 해당하는 작업 큐(job queue)를 별도로 유지하고 해당 작업 큐에 등록된 프로그램은 반드시 해당 분할에 적재되기를 기다리게 된다. 만약 해당 분할이 이미 다른 프로세스에 의해 사용되고 있을 경우 다른 분할이 사용 가능하더라도 계속 기다려야 한다.
반면 재배치 적재 기법은 프로그램이 번역되는 과정에서 그 프로그램이 어느 분할에 적재될 것인지 결정하지 않고 프로그램이 절재될 시점에서 동적으로 결정한다. 이 경우 운영체제는 하나의 작업 큐를 유지하고 모든 프로그램들은 동일한 적업 큐에서 적재되기를 기다리면서 사용 가능한 어떤 분할에도 적재될 수 있다.
- 고정 분할 방식에서는 분할의 수와 크기가 고정되어 있다. 따라서 실행시키려는 프로세스의 크기는 반드시 분할의 크기보다 작거나 같아야 한다. 만약 프로세스의 크기는 반드시 분할의 크기보다 작거나 같아야 한다.
- 프로세스의 크기가 분할의 크기보다 너무 작을 경우에는 분할 내부에 사용하지 않는 커다란 빈 공간이 생겨 낭비하게 된다. 이와 같은 현상을 "내부 단편화(internal fragmentation)"라고 한다.
- 고정 분할 방식의 다중 프로그래밍 시스템을 지원하기 위하여 운영체제에서는 각 분할의 시작 주소, 크기, 사용 여부 등의 정보를 유지, 관리하기 위한 자료구조가 필요하다. 분할의 수와 크기가 고정되어 있기 때문에 배열(array) 구조로 구현하는 것이 효율적이다.
| 시작주소 | 크기 | 사 용 여 부 | |
| 분할 - 1 | 30k | 20k | 1 |
| 분할 - 2 | 50k | 50k | 0 |
| 분할 - 3 | 100k | 412k | 1 |
고정 분할의 자료 구조
또한 사용자 프로그램의 오류에 대한 운영체제의 보호는 물론 사용자 프로그램들 간의 보호가 필요하다. 이를 위하여 CPU 내부의 레지스터를 이용하여 현재 실행 중인 프로그램이 적재된 분할의 상한 주소와 하한 주소를 비교함으로써 사용자 프로그램의 오류에 의해 운영 체제 및 사용자 프로그램들 간의 침범을 보호할 수 있다.
가변 분할
가변 분할은 다중 프로그래밍을 위하여 메모리 전체 공간을 처음부터 여러 개의 고정된 크기로 분할하지 않고 작업 큐의 프로그램들이 작업 스케줄러에 의해 적재되는 순서대로 프로그램의 크기 만큼 메모리 공간을 가변적으로 분할하여 할당하는 기법이다.
처음에는 운영체제 영역을 제외한 나머지 메모리 공간을 하나의 커다란 분할로 취급하고 프로그램이 적재될 때마다 프로그램의 크기만큼 분할하여 할당해 나간다. 따라서 고정 분할에서 발생했던 내부 단편화 현상이 발생하지 않는다. 그러나 처음에 할당되었던 프로그램들이 종료되면 그들이 사용하였던 분할들이 빈 공간으로 남게 된다. 빈 공간들을 다시 분할하여 할당하게 되면 결국 크기가 너무 작아 사용할 수 없는 빈 공간들이 산재하게 된다. 이러한 현상을 "외부 단편화(external fragmentation)"라고 한다. 이러한 외부 단편화 현상으로 인한 메모리 낭비를 줄이기 위한 방법으로 다음과 같은 것들이 있다.
- 메모리 합병(memory coalescing) : 인접한 빈 공간이 발생할 때마다 이들을 합하여 보다 큰 크기의 빈 공간으로 만든다
- 메모리 집약(memory compaction) : 산재되어 있는 모든 빈 공간들을 주기적으로 합하여 하나의 커다란 빈 공간으로 만든다.
이러한 방법들에 의한 외부 단편화 대책은 프로그램 실행과는 무관한 것으로서 시스템의 성능을 저하시키는 요인이 된다. 외부 단편화 현상이 발생하는 근본적인 원인은 가변 분할에 의한 연속 할당 때문이다. 따라서 근본적으로 외부 단편화가 발생하지 않기 위해서는 고정 분할에 의한 불연속 할당 기법이 요구된다.
한편 가변 분할 기법에서 프로그램 적재가 가능한 빈 공간이 여러 개 존재할 경우 어느 공간에 할당할 것인가를 결정하는 동적 기억장소 할당에는 다음과 같은 방법이 있다.
- 최초 적합(first-fit) : 적재가 가능한 분할 중에서 첫 번째 분할에 할당한다. 이 방법은 가장 간단하고 오버헤드가 적다는 장점이 있다.
- 최적 적합(best-fit) : 적재 가능한 분할 중에서 분할의 크기가 프로그램의 크기에 가장 근접한 분할에 할당한다. 이 방법은 보다 큰 크기의 분할을 항상 확보할 수 있기 때문에 다음에 큰 크기의 프로그램을 적재할 수 있는 장점이 있다. 그러나 적재 가능한 모든 분할들 중에서 가장 근접한 크기의 분할을 찾아야 하는 오버헤드와 아주 작은 크기의 분할이 많이 생기는 외부 단편화 현상이 쉽게 발생하는 단점이 있다.
- 최악 적합(worst-fit) : 적재 가능한 분할 중에서 분할의 크기가 가장 큰 분할에 할당한다. 이 방법은 외부 단편화를 최소화 할 수 있는 장점이 있지만, 다음에 큰 크기의 프로그램을 적재할 수 없게 되는 단점이 있다.
가변 분할 방식의 다중 프로그래밍 시스템을 지원하기 위한 운영체제는 고정 분할에서처럼 각 분할의 시작 주소, 크기 ,사용 여부 등의 정보를 유지, 관리하기 위한 자료구조가 필요하다. 그러나 분할의 형태가 동적으로 변하기 위한 자료구조가 필요하다. 그러나 분할의 형태가 동적으로 변하기 때문에 연결 리스트(Linked list)로 구현하는 것이 효율적이다.
불연속 할당
불연속 할당은 프로세스의 주소 공간을 여러 개로 나누어 서로 다른메모리 분할에 불연속적으로 할당하는 방법이다. 따라서 분할의 크기가 할당하려는 프로세스 크기보다 반드시 클 필요가 없다. 불연속 할당에는 분할의 크기를 설정하는 방법에 따라 페이징(paging)과 세그멘테이션(segmentation), 그리고 페이징/세그멘테이션 혼용 기법이 있다.
페이징 기법
페이징(paging) 기법은 사용자 프로세스와 동일한 크기로 고정 분할하여 메모리에 불연속적으로 할당한다. 이때 프로세스의 고정 분할을 '페이지(page)', 메모리의 고정 분할을 '프레임(Frame)'이라고 부른다. 하나의 프로세스는 여러 개의 페이지로 구성될 수 있으며 각각의 페이지는 사용 가능한 임의의 프레임에 할당될 수 있다.
사용자 프로세스의 논리적 주소 공간은 메모리의 물리적 주소 공간과 구별된다. 프로세스의 논리주소는 페이지 번호(p: page #)와 변위(d:displacement)로 표현되고 메모리의 물리 주소는 프레임 번호(f : frame #)와 변위(d:displacement)로 표현된다. 여기에서 변위는 페이지 혹은 프레임의 시작 주소로부터 떨어진 상대적 위치를 의미한다.
프로세스가 실행되기 위해서는 프로세스의 논리주소(p, d)가 물리주소(f, d)로 변환되어야 한다. 운영체제는 논리주소를 물리주소로 변환하기 위하여 페이지 사상 테이블(PMT : Page Mapping Table)자료 구조를 유지, 관리한다. 일반적으로 페이지 사상 테이블은 각 사용자 프로세스마다 하나씩 유지, 관리하며 그 내용은 페이지의 프레임 번호를 포함하여 페이지 관리에 필요한 정보를 가지고 있다.
페이징 기법을 지원하는 운영체제에서는 모든 논리주소가 물리주소로의 신속한 주소 변환이 매우 중요하다. 주소 변환을 위한 페이지 사상 테이블 관리 기법에는 다음과 같은 것들이 있다.
직접 사상(direct mapping)
직접 사상 기법은 페이지 사상 테이블을 메모리의 운영체제 영역에 유지하며, 논리주소(p, d)를 물리주소(f,d)로 변환하는 과정이다. 논리 주소의 페이지 번호(p)에 해당하는 프레임 번호(f)를 얻기 위해선 먼저 논리주소의 페이지 번호(p)에 해당하는 번호(f)가 저장된 페이지 테이블의 엔트리 주소를 알아야한다. 이를 위하여 페이지 사상 테이블의 시작 주소를 CPU 내부의 레지스터(PMTBR: Page Mapping Table Base Register)에 저장한다. 따라서 페이지 번호(p)에 해당되는 프레임 번호(f)가 저장된 페이지 테이블의 엔트리 주소는 "PMTBR의 내용(b) + 페이지 번호(p) x 엔트리 크기"로 계산된다. 이 주소에서 얻은 프레임 번호(f)를 이용하여 물리주소는 :프레임 번호(f) x 페이지 크기 + 논리 주소의 변위(d)"로 변환된다.
연관 사상(associative mapping)
연관 사상 기법은 페이지 사상 테이블을 일반적인 구조의 메모리(ex: DREAM)에 유지하기 때문에 발생하는 접근 속도의 오버헤드를 개선하기 위하여 접근 속도가 빠른 연관 메모리(associative memory)를 사용하는 기법이다. 연관 메모리는 메모리 위치를 일련의 연속된 주소가 아닌 내용을 키(key) 값으로 직접 검색할 수 있는 구조의 메모리이다. 이러한 구조의 메모리에 페이지 사상 테이블을 유지함으로써 임의의 페이지에 해당하는 프레임 번호를 보다 빠르게 검색할 수 있다.
연관 사상 기법에서 논리주소를 물리 주소로 변환하는 과정은 직접 사상 기법과 매우 유사하다. 페이지 사상 테이블에 페이지 번호가 추가되어 있음을 유의해야 한다.
직접/연관 혼용(combined direct/associative)
연관 메모리는 하드웨어적으로 접근 속도는 빠르지만 가격이 비싸다. 따라서 모든 프로세스의 페이지 사상 테이블을 유지하는데 비용이 너무 많이 든다. 이러한 단점을 개선하기 위하여 직접.연관 사상 기법을 혼동하여 사용한다.
직접/연관 사상 기법에서 논리 주소를 물리 주소로 변환하는 과정은 임의의 페이지(p)에 해당하는 프레임(f)을 찾기 위하여 연관 사상 테이블을 우선적으로 검색한다. 만약 찾고자하는 페이지 (p)가 존재하지 않을 경우에는 직접 사상 테이블을 검색한다. 이때 직접 사상 테이블에 존재하는 페이지를 연관 사상 테이블에 등록시켜 줌으로써 다음에는 빠르게 접근할 수 있도록 한다. 연관 사상 테이블이 꽉 차게 될 경우 기존의 페이지를 직접 사상 테이블로 교체하도록 한다. 결국 직접.연관 혼동 기법에 의한 주소 변환은 빠르지만 그렇지 않을 경우에는 직접 사상 기법보다 느려지게 된다. 따라서 자주 접근되는 페이지들을 연관 사상 테이블에 유지할 수 있는 효과적인 페이지 교체기법이 요구된다.
페이징 기법에서 페이지 크기의 결정은 매우 중요하다. 페이지의 크기는 2^nbyte로 정의되며 일반적으로 시스템의 특성과 주로 실행되는 프로세스의 크기에 따라 512B에서 16MB까지 다양하다. 페이지의 크기를 작게 할 경우 페이지 사상 테이블의 엔트리 수가 늘어나게 되어 테이블의 크기가 커지게 되고 페이지 크기를 크게 하면 내부 단편화가 커지게 된다.
일반적으로 페이징 기법을 지원하는 운영체제에서는 관리의 편의성을 위하여 프로세스 당 하나의 페이지 사상 테이블을 유지한다. 그러나 시스템 내부에 하나의 페이지 사상 테이블을 유지할 수 있다.
실제 프레임 수만큼의 페이지 테이블을 유지하고 각 프레임에 할당된 프로세스 식별자(pid)와 프로세스의 페이지 번호(p)를 페이지 테이블에 기록한다. 따라서 페이지 테이블의 엔트리 번호(i)는 프레임 번호(f)가 해당된다. 페이지 사상 테이블의 인트리 번호(i)는 실제 메모리의 프레임 번호(f)를 의미하며 엔트리 내용은 할당된 프로세스 식별자(pid)와 페이지 번호(p)로 구성된다. 또한 논리 주소는 프로세스 식별자(pid), 페이지 번호(p) 변위(d)로 표현한다. 페이지 사상 테이블에서 논리주소의 프로세스 식별자(pid)와 페이지 번호(p)를 검색하여 해당되는 엔트리 번호(i)가 프레임 번호 (f)가 된다. 결국 페이지 사상 테이블은 임의의 프레임(f)에 할당된 프로세스의 식별자(pid)와 그 프로세스의 페이지(p)를 나타내고 이씩 때문에 '역 페이지 테이블(inverted page table)'이라고도 부른다.
페이징 기법에서 페이지 사상 테이블은 연속적으로 할당되어야 함으로 페이지 사상 테이블의 크기가 페이지 크기를 초과할 경우 문제점이 있다. 이러한 문제점을 해결하기 위한 방법으로 다단계 페이징 기법이 있다. 다단계 페이징 기법은 페이지 사상 테이블 자체를 일정한 크기로 분할하여 메모리에 불연속적으로 할당하는 기법이다.
논리 주소는 두 개의 페이지 번호(p1, p2)와 변위(d)로 표현되며 페이지 사상 테이블은 2-단계로 구성된다. 1차 페이지 사상 테이블의 엔트리(p')는 2차 페이지 사상 테이블의 시작 주소를 가리킨다. 따라서 두 개의 페이지 사상 테이블은 불연속으로 할당될 수 있다. 논리 주소의 p1은 1차 페이지 사상 테이블의 엔트리 번호를 가리키며 p2는 2차 페이지 사상 테이블의 인덱스를 가리킨다.
다단계 페이징 기법은 페이지 사상 테이블 자체를 불연속적으로 할당함으로써 페이지 사상 테이블의 크기가 페이지 크기를 초과할 경우 문제점을 해결할 수 있지만 주소 변환을 위하여 단계별로 페이지 사상 테이블을 접근해야 하는 오버헤드가 있다.
지금까지 설명한 페이징 기법은 프로세스의 논리 주소와 메모리의 물리 주소 공간을 일정한 크기로 고정 분할하여 불연속적으로 할당하였다. 따라서 고정 분할에 의한 내부 단편화가 발생하게 된다. 이러한 내부 단편화는 모든 플세스의 마지막 페이지에서만 발생하기 때문에 고정 분할 방식의 연속 할당에서 발생하는 내부 단편화에 의한 메모리 낭비보다 훨씬 적어진다. 그러나 이러한 낭비를 근본적으로 없애기 위해서는 가변 분할 방식의 불연속 할당 기법이 필요하다.
세그멘테이션(segmentation)
세그멘테이션은 페이징 기법에서 발생하는 내부 단편화를 해결하기 위한 기법으로써 사용자 프로세스를 서로 다른 크기로 분할하여 메모리에 불연속적으로 할당하는 기법이다. 이때 서로 다른 크기로 분할된 사용자 프로세스의 일부분을 '세그멘트(segment)'라고 부른다. 따라서 하나의 프로세스는 여러 개의 세그멘트로 구성될 수 있으며 사용 가능한 임의의 메모리 공간에 할당될 수 있다.
사용자 프로세스의 논리적 주소 공간은 메모리의 물리적 주소 공간과 구별된다. 사용자 프로세스의 논리 주소와 메모리의 물리 주소는 세그멘트 번호(s)와 변위 (displacement)로 표현된다. 따라서 운영체제는 논리 주소 (s, d)를 메모리의 물리 주소(s', d)로 변환하기 위하여 "세그멘트 사상 테이블(SMT : Segment Mapping Table)"이라고 부르는 자료 구조를 유지 관리한다.
일반적으로 세그멘트 사상 테이블은 각 사용자 프로세스마다 유지, 관리하며 그 내용은 세그멘트의 시작 주소와 크기를 포함하여 세그멘트 관리에 필요한 정보를 가지고 있다. 세그멘테이션 기법을 지원하는 운영체제에서 주소 변환 방법은 페이징 기법과 유사하며 신속한 주소 변환을 위한 직접 사상, 연관 사상, 그리거 직접.연관 혼합 사상 기법을 적용할 수 있다.
세그멘테이션 기법에서 직접 사상에 의한 논리 주소를 물리 주소로 변환하는 과정은 다음과 같다.
사용자 프로세스의 세그멘트 사상 테이블의 시작 주소는 CPU 내부의 레지스터(SMTBR: Segment Mapping Table Base Register)에 저장되어 있다. 따라서 논리 주소의 세그멘트 번호(s)에 해당하는 세그멘트 사상 테이블의 엔트리 주소는 :SMTBR의 내용(b) + 세그멘트 번호(s) x 엔트리 크기:로 계선된다. 실제 메모리는"세그멘트의 시작 주소(s') + 논리 주소의 변위(d)"로 계산된다.
페이징/세그멘테이션 혼용
페이징 기법은 사용자 프로세스를 단순히 일정한 크기의 페이지 단위로 분할함으로써 분할된 페이지들 간의 논리적인 연관성이 전혀 고려되지 않았다. 반면 세그멘테이션 기법은 사용자 프로세스를 논리적인 연관성을 고려하여 분할한다는 장점이 있지만 세그멘트의 크기가 다르기 때문에 이를 관리하는데 오버헤드가 증가하는 단점이 있다. 페이징/세그멘테이션 혼용 기법은 이러한 단점을 보완하기 위하여 두 기법을 혼용하여 적용하는 기법이다.
페이징.세그멘테이션 혼용 기법은 우선 사용자 프로세스를 논리적으로 연관성이 있는 세그멘트 단위로 분할하고 다시 각 세그멘트를 일정한 크기의 페이지 단위로 분할한다. 따라서 사용자 프로세스의 논리 주소는 세그멘트 번호(s), 세그멘트 내에서의 페이지 번호(p), 그리고 페이지 내부에서의 변위(d)로 표현되고 메모리의 물리 주소는 프레임 번호(f)와 변위 d로 표현된다. 운영체제는 논리 주소(s, p, d)를 메모리으 ㅣ물리주소(f, d)로 변환하기 위하여 세그멘트 사상 테이블(SMT)과 페이지 사상 테이블(PMT)의 자료 구조를 각각 유지, 관리하며 페이징, 세그멘테이션 혼용 기법에서 논리 주소를 물리 주소로 변환하는 과정은 아래와 같다.
사용자 프로세스의 세그멘트 사상 테이블의 시작 주소는 CPU 내부의 레지스터(SMTBR: Segment Mapping Table Base Register)에 저장되어 있다. 따라서 논리 주소의 세그멘트 번호(s)에 해당하는 세그멘트 사상 테이블의 엔트리 주소는 "SMTBR의 내용(sb) + 세그멘트 번호(s) x 엔트리 크기"로 계산된다. 세그멘트 사상 테이블 엔트리에는 그 세그멘트에 연관된 페이지 사상 테이블의 시작 주소(pb)를 가지고 있다. 따라서 논리 주소의 페이지 번호(p)에 해당하는 페이지 사상 테이블의 엔트리 주소는 "SMT의 내용(pb) + 페이지 번호(p) x 엔트리 크기"로 계산된다. 마지막으로 실제 메모리 주소는 "PMT의 내용(f) x 페이지 크기 + 논리 주소의 변위(d)"로 계산된다.
페이징/세그멘테이션 혼용 기법은 페이징과 세그멘테이션의 단점을 보완할 수 있지만 두 개의 사상 테이블을 유지, 관리해야하고 주소 변환을 위하여 SMT와 PMT를 두 번 참조해야 하는 오버헤드가 있다. 또한 세그멘트의 크기가 페이지 크기의 정수 배로 고정되기 때문에 고정 분할에 의한 내부 단편화가 발생할 수 있다. 그러나 이러한 내부 단편화는 항상 세그멘트 내부의 마지막 페이지에서만 발생하게 된다.
가장 전형적인 페이징/세그멘테이션 기법을 지원하고 있는 Intel 프로세서의 주소 변환 과정은 아래와 같다.
디스크리버 테이블이 SMT 역할을 담당하며 일련 주소(Linear address)를 사용하여 2-단계 페이징 기법을 사용하고 있다. 페이징 기법에서 페이지 디렉토리가 1차 페이지 사상 테이블에 해당됨을 알 수 있다.
메모리 관리 기법은 프로세스를 실행하기 위하여 반드시 프로세스 전체가 메모리에 적재되어야 함을 가정한다.
즉, 프로세스의 크기가 실제 메모리의 빈 공간보다 작을 경우에만 가능한 것이다.
Reference
개념 이해를 위한 운영체제
https://joepasss.tistory.com/11
OS - 다중 프로그래밍 (고정분할 다중 프로그래밍)
1. 고정분할 다중 프로그래밍 운영체제가 주기억장치를 할당하기 전에 주기억장치의 사용자 영역을 여러 개의 일정한 크기로 분할하고 준비상태 큐에서 프로그램을 각 영역에 할당하여 실행하
joepasss.tistory.com
'CS > 운영체제' 카테고리의 다른 글
| [Chapter 6] 개념 이해를 위한 운영체제 [파일 시스템 - 빈 공간 관리] (0) | 2025.03.03 |
|---|---|
| [Chapter 6] 개념 이해를 위한 운영체제 [파일 시스템 - 개요] (0) | 2025.03.02 |
| [Chapter 5] 개념 이해를 위한 운영체제 [메모리 관리 - 단일 프로그래밍 시스템] (0) | 2025.02.27 |
| [Chapter 5] 개념 이해를 위한 운영체제 [메모리 관리 - 개요] (0) | 2025.02.27 |
| [Chapter 4] 개념 이해를 위한 운영체제 [교착상태 - 교착상태 해결책] (0) | 2025.02.26 |