9.2 연속 메모리 할당
각 프로세스는 다음 프로세스가 적재된 영역과 인접한 하나의 메모리영역에 적재된다.
9.2.1 메모리 보호(Memory Protection)
만일 시스템이 상한 레지스터와 재배치 레지스터를 가지고 있다면 프로세스는 자신이 소유하지 않은 메모리를 접근할 수 없다 재배치 레지스터는 가장 작은 물리 주소의 값을 저장하고, 상한 레지스터는 논리 주소의 범위 값을 저장한다. 각각의 논리주소는 상한 레지스터가 지정한 범위 안에 존재 해야한다.
MMU는 논리적 주소를 동적으로 매핑한다.
문맥 교환에서 디스패처는 올바른 값으로 재배치 및 상한 레지스터를 로드한다.
Relocation register cheme 을 통해 OS 및 프로세스의 크기를 동적으로 변경할 수 있다.
9.2.2 메모리 할당(Memory Allocation)
메모리 할당 기법은 2가지가 존재한다.
고정 파티션 기법
메모리를 여러 고정된 크기의 파티션으로 나눈다.
각 파티션에 하나의 프로세스가 할당된다.
주로 배치 환경에서 사용되며, 현재 시스템에서는 사용되지 않는다.
다중 프로그래밍의정도는 파티션의 수에 의해 결정된다.
동적 파티션 기법
메모리를 여러 가변 크기의 파티션으로 나눈다.
OS는 사용 가능한/점유된 부분을 나타내는 테이블을 유지한다.
Hole : 여유 메모리 블록, 메모리 전체에 흩어져 있는 다양한 크기
프로세스가 할당되려면 먼저 운영체제가 할당될 수 있는 충분한 크기의 Hole을 찾아야한다.
Hole이 너무 크다면 두 부분으로 나누어진다.
한 부분은 프로세스에 할당되고, 나머지 부분은 다음에 사용가능한 Hole set으로 분류된다
프로세스가 종료된다면 메모리 블록을 해재한다.
해제된 블록은 Hole이 되며 인접한 Hole과 병합되어 하나의 사이즈가 큰 Hole이 된다.
메모리를 기다리는 프로세스가 있는지 그리고 이 Hole이 대기 프로세스의 요구를 충족 할 수 있는지 확인한다.
프로세스를 Hole에 할당할때 세가지기법이 사용된다.
1. 최초 적합(First fit) : 첫 번째 사용 가능한 가용 공간을 할당한다. 검색은 집합의 시작부터거나, 지난번 검색이 끝난 곳에서 시작될 수있다. 물론 충분히 사용 가능한 큰 공간을 찾았을때 검색이 끝난다.
2. 최적 적합(Best fit) : 사용 가능한 공간 중에서 가장 작은 것을 택한다. 리스트가 크기 순으로 되어 있지 않다면 전 리스트를 검색해야 한다. 이 방법은 가장 작은 Hole을 만들어 낸다.
3. 최악 적합(Wort fit) : 사용 가능한 공간 중에서 가장 큰 것을 택한다.이 방식에서 할당해 주고 남게 되는 가용 공간은 충분히 커서 다른 프로세스들을 위하여 유용하게 사용될 수 있다.
모의시험이세는 최초, 최적 접합모두가 시간과 메모리 효율 측면에서 최악 적합 보다 좋다는 것이 입증되었다. 속도는 최초적합이 일반적으로 빠르다.
9.2.3 단편화(Fragmentation)
외부 단편화(External Fragmentation) : 충분한 총 메모리 공간이 있지만 연속적이지 않아 사용이 불가능하다.
내부 단편화(Internal Fragmentation) : 요청된 메모리 공간보다 크게 할당된 메모리, 즉 이 공간은 사용을 하지 않는다.
최초 적합 또는 최적 접합 전략은 이러한 단편화의 양에 영향을 미칠 수 있다.
최초 적합의 경우 통계적 분석에서 N개의 블록이 할당되었을때 0.5N개의 블록이 단편화 때문에 손실될 수 있다고 나타난다. 즉, 1/3 정도의 메모리 공간을 사용하지 못한다. (50 percent rule)
Segmentation
개발자의 입장에서는 메모리가 가변 크기의 세그먼트 모음으로 보인다. 각 세그먼트는 순서가 없으며 메모리 주소에 대해 상관이 없다.
Segments : 가변길이, 세그먼트 내의 요소는 세그먼트 시작으로부터 오프셋으로 식별된다.
Segmentation : 세그먼트 개념을 지원하는 메모리 관리 체계, 논리 주소 공간은 세그먼트의 집합이다. 각 세그먼트에는이름 과 길이가 있다. (e.g. Logical address <segment number, offset>
각 세그먼트들의 재배치 및 상한 레지스터들을 저정한 테이블을 참조하여 논리 주소를 물리 주소로 변환한다.
9.3 페이징
지금까지 논의된 메모리 관리는 프로세스의 물리 주소 공간이 연속적이어야 했다. 페이징은 비연속적 메모리 공간을 프로세스에게 연속적이게 보이도록 하는 방법을 설명한다.
9.3.1 기본 방법(Basic method)
물리 메모리를 Frame이라고하는 고정된 크기의 블록으로 분할한다.
논리 메모리를 Page라고 하는 Frame과 동일한 크기의 블록으로 분할한드.
Page number(p)와 page offset(d)으로 구분된 주소를 정의한다.
페이지 번호는 물리 메모리에 있는 각 프로엠의 기본 주소를 포함하는 페이지 테이블에 대한 색인으로 사용된다.
물리 주소 = base address + offset
페이지의 크기는 하드웨어에 의해 정의되며 2의 제곱(512B ~ 1GB, 일반적으로 4KB)
만약 논리 주소 공간의 크기가 2^n이고, 페이지 크기가 2^m 이라면
상위 m-n bit 는 페이지 번호를 가르키며, 하위 n비트는 페이지 오프셋을 가르킨다.
예를들어
m=4, n=2, page size = 4 byte일때
32 byte memory는 8page로 구성된다.
Logical address 0 은 frame 5, offset 0에 매핑
Physical address = 5 * 4 + 0 = 20
Logical address 3 은 frame 5, offset 3에 매핑
Physical address = 5 * 4 + 3 = 23
Logical address 13 은 frame 2, offset 1에 매핑
Physical address = 2 * 4 + 1 = 9
개발자는 메모리를 하나의 프로그램만 포함하는 하나의 단일 공간으로 간주한다. 그러나 실제 사용자 프로그램은 물리적 메모리 전체에 흩어져 있다. 또한, 하나의 프로세스는 자신이 소유한 한 메모리 영역에만 액세스 할 수 있다. 즉, 다른 프로세스의 메모리 영역에있는 데이터에 대해 접근하지 못한다.
페이징 기법에서는 외부 단편화는 발생하지 않는다. 대신 내부 단편화 문제는 발생하게된다.
예를들어 page size = 2048 byte, process needs = 72766 byte일 때, 35개의 풀 페이지와 1086 byte를 사용하는 페이지 1개가 필요하다. 따라서 마지막 페이지에서 962 byte는 내부 단편화가 발생된다.
크기가 작은 페이지가 내부 단편화 문제에서는 더 좋은 선택이다. 하지만 더 많은 페이지 테이블 엔트리가 필요하며 이것은 오버헤드로 작용해 시스템에 좋지않다. 또한, 큰 사이즈의 페이지는 Disk I/O에 좀더 높은 효율을 보여준다.
9.3.2 하드웨어 지원(Hardware Support)
전용 레지스터를 사용
빠른 페이지 주소 변환을 위한 high speed circuit
문맥 전환시 디스패처에서의 모든 레지스터 재 로드
제한 : 작은 크기의 페이지 테이블에서만 작동한다
메모리의 프로세스별 페이지 테이블 사용
PCB의 페이지 테이블에 대한 포인터
Root 페이지 테이블 을 가리키는 레지스터
페이지 테이블을 변경하려면 레지스터 하나만 변경하면 된다. -> 문맥 전환이 빠르다.
제한 : 다중 메모리 액세스 필요->테이블 자체가 메모리에 존재한다. (페이지테이블 액세스 + 원하는 데이터 액세스)
TLB(Translation look-aside buffer)
페이지 테이블 항목을 위한 작고 빠른 검색 하드웨어 캐시
엔트리에는 Key, value 값이 존재
크기가 작아 고속 검색에 유리하다(32-1024 개 항목)
CPU 파이프 라인에 통합되어 있다.
일부 시스템에는 여러 수준의 TLB가 존재한다.
TLB의 작업
1. CPU는 논리 주소를 생성한다.
2. 페이지 번호가 TLB에서 발견되면(TLB hit)해당 프레임 번호가 즉시 메모리에 액세스하는 데에 사용한다.
3. 페이지 번호가 TLB에 없는 경우(TLB miss) 페이지 테이블에 액세스하여 페이지 테이블 항목을 얻어온다
4. 이 작업은 하드웨어 및 운영체제 지원(인터럽트)로 만 수행할 수 있다.
만약 TLB가 가득 차있는 상태(full)이라면 교체를 위해 기존 항목을 선택하여 교체해야한다.(LRU, RR, Random)
특정 페이지 테이블 항목을 TLB에서 제거되는 것을 방지 할 수 있다.(e.g. 커널 코드)
문맥 교환시에서 각 프로세스는 자체의 논리 주소 공간이 있으므로 TLB를 flush해주어야 한다.
문맥 교환에서 TLB flush를 방지하기 위해 일부 TLB 항목에 ASID(Address space identifiers)를 저장한다.
ASID는 각 프로세스의 페이지 테이블 항목을 식별하는 데에 사용한다. ASID가 일치하지 않는 경우는 TLB miss이며 ASID를 사용하면 TLB는 여러 프로세스에 대한 페이지 테이블 항목을 동시에 포함할 수 있다.
예를들어
메모리 액세스 시간 : 100ns,
TLB 액세스 시간 : 0ns,
TLB miss시 메모리 액세스 시간 : 200ns(페이지 테이블 액세스 + 데이터 액세스)
TLB hit시 메모리 액세스 시간 : 100ns
TLB Hit ratio = 80%일때는 유효 메모리 액세스 시간 = 0.8*100 + 0.2*200 = 120ns
TLB Hit ratio = 99%일때는 유효 메모리 액세스 시간 = 0.99*100 + 0.01*200 = 101ns
9.3.3 보호(Protection)
페이지 테이블 항목에는 메모리 보호를 위한 추가 비트가 존재한다.
1. Read-Write/Read Only bit
페이지 업데이트(RW) 또는 페이지 읽기 전용(RO)
읽기 전용 페이지에 쓰기 시도시 하드웨어 트랩(Trap)발생
2. Valid/Invalid bit
유효한 경우 페이지가 프로세스의 주소 공간에 존재한다.
OS는 이 비티를 사용하여 페이지에 대한 액세스를 허용하거나 허용하지 않는다.
잘못된 페이지 액세스 접근 시도시 하드웨어 트랩(Trap)발생
예를들어 14비트 주소공간(0~26383) 시스템에서 어느 프로그램은 0 ~ 10468만 사용가능하다. 페이지 크기는 2KB이며 페이지는 0~5의 주소는 유효하다. 하지만 페이지 6, 7에 접근하려면 Invalid 비트를 확인해 트랩을 발생시킨다.
9.3.4 공유 페이지(Shared Page)
페이지 테이블을 사용한 페이지 공유 방법
프로세스가 재진입 코드인경우 코드 페이지를 공유할 수 있다(재진입 코드 : non-self modifying code)
따라서 하나의 사본만 메모리에 보관되며 공유된다.
9.4 페이지 테이블의 구조(Structure of the page table)
페이지 테이블을 구성하는 가장 일반적인 방법들
9.4.1 계층적 페이징(Hierarchical Paging)
현대 컴퓨터는 매우 큰 주소 공간을 가진다. 따라서 이러한 환경에서는 페이지 테이블도 상당히 커진다.
예를들어 32bit 시스템에서 페이지 크기가 4KB라면 페이지 테이블은 2^20개 이상의 항목으로 구성되어야 한다.
그럼 페이지 테이블만을 위해서도 4MB의공간이 필요한데 이는 또한 연속적 할당을 바라지 않는다.
따라서 페이지 테이블을 여러개의 작은 조각으로 나누는 것이다.
2단계 페이징 기법(Two level paging scheme)
페이지 테이블 자체가 다시 페이징되게 만든다.
32bit 시스템에서 4KB 페이지 사용 시스템에서는 20bit 페이지 번호와 12bit 페이지 오프셋으로 구성된다.
논리주소는 위와같은 모습을 보이게 된다.
p1은 outer page table의 인덱스이며, p2는 inner page table의 오프셋으로 사용된다.
만약 64bit 논리 주소 공간을 가진다면 2단계 페이징 기법도 적절하지 못하다. 이러한 경우에는
Outer page table 인덱스가 2^42 항목을 가지게되어 이 또한 페이지 테이블을 작게 나누어야 한다.
첫번째 해결 방법으로, Outer page table을 다시 2단계로 분할하여 총 3단계 페이징을 하는것이다.
이경우도 Outer page table에 2^34 항목을 가지게 되어 크기가 크다. 따라서 64bit 시스템에서의 계층적 페이징은 부적합하다는 것을 알 수 있다.
9.4.2 해시 페이지 테이블(Hash Page Table)
주소공간이 32bit보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블을 많이 사용한다. 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있으며 이곳에는 충돌을 일으켜 모두 이곳으로 해시되는 원소들이 연결된다.
각 엔트리들은 세 개의 필드를 가진다. 가상페이지 번호, 페이지 프레임 번호, 연결 리스트상 다음 포인터
가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱한다. 해싱번호를 가지고 해시 페이지 테이블에서 연결 리스트를 따라가며 첫번째 원소와 가상 페이지 번호를 비교해본다. 일치하면 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 계산한다. 일치되지 않으면 다음 연결 리스트를 확인해 위와 같은 일을 반복한다.
9.4.3 역 페이지 테이블(Inverted page table)
보통 각 프로세스는 각자 하니씩의 자신에 대한 페이지 테이블이 있다.
프로세스가 많은 경우 페이지 테이블 -> 너무 많은 공간 필요
역 페이지 테이블에서는 실제 페이지(또는 프레임)당 하나의 항목이 존재한다.
항목 : 가상 페이지 번호, 프로세스 ID
이렇게 되면 시스템에는 단 하나의 페이지 테이블만이 존재하게 되고, 테이블 내의 항목은 메모리 한프레임을 가르킨다.
그러나 검색 속도가 느려지거나 공유 페이지 구현이 어려워 진다.
9.5 스와핑(Swapping)
모든프로세스를 실행하는 데 필요한 총 메모리 공간이 물리적 메모리 공간 크기를 초과하는 경우 스와핑을 사용할 수있다.
프로세스를 일시적으로 메모리에서 백업 저장소로 이동하고 계혹하기 위해 다시 가져오는 기술
CPU스케줄러가 프로세스를 실행하기로 결정하면
디스패처는 다음 프로세스를 위한 메모리공간이 있는지 확인한다.
그렇지 않고 사용 가능한 메모리 영역이 없는경우 디스패처는 현재 메모리에 있는 프로세스의 메모리를 교체하고 원하는 프로세스 메모리로 교체한다.
문맥 교환에서 스와핑이 차지하는 시간이 높다.
스왑 시간의 주요 부분은 스왑된 메모리 양에 정비례하는 전송 시간이다.
예를들어
100MB의 프로세스 크기, 50MB/s HDD 전송 속도 가정(전송 시간 100MB/50MB/s = 2s)
스왑 아웃 + 스왑 인 (100MB) : 4s
스왑 아웃 + 스왑 인 (3GB) : 60s
두가지의 swap 제약 조건
Pendign I/O : I/O 완료를 기다리는 프로세스를 swap out할 수 없다.(I/O가 완료되면 다른 프로세스가 메모리를 사용할 수있다.)
Two solutions : peding I/O 프로세스를 스왑하거나 커널 버퍼로 I/O 작업을 수행할 수 없다.
Appendix
'책 > 운영체제' 카테고리의 다른 글
| 운영체제 Ch09_'Main Memory-1' (0) | 2021.01.11 |
|---|---|
| 운영체제 Ch05_'CPU Scheduling-2' (0) | 2021.01.11 |
| 운영체제 Ch05_'CPU Scheduling-1' (0) | 2021.01.11 |
| 운영체제 Ch04_'Thread and Concurrency-2' (0) | 2021.01.10 |
| 운영체제 Ch04_'Thread and Concurrency-1' (0) | 2021.01.10 |