7. 메모리 관리

---

 

 

1. 메인 메모리

메인 메모리는 컴퓨터의 핵심 자원으로 프로세서는 메인 메모리로부터 처리할 내용을 불러오고 메인 메모리에 처리 결과를 저장한다.

기본 단위는 바이트(byte) 또는 워드(word)를 사용한다.

 

1.1) 메모리 관리

운영체제는 동적으로 메인 메모리를 관리한다.

메인 메모리 관리 활동에는 프로세스들을 위한 메모리 할당, 제거, 보호 등이 있다.

메인 메모리는 운영체제를 위한 영역과 실행 중인 프로그램을 위한 사용자 영역으로 구분된다.

다중 프로그래밍 시스템에서는 사용자 영역을 여러 프로세스가 사용하도록 세분화하는 작업이 필요하다.

 

---

 

2. 메모리 관리 개념과 정책

2.1) 반입 정책/적재 정책 (Fetch Strategy)

디스크에 있는 프로세스를 메인 메모리에 로드할 시기를 결정하는 방법이다.

요구 반입(Demand Fetch), 예상 반입(Anticipatory Fetch) 등이 있다.

 

2.2) 배치 정책 (Placenment Strategy)

디스크에서 반입한 프로세스를 메인 메모리의 빈 공간 중 어디에 저장할 것인지를 결정하는 방법이다.

최초 적합(First-Fit), 최적 적합(Best-Fit), 최악 적합(Worst-Fit) 등이 있다.

 

2.3) 교체 정책/대치 정책 (Replacement Strategy)

메인 메모리가 부족하여 새로 로드할 프로세스를 놓을 공간이 없을 때, 기존의 어떤 프로세스를 제거할 것인지를 결정하는 방법이다.

 

2.4) 메모리를 해석하는 2가지 관점

메인 메모리에 프로세서의 계산 값을 저장하거나, 필요한 정보를 불러오기 위해서는 논리적 주소를 물리적 주소로 변환하는 과정이 필요하다.

논리적 주소 공간은 실제 메인 메모리의 주소 공간과 무관하게 0부터 시작하는 프로그램 코드 상에서의 메모리 주소 공간이다.

논리적 공간 크기는 각 시스템에서 정의한 워드 길이에 따라 다르다.

32Bit 시스템이라면 논리적 공간의 크기가 2^32바이트이므로 4GB가 된다.

물리적 주소 공간은 데이터, 프로그램이 저장되는 실제 메모리 공간을 말한다.

물리적 주소 공간은 논리적 공간보다 크거나 작을 수 있다.

예를 들어 32bit 시스템을 사용하지만 메모리를 2GB만 사용할 경우, 논리적 공간(4GB)이 물리적 공간(2GB) 보다 더 크다.

 

---

 

3. 메모리 구조와 매핑

3.1) 메모리 장치의 주소 변환

주소 매핑(Mapping) 작업은 MMU(Memory Management Unit)에서 이루어진다.

주소 변환 기법은 다음과 같이 메모리 관리 방식에 따라 달라진다.

• 연속 메모리 할당: 고정 분할, 가변 분할(동적 분할)
• 불연속 메모리 할당: 페이징, 세그멘테이션, 페이지화된 세그멘테이션

연속 메모리 할당은 메모리 주소 배치가 연속적이다.

이로 인해 주소가 변환되어 저장된 데이터가 어디에 어떻게 저장되는가를 비교적 쉽게 파악할 수 있다.

불연속 메모리 할당은 변환 기법에 따라 데이터가 저장되는 위치가 달라질 수 있다.

 

3.2) 바인딩의 분류

프로세서가 프로세스를 실행하려면, 그 프로세스의 논리적 주소에 대한 물리적 주소가 정해져야 한다.

이를 바인딩이라고 하며, 바인딩이 이루어지는 시점은 다음과 같이 다양하다.

주소 바인딩이란, 논리적 주소에 해당하는 물리적 주소를 정해주는 것을 말한다.

프로그램의 주소를 절대 주소로 바꾸어 메인 메모리에 적재될 수 있게 한다.

주소 바인딩 시점에 따른 구분으로는 다음과 같다.

• 컴파일 시간 바인딩: 원시 코드가 컴파일되어 목적 파일로 변환되는 단계에서 컴파일러가 절대 주소를 생성한다.
• 적재 시간 바인딩: 링킹 과정을 거쳐서 메모리에 로드되는 단계에서 물리적 주소가 결정된다. 최종 바인딩을 적재 시간까지 연기한다. 컴파일러가 재배치 가능한 상대 주소를 생성하는 경우, 상대 주소는 프로그램 시작 주소가 0이다.
  
