[운영체제] 08 Memory Management (2) 불연속 할당

gramm·2021년 2월 6일

운영체제

목록 보기

9/14

내용 출처

KOCW 반효경 교수님 <운영체제> 강의
책 <운영체제와 정보기술의 원리>

반효경 교수님의 <운영체제> 강의 내용을 기반으로 정리했으며,

교수님의 저서 <운영체제와 정보기술의 원리>에서 추가할 만한 내용을 이와 같은 인용문 형식으로 추가함.

이 포스팅의 모든 이미지는 <운영체제> 강의에서 가져왔습니다.

불연속 할당

현대의 컴퓨터 시스템은 주로 불연속 할당 방식을 사용한다.

Paging
- 프로그램을 구성하는 주소 공간을 동일한 크기의 Page 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식
- Page 단위로 물리적 메모리에 올리거나 내린다.
- PageFrame : 페이지가 들어갈 수 있는 공간
- 장점 : hole들의 크기가 균일하지 않은 문제가 없다. 물리적 메모리에서 비어 있는 위치에 어떤 페이지든지 들어갈 수 있기 때문이다.
- 단점 : 주소 변환이 복잡해진다. 주소 변환을 페이지 별로 해야 한다.
Segmentation
- 주소 공간을 Page 단위가 아니라 의미 단위인 세그먼트(segment)로 나누는 방식
- 프로그램의 주소 공간은 크게 code, data, stack으로 구성된다. 이를 각각 code/data/stack segment으로 나누어, 필요 시에 물리적 메모리의 다른 위치에 올릴 수 있다. 혹은 함수 단위로 세그먼트를 나눌 수도 있다.
- 단점 : 의미 단위로 주소 공간을 나누었으므로, 크기가 균열하지 않다. 따라서 Dynamic Storage-Allocation Problem이 발생할 수 있다.
Paged Segmentation
- 세그먼트 하나를 다수의 페이지로 구성하는 방식

1. Paging

Paging
- 프로세스의 virtual memory를 동일한 사이즈의 page 단위로 나눈다.
- virtual memory의 내용이 page 단위로 불연속적으로 저장된다.
- 일부는 backing storage에, 일부는 물리적 메모리에 저장된다.
Basic Method
- 물리적 메모리를 동일한 크기의 frame으로 나눈다.
- 논리적 메모리를 동일한 크기의 page로 나눈다. (frame과 같은 크기)
- 모든 가용 frame들을 관리한다.
- page table을 사용하여 논리적 주소를 물리적 주소로 변환한다.
  (page table에는 페이지 수 만큼의 엔트리가 존재한다.)
- 외부 조각은 발생하지 않지만, 내부 조각은 발생할 수 있다. 예를 들어, 프로그램 크기가 1005일 때 이를 크기 100의 페이지로 나누면, 크기 5의 내부 조각이 발생할 것이다.

주소 변환 아키텍처

(p, d)에서 p는 페이지 번호, d는 페이지 내에서 얼마나 떨어져 있는지를 나타내는 오프셋이다.
(f, d)에서 f는 페이지 프레임의 번호다. 페이지 내에서의 상대적 위치는 변하지 않으므로 d는 그대로 유지된다.

페이지 테이블에서 p번째 주소에서 페이지 프레임의 번호 f를 찾을 수 있다. 물리적 메모리에서 f번째 주소를 찾으면 주소변환이 이루어진다.

페이지 테이블의 구현

주소 변환을 하려면 page table에 접근해야 한다. 그런데 page table은 프로그램마다 별도로 존재해야 하며 용량이 매우 크므로, 레지스터나 캐시에 넣기는 어렵다. 따라서 page table은 메인 메모리에 상주한다.

( 2단원 저장장치의 계층 구조 참고 )

결국 메모리 접근 연산에는 2번의 메모리 접근이 필요하다. (page table 접근 1번, 데이터/명령 접근 1번)
Page-Table Base Register(PTBR)는 메모리 내에서의 page table의 시작 주소를 가리킨다.
Page-Table Length Register(PTLR)는 page table의 크기를 보관한다.
(PTBR, PTLR은 각각 base register, limit register와 대응된다.)
속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 주소 변환용 하드웨어 캐시를 사용한다.

Paging Hardware with TLB

TLB는 페이지 테이블의 캐시 역할을 한다.

