Main Memory (주기억장치)

OS에서 주기억 장치를 관리하는 것에 앞서 먼저 주기억장치에서 사용되는 데이터가 어떻게 처리되는지 설명하겠습니다.

 

먼저 HDD에 있는 물리적 레코드(Physical Record)를 가져와서 RAM의 OS영역에 적재합니다. 그리고 실제로 프로세스에서 사용하게 되는건 RAM의 OS영역에 적재된 내용입니다. 이렇게 프로세스 에서 사용되는 레코드는 논리적 레코드(Logical Record)라고합니다.

 

위처럼 레코드를 사용하게 되면 주소 역시 변환이 필요합니다. 프로세스에서 논리적 레코드를 사용하게 되면서 HDD 상의 데이터에 접근하게 되는데 이때 RAM에 적재된 논리주소를 물리주소로 변환합니다. 이 과정을 Address Binding 이라고 합니다.

 

Address binding은 다음 3가지 시기에 정해집니다.

1. Compile
2. Load
3. Execute

먼저 1번의 경우 컴파일할때 실제 주소(Absolute Address, 절대주소)를 전부 가져와서 바인딩을 해두기때문에 Relocation이 필요할 때 컴파일을 다시해야하는 단점이 있습니다.

 

2번의 경우 컴파일해서 로드하는 과정에서 상대주소(Relative Address)를 사용하여 바인딩합니다. 이 경우 Relocation 시 다시 로드해야하는 단점이 있습니다.

 

3의 경우 실행할 때 CPU의 Relocation Register를 통해서 Relocation하기 때문에 Relocation 시 프로그램의 변경이 필요없이 Dynamic Relocation(동적 재배치)가 가능합니다. 즉, 주소가 필요한 명령어가 실행될 때, Relocation Register(Base Register)와 Offset 값을 통해 Effective Address(유효 주소)를 결정합니다.

 

코드 상의 Function Call이나 Subroutine Call ..etc 또한 주소를 가지는데, 이러한 Externel symbol들이 주소로 변환되는 과정을 Linking 이라고 합니다.

 

Externel Symbol들이 코드에 그대로 적재되어 있다면, 변경 시 re - compile 혹은 re - load가 필요하지만, 해당 내용들을 다른 파일로 빼두어서 데이터 독립성(Data Independency)를 유지시켜주거나 CALL 명령어를 통해 동적 링킹(Dynamic Linking)의 방법으로 재컴파일, 재로드를 방지합니다.

 

실행하고자 하는 프로그램이 주기억장치의 용량보다 큰 경우, Dynamic Loading을 사용하게 됩니다.

Dynamic Loading은 프로그램A에 있는 서로 연관이 없는 SubroutineA, SubroutineB 중 필요한 걸 먼저 RAM에 적재하고, 끝난 Subroutine을 Swap-out 후에 남은 Subroutine을 적재하는 방법입니다. 이 방법을 사용하기 위해 OS는 Overlay driver를 RAM의 OS영역에서 Swap-out 되지않게끔 적재해둡니다.

 

주기억장치를 관리하는 방법에는 다음 4가지가 있습니다.

1. RAM에 1개의 Program, 1개의 Process 적재
2. RAM에 1개의 Program, 2개의 Process 적재
3. Memory Contiguous Allocation(메모리 연속 할당)
4. Paging

1번의 경우 한번에 1개만 적재하기 때문에 CPU와 RAM의 활용도가 떨어지는 방법입니다.

2번의 경우 앞서 설명한 Swapping을 활용하여 1번보다 활용도가 높지만, 보조기억장치에 접근해야하므로 Swapping하는 시간이 많이 듭니다.

 

3번의 경우는 2가지 방법으로 다시 나뉩니다.

먼저 MFT(Multi Programming with a Fixed Number of Tasks)입니다.

MFT는 주기억장치를 일정크기로 나누어서 적재하는 방법으로 1번과 2번에 비해서 활용도가 더 높습니다.