• 실행 시간 바인딩: 프로그램이 실행되는 도중 메모리 상의 위치가 변하는 경우, 바인딩을 실행 시간까지 연기한다. 현재 범용 운영체제 대부분이 실행 시간 바인딩 구조이다.

 

---

 

4. 메모리 관리 관련 용어

4.1) 동적 적재 (Dynamic Loading)

프로세스가 실행되기 직전에 주소를 확정하여 메모리를 효율적을 사용하는 방법.

초기 컴퓨터 시스템에서 메모리의 크기가 프로세스의 크기를 제한하는 문제를 해결하기 위해 고안되었다.

당장 사용하지 않는 루틴은 메모리에 올리지 않는 방법을 통해 메모리 크기보다 더 큰 프로세스도 원활하게 로드하여 사용할 수 있게 만들었다.

동적 적재 수행 과정은 다음과 같다.

• 모든 루틴은 실행 시간에 호출될 때까지 메모리 내에 로드되지 않고 재배치 가능한 형태로 디스크에 저장된다.
• 메인 루틴은 먼저 메모리에 로드되어 실행된다.
• 메인 루틴이 다른 루틴을 호출할 때, 호출될 루틴이 메모리에 로드되어 있는지를 조사한다.
• 호출될 루틴이 로드되어 있지 않다면 루틴을 메모리에 적재하고 프로그램 주소 테이블을 갱신한다.

 

4.2) 중첩 (Overlay)

메인 메모리보다 더 큰 프로그램을 실행할 수 있도록 하는 방법을 중첩이라고 부른다.

메모리 일부분에 프로그램 실행 중 계속 필요한 사용자 코드와 데이터를 로드한다.

중첩 영역에는 메모리 크기보다 더 큰 초기 모듈, 처리 모듈, 출력 모듈 중에서 상황에 맞춰 1개씩 로드하여 실행한다.

메모리보다 크기가 큰 프로그램들 중에서 동시에 실행될 필요가 없는 모듈들은 중첩 영역을 공유해 조건에 맞게 모듈을 1개씩 불러와 사용하는 방식이다.

중첩을 사용하려면, 프로그래머가 중첩 구조를 적절하게 설계하고 프로그래밍해야 한다.

 

3) 메모리 스와핑 (Swapping)

프로세스가 메인 메모리에 계속 머물 필요가 없도록 하는 방법.

• 스왑 아웃(Swap out): 프로세스가 메모리를 차지하고 실행하다가 프로세서를 사용하지 않을 때는 메모리를 내어준다. 
• 스왑 인(Swap In): 프로세스가 다시 작업을 수행해야 하면 메모리에 다시 올라와 실행된다.

스와핑은 프로세스를 일시적으로 보조 기억 장치에 내보내고 새롭게 시작할 프로세스를 메모리에 적재하는 과정이므로 중기 스케줄링에 해당한다.

초기 시분할 시스템에서 사용된 기법으로 이후 페이징(Paging)으로 발전되었다.

 

---

 

5. 연속 메모리 할당

5.1) 메모리 할당 방법 분류

연속 메모리 할당이란, 프로세스가 필요한 만큼 메모리의 연속된 공간을 할당받는 것을 말한다.

불연속 메모리 할당(분산 메모리 할당)이란, 프로세스가 필요로 하는 공간을 메모리의 여러 위치에 분산하여 할당받는 것을 말한다.

 

5.2) 연속 메모리 할당

메모리 공간을 연속적으로 할당받는다.

프로그램이 메모리 용량보다 크면, 한 번에 적재할 수 없어 실행도 불가능해진다.

이 문제를 해결하려면 프로그램을 수정하거나, 작은 모듈로 구성해야 한다. (중첩 기법 등)

초기 컴퓨터 시스템의 메모리 관리 기법이다.

 

5.3) 단일 사용자 연속 메모리 할당

메모리 영역을 운영체제를 위한 공간과 사용자 프로그램을 위한 공간으로 구분한다.

1번에 1개의 프로세스만 메모리를 사용할 수 있다.

• 메모리 보호 기법: 사용자 프로세스가 운영체제 영역에 접근하는 것을 막고자, 프로세서 내에 경계 레지스터를 두고, 사용자 프로세스가 메모리를 참조할 때마다 경계 레지스터로 주소를 검사한다.
• 경계 레지스터: 운영체제 영역의 끝을 가리키고 있으며, 사용자 프로세스가 경계 레지스터의 주소 값보다 작은 주소를 참조하고자 하면 오류를 발생시킨다.

 

5.4) 고정 분할 다중 프로그래밍

메모리를 여러 개의 고정된 크기의 분할로 나누고, 각 분할에 프로세스를 1개씩 할당한다.

메모리에 할당될 프로세스들은 선입선출 큐를 사용해 관리한다.