메인 메모리와 CPU 사이에 존재하는 TLB는 주소 변환을 위한 캐시 메모리다. TLB는 page table에서 빈번히 참조되는 일부 엔트리를 보관한다. 논리적 주소(p)를 주었을 때, page table에 접근하기 전에 우선 TLB에 접근한다. TLB에 해당 주소의 내용이 있다면, TLB를 통해 바로 주소 변환을 할 수 있다. 이 경우에는 한 번의 메모리 접근만이 필요하다.

page table의 경우, 논리적 주소 p가 주어지면 위에서부터 p번째 인덱스로 가면 바로 주소 변환이 이루어진다. 반면 TLB에서 논리적 주소 p에 대한 엔트리가 있는지 확인하려면 TLB 내의 모든 엔트리를 확인해야 하는데, 이는 비효율적이다. 따라서 TLB는 검색 시간을 단축하기 위해 일반적으로 병렬 탐색(parallel search)이 가능한 associative register를 사용한다.

TLB도 page table과 마찬가지로 프로세스마다 별도로 존재해야 한다. 그래서 TLB는 문맥 교환이 발생할 때마다 flush를 시켜서 모든 엔트리를 비워야 한다.

Effective Access Time (EAT)

α = Hit ratio (TLB에서 주소 변환이 되는 비율)
ε = 주소 변환 정보가 TLB에 있는지 확인하는 시간

EAT = (1 + ε)α + (2 + ε)(1 - α) = 2 + ε - α

2단계 페이지 테이블

현대의 컴퓨터는 주소 공간이 매우 큰 프로그램을 지원한다.

32 bit address 사용시 : $2^{32}$ byte (4GB)의 주소 공간
- 각각의 page의 크기는 4KB이므로, 1M개의 page table entry가 필요하다.
- 각 page entry가 4바이트 정도이므로, 프로세스당 4M의 page table이 필요하다.
- 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비된다.
  (page table은 인덱스를 통해 접근하므로, 사용되지 않는 주소 공간이 많더라도 페이지 테이블 엔트리는 일부를 생략할 수 없다.)

이러한 비효율성을 극복하기 위한 것이 바로 2단계 페이지 테이블이다.

[2단계 페이징에서의 Address-translation scheme]

안쪽 페이지 테이블의 크기는 페이지 크기와 같은 4KB다. 그리고 각 엔트리는 4Byte다. 4바이트짜리 엔트리가 4KB 테이블 내에 있으므로, 하나의 테이블 안에 있는 엔트리의 개수는 1K개다.

logical address (on 32-bit machine with 4K page size)
- 20 bit의 page number
- 12 bit의 page offset
page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉜다. (각 page table entry가 4바이트)
- 10 bit의 page number
- 10 bit의 page offset

p1은 outer page table의 index이다.
p2은 outer page table의 page에서의 변위다.

페이지 하나의 크기는 4KB이다. 이는 2의 12승이다. 따라서 이를 구분하기 위해서는 12bit가 필요하다. 그래서 page offset은 12bit다.

하나의 테이블 안에 있는 엔트리의 개수는 1K개다. 그래서 엔트리 위치를 구분하기 위해서는 10bit가 필요하다. (1K = $2^{10}$ ) 그래서 outer page table을 위한 page offset은 10bit다.

[2단계 페이지 테이블을 사용하는 이유]

프로그램을 구성하는 공간의 상당 부분은 사용되지 않는다. 하지만 page table로 만들 때는 모든 주소 공간의 엔트리를 만들어야 했다. 그런데 2단계 페이지 테이블을 사용하면 이러한 문제를 해소할 수 있다. 바깥쪽 페이지 테이블은 전체 논리적 메모리의 크기만큼 만들어진다. 하지만 실제로 사용되지 않는 주소에 대해서는 안쪽 페이지 테이블이 만들어지지 않고, 이에 대한 바깥쪽 페이지 테이블의 엔트리 값은 NULL이다.

다단계 페이지 테이블

주소 공간이 더 커지면 다단계 페이지 테이블이 필요하다.
각 단계의 페이지 테이블이 메모리에 존재하므로, 논리적 주소를 물리적 주소로 변환하는 데 더 많은 메모리 접근이 필요하다.
TLB를 통해 메모리 접근 시간을 줄일 수 있다.
4단계 페이지 테이블을 사용하는 경우
- 메모리 접근 시간이 100ns, TLB 접근시간이 20ns이고
- TLB hit ratio가 98%인 경우
  effective memory access time = 0.98 x 120 + 0.02 x 520 = 128 nanoseconds