하지만 나눈 파티션이 프로그램보다 크게된다면, 내부단편화(Internel Fragmentation)가 발생합니다. 또한, 정적이기 때문에 동적환경 적응에 불리합니다.

 

다음으로 MVT(Multi Programming with a Various Number of Tasks)입니다.

MVT는 MFT와는 반대로 동적으로 주기억장치의 공간을 나눕니다. 따라서, 내부단편화는 발생하지 않지만, 동적으로 공간을 나누고 다시 Swap-out되고 다른 프로그램이 적재되는 과정에서 너무 작은 Hole이 생기게 되어 외부단편화(Externel Fragmentation)이 발생하게됩니다. 또한 외부단편화가 아니더라도 너무 작은 Hole들로 효율이 조금 줄어들 수 있습니다.

 

외부단편화를 해결하기 위해 Compaction(압축)하는 방법도 있지만, 이를 위해 메모리를 복사하고 동적 재배치를 해야하기 때문에 복사하는 시간도 걸리게되고 바인딩 또한 동적으로 이루어져야하므로 선택하지 않습니다.

 

마지막으로 Paging입니다.

이 방법은 페이지 단위로 주기억장치에 적재하는 방법으로 프로그램을 페이지 단위로 쪼개서 RAM에 적재하게 되므로 외부단편화가 사라집니다. (다소의 내부단편화는 존재할 수 있음) 그리고 각 프로그램은 쪼개진 페이지들이 어디에 적재되어 있는지 확인하기 위해 별도의 Page Table을 가지게됩니다.

 

Page Table을 통해 바인딩하는 과정은 프로그램A의 논리주소를 Page의 크기로 나누어 몫과 나머지를 구하는데, 몫은 페이지의 번호로, 나머지는 Offset(변위)로 사용하여 프로그램을 찾습니다.

 

이 방법의 단점으로는 항상 Page Table을 참조해야하므로 Page Table이 주기억장치에 없게된다면 시간이 오래걸리게 됩니다. 주기억장치에 저장되어 있다 하더라도, Page Table을 찾고 바인딩을 통해 물리주소에 접근해야하므로 RAM을 총 2번 접근하게 되기때문에 이를 해결하기 위해 Page Table을 TLB라고 불리는 Cache Memory에 저장합니다.

 

EX)

RAM Access Time = 100nsec일때, Effective Memory Access Time = 100nsec + 100nsec = 200nsec.(Page Table 참조, 물리주소 접근)

 

RAM Access Time = 120nsec, Cache Access Time = 20nsec, Hit ratio = 90%일때, Effective Memory Access Time = 0.9 * 20 + 0.1 * (120 + 20) = 32nsec 으로 주기억장치 접근시간이 위 예시보다 긴데도 불구하고 캐시를 사용하므로 더 빠름. (물론, 캐시 적중률에 따라 크게 변함.)

 

위 예시에서 Hit ratio가 높게 설정될 수 있는 이유로는, 컴퓨터구조론에서 설명했던 참조의 지역성(Locality of Reference)에 의해 분기문을 만나는 경우가 아니라면 다음 접근하는 데이터는 근방에 있는 이유로 해당 지역을 캐시로 올려버리기 때문에 적중률이 높습니다.

 

다음 단점으로는 페이지 테이블 공간을 차지하는 문제입니다.

 

이 경우 Hierarchical Paging(Multi Level Paging)이나 Hashed Page Table, Inverted Page Table로 해소할 수 있습니다.

 

Multi Level Paging은 다음 예시처럼 이루어집니다.

 

EX)

Multi Level Paging의 사용전엔 32bit에서 Page 저장을 20bit, 변위를 12bit로 나누었다면, 2 Level Paging에서는 Page1이 10bit, Page2가 10bit를 사용하면서 같은 32bit에 페이지가 더 저장됩니다. 이때, valid, invalid 표기를 통해서 사용 시 생성안하는 Page Table이 존재하게 되면서 Page Table 참조시간이 늘어나는 대신 Page Table Size가 줄어드는 방식입니다.

 