기준 레지스터와 한계 레지스터를 사용하여 분할된 영역을 보호한다.

• 기준 레지스터: 분할이 시작되는 지점을 나타내는 물리 메모리 주소
• 한계 레지스터: 분할의 크기를 나타내는 물리 메모리 주소

기준 레지스터와 한계 레지스터를 더하면, 해당 작업의 메모리 주소가 끝나는 경계선을 알 수 있다.

프로세서가 생성한 모든 주소를 기준/한계 레지스터로 검사하여 다른 사용자 프로그램을 보호한다.

프로세서가 실행 중인 사용자 프로세스가 기준 레지스터 이상 ~ 기준+한계 레지스터 미만의 주소를 요청했을 때만 메인 메모리에 접근할 수 있도록 허용한다.

고정 분할 다중 프로그래밍 방식에서는 고정된 분할보다 큰 프로세스 실행이 불가능하다.

할당받은 공간보다 프로세스 크기가 더 작으면, 내부 단편화 문제가 발생할 수 있다.

이는 고정된 크기로 메모리를 먼저 분할하고 분할된 크기 이하인 프로세스라면 해당 프로세스가 실질적으로 사용하는 메모리 공간을 고려하지 않고 무조건 할당하기 때문이다.

 고정 분할 다중 프로그래밍의 성능 향상에는 분할 영역의 개수와 크기 결정과 프로세스를 어느 영역에 배치하는지 결정하는지가 큰 영향을 미친다.

 

5.5) 각 영역별로 독립된 큐가 있는 고정 분할 시스템

각 영역별로 배치되어 있는 큐에서 하나씩 꺼내서 메모리에 할당한다.

 

5.6) 통합된 대기 큐가 있는 고정 분할 시스템

통합된 큐 하나에서 하나씩 꺼내어 메모리에 할당한다.

 

5.7) 가변 분할 다중 프로그래밍

고정된 경계를 없애고, 프로세스가 필요로 하는 만큼만 메모리를 할당하는 방법.

각 프로세스(분할 영역)를 나타내기 위해 기준/한계 레지스터를 사용한다.

• 기준 레지스터(Base Register): 프로세스의 메모리 시작 주소
• 한계 레지스터(Limit Register): 프로세스의 크기를 나타내는 메모리 주소

프로세서 스케줄러가 프로세스 선택 시, 디스패처는 기준/한계 레지스터에 새로운 값을 로드한다.

 

5.8) 가변 분할 다중 프로그래밍 동작 과정

(a)와 같이 작업 큐에 작업이 대기 중이라면, 메모리 할당은 (b)와 같이 이루어진다.

가변 분할 다중 프로그래밍 시스템에서는 메모리 할당, 반납을 반복하면서 여러 개의 작은 빈 공간이 발생하게 된다.

이로 인해 요구한 크기의 메모리를 어느 공간에 할당할 것인지를 결정하기 위한 배치 정책이 필요하다.

물리적 메모리에 작업이 할당되는 과정에서 외부 단편화 문제가 발생할 수 있다.

즉, 비어 있는 사용 가능 공간이 흩어져 있어서 전체 사용 가능 공간은 충분함에도 작업 할당이 불가능해지는 문제가 발생할 수 있다.

배치 정책의 예로는 다음과 같이 3가지가 있다.

• 최초 적합(First-Fit)
• 최적 적합(Best-Fit)
• 최악 적합(Worst-Fit)

일반적으로 최초 적합(First-Fit) 방식과 최적 적합(Best-Fit) 방식이 최악 적합(Worst-Fit) 방식보다 더 효율적이다.

또한 최초 적합(First-Fit) 방식이 최적 적합(Best-Fit) 방식보다 메모리를 더 빨리 할당한다.

최초 적합은 사용 가능 공간 리스트에서 프로세스가 요구한 크기 이상인 1번째 Hole을 할당한다.

리스트의 처음부터 검색하거나, 이전에 검색을 마친 곳부터 검색한다.

검색은 빠르지만, 공간 활용률이 떨어진다.

최소 적합은 사용 가능 공간 리스트에서 프로세스가 요구한 크기 이상인 Hole 중에서 가장 작은 Hole을 할당한다.

사용 가능 공간 리스트를 Hole 크기 오름차순으로 정렬/유지해야 하며, 오름차순으로 정렬되어 있지 않다면 전체 리스트 검색이 필요하다.

공간 활용률은 최초 적합 방식보다는 좋으나, 할당/반납 시간이 오래 걸린다.

남는 공간이 가장 적은 Hole을 선택하므로, 할당 과정에서 매우 작은 Hole들이 생길 수 있다.

최악 적합은 사용 가능 공간 리스트 중 가장 큰 Hole에 할당한다.