- 결과적으로 주소변환을 위해 28ns만 소요된다.

앞서 page table에 주소 변환 정보가 들어있음을 배웠다. 그런데 page table에는 주소 변환 정보 말고도, 엔트리마다 부가적인 비트가 저장되어 있다. 그중 하나가 Valid-invalid bit이다.

valid는 해당 주소 변환에 대한 정보가 유의미함을 뜻한다. 예를 들어, 위 그림에서 맨 위의 v는 0번 페이지가 2번 프레임에 실제로 올라와있음을 보여준다.

반면 invalid는 해당 주소의 프레임에 유효한 내용이 없음을 뜻한다.

i) 프로세스가 그 주소 부분을 사용하지 않는 경우
ii) 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

valid의 경우 접근을 허용하지만, invalid의 경우 접근을 불허한다.

valid-invalid bit 이외에, Protection bit도 존재한다. protection bit은 페이지마다 어떤 연산에 대한 접근 권한이 있는가를 나타낸다.

코드 영역은 내용을 읽어 명령을 실행할 뿐, 내용이 바뀌지 않아야 한다. 그래서 코드 영역은 read-only로 설정한다. 반면 읽고 써야 하는 데이터 영역/스택 영역의 경우 read와 write의 권한을 모두 가진다.

역 페이지 테이블

page table이 매우 큰 이유
- 모든 프로세스 별로 그 논리적 주소에 대응하는 모든 페이지에 대해 page table entry가 존재한다.
- 대응하는 page가 메모리에 있든 아니든 간에 페이지 테이블에는 entry로 존재한다.

Inverted Page Table
- page frame 하나당 page table에 하나의 entry를 둔 것
- 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시 (process-id, 프로세스의 논리적 주소)

시스템 전체(system-wide)에 페이지 테이블이 딱 하나만 존재한다. 페이지 테이블의 엔트리가 프로세스의 페이지 개수만큼 존재하는 것이 아니라, 물리적 메모리의 페이지 프레임의 개수만큼 존재한다. n번째 entry는 n번째 프레임을 나타내며, n번째 entry에 가면 그에 대응하는 논리적 주소가 나오게 된다. 기존 방식을 뒤집은 것이다.

그런데 주소 변환은 논리적 주소를 물리적 주소로 바꾸는 것이다. 그렇다면 이 테이블에서 어떻게 주소 변환을 할 수 있는가? 논리 주소에 해당하는 페이지 p가 물리적 주소의 어디에 올라가 있는지를 찾기 위해서는, 페이지 테이블의 entry 전체를 탐색해야 한다. 그래서 inverted page table은 공간을 줄이기 위한 방식이지만, 대신 시간적 오버헤드가 많이 든다.

또한 페이지 테이블에는 논리적 페이지 p뿐만 아니라, 그 주소가 어떤 프로세스의 페이지인지를 나타내는 process id가 함께 들어가야 한다.

inverted page table은 시간적 오버헤드가 너무 크므로, associative register라는 별도의 하드웨어에 집어넣어서 동작을 하게 함으로써, 순차적 탐색의 시간 오버헤드를 줄인다.

공유 페이지

Shared code

재진입 코드 (Re-entrant code) = 순수 코드 (Pure code)
shared code의 2가지 조건
- i) read-only로 하여 프로세스 간에 하나의 코드만 메모리에 올린다.
- ii) 모든 프로세스의 논리적 주소 공간에서 동일한 위치에 있어야 한다.

Shared Page

shared code를 담고 있는 페이지
공유 가능한 코드는 물리적 메모리에 하나만 올리는 방식
여러 프로세스가 공유되는 부분을 같은 프레임으로 mapping시킴으로써 코드를 공유한다.

Private Page (<--> shared page)

각 프로세스들은 독자적으로 메모리에 올린다.
private data는 논리적 주소 공간의 아무 곳에 와도 무방하다.

2. Segmentaion

프로그램을 구성하는 주소 공간을 의미 단위인 segment로 쪼개는 방식

논리적 주소는 세그먼트 번호(s)와 오프셋(d)로 구성된다. CPU가 논리 주소를 주면, 세그먼트 번호와 오프셋으로 나눈다. segment table의 시작 위치는 레지스터가 가지고 있다. 거기에서부터 세그먼트 번호에 해당하는 위치만큼 떨어진 위치에, 세그먼트가 물리적 메모리의 어떤 위치에 올라가 있는지가 있다.

