CHAPTER 8 - 메모리 관리 전략(Memory Management Strategies)
CH 8에서는,
- 첫째로, Memory Hardware를 구성하는 다양한 방법에 대해 알 수 있다.
- 둘째로, 프로세스에게 Memory를 할당하는 다양한 기법들에 대해 알 수 있다.
- 셋째로, 현대 컴퓨터 시스템의 Paging의 동작 방법에 대해서 알 수 있다.
- 성능을 향상시키기 위해서는 여러 프로세스들이 주 메모리(Main Memory)를 공유해야 한다.
- 메모리를 관리하는 방법은 단순 hardware 방식에서 paging, segment 방법까지 다양하게 존재한다.
8.1 배경(Background)
- Memory는 각각 주소가 할당된 byte들의 array로 구성된다.
* 기본 하드웨어
- Main Memory와 processor 자체에 내장되어 있는 register들은 CPU가 직접 접근할 수 있는 유일 general-purpose storage이다.
- 따라서, 모든 실행되는 instruction과 data들은 CPU가 직접적으로 접근할 수 있는 main memory와 register에 있어야 한다.
- CPU에 내장되어 있는 register들은 일반적으로 CPU clock의 1 cycle 내에 접근이 가능하다.
- 대부분의 CPU들은 register에 있는 instruction의 decode와 간단한 operation을 이 시간 내에 처리한다.
- memory bus를 통해 전송되는 main memory의 경우, main memory에 대한 접근을 완료하기 위해서는 많은 CPU clock tick cycle이 소요되며, 이 경우 CPU가 필요한 데이터가 없어서 명령어를 수행하지 못하고, 지연(Stall) 되는 현상이 발생하게 된다.
- 이 문제를 해결하기 위해 CPU와 main memory 사이에 빠른 속도를 가진 Cache를 추가하는 것이다.
- Cache는 보통 빠르게 접근할 수 있도록 하기 위해 CPU 안에 있으며, Memory 접근 속도를 향상시킨다.
- 시스템이 올바르게 동작하기 위해서는 운영체제 영역을 보호해야 하며, Multi-user System인 경우
추가적으로 다른 user program이 특정 user program을 접근하는 것을 막아야 한다.
- OS가 이를 행하면 성능이 떨어지기 때문에, hardware가 이를 지원해야 한다.
- base와 limit register를 사용하여 Memory 보호 기법을 제공할 수 있다.
* 주소의 할당
- 프로그램은 원래 binary executable file로 disk에 저장되어 있어야 한다.
- 프로그램이 "Main Memory"로 올라오게 되면, 프로세스가 되어야 한다.
- 디스크에서 Main Memory로 들어오기를 기다리고 있는 프로세스들의 집합은 input queue를 구성한다.
- 보통 single-tasking의 작업 절차는 input queue의 프로세스 중 하나를 선택해서, Memory로 load 한다.
- 이 프로세스가 종료되면, 해당 프로세스가 사용했던 memory space가 available space가 된다.
- 대부분의 시스템은 user 프로세스가 memory 내 어느 부분으로도 올라올 수 있도록 지원한다.
- 대부분의 경우 user pgoram은 아래 그림과 같이 여러 단계를 거쳐 실행되기 때문에 이들 단계를 거치는 동안
주소들은 여러 가지 다른 표현 방식을 거치게 된다.
- 전통적으로 Memory 주소 공간에서 instruction과 data의 binding은 그 binding이 이루어지는 시점에 따라 다음과 같이 구분된다.
(1) 컴파일 시간(Compile time) 바인딩 : 만일 프로세스가 memory 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 absolute code를 생성할 수 있다.
(2) 적재 시간(Load time) 바인딩 : 만약 프로세스가 memory 내 어디로 올라오게 될지를 compile 시점에 알지 못하면, 컴파일러는 일단 이진 코드를 relocatable code로 만들어야 한다.
(3) 실행 시간(Execution time) 바인딩 : 만약 프로세스가 실행하는 중간에 Memory 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면, "바인딩이 실행 시간까지 허용되었다"라고 한다.
* 논리 대 물리 주소 공간(Logical-Versus Physical-Address Space)
- CPU가 생성하는 주소를 논리 주소(Logical Address)라고 하며, memory가 취급하게 되는 주소를 일반적으로
물리 주소(Physical Address)라고 한다.
- 앞의 binding 분류에서 compile time과 load time의 bind은 논리 주소와 물리 주소가 같다.
- Execution time의 binding의 경우 논리 주소를 가상 주소(Virtual Address)라고 한다.
- 프로그램의 실행 중에는 가상 주소를 물리 주소로 바꿔주어야 하는데, 이 변환 작업은 hardware인 MMU(Memory Management Unit)에 의해 실행된다.
- base register는 relocation register라고도 불린다.
- 만약, relocation register 값이 14000이라면, 346번지를 access 할 때, 실은 14346 번지를 access 하게 된다.
- 이에, user program은 실제적인 물리 주소(Physical Address)를 절대 알 수 없다.
- 단지 346번지에 대한 pointer를 생성해서 그것에 대한 저장, 연산, 비교 등의 작업을 수행할 수 있다.
* 동적 적재(Dynamic Loading)
- 지금까지 프로세스가 실행되기 위해서는 그 프로세스 전체가 미리 memory에 올라와 있어야 했다.
- 이 경우, 프로세스의 크기는 memory의 크기보다 커서는 안 된다.
- 이에, memory 공간의 보다 효율적인 이용을 위해서는 동적 적재(Dynamic Loading)이 필요하다.
- 동적 적재(Dyanmic Loading)의 장점은 Routine이 필요한 경우에만 적재되는 것이다.
- 이러한 구조는 오류 처리 루틴과 같이 아주 간혹 발생하면서도 많은 양의 코드를 필요로 하는 경우에 유용하다.
* 동적 연결 및 공유 라이브러리(Dynamic Linking & Shared Libaries)
- 동적 연결 라이브러리(Dynamically linked libraries)는 사용자 프로그램이 실행될 때, 해당 프로그램에 연결되는 시스템 라이브러리이다.
- 동적 연결에서는 library를 부르는 곳마다 stub이 생기게 된다.
(stub : 라이브러리를 어떻게 찾을 것인가에 대해 알려주는 small code piece)
8.2 스와핑(Swapping)
- 프로세스가 실행되기 위해서는 memory에 있어야 하지만, 프로세스는 실행 중에 임시로 예비 저장 장치(backup store)로 내보내어졌다가 실행을 계속하기 위해 다시 Memory로 되돌아올 수 있다.
- 모든 프로세스의 물리 주소 공간 크기의 총합이 시스템의 실제 물리 memory 크기보다 큰 경우에도 swapping을 사용하면, 동시에 실행하는 것이 가능하여 Multi-programming의 사용도를 높일 수 있다.
* 기본 스와핑(Standard Swapping)
- 기본 스와핑(Standard Swapping)은 Main Memory와 backing store 사이에서 프로세스를 이동시킨다.
- backing store는 일반적으로 fast disk를 사용한다.
- 이 저장 장치의 크기는 모든 사용자의 memory image를 저장할 만큼 커야 하며, 직접 접근이 가능해야 한다.
- 시스템은 실행할 준비가 된 모든 프로세스를 모아 ready queue에 가지고 있어야 하며, CPU 스케줄러는 다음 프로세스를 고를 때 dispatcher를 호출한다.
- dispatcher는 이 queue에 있는 다음 프로세스가 memory에 올라와 있는지를 확인하여, 만약 안 올라와 있다면 디스크에서 불러들어야 한다.
- 이 프로세스를 위한 공간이 memory에 없다면, 공간을 만들기 위해 현재 memory에 올라와 있는 프로세스를 내보낸다.(Swap out)
- 만약 사용자 프로세스의 크기가 100MB이고, backing store는 50MB/s의 전송률을 가진 디스크라고 하면, backing store로부터 100MB 프로세스를 전송하는 데 걸리는 시간은 100MB/(50MB/s) = 2s이다.
- Swap in과 Swap out을 해야 하므로 총 걸리는 시간은 2s X 2 = 4s이다.
- 한 프로세스가 스왑(swap)하기를 원한다면, 그 프로세스가 완전히 idle 하다는 것을 보장해야 한다.
- 해당 프로세스가 I/O 장치의 어떤 신호를 주고받는 동안이라면, 그동안은 스왑(Swap)해서는 안 된다.
- 현대 운영체제들은 보통 기본 스와핑(Standard Swapping)을 사용하지 않는다.
- 스와핑 시간이 오래 걸리므로, 실행에 할당되는 시간이 적어지기 때문이다.
- 이에, 변형하여 swapping을 사용하는데 free memory가 threashold보다 부족하게 될 때만 swapping을 수행한다.
- 또 다른 변형 Swapping은 프로세스 전체를 Swapping 하지 않고, 일부만을 Swapping 하여 사용한다.
* 모바일 시스템에서의 스와핑
- 보통 모바일 시스템은 어떠한 형태의 스와핑(Swapping)도 제공하지 않는 것이 일반적이다.
- 대신, free memory가 정해진 Threshold보다 떨어지면 Apple의 iOS는 Application에게 할당된 memory를 자발적으로 반환하도록 요청한다.
- Android는 Swapping을 지원하지 않고, free memory가 부족하다면 프로세스를 종료시키는 것이 가능하다.
8.3 연속 메모리 할당(Contiguous Memory Allocation)
- (Main) Memory는 일반적으로 두 개의 부분으로 나뉘는데, 하나는 Memory에 존재하는 운영체제를 위한 것이며, 다른 하나는 User Process를 위한 것이다.
* 메모리 보호(Memory Protection)
- 만일 시스템이 limit register와 relocation register를 가지고 있다면, 프로세스가 자신이 소유하지 않은 memory를 접근할 수 없게 강제할 수 있다.
- CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, 디스패처(dispatcher)는 context switch의 부분으로 relocation register와 limit register에 정확한 값을 load 한다.
* 메모리 할당(Memory Allocation)
- 가장 간단한 memory allocation 방법은 memory를 똑같이 고정된 크기로 분할(partition) 하는 것이다.
- 각 분할(Partition)마다 한 프로세스를 가지고, 이때 분할의 개수를 Multi-programming degree라고 부른다.
- 가변 분할(Variable-partition) 기법에서 운영체제는 memory의 어떤 부분이 사용되고 있고, 어떤 부분이 사용 되지 않고 있는가를 파악할 수 있는 테이블을 유지한다.
- 초기에 모든 memory 공간은 한 개의 큰 사용 가능한 블록으로 구성되어 있으며, 이때 1개의 hole이 있다고 한다.
- 일반적으로 memory에는 다양한 크기의 free space가 여기저기 존재하게 된다.
- 이런 memory에서는 동적 메모리 할당 문제(Dynamic Storage Allocation problem)이 있을 수 있다.
- 이 문제는 free hole의 list로부터 size n의 block을 요구하는 것을 어떻게 만족시킬 것인가에 대한 문제이다.
- 이 문제의 해결책은 대표적으로 아래 3가지가 있다.
(1) 최초 적합(first-fit) : 첫 번째 사용 가능한 가용 공간에 할당한다.
(2) 최적 적합(best-fit) : 사용 가능한 공간들 중에서 가장 작은 공간에 할당한다.
(3) 최악 적합(worst-fit) : 사용 가능한 공간들 중에서 가장 큰 공간에 할당한다.
* 단편화(Fragmentation)
- 앞에서 기술한 방법들은 외부 단편화(External fragmentation)가 발생한다.
- 프로세스들이 memory에 load 되고, 제거되는 일이 반복되다 보면, 일부 free space는 사용하지 못할 만큼 작아진다.
- 최초 적합(first-fit)의 경우, 통계적인 분석을 통해 N 개의 block이 할당되었을 때 0.5N 개의 block이
단편화(Fragmentation) 때문에 손실될 수 있다고 알려져 있으며, 이를 50% 규칙이라고 한다.
- 18,464B의 free space에서 어느 한 프로세스가 18,462B를 요구하면, 2B의 hole이 남게 된다.
- 이 경우, 2B의 hole을 위해 시스템이 더 큰 부담을 가진다.
- 이에 일반적으로 memory를 작은 공간들로 분할한 뒤에, 이 공간 크기의 정수 배로 만 공간을 할당하는 것이 일반적이다.
- 이 경우 할당된 공간은 요구된 공간보다 약간 더 클 수 있는데, 이 두 공간의 크기 차이를 내부 단편화(Internal fragmentation)이라고 한다.
- 외부 단편화 문제를 해결하는 방법으로는 압축(Compaction)이 있다.
- 이 방법은 memory의 모든 내용을 한 군데로 몰고, 모든 free space들을 다른 한 군데로 몰아서 큰 block을 만드는 방법이다.
8.4 세그먼테이션(Segmentation)
- 세그먼테이션은 프로그래머가 인지하는 memory의 모습을 실제 physical memory의 모습으로 변환해주는 기법을 제공한다.
* 기본 방법(Basic Method)
- 프로그래머가 생각하는 프로그램의 모습은 아래 그림과 같이 가변적인 길이를 가지는 모습이다.
- 세그먼테이션(Segmentation)은 위와 같이 프로그래머가 생각하는 모양을 그대로 지원하는 메모리 관리 기법.
- 프로그래머가 생각하는 논리 구조 공간(Logical address space)은 세그먼트들의 집합으로 이루어진다.
* 하드웨어(Hardware)
- Segment table의 각 항목은 Segment의 base와 limit를 가지고 있다.
- Segment base는 Segment의 시작 주소를 나타내며, Segment limit은 Segment의 길이를 명시한다.
- 세그먼테이션(Segmentation)의 예시는 아래와 같다.
8.5 페이징(Paging)
- 세그먼테이션(Segmenation)은 프로세스가 load 되는 물리 주소 공간이 연속적이지 않더라도 load를 허용한다.
- 페이징(Paging)은 위의 이점을 가지면서, 단편화에 따른 압축 작업이 필요 없다.
- 또한, 페이징(Paging)은 swap-out 되는 다양한 크기의 세그먼트를 backing storage에 저장해야 하는 문제도 해결한다.
* 기본 방법(Basic Method)
- 물리 메모리(Physical Memory)는 프레임(Frame)이라 불리는 같은 크기의 block으로 나누어진다.
- 논리 메모리(Logcial Memory)는 페이지(Page)라 불리는 같은 크기의 block으로 나누어진다.
- 프로세스가 실행될 때, 그것의 페이지는 파일 시스템이나 예비 저장 장치로부터 가용한 main memory frame으로 load 된다.
- CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 변위(d) 두 개의 부분으로 이루어진다.
- 페이지 번호(p)는 페이지 테이블(Page Table)을 access 할 때 사용되며, 페이지 테이블은 main memory에서 각 page가 점유하는 주소를 가지고 있다.
- 아래 그림에서 논리 주소 0은 페이지(page) 0, 변위(offset) 0이다.
- 페이지 테이블을 색인으로 찾아서 페이지(page) 0이 프레임(frame) 5에 있다는 것을 알아낸다.
- 이에 논리 주소 0은 실제 주소 20 ( = (5 X 4) + 0)에 mapping 된다.
- 페이징(Paging) 그 자체는 동적 재배치의 한 형태이다.
- 페이징 기법을 사용하면 외부 단편화는 발생하지 않지만, 내부 단편화는 발생될 수 있다.
- 예를 들어, 페이지 크기가 2048 Byte이고, 프로세스가 72,766 Byte를 요구한다면, 35개의 Page Frame을 할당하고, 1086Byte가 남게 된다.
- 이때, 36개의 Page Frame을 할당하면 36번째 Page Frame은 2048-1086 = 962Byte의 내부 단편화가 발생한다.
- 이에 작은 페이지 크기가 바람직할 수 있지만, 너무 작게 되면 페이지 테이블의 크기가 커지게 될 수 있다.
- 한 프로세스가 실행되기 위해 도착하면, 그 프로세스의 크기가 페이지 몇 개 분에 해당하는가를 조사한다.
- 각 사용자 페이지(Page)는 한 프레임(Frame) 씩을 필요로 한다.
- 페이징의 가장 중요한 특징은 memory에 대한 프로그래머의 인식과 실제 내용이 서로 다를 수 있다는 점이다.
- 프로그래머는 memory가 하나의 연속적인 공간으로 이루어졌다고 생각할 수 있다.
- 그러나, 실제로는 프로그램은 여러 곳에 프레임 단위로 분산되어 있고, 많은 다른 프로그램들이 존재하고 있다.
- 운영체제는 memory를 관리하기 때문에, 물리 Memory에 Allocation Details에 대해 파악하고 있어야 한다.
- 어느 프레임이 사용 가능 한지, 총 프레임이 몇 개인지에 대한 정보가 프레임 테이블(Frame Table)에 존재한다.
- 운영체제는 모든 프로세스들의 주소들을 실제 주소로 mapping 할 수 있어야 한다.
* 하드웨어 지원(Hardware Support)
- 각 운영체제는 페이지 테이블을 저장하기 위한 고유의 방법을 가지고 있다.
- 몇몇 OS는 각 프로세스마다 하나의 page table을 할당한다.
- 페이지 테이블이 작은 경우에 register들의 집합으로 구현될 수 있다.
- 페이지 테이블의 크기가 큰 경우에는 페이지 테이블을 주 메모리(Main Memory)에 저장하고,
페이지 테이블 기준 레지스터(PTBR)로 하여금 페이지 테이블을 가리키도록 한다.
- 이 방식은 context switch 시간을 줄일 수 있지만, 메모리 접근 시간을 늘릴 수 있다.
- 이에 TLB(Translation Look-aside Buffers)로 불리는 특수한 소형 hardware cache가 사용된다.
- 접근하려는 memory의 page 번호가 TLB에서 발견되는 비율을 적중률(hit ratio)라고 한다.
- 예를 들어, 80%의 적중률이란 TLB에서 원하는 page 번호를 발견할 횟수가 80%라는 것을 의미한다.
- Main memory를 접근하는데 총 100ns가 소요된다면, 원하는 데이터를 접근하는 데 총 100ns가 걸린다.
- 만약 TLB에서 페이지 번호를 찾지 못하면, 페이지 테이블에 접근(100 ns), 원하는 데이터를 메모리에서 읽어야(100ns) 하므로 (100ns + 100ns = 200ns)의 시간이 소요된다.
- 만약 hit ratio가 80% 라면 실제 접근 시간은 0.80 X 100 + 0.20 X 200 = 120 ns가 된다.
- 만약 hit ratio가 99% 라면, 실제 접근 시간은 0.99 X 100 + 0.01 X 200 = 101 ns가 된다.
* 보호(Protection)
- 페이지화된 환경에서 memory 보호는 각 페이지에 붙어 있는 protection bits에 의해 구현된다.
- 각 비트는 이 페이지가 읽기 전용인지 쓰기가 가능한지를 정의할 수 있다.
- 페이지 테이블의 각 엔트리에는 유효/무효(valid/invalid)라는 하나의 비트가 더 있다.
- 이 비트가 유효로 설정되면, 관련된 페이지가 프로세스의 합법적인 페이지임을 나타낸다.
- 이 비트가 무효로 설정되면, 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.
- 몇몇 시스템은 페이지 테이블의 크기를 나타내기 위해 페이지 테이블 길이 레지스터(PTLR)을 제공한다.
- 프로세스가 제시한 주소가 유효한 범위 내에 있는지를 확인하기 위해 모든 논리 주소 값이 PTLR과 비교된다.
* 공유 페이지(Shared Pages)
- 페이징(Paging)의 또 다른 장점은 코드를 쉽게 공유할 수 있다는 점이다. (Multi-tasking에서 중요)
- 재진입 가능 코드는 수행하는 동안 절대 변하지 않고, 두 개나 그 이상의 processor들이 동시에 같은 코드를 수행할 수 있다.
8.6 페이지 테이블의 구조(Structure of Page Table)
* 계층적 페이징(Hierarchical Paging)
- 많은 컴퓨터들이 매우 큰 주소 공간을 가지므로, 페이지 테이블의 크기도 맞춰서 커지고 있다.
- 만약 32bit 논리 주소 공간을 가진 시스템에서 페이지의 크기가 4KB라면, 페이지 테이블은 (2^32 /2^12)로
대략 100만 개의 항목으로 구성될 것이다.
- 이에 커지는 페이지 테이블을 Main memory에 연속적으로 할당하기 보다, 페이지 테이블을 여러 개로 나누어 사용하는 방법이 가능하다.
- 대표적인 방법 중 하나는 2단계 페이징 기법(Two-level paging scheme)로 페이지 테이블 자체를 다시 페이지화하는 것이다.
* 해시 페이지 테이블(Hash Page Tables)
- 주소 공간이 32비트보다 커지면, 가상 주소를 hash로 사용하는 hash page table을 많이 쓴다.
- 해시 페이지 테이블(Hash Page Table) 알고리즘은 다음과 같이 작동한다.
(1) 가상 주소 공간으로부터 페이지 번호가 오면 그것을 hashing 한다.
(2) 그 값으로부터 hash page table에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교한다.
(3) 일치되면, 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다.
* 역 페이지 테이블(Inverted Page Table)
- 운영체제는 프로세스가 가상 페이지 주소를 제시할 때마다 이 테이블에 와서 그것을 실제 페이지 주소로 변환해 주어야 한다.
- 이때 테이블이 오름차순으로 정렬되어 있기 때문에, 페이지 테이블이 클 경우 많은 메모리 공간을 점유한다.
- 이 문제를 해결하는 방법 중 하나는 역 페이지 테이블(Inverted Page Table)을 사용하는 것이다.
- 역 페이지 테이블(Inverted Page Table)에서는 메모리 frame마다 한 항목씩을 할당한다.
- 각 항목은 그 frame에 올라와 있는 페이지 주소, 페이지를 소유하고 있는 프로세스의 ID를 표시한다.
- 역 페이지 테이블을 사용하는 시스템에서 Memory의 공유는 더 어렵다.
- Memory의 공유는 보통 하나의 physical memory에 mapping 되는 여러 개의 가상 주소를 통해 구현된다.
- 이 방법은 모든 physical page에 대해 하나의 가상 주소를 갖게 하는 이 구조에서는 사용할 수 없다.
-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』
'운영체제(OS)' 카테고리의 다른 글
| 공룡책으로 정리하는 운영체제 - CHAPTER 9. 가상 메모리(Vritual Memory) (0) | 2022.05.08 |
|---|---|
| 공룡책으로 정리하는 운영체제 - CHAPTER 7. 교착상태(Deadlocks) (0) | 2022.05.08 |
| 공룡책으로 정리하는 운영체제 - CHAPTER 6. CPU 스케줄링(CPU Scheduling) (0) | 2022.05.07 |
| 공룡책으로 정리하는 운영체제 - CHAPTER 5. 프로세스 동기화(Process Synchronization) (1) | 2022.05.07 |
| 공룡책으로 정리하는 운영체제 - CHAPTER 4. 스레드(Threads) (0) | 2022.05.07 |