사용 가능 공간 리스트를 Hole 크기 내림차순으로 정렬/유지해야 하며, 내림차순으로 정렬되어 있지 않다면 전체 리스트 검색이 필요하다.

매우 작은 Hole이 생기는 문제는 해결할 수 있으나, 매우 큰 Hole이 남아있지 않아 상대적으로 크기가 큰 작업을 할당하기가 곤란해진다.

 

5.9) 외부 단편화 문제

메모리 전체 빈 공간의 양은 충분하더라도, 너무 작은 공간들로 나눠져 있어서 어느 프로세스의 요구도 들어줄 수 없는 상태를 말한다.

가변 분할 방식을 사용하면 외부 단편화 문제가 발생할 수 있다.

크기가 서로 다른 프로세스들이 연속된 메모리를 할당, 반납하는 과정이 반복되면, 사용 가능 공간이 여러 개의 작은 공간(Hole)들로 단편화될 수 있다.

외부 단편화 문제를 해결하는 방법으로는 메모리 통합(Coalescing), 메모리 압축(Compaction), 버디 시스템 등이 있다.

메모리 통합(Coalescing)이란, 1개의 작업이 끝났을 때 반납할 Hole이 다른 Hole과 인접한 지를 검사하여 인접한 경우 Hole을 합쳐서 큰 Hole로 바꾸는 방법을 말한다.

메모리 통합을 수행하더라도, 인접한 Hole만 합칠 수 있기 때문에 메모리 전반에 흩어진 모든 Hole을 하나로 합치기는 힘들다.

메모리 압축(Compaction)이란, 사용 중인 메모리 공간의 내용들을 적절하게 이동하여 사용 가능 공간을 1개의 큰 Hole로 모으는 방법을 말한다.

동적 주소 재배치(실행 시간 바인딩)가 가능한 경우에만 사용할 수 있다.

메모리 압축 과정 중에는 참조하게 되는 메모리 주소가 바뀌게 되므로, 모든 다른 작업을 중지해야 한다.

메모리 압축 방법에 따라 이동량에 차이가 있을 수 있다.

버디 시스템이란, 고정 분할과 가변 분할의 단편화 현상을 해결하는 방법을 말한다.

큰 버퍼들을 요청에 맞게 이등분하여 작은 버퍼들을 얻고, 가능할 때마다 이등분된 인접한 빈 버퍼를 합치는 과정을 반복한다.

이때, 한 버퍼를 나누어 얻은 두 버퍼를 서로의 버디라고 한다.

 

---

 

6. 분산 메모리 할당

분산 메모리 할당(불연속 메모리 할당)이란, 1개의 프로세스를 메인 메모리에 분산하여 불연속적으로 할당할 수 있도록 허용하는 것이다.

 

6.1) 페이징 기법 (Paging)

논리 메모리를 일정 크기의 페이지로 나눠서 물리 메모리에 분산 적재하는 기법.

물리 메모리를 페이지 프레임이라 불리는 고정 크기 블록으로 나눈다.

각 프로세스 논리 메모리도 페이지라고 불리는 블록으로 나눈다.

이때, 페이지의 크기는 페이지 프레임 크기와 동일하다.

사용자 프로세스는 메모리가 1개의 연속적인 공간이라고 생각할 수 있으나, 물리 메모리 상에서는 흩어져서 저장되는 비연속 메모리 할당 방법이다. (주소 변환 HW가 논리 주소를 실제 주소로 변환)

프로세스 논리 메모리의 각 페이지가 실제 메모리의 어느 위치에 놓였는지를 찾을 수 있어야 한다.

이를 위해 프로세스마다 페이지 테이블을 가진다.

페이지 테이블에는 각 페이지가 몇 번 프레임에 로드되었는지를 기록해 둠으로써, 논리 페이지 번호를 알면 물리 페이지 프레임 번호를 알아낼 수 있도록 해준다.

매핑 단계는 논리 메모리 페이지 -> 페이지 테이블 -> 물리 메모리 순이다.

동작 방식을 보면, 일종의 고정 분할 다중 프로그래밍 기법이라고 볼 수 있다.

페이징 기법은 빈 페이지 프레임을 어떤 프로세스의 어떤 페이지도 사용할 수 있기 때문에 효율적으로 메모리 사용이 가능하다.

메모리를 고정된 크기의 페이지로 나누어 할당함으로써, 효율적인 다중 프로그래밍 실현을 가능하게 한다.

외부 단편화 문제가 발생하지 않는다.

배치(Placement) 전략이 필요 없다.

공유 페이지를 통해 프로세스의 코드를 공유할 수 있다.

연속 메모리 할당 방식에 비해서 운영체제 메모리 관리 부담이 커진다.