페이징 기법의 page table의 entry에는 물리적 메모리에서의 시작 위치가 저장되어 있다. 그런데 segment table은 물리적 메모리에서의 시작 위치 외에, segment의 길이 또한 저장한다. segment는 page와 달리 길이가 가변적이기 때문이다.

Segment table
- each table entry has:
  - base (기준점) - 물리적 메모리에서 세그먼트의 시작 주소
  - limit (한계점) - 세그먼트의 길이
Segment Table Base Register (STBR)
물리적 메모리에서의 segment table의 위치
Segment Table Length Register (STLR)
프로그램이 사용하는 segment의 수
- segment number s is legal if s < STLR.
  (세그먼트 번호가 STLR 이상인 경우, 잘못된 참조이므로 trap을 발생시킨다.)

STBR과 STLR은 페이징 기법에서의 PTBR/PTLR과 대응된다. 이는 테이블 내의 base/limit 레지스터와는 별개다.

Segmentation Architecture

Protection
- 페이징 기법과 마찬가지로 segment table의 각 항목에 protection bit와 valid bit를 둔다.
Sharing
- Shared Segment (공유 세그먼트)
- 공유 페이지와 마찬가지로, 이 세그먼트를 공유하는 모든 프로세스의 주소 공간에서 같은 논리적 주소를 가져야 한다.
- 세그먼트는 의미 단위이기 때문에 공유와 보안에 있어 페이징 기법보다 훨씬 효과적이다.
Allocation
- first fit / best fit
- 외부 조각이 발생한다. segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생한다.
  (반면 paging의 경우, 비어있는 page frame은 어디든 활용 가능하므로, 외부 조각이 발생하지 않는다.)

paging 기법에 비해, segmentation 기법은 테이블을 위한 메모리 낭비가 적다.

3. Paged Segmentation

세그먼트 하나가 여러 개의 페이지로 구성된다.

먼저 세그먼트에 대한 주소 변환을 한다. 각 프로그램이 가지고 있는 논리적 주소는 세그먼트 번호와 세그먼트 오프셋으로 구성된다. segment table을 통해 주소 변환을 하면, 바로 물리적 메모리의 시작 주소가 나오는 것이 아니라, page table의 시작 위치가 나온다.

세그먼트 오프셋은 세그먼트 안에서 얼마나 떨어져있는가를 나타낸다. 그런데 세그먼트 하나가 여러 페이지로 구성되므로, 세그먼트 오프셋(d)을 다시 쪼개서 페이지 번호(p)와 페이지의 오프셋(d')으로 사용한다.

pure segmentation과는 달리, segment table entry가 세그먼트의 base address를 가지고 있는 것이 아니라 세그먼트를 구성하는 page table의 base address를 가지고 있다.

paged segmentation의 경우, 물리적 메모리에는 페이지 단위로 올라가기 때문에 외부 조각 문제가 해결된다. 또한 공유, 보안 같은 의미 단위의 일은 segment table에서 처리한다. 그래서 paging과 segmentation의 장점을 모두 가지게 된다.

실제로 대부분의 segmentation은 paging 기법을 함께 사용한다.

메모리 관리와 운영체제

어떤 프로세스가 CPU를 가지고 있으면서 메모리 접근을 할 때는 운영체제의 도움을 전혀 받지 않는다. 왜냐하면 만약 주소 변환 시마다 운영체제가 개입하게 된다면, CPU가 운영체제에게 넘어갔다가 다시 프로세스에게 넘어와야 하는데, 이는 말이 되지 않기 때문이다.

프로세스가 CPU를 가지고 있다면 매 CPU 클럭 사이클마다 메모리에서 어떤 명령을 읽어와서 CPU에서 실행하고, 또 필요시 CPU에서 데이터를 읽어와서 실행한다. 이러한 모든 과정은 주소 변환을 통한 메모리 접근을 필요로 하는데, 그때마다 운영체제의 도움을 받을 수는 없다는 것이다. 따라서 결국 주소 변환에 있어서 운영체제의 역할은 하나도 없다. 주소 변환은 모두 하드웨어가 담당한다.

프로세스가 I/O 장치에 접근할 때는 운영체제가 개입한다. 사용자 프로세스가 I/O 장치에 직접 접근할 수 없기 때문이다. 하지만 프로세스가 메모리에 접근할 때는 운영체제는 아무런 역할을 하지 않는다.