< Main Memory>
# 메모리란?
각각 주소가 할당된 일련의 워드 또는 byte로 구성된 집합체메모리는 단지 메모리 주소의 stream만 볼 뿐,
이 주소들이 어떻게 생성되었는지, 혹은 그 주소가 가리키는 내용이 무엇인지(data, code) 모른다.
1.1 기본 하드웨어
CPU는 main memory와 registry에 직접 접근할 수 있는 유일한 device이다.
CPU에 내장되어 있는 register는 일반적으로 CPU clock의 1 cycle내에 접근이 가능하다.
그러나, main memory의 경우, 수 많은 CPU clock tick cycle이 소요됨.
그래서 register와 main memory간의 속도를 줄이기 위해 두 계층 사이에 cache 라고 부르는
버퍼 영역을 둔다.
각각의 프로세스는 독립된 메모리 공간을 갖고, base와 limit 이라는 두개의 레지스터들을 사용해
해당 메모리 공간을 보호한다.
CPU는 메모리 공간 보호를 위해 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교한다.
만일, 운영체제의 메모리 공간이나, 다른 프로세스의 메모리 공간을 침범한다면,
치명적인 오류로 간주하고, trap을 발생시킨다.
1.2 주소 할당(Address Binding)
# Input queue - disk 에서 main memory로 들어오기를 대기하고 있는 프로세스들의 집합로 구성됨
전통적으로 메모리 주소 공간에서 명령어와 자료의 바인딩은 이루어지는 시점에 따라 다음과 같이 구분됨.
1) 컴파일 시간 바인딩
- 만일 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 할 수 있으면 컴파일러는2) 적재 시간 바인딩
- 심볼(논리적 주소)와 진짜 번지수와의 바인딩은 프로그램이 main memory로 실제로 적대되는 시간에 이루어지게 된다.3) 실행 시간 바인딩
- 만약 프로세스가 실행하는 도중에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면우리는 "바인딩이 실행 시간까지 허용되었다" 라고 이야기 한다.
1.3 논리 대 물리적 주소 공간
CPU가 생성하는 주소를 일반으로 논리적 주소라고 함.
반면에 메모리가 취급하게 되는 주소(MAR - Memory Address Register)는 일반적으로 물리적 주소하고 함.
컴파일시 바인딩과, 적재시 바인딩일 경우 논리, 물리 주소가 동일하다.
그러나, 실행시 바인딩일 경우 논리, 물리 주소가 다르다. 이때 논리 주소를 가상 주소(virtual address)라고 한다.
Memory management Unit(MMU)
- 프로그램 실행 중에 논리적 주소를 물리적 주소로 변환 작업 수행
relocation register(재배치 레지스터)을 이용한 변환 기법(아주 기본적임)
논리적 주소가 346번이고, 재배치 레지스터가 14000 이면,
실제 물리 주소는 14346이다.
그러므로, 사용자 프로세스 입장에선 실제 물리 주소를 알수가 없다.
1.4 동적 적재(dynamic loading)
# 동적 적재란?
프로그램 내 각 루틴은 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기한다.사용하지 않는 루틴의 경우 결코 미리 적재되지 않는다. 운영체제는 동적 적재를 구현하는 라이브러리 루틴을 제공해줄 수 있지만,
동적 적재에 대한 구현은 프로그래머가 책임져야 한다.
1.5 동적 연결 및 공유 라이브러리(Dynamic linkin & Shared Library)
# 동적 연결이란?
- 동적 적재는 loading이 실행시까지 미뤄지지만, 동적 연결은 linking이 실행시까지 미뤄지는 것- 주로 시스템 라이브러리에서 사용
라이브러리를 호출하는 곳마다, stub이 생긴다.
이 stub은 해당 라이브러리를 어떻게 찾을 것인가를 알려주는 작은 코드 조각
라이브러리 루틴의 번지수를 알게 되면, stub은 자신을 그 루틴의 번지로 대체하게 된다.
다음 번에 그 부분이 호출되면, 동적 연걸과정을 다시 거칠 필요없이 직접 그곳의 라이브러리 루틴을 수행한다.
2. 스와핑
프로세스가 실행되기 위해서는 main memory에 있어야 하지만, 필요한 경우 프로세스는 실행 도중에
임시로 보조 메모리(디스크)로 보내어 졌다가 다시 메모리로 되돌아 올 수 있다.
swap out : memory -> disk
swap in : disk -> memory
우선 순위에 의한 프로세스 이동은 roll out, roll in 이라고 함.
swap out됐다가 다시 실행할 준비된 프로세스들을 OS는 준비 완료 큐(ready queue)에 모아놓는다.
CPU scheduler는 dispatcher를 호출하여 다음에 처리할 프로세스를 고른다.
swapping이 발생하면 context switching 또한 상당히 많이 발생한다.
# 총 스왑시간 계산
프로세스 크기 : 10 MB보조 메미로 초당 전송률 : 40 MB
보조 메모리로부터 10MB 프로세스를 전송하는데 걸리는 시간
10000 KB / 4000 KB = 0.25 sec => 250 mili sec
8 mili sec의 회전 지연시간을 가정하고, 하나의 프로세스를 swap out하고 다른 프로세스를 swap in 한다면,
총 스왑시간은 512 mili sec이 된다.
스와핑 대상 프로세스는 반드시 유휴 상태여야 한다.
input/output 수행시 해당 작업이 완료될때까지 대기하거나,
프로세스가 직접 I/O를 수행하지 말고, 운영체제의 버퍼에서 수행하도록 하는 것이다.
3. 연속 메모리 할당 (Contiguous Memory Allocation)
연속 메모리 할당은 일반적인 메모리 할당 기법 중 하나이다.
메모리는 크게 2 부분으로 나뉜다.
1) 메모리에 상주하는 운영체제를 위한 것
2) 사용자 프로세스를 위한 것
3.1 메모리 사상과 보호
# memory mapping이란
- 상한 레지스터로 논리주소의 범위값을 지정하고, MMU는 동적으로 논리적 주소에 재배치 레지스터 값을 더하여 물리적 주소로 변환한다.
CPU 스케줄러가 ready queue에서 다음으로 수행할 프로세스를 선택할 때, dispatcher를 호출하여
context switching 작업의 일환으로 재배치 레지스터(base)와 상한 레지스터(limit)에 정확한 값을 적재하도록 한다.
CPU에 의해서 생성되는 모든 주소들은 상한 레지스터와 재배치 레지스터들의 값을 참조해서 확인작업을 거치기 때문에
운영체제와 다른 사용자 프로그램을 현재 수행중인 사용자 프로그램의 접근으로부터 보호할 수 있다.
3.2 메모리 할당
3 가지의 메모리 할당 기법
1) 최초 적합(first fit) : 첫번째 사용 가능한 공간을 할당,
검색은 집한의 시작에서부터 하거나, 지난 번 검색이 끝났던 곳에서 시작될 수 있다. 충분히 큰 자유 공간을 찾았을 때 검색이 완료
2) 최적 적합(Best-fit) : 사용 가능한 공간들 중에서 가장 작은 것을 택한다. 공간 리스트가 크기 순으로 되어 있지 않다면 전 리스트를 검색한다.
3) 최악 적합(Worst-fit) : 가장 큰 공간을 택한다.
최초적합이 일반적으로 공간효율도가 좋고, 속도도 빠르다.
3.3 단편화 (fragmentation)
최초적합, 최적적합, 최악 적합을 이용한 메모리 할당시 외부 단편화가 발생한다.
최초 적합 또는 최적 적합 전략 중 어떤 것을 선택할 것인지에 대한 결정은 단편화 크기에 영향을 받는다.
또, 어느 쪽(위쪽에서부터 할당할 것인지, 아래쪽에서부터 할당할 것인지) 빈 공간을 할당할 것인가도 고려해야 한다.
최초 적합의 경우 N개 블록이 할당되었을 경우 0.5N개의 블록이 단편화 때문에 손실될 수 있다. 이것이 바로 50% 규칙
# 내부 단편화란?
- 일반적으로 메모리를 먼저 고정된 크기로 분할하고, 프로세스가 요청하면, 항상 이 분할된 크기의 정수배로만 할당해준다.
이 경우 할당된 공간은 요구된 공간보다 약간 더 클 수 있다. 이 두 크기의 차이가 내부 단편화이다.
외부 단편화 해결방법은 바로 압축 (compaction)
=> 압축은 프로세스내의 모든 주소들이 프로세스 실행기간에 동적으로 재배치가 이루어지는 경우 가능함
=> 압축 비용도 고려해야 한다.
또다른 해결 방벙은 페이징(paging)과 세그먼테이션(segmentation)
4. 페이징(paging)
4.1 기본 방식
페이징 그 자체는 동적 재배치의 한 형태
모든 논리 주소는 페이징 하드웨어에 의해 물리 주소로 사상됨.
페이징을 사용하면 외부 단편화 해결, 그러나 내부 단편화 발생,
프로세스가 n개의 페이지와 추가로 1바이트를 요구한다면, n+1번째 프레임은 항상 내부단편화가 발생할 수 있다.
내부 단편화 비율을 낮추기 위해 페이지 크기가 작은 것이 바람직할 수도 있지만, 그렇게 되면 페이지 테이블의 크기가 커지게 되고,
이 테이블이 차지하는 공간은 낭비될 수 있다.
# 프레임 테이블이란?
메모리 프레임의 각 상태 및 해당 프레임을 사용하고 있는 프로세스 및 페이지 정보를 담고 있다.
4.2 하드웨어 지원
각 프로세스마다 하나의 페이지 테이블을 할당한다.
페이지 테이블을 가리키는 포인터는 프로세스의 다른 레지스터 값과 함께 저장
페이지 테이블을 main memory에 저장하고 페이지 테이블 기준 레지스터(PTBR, Page_Table Base Register)로 하여금 페이지 테이블을 가리키도록 한다.
메모리 접근 시간이 문제될 수 있다. 특정 물리 메모리 주소에 접근하기 위해서 중간에 페이지 테이블을 거쳐야 하기 때문에
2번의 메모리 접근이 일어난다.
이 문제에 대한 해결은 TLB(Translation Look-aside Buffer)라고 불리는 특수한 하드웨어 캐시가 사용됨.
TLB에 대한 페이지 탐색은 동시에 이뤄지기 때문에 빠르다.
TLB는 비싸기 때문에 일부 페이지 테이블만 가지고 있을 수 밖에 없다.
TLB miss가 발생하면 페이지 테이블에서 찾고, 찾아낸 페이지 번호와 프레임 번호는 TBL에 추가하여 다음 참조시 매우 빨리 처리할 수 있게 한다.
TLB에 ASID가 추가되면 한 TLB안에 여러 프로세스들의 정보를 동시에 함께 보관할 수 있다.
ASID는 TLB 항목이 어느 프로세스에게 속한 것인지를 알려주며, 그 프로세스의 정보를 보호하기 위해 사용
4.3 보호
보호비트를 이용해 읽기 전용, 읽기-쓰기인지 정의 가능
페이지 테이블에는 유효 비트(valid/invalid) 라는 비트가 하나 더 있다.
유효 페이지는 합법적인 페이지, 무효 페이지는 논리적인 주소공간에 속하지 않는 것
4.4 공유 페이지(shared page)
재진입 가능 코드(reentrant code, pure code)는 수행하는 동안 절대 변하지 않는다. 그래서 두 개이상의 프로세스들이 동시에 공유 가능함.
각 프로세스들은 레지스터들의 복사값과 프로세스가 수행되는 동안 필요한 자료들을 따로 저장함.
공유를 위해선 코드는 반드시 재진입이 가능해야 함.
5 페이지 테이블 구조
5.1 계층적 페이지
two-level paging scheme
three-level paging scheme
four-level paging scheme
64 bit OS에서는 계층적 페이지 테이블 구조를 잘 사용하지 않는다.
참고로, UltraSPARC은 7 level paging scheme을 사용한다.
5.2 Hashed Page Table
주소 공간이 32 bit보다 커지면 해시 값이 가상 페이지 번호가 되는 Hashed Page Table을 많이 쓴다.
Hashed Page table의 각 항목은 linked list 구조로 연결되어 있는데, 세개 필드를 가지고 있다.
1) 가상 페이지 번호(Hash 값) 2) mapping되는 페이지 프레임 번호 3) linked list 상의 다음 원소 포인터
# 클러스터형 페이지 테이블(clustered page table)이란?
각 항목들이 여러 개의 페이지를 가리킨다. 따라서, 한 개의 페이지 테이블 항목이 여러 페이지 프레임에 대한 mapping 정보를 지닐 수 있다.
메모리 접근이 불연속적이면서 전 주소 공간으로 넓게 퍼져 나오는 경우 유용
5.3 역 페이지 테이블
일반적으로 페이지 테이블의 가상 주소는 오름차순으로 정렬되어 있다.
# 역 페이지 테이블 이란?
- 메모리 프레임마다 한 항목씩을 할당한다. 각 항목은 그 프레임에 올라와 있는 페이지 주소, 그리고, 그 페이지를 소유하고 있는 프로세스의 ID를 표시하고 있다.
이렇게 되면 시스템에는 단 하나의 페이지 테이블만이 존재하게 되고, 테이블 내 각 항목은 메모리 한 프레임씩을 가리키게 된다.
논리 페이지마다 항목을 가지는 대신 물리 프레임에 대응되는 항목만 테이블에 저장하기 때문에 메모리에서 훨씬 작은 공간을 점유함.
역 페이지 테이블은 메모리 프레임에 따라 저장되어 있어서, 전체 테이블을 탐색해야 하기 때문에 페이지 탐색시간이 오래 걸릴 수 있다.
페이지 탐색 시간을 중이기 위해 주소공간 ID(프로세스ID+page number)를 Hash 하기도 하고, TLB 연관 메모리 레지스터에 임시로 저장하여 레지스터를 검색할 수 있다.
역페이지 테이블 구조에서는 메모리 공유를 할 수 없다.
6. 세그먼테이션(Segmentation)
6.1 기본 방식
메모리를 바라보는 사용자의 관점에 따른 것
논리구조 공간을 세그먼트들의 집합으로 정의,
논리 주소는 <segment-number, offset>으로 구성됨.
6.2 하드웨어
세그먼트 테이블은 base와 limit에 대한 레지스터들이 쌍으로 이루어진 배열
base는 세그먼트의 시작 주소, limit은 세그먼트의 길이
7.1 pentium segmentation
CPU - (논리주소) -> 세그먼테이션 유니트 - (선형주소) -> 페이징 유니트 -(물리 주소)-> 물리메모리
7.2 Pentium Paging
페이지 크기는 4KB, 4MB 임.
10개의 상위 비트는 Pentium 구조에서 페이지 디렉토리(page directory)라고 부르는 최상위 페이지 테이블의 항목을 가리킴
Page size라는 플래그가 있는데, 이게 설정되면 page size는 4MB 라는 의미임. 페이지 디렉토리가 직접적으로 4 MB 페이지 프레임을 가리킴.
7.3 Pentiumn 시스템 기반의 Linux
오직 6개의 세그먼트를 사용
1) 커널 코드를 위한 세그먼트
2) 커널 자료를 위한 세그먼트
3) 사용자 코드를 위한 세그먼트
4) 사용자 자료를 위한 세그먼트
5) 작업 상태 세그먼트(Task-state segment, TSS)
6) 디폴트 지역 기술자 테이블(LDT) 세그먼트
linux는 3 level paging scheme을 사용한다.
전역 디렉토리 + 중간 디렉토리 + 페이지 테이블 + 변위
Pentium 구조는 2 level paging scheme만을 사용하는데, Linux의 경우 중간 디렉토리를 0으로 설정함으로써 사용하지 않는다.