고정된 크기의 페이지 프레임 단위로 할당하므로, 내부 단편화가 발생할 수 있다.

페이지의 크기를 줄이면 내부 단편화를 줄일 수 있으나, 페이지 테이블이 커져서 메모리 낭비가 발생할 수 있다.

페이지 매핑용 하드웨어로 인한 비용이 상승한다.

내부 단편화 문제가 발생할 수 있다.

주소 공간을 고정된 페이지로 분할하고 페이지 단위로 메모리를 할당하므로 사용자 관점과 다르게 메모리가 할당된다.

 

6.2) 페이징 시스템의 하드웨어

페이지 테이블을 참조하여 논리 주소를 물리 주소로 매핑한다. (논리 주소 -> 페이지 테이블 -> 물리 주소)

페이지 테이블에 참조하여 물리 주소를 찾아낼 수 있도록, 논리 주소를 페이지 번호(p)와 오프셋(d)으로 나눈다.

페이지 번호 p는 페이지 테이블 시작 주소에서 얼마나 떨어져 있는가를 나타내며, 페이지 테이블에서 p 위치만큼 떨어진 곳에 저장된 페이지 프레임 번호(f)를 얻어온다.

만약 p가 2일 경우, 페이지 테이블 시작 주소에서 2만큼 떨어진 곳에 저장된 값이 페이지 프레임 번호이다.

페이지 프레임 번호 f는 물리 주소의 앞부분이 되며, 물리 주소 뒷부분은 논리 주소가 가지고 있던 오프셋 d가 따라붙는다.

이렇게 만들어진 물리 주소가 물리 메모리에 저장된 데이터의 주소가 된다.

 

6.3) 페이징 시스템의 논리 주소

페이지 크기는 2의 n승이며, HW에 의해 정의된다.

페이지 크기가 2^n승이면, 논리 주소의 하위 n비트는 페이지 오프셋을 나타내고, 나머지 상위 비트는 페이지 번호를 나타낸다.

페이징 시스템에서는 1개의 큰 페이지 테이블을 메인 메모리 연속 공간에 유지해야 한다.

가상 주소 공간의 크기가 커질수록, 페이지 테이블의 크기 또한 증가하므로, 더 큰 메인 메모리 공간을 요구하게 된다.

다중 단계 페이징(Multi-Level Paging)으로 이러한 문제를 해결할 수 있다.

예를 들어 32bit 주소 공간, 페이지 크기가 4kb(2^12)인 경우, 아래와 같다.

• 프로세스의 최대 가상 메모리 크기: 4G(2^32)
• 페이지 테이블 항목의 수: 2^20
• 페이지 테이블 항목 1개가 4byte라면, 페이지 테이블이 차지하는 메모리 크기: 4 * 2^20 = 4mb(2^22)

 

6.4) 다중 단계 페이징 기법

페이지 테이블을 N-단계 계층 구조로 구성한다.

즉, 페이지 테이블을 다시 페이징 하는 것이다.

실제 참조할 페이지들이 존재하는 영역에 대해서만 단계별 페이지 테이블을 설정해 처리하며, 페이지 테이블을 메인 메모리에 분산 저장한다.

• 논리적 주소 하위 12비트는 페이지 오프셋
• 논리적 주소 중간 10비트는 2차 수준 테이블 인덱스 (P2)
• 논리적 주소 상위 10비트는 1차 수준 테이블 인덱스 (P1)

P1을 사용해 1차 수준 테이블(페이지 디렉터리)에 접근하여 2차 수준 테이블을 선택한다.

P2를 사용해 2차 수준 테이블에서 테이블 시작 지점부터 P2만큼 떨어진 지점을 계산, 프레임 주소를 알아낸다.

페이지 오프셋과 P2를 통해 알아낸 프레임 주소를 결합해 물리적 주소를 알아내 접근한다.

페이지 테이블에는 다음과 같이 다양한 정보들을 기록해둘 수 있다.

 

6.5) 페이지 테이블 구현 방법

전용 레지스터를 사용해 페이지 테이블을 구현하는 방법

• 페이지 테이블의 각 항목들을 전용 레지스터에 저장한다.
• 페이지 테이블 접근 속도가 빠르므로, 페이징 주소 변환도 매우 빠르다.
• 페이지 테이블 크기가 작은 경우에 사용할 수 있다.

페이지 테이블을 메인 메모리에 유지하는 방법

• 대부분의 시스템에서 페이지 테이블이 크므로, 전용 레지스터로 구현하는 것이 적합하지 않다.
• 페이지 테이블을 메인 메모리에 두고, 페이지 테이블 기준 레지스터(PTBR)가 실행 중인 프로세스의 페이지 테이블을 가리키도록 한다.

 

6.6) 직접 매핑(Direct Mapping)에 의한 페이지 주소 변환