Hashed Page Table은 Page Table이 정렬이 안되어 있다면 Sequential Search에 의해 O(N), 정렬이 되어있다면 정렬하는데 걸리는 시간과 이진탐색에 의해 O(n log n)이 소요되는 두가지에 비해 Hash Function으로 바로 접근하므로 O(1)로 빨라집니다. 하지만, 이 방법은 충돌을 우려해야하는 단점이 있습니다.

 

Inverted Page Table은 이름처럼 역 페이지 테이블로 RAM에 페이지 테이블을 1개만 적재합니다. 따라서 페이지 테이블의 PID를 찾아야하는 문제가 발생합니다. 대신 각 프로그램마다 페이지 테이블을 가졌던거에 비해 용량은 크게 줄어듭니다.

 

동적 적재에는 Overlay 방식외에도 Demand Paging과 Demand Segmentation이 제공되는데 demand Segmentation은 단편화 문제가 있어 주로 Demand Paging을 사용합니다.

 

Demand Paging은 프로그램이 RAM보다 클 때, 공간이 큰 RAM이 있다고 가정하고 프로그램을 작성하여 RAM 사이즈를 고려할 필요가 없습니다. 그 이유로는 Demand Paging을 이용하여 Virtual Memory를 구현해 논리주소공간과 물리주소공간의 독립을 이루어내기 때문입니다.

 

Inverted Page Table을 사용하면서 각 프로그램은 valid, invalid를 표현하는데, invalid라면, Page Fault Interrupt가 발생하여 Page - In(필요한 Page를 빈 frame에 적재)을 하게 됩니다.

 

Page - In을 하게되면 그 값을 토대로 Page Table이 수정되고 invalid 값은 valid로, Page Table은 해당 Page의 frame number를 가집니다.

 

즉, Page Fault Interrupt가 얼마나 발생하는지에 따라 demand Paging의 성능이 갈라집니다.

 

Page Fault Interrupt가 발생했을 때, 만일 빈 frame이 없다면, Page Out과 In이 발생하는데, 이 과정에서 Page replacement (페이지 교체)가 이루어집니다.

 

Page replacement는 다음 알고리즘에 의해 실행됩니다.

1. FIFO
2. Optimal Algorithm
3. LRU
4. LRU Approximation Algorithm

여기서 1번인 FIFO를 통해 victim을 선정하게되면, FIFO Anomoly(frame이 늘어났는데, page fault 발생률 증가)가 발생합니다.

 

2번의 Optimal Algorithm은 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는데, 어떤 페이지가 가장 오랫동안 사용하지 않을 지 예상하기 어렵기에 실제로 구현하지 않습니다.

 

3번인 LRU는 Belady Anomoly가 없는 알고리즘인 Stack Algorithm으로, 1번, 2번에 비해 효율적입니다.

 

LRU를 구현하기 위해 Counter(계수기)나 Stack 자료구조를 사용하여 순서를 유지합니다.

계수기를 사용하는 경우는 계수기 값이 작은 것부터 POP 하는 방식입니다.

 

4번은 LRU이지만, LRU와는 조금은 다른 방식으로 구현됩니다.

먼저, Shift Register를 이용하는 방식입니다. Shift Register를 0으로 초기화하고, 참조시에 최상위 비트를 1로 변경합니다. 일정시간 마다 오른쪽으로 시프트 연산을 수행하는 방식으로 구성됩니다.

 

두번째로 Second Chance Algorithm입니다. 이 경우, RAM의 각 프로그램에 reference bit를 붙여 초기값을 0으로 초기화합니다. 이때 참조하게된다면, 1로 바뀝니다. 만일 reference bit가 1일 때, 참조한다면 0으로 다시 변경하고 1번더 할 수 있게 합니다. 즉 이는 reference bit를 이용한 FIFO 알고리즘과 유사합니다.