페이지 테이블의 모든 항목을 메인 메모리에 둔다.

매핑 과정으로 인해 메모리 접근 시간이 길어진다.

1개의 메모리 워드에 접근하려면, 2번의 메모리 접근(페이지 테이블 접근, 메모리 워드 접근)이 필요하다.

페이지 번호와 페이지 테이블 기준 레지스터 값을 더하면 페이지 테이블 주소 값이 나온다.

그 값에 오프셋을 더하면 물리적 주소를 얻을 수 있다.

 

6.7) 연관 매핑(Associative Mapping)에 의한 페이지 주소 변환

연관 레지스터 또는 변환 우선 참조 버퍼로 페이지 테이블을 구현한다.

연관 레지스터는 <키, 값> 쌍을 저장하며, 모든 키를 동시에 비교해 키가 발견되면 대응하는 값 부분을 출력하므로, 빠른 탐색이 가능하다.

연관 레지스터에 <페이지 번호, 페이지 프레임 번호>를 쌍으로 저장하여 페이지 번호로부터 프레임 번호를 빠르게 얻을 수 있도록 구성한다.

페이지 테이블 기준 레지스터는 불필요하다.

주소 변환 속도가 매우 빠르지만, 연관 메모리 하드웨어가 비싸다.

시스템의 모든 프로세스의 페이지 테이블 항목을 저장할 만큼 충분한 연관 레지스터를 갖추기가 어렵다.

 

6.8) 연관/직접 매핑을 결합한 페이지 주소 변환

페이지 테이블의 모든 항목을 메인 메모리에 유지한다.

단, 일부 항목 정보를 빠른 연관 레지스터에 유지한다.

즉, 일종의 캐시처럼 최근 참조한 일부 페이지들에 대한 매핑 정보만 연관 레지스터에 유지하는 것이다.

이는 지역성을 기반으로 작동된다.

프로세스는 메모리의 정보에 균일하게 접근하는 것이 아니라, 최근에 참조한 것을 빠른 시일 내에 또 참조하려는 시간적 지역성을 기반으로 접근한다.

따라서 적은 양의 연관 메모리로도 큰 성능 향상을 기대할 수 있다.

여기서 적중률이란, 페이지 번호가 연관 레지스터에서 발견되는 비율을 말한다.

적중률이 80% 일 때, 연관 레지스터 탐색 시간: 50ns, 메모리 접근 시간이 750ns이라면 다음과 같다.

• 적중까지 소요 시간: 50 + 750 = 800ns
• 적중하지 못한 경우 소요 시간: 50 + 750 + 750 = 1550ns
• 유효 접근 시간(평균): 0.8 * 800 + 0.2 * 1550 = 950ns

적중률이 90% 일 때는 다음과 같다.

• 유효 접근 시간: 0.9 * 800 + 0.1 * 1550 = 875ns

적중률이 높을수록, 유효 접근 시간이 짧아진다. (적중률은 연관 레지스터의 수와 관련됨)

연관 레지스터에 해당 페이지가 없는 경우, 메인 메모리 상의 페이지 테이블에 접근해야 하므로, 연관 매핑보다 주소 변환 속도가 느리다. (직접 매핑보다는 평균 주소 변환 속도가 빠름)

 

6.9) 공유 페이지

페이징 시스템에서 여러 프로세스가 공통된 코드를 공유할 수 있다.

3명의 사용자가 문서 편집기를 동시에 실행하는 경우, 문서 편집기는 재진입 가능 코드(Re-Entrant Code)와 데이터로 구성된다.

코드 페이지 ed1, ed2, ed3는 프로세스들이 공유하며, 데이터 페이지는 각자 따로 가진다.

 

6.10) 페이징에서의 메모리 보호

페이지 테이블 항목에 읽기/쓰기, 읽기 전용 등을 정의하는 비트를 둔다.

• 1100: 읽기 전용 페이지이다.
• 1110: 읽기, 쓰기가 가능한 페이지이다.
• 1111: 읽기, 쓰기, 실행이 모두 가능한 페이지이다.

읽기 전용 페이지에 쓰기를 시도할 경우, 하드웨어 트랩(메모리 보호 위반)을 발생시킨다.

페이지 접근 허용 여부를 결정하려면, 페이지 테이블에 valid/invalid 비트를 두어 각 페이지 접근이 타당한가를 확인하면 된다.

타당/비타당 비트는 맨 앞 1비트를 사용한다. (값이 1이면 타당, 값이 0이면 비타당)

비타당 비트일 경우, 해당 구역은 페이지 테이블이 빈 영역임을 의미한다. (접근이 타당하지 않은 영역 == 데이터 자체가 없는 영역)

 

6.11) 세그먼테이션 기법 (Segmentation)

프로세스의 논리 주소 공간을 세그먼트라는 다양한 크기 블록의 모임으로 보고, 세그먼트 단위로 메인 메모리를 할당한다.

세그먼트의 종류로는 서브루틴(SubRoutin), 함수(Function), 스택(Stack) 등이 있다.

각각의 세그먼트들은 연관된 기능을 수행하는 1개의 모듈이다.

일반적으로 컴파일러가 소스 프로그램으로부터 서브 루틴, 함수, 모듈 등 크기가 서로 다른 세그먼트들을 생성한다.

페이지와는 달리, 세그먼트는 크기가 다양하므로, 메인 메모리를 일정한 크기의 블록으로 나눠서 관리하지 않는다.

1개의 프로세스에 여러 세그먼트가 있을 때, 각 세그먼트는 연속된 메모리 공간에 할당되지만, 세그먼트끼리는 메모리에 연속일 필요가 없다.

동적 분할(가변 분할) 기법으로 메인 메모리를 할당한다.

동작 방식을 보면, 일종의 가변 분할 다중 프로그래밍 기법이라고 볼 수 있다.

메모리의 사용자 관점을 지원하는 비연속 메모리 할당 방법이다.

서브루틴, 함수, 스택 등의 세그먼트들은 사용자가 봤을 때 특정 기능을 수행하는, 메모리 할당이 필요한 부분임을 직관적으로 이해할 수 있다.

능동적으로 메모리 공간을 할당하므로 페이징 기법의 내부 단편화 문제를 해결할 수 있으나, 외부 단편화 문제가 발생할 수 있다.

 

6.12) 세그먼테이션의 하드웨어

세그먼테이션의 논리적 주소는 세그먼트 번호(S)와 세그먼트 내의 오프셋(D)으로 구성된다.

논리적 주소 = <세그먼트 번호(s), 세그먼트 오프셋(d)>

Ex) 세그먼트가 최대 2^8개, 각 세그먼트 길이가 최대 64KB(2^16) 일 때, 세그먼테이션의 논리 구조

 

6.13) 세그먼트 테이블

각 프로세스는 자신의 개별 세그먼트 테이블을 가진다.

세그먼트 테이블은 메인 메모리에 유지한다.

프로세스의 세그먼트 개수 == 프로세스의 세그먼트 테이블 항목 수

세그먼트 테이블의 각 항목은 해당 세그먼트의 메인 메모리상 주소와 길이 정보를 지닌다.

STBR (Segment-Table Base Register)

• 실행 중인 프로세스의 세그먼트 테이블 시작 주소를 나타낸다.

STLR (Segment-Table Length Register)

• 실행 중인 프로세스의 세그먼트 테이블 길이, 즉, 세그먼트의 개수를 나타낸다.

 

6.14) 세그먼테이션 동작 과정

세그먼트 번호 0~4인 5개의 세그먼트로 구성된 프로세스

논리 주소 <3, 250> -> 물리 주소 3450(3200 + 250)을 매핑한다.

논리 주소 <0, 1222> -> 세그먼트 0의 길이를 초과하므로 오류가 발생한다.

세그먼트 테이블 길이 레지스터(STLR)의 시작 주소에서 세그먼트 번호 값만큼 떨어진 위치를 탐색한다.

세그먼트 테이블의 길이와 세그먼트 오프셋의 값을 비교해 (세그먼트 오프셋 < 세그먼트 테이블)이 참인지 검사한다.

검사 결과가 참일 경우, 세그먼트 테이블의 기준 레지스터 값(STBR)과 세그먼트 오프셋 값을 더해서 물리 메모리 주소 값을 계산한다.

 

6.15) 세그먼트 공유

페이징 시스템보다 단순하다.

세그먼트 1개를 공유하려면, 2개 이상의 세그먼트 테이블에 속한 세그먼트 항목 1개에 동일한 물리 메모리 주소를 지정하면 된다.

Ex) 문서 편집기의 코드를 공유할 때, 각 세그먼트 테이블에서 메모리의 같은 세그먼트(43062)를 지정한다.

• 사용자 1의 세그먼트 0이 논리 주소 <0, 1234>를 생성한다.
• 사용자 1의 세그먼트 테이블에서 STLR의 0의 값과 비교한다.
• 세그먼트 0 논리 주소의 오프셋 값이 STLR 값보다 작으므로, 오프셋과 STBR을 더한다. (물리 메모리 주소)
• 사용자 2의 세그먼트 0이 논리 주소 <0, 1234>를 생성한다.
• 사용자 1과 동일한 과정을 거쳐 동일한 물리 메모리 주소가 계산된다. (세그먼트 1개 공유)

 

6.16) 페이징과 세그먼테이션 비교

페이징은 물리적 메모리와 무관하게 큰 연속된 논리 주소 공간이 가능하게 만들고자 등장한 개념이다.

세그먼테이션은 프로그램과 데이터를 논리적으로 독립된 주소 공간으로 나누고, 쉽게 공유/보호할 수 있게 만들고자 등장한 개념이다.

페이징은 비어있는 페이지 프레임 아무 곳에나 배치한다.

그에 달리 세그먼테이션은 크기가 서로 다른 세그먼트에 대해서 메모리의 적당한 공간을 찾아 동적으로 메모리를 할당해주어야 한다. (Best-Fit 또는 First-Fit 알고리즘 이용)

페이징은 내부 단편화(Internal Fragmentation) 발생이 가능하다.

세그먼테이션은 외부 단편화(External Fragmentation) 발생이 가능하다.

메모리의 빈 공간들이 흩어져 있고, 각각의 공간들 크기가 너무 작아서 세그먼트를 수용할 수 없는 문제가 발생할 수 있다.

단순히 기다리거나 압축하여 더 큰 공간을 생성할 수 있다.

평균 세그먼트 크기가 작으면, 외부 단편화도 줄어든다.

이는 작은 빈 공간이 생성되어도 세그먼트를 수용할 가능성이 높아지기 때문이다.

 

6.17) 페이지화된 세그먼테이션 기법 (Paged Segmentation)

세그먼테이션 기법을 기반으로 동작하지만, 각각의 세그먼트를 일정 크기의 페이지로 다시 나눠서 처리한다.

가변적인 데이터 구조와 모듈 처리, 공유와 보호 지원이 편리한 세그먼테이션의 장점과, 외부 단편화 문제를 해결하고 배치 정책이 불필요하여 쉬운 할당 과정을 지닌 페이징의 장점을 살릴 수 있다.

논리적 주소 = 18bits의 세그먼트 번호, 16bit의 세그먼트 오프셋으로 구성된다.

세그먼트 오프셋 = 6bit의 페이지 번호, 10bit의 페이지 오프셋으로 구성된다.

페이지화된 세그먼테이션 기법을 사용하면 외부 단편화는 없으나, 내부 단편화는 발생할 수 있다. 

또한 메모리 워드 참조를 위해 세그먼트 테이블 참조, 페이지 테이블 참조, 목표하는 워드 참조까지 총 3번 메인 메모리에 접근해야 한다.

 

6.18) 멀틱스 시스템의 페이징 세그먼테이션 구조

• 세그먼트 번호: s
• 세그먼트 오프셋: d
• 페이지 번호: p
• 페이지 오프셋: d'

세그먼트 번호(s) + 세그먼트 테이블 기준 레지스터 값 == 프로세스의 세그먼트 테이블 주소

세그먼트 오프셋(d)의 상위 비트, 페이지 번호(p)가 세그먼트 길이보다 짧은 지 검사

세그먼트 오프셋의 상위 비트, 페이지 번호(p) + 세그먼트 테이블 기준 레지스터 값 == 프레임 번호(f)

프레임 번호(f) + 페이지 오프셋(d') == 실제 메모리 물리 주소

 

6.19) 페이지화된 세그먼테이션의 주소 변환 과정

세그먼트 테이블에 저장된 테이블 항목들은 각각의 페이지 테이블을 지닌다.

세그먼트 테이블 항목 4의 논리 주소가 [4, 2, 64]라면, 세그먼트 번호, 페이지 번호, 오프셋은 각각 4, 2, 64이다.

세그먼트 테이블 항목 4의 페이지 테이블에서 페이지 번호만큼 떨어진 위치의 값을 검색한다.

이때 검색된 값은 물리 주소의 프레임 주소(f)가 된다.

알아낸 프레임 주소와 오프셋 값을 더하면, 위 사진과 같이 [1, 64]가 나오는데, 이 값이 물리 주소가 된다.

 

6.20) 페이지화된 세그먼테이션의 메모리 할당

각 프로세스는 1개의 세그먼트 테이블을 가지며, 각 세그먼트는 자신의 페이지 테이블을 가진다.

세그먼트 테이블 항목: 세그먼트 길이, 페이지 테이블 기준 주소

페이지 테이블 항목: 페이지 프레임 번호

특정 프로세스가 실행 중일 때, 세그먼트 테이블 기준 레지스터(STBR: Segment Table Base Register)가 프로세스에 대한 세그먼트 테이블 시작 주소를 가진다.

 

6.21) 세그먼테이션 구조와 페이지화된 세그먼테이션 구조 비교

세그먼테이션 구조는 다음과 같다.

페이지화된 세그먼테이션 구조는 다음과 같다.

 

---

 

---

수고하셨습니다!

---