- Memory Hardware를 구성하는 다양한 방법에 대해 알 수 있습니다.
- 프로세스에게 Memory를 할당하는 다양한 기법들에 대해 알 수 있습니다.
- 현대 컴퓨터 시스템의 Paging의 동작 방법에 대해서 알 수 있습니다.
8.1 Background
메모리는 각각 주소가 할당된 일련의 바이트들로 구성되며,명령어 실행은 메모리로 부터 명령어를 가져와 decode하고, operand를 fetch하여 operand에 대한 명령어를 실행하고 이를 다시 저장합니다. 이 장에서는 세부사항 보다는 일련의 주소만 언급하기로 합니다.
8.1.1 Basic Hardware
주 메모리와 프로세서 자체에 내장되어 있는 레지스터들은 CPU가 직접 접근할 수 있는 유일한 범용 저장장치입니다. 따라서, 모든 실행되는 instruction과 data들은 CPU가 직접적으로 접근할 수 있는 main memory와 register에 있어야 합니다. CPU에 내장되어 있는 register들은 일반적으로 CPU clock의 1 cycle 내에 접근이 가능합니다. 대부분의 CPU들은 register에 있는 instruction의 decode와 간단한 operation을 이 시간 내에 처리합니다.
하지만 메모리 버스를 통해 전송되는 main memory의 경우, main memory에 대한 접근을 완료하기 위해서는 많은 CPU clock tick cycle이 소요되며, 이 경우 CPU가 필요한 데이터가 없어서 명령어를 수행하지 못하고, 지연(Stall) 되는 현상이 발생하게 됩니다. 이 문제를 해결하기 위해 CPU와 main memory 사이에 빠른 속도를 가진 캐시를 추가하는 것입니다. 캐시는 보통 빠르게 접근할 수 있도록 하기 위해 CPU 안에 있으며, Memory 접근 속도를 향상시킵니다.
시스템이 올바르게 동작하기 위해서는 운영체제 영역을 보호해야 하며, Multi-user System인 경우 추가적으로 다른 유저 프로그램이 특정 유저 프로그램에 접근하는 것을 막아야 합니다. OS가 이를 행하면 성능이 떨어지기 때문에, 하드웨어가 이를 지원해야 하며, 이는 base와 limit register를 사용한 메모리 보호 기법을 통해 수행 가능합니다.
CPU는 레지스터를 참조하며 메모리 공간을 보호하며, 레지스터 정보는 PCB에 담겨져 있습니다. 이때 레지스터는 base와 limit으로 나뉘어 base는 프로세스가 메모리에서 사용할 수 있는 가장 작은 physical address를 의미하며, limit은 사용할 수 있는 주소의 범위를 의미합니다. 즉, 프로세스가 사용할 수 있는 가장 큰 주소는 base와 limit의 합으로, 만약 따라서 어떤 프로세스의 base가 300040이고, limit이 120900이라면 프로세스가 접근할 수 있는 메모리 주소의 범위는 300040부터, 300040에 120900를 더한 420940까지가 됩니다. 이 범위를 벗어나면 segment fault를 던집니다.
8.1.2 Address Binding
일반적으로 프로그램은 디스크에 binary executable 파일로 저장되어 있습니다. 프로그램을 실행하기 위해서는 메모리에 로드해 프로세스로 만들어야 합니다. 이때 디스크에서 메인 메모리로 로드되기를 대기하는 곳이 입력 큐(input queue)입니다. 운영체제는 입력 큐에서 프로세스를 선택해 메모리에 로드합니다.
- 컴파일 시간(Compile time) 바인딩: 만약 compile time에 프로세스가 메모리의 어느 위치에 들어갈지 미리 알고 있다면 절대 코드를 생성할 수 있습니다. 이는 위치가 변경될 시 코드를 다시 컴파일해야 한다.
- 적재 시간(Load time) 바인딩: 프로세스가 메모리의 어느 위치에 들어갈지 미리 알 수 없다면 컴파일러는 relocatable code를 만들어야 하며, 이는 최종 바인딩은 로드의 소요 시간만큼 지연될 수 있습니다.
- 실행 시간(Execution time) 바인딩: 프로세스가 실행 중 메모리의 한 세그먼트에서 다른 세그먼트로 이동할 수 있다면 바인딩은 runtime까지 지연되어야 하며 "바인딩이 실행 시간까지 허용되었다"라고 합니다.
프로그램은 원래 binary executable file로 디스크에 저장되어, 프로그램이 main memory에 올라가면, 프로세스가 됩니다. 디스크에서 Main Memory로 들어오기를 기다리고 있는 프로세스들의 집합은 input queue를 구성합니다.
8.1.3 Logical Address vs Physical Address
CPU가 생성하는 주소는 논리 주소(logical address)이고, 메모리에 의해 취급되는 주소는 물리 주소(physical address)입니다. 컴파일 타임과 load-time에서 주소를 binding할 때는 논리 주소와 물리 주소가 같게 생성되는 반면 실행 시간에서는 다르게 생성됩니다. 이 경우 논리 주소를 가상 주소(Virtual Address)라고 한다. virtual address를 physical address로 대응시키는 것은 하드웨어 디바이스인 MMU(Memory-Management Unit)를 통해 수행됩니다.
예를 들어, relocation register 값이 14000이고, 346번지에 접근할 때, 실제 물리적 주소는 14346 번지를 접근하게 됩니다. 이에, 프로그램은 실제적인 물리 주소를 알 수 없지만 이에 대한 작업은 수행 가능합니다.
8.1.4 Dynamic Loading
지금까지 프로세스가 실행되기 위해서는 그 프로세스 전체가 미리 메모리에 올라와 있어야 하는데, 프로세스의 크기는 메모리의 크기보다 큰 경우에는 모두 불러들이는 것이 불가능하여, 효율적인 이용을 위해서는 동적 적재(Dynamic Loading)이 필요해집니다. 동적 적재의 장점은 Routine이 필요한 경우에만 적재되어 오류 처리 루틴과 같이 아주 간혹 발생하면서도 많은 양의 코드를 필요로 하는 경우에 유용합니다.
8.1.5 Dynamic Linking & Shared Libaries
동적 연결 라이브러리(Dynamically linked libraries)는 사용자 프로그램이 실행될 때, 해당 프로그램에 연결되는 시스템 라이브러리입니다. 다양한 프로그램에서 하나의 라이브러리를 참조하는데, 모든 프로그램에서 각자 사용한다면 이는 메모리 낭비가 심할 것입니다. 따락서 이를 하나의 라이브러리를 두고 프로그램마다 필요할 때 이를 부르는 식으로 해결하였습니다. 동적 연결을 수행할 때마다 stub이 생겨, stub으로 라이브러리를 찾게 됩니다. 이는 해당 라이브러리가 메모리에 존재 여부를 검사하고 없다는 이를 가져옵니다. 이러한 동적 연결은 라이브러리가 업데이트될 때 모든 프로그램을 다시 컴파일할 필요 없이 해당 라이브러리만 컴파일하면 되게 됩니다.
8.2 Swapping
프로세스가 실행되기 위해서는 메모리에 있어야 하지만, 프로세스는 실행 중에 임시로 예비 저장 장치(backup store)로 내보내어졌다가 실행을 계속하기 위해 다시 메모리로 되돌아올 수 있습니다. 모든 프로세스의 물리 주소 공간 크기의 총합이 시스템의 실제 물리 메모리 크기보다 큰 경우에도 swapping을 사용하면, 동시에 실행하는 것이 가능합니다.
8.2.1 Standard Swapping
기본 스와핑(Standard Swapping)은 메인 메모리와 예비 저장 장치 사이에서 프로세스를 이동시킵니다. 시스템은 실행할 준비가 된 모든 프로세스를 모아 ready queue에 가지고 있어야 하며, CPU 스케줄러는 다음 프로세스를 고를 때 dispatcher를 호출합니다. dispatcher는 이 queue에 있는 다음 프로세스가 memory에 올라와 있는지를 확인하여, 만약 안 올라와 있다면 디스크에서 불러들어야 합니다. 이때 디스크로 내보내는 것을 swap out, 메모리로 들여보내는 것을 swap in이라고 하며, 우선 순위에 따라 어떤 프로세스를 swap in/out할지 결정한다. swap하는데 걸리는 시간의 대부분은 디스크 전송 시간입니다. 만약 사용자 프로세스의 크기가 100MB이고, 저장 공간이 50MB/s의 전송률을 가진 디스크라고 하면, 100MB 프로세스를 전송하는 데 걸리는 시간은 100MB/(50MB/s) = 2s이다. swap in과 swap out을 해야 하므로 총 걸리는 시간은 2s X 2 = 4s입니다.
한 프로세스가 swap하기를 원한다면, 그 프로세스가 완전히 휴지(idle) 하다는 것을 보장해야 합니다. 만약 해당 프로세스가 I/O 장치의 어떤 신호를 주고받는 동안이라면, 그동안은 swap해서는 안 됩니다. 현대 운영체제들은 보통 기본 스와핑을 사용하지 않는데 이는, 시간이 오래 걸리므로, 실행에 할당되는 시간이 적어지기 때문입니다. 따라서, 이를 변형하여 swapping을 사용하는데 자유 메모리 양이 threashold보다 부족하게 될 때만 swapping을 수행하거나, 프로세스 전체를 swapping 하지 않고, 일부만을 swapping 하여 사용합니다.
8.2.2 모바일 시스템에서의 스와핑
보통 모바일 시스템은 어떠한 형태의 swapping도 제공하지 않는 것이 일반적입니다. 대신, 자유 메모리가 정해진 Threshold보다 떨어지면 Apple의 iOS는 Application에게 할당된 메모리를 자발적으로 반환하도록 요청합니다. Android는 swapping을 지원하지 않고, free memory가 부족하다면 프로세스를 종료시키는 것이 가능합니다.
8.3 Contiguous Memory Allocation
메모리는 일반적으로 두 개의 부분으로 나뉘는데, 하위 메모리에는 존재하는 운영체제를 위한 것이며, 상위 메모리에는 유저 프로세스를 위한 것입니다. 이때 연속 메모리 할당 시스템에서는 각 프로세스들이 연속적인 메모리 공간을 차지하게 됩니다.
8.3.1 Memory Protection
만일 시스템이 limit register와 relocation register를 가지고 있다면, 프로세스가 자신이 소유하지 않은 메모리로 접근할 수 없게 강제할 수 있습니다. CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, 디스패처(dispatcher)는 context switch의 부분으로 relocation register와 limit register에 정확한 값을 불러들입니다.
8.3.2 Memory Allocation
가장 간단한 메모리 할당 방법은 메모리를 똑같이 고정된 크기로 분할(partition)하는 것입니다. 각 분할마다 한 프로세스를 가지고, 이때 분할의 개수를 Multi-programming degree라고 부릅니다. 가변 분할(Variable-partition) 기법에서 운영체제는 메모리의 어떤 부분이 사용되고 있고, 어떤 부분이 사용되지 않고 있는가를 파악할 수 있는 테이블을 유지합니다.
프로세스를 메모리에 로드할 때는 먼저 메모리 상에 프로세스를 넣을 수 있는 공간을 찾습니다. 초기에 모든 메모리 공간은 한 개의 큰 사용 가능한 메모리을 분할하는 단위인 블록으로 구성되어 있으며, 이때 한 개의 공간(hole) 있다고 합니다다. 일반적으로 메모리에는 다양한 크기의 자유 공간이 여기저기 존재하게 된다. 이런 메모리에서는 동적 메모리 할당 문제(Dynamic Storage Allocation problem)이 있을 수 있습니다. 이 문제는 공간으로부터 크기 n의 블록을 요구하는 것에 대해 어떻게 만족시킬 것인가에 대한 문제가 발생하며 이에 대한 해결책은 대표적으로 아래 3가지가 존재합니다.
- 최초 적합(first-fit) : 첫 번째 사용 가능한 가용 공간에 할당합니다.
- 최적 적합(best-fit) : 사용 가능한 공간들 중에서 가장 작은 공간에 할당합니다.
- 최악 적합(worst-fit) : 사용 가능한 공간들 중에서 가장 큰 공간에 할당합니다.
최악은 메모리 효율적에서 가장 별로이며, 최적과 최초의 경우는 메모리 효율은 비슷하지만, 최초 적합이 속도가 더 빠릅니다.
8.3.3 Fragmentation
앞에서 기술한 방법들은 외부 단편화(External fragmentation)가 발생합니다. 프로세스들이 메모리에 적재되었다가, 제거되는 일이 반복되다 보면, 일부 자유 공간은 사용하지 못할 만큼 작아집니다.
최초 적합의 경우, 통계적인 분석을 통해 N 개의 블록이 할당되었을 때 0.5N 개의 block이 단편화 때문에 손실될 수 있다고 알려져 있으며, 이를 50% 규칙이라고 합니다. 18,464B의 free space에서 어느 한 프로세스가 18,462B를 요구하면, 2B의 hole이 남게 됩니다. 이 경우, 2B의 hole을 위해 시스템이 더 큰 부담을 가집니다. 이에 일반적으로 메모리를 작은 공간들로 분할한 뒤에, 이 공간 크기의 정수 배로 만 공간을 할당하는 것이 일반적입니다. 이 경우 할당된 공간은 요구된 공간보다 약간 더 클 수 있는데, 이 두 공간의 크기 차이를 내부 단편화(Internal fragmentation)라고 합니다.
외부 단편화 문제를 해결하는 방법으로는 압축(Compaction)이 있습니다. 이 방법은 메모리의 모든 내용을 한 군데로 몰고, 모든 자유 공간들을 다른 한 군데로 몰아서 큰 블록을 만드는 방법입니다. 하지만 이는 재배치가 어셈블 또는 적재 시에 정적으로 행해진다면 압축을 실행될 수 없고, 재배치가 가능한 경우에만 가능합니다.
외부 단편화 문제를 해결하려면 한 프로세스의 논리 주소 공간을 여러 개의 비연속적인 공간으로 나누는 방법인데 이는 페이징과 세그멘테이션을 통해 상호보완적으로 해결됩니다.
8.4 Segmentation
세그먼테이션은 하나의 프로세스를 여러 개로 나누는 것을 말하며, 이는 프로그래머가 인지하는 메모리의 모습을 실제 물리 메모리의 모습으로 변환해주는 메모리 기법입니다.
8.4.1 Basic Method
프로그래머가 생각하는 프로그램의 모습은 위와 같이 가변적인 길이를 가지는 모습입니다. 세그먼테이션은 위와 같이 프로그래머가 생각하는 모양을 그대로 지원하는 메모리 관리 기법으로 프로그래머가 생각하는 논리 구조 공간은 세그먼트들의 집합으로 이루어진다. 구현을 쉽게 하기 위해 세그먼트 이름 대신에 세그먼트 번호가 시스템에 매겨져 논리 주소는 <segment-number, offset>으로 이루어지게 됩니다.
8.4.2. Hardware
세그먼트 테이블에 의해 세그먼트를 추가한 2차원 주소를 실제 메모리 주소인 1차원 구조로 매칭시킵니다. 이 때 세그먼트 테이블의 각 항목은 세그먼트의 base와 limit를 가지고 있습니다. Segment base는 세그먼트의 시작 주소를 나타내며, Segment limit은 세그먼트의 길이를 명시합니다. 세그먼테이션의 예시는 아래와 같습니다.
8.5 Paging
세그먼테이션은 프로세스가 적재되는 물리 주소 공간이 연속적이지 않더라도 적재를 허용합니다. 페이징(Paging)은 마찬가지로 프로세스를 여러 조각으로 나누는데 단순히 크기를 기준으로 나누어 비슷한 요소라도 메모리 공간에 연속적으로 할당되지 않습니다. 이는 위의 이점을 가지면서, 단편화에 따른 압축 작업이 필요없게 됩니다. 또한, swap-out 되는 다양한 크기의 세그먼트를 저장 공간에 저장해야 하는 문제도 해결합니다.
8.5.1. Basic Method
CPU에 의해 만들어진 주소는 페이지 번호(p)와 페이지 변위(d) 두 부분으로 나뉩니다. 페이지 번호는 페이지 테이블의 index로써 페이지 테이블에 접근할 때 사용됩니다. 페이지 변위는 물리 주소를 얻을 때 쓰이며, 페이지 테이블의 base address에 페이지 변위을 더하면 무리 메모리를 구할 수 있다. 페이지 테이블은 메인 메모리에서 각 페이지가 점유하는 주소를 지니고 있습니다.
- 물리 메모리(Physical Memory)는 프레임(Frame)이라 불리는 같은 크기의 블록으로 나누어집니다.
- 논리 메모리(Logcial Memory)는 페이지(Page)라 불리는 같은 크기의 블록으로 나누어집니다.
페이징 그 자체는 동적 재배치의 한 형태이다. 페이징 기법을 사용하면 외부 단편화는 발생하지 않지만, 내부 단편화는 발생될 수 있습니다. 이에 작은 페이지 크기가 바람직할 수 있지만, 너무 작게 되면 페이지 테이블의 크기가 커지게 될 수 있습니다. 한 프로세스가 실행되기 위해 도착하면, 그 프로세스의 크기가 페이지 몇 개 분에 해당하는가를 조사합니다. 각 사용자 페이지(Page)는 한 프레임(Frame) 씩을 필요로 합니다. 페이징의 가장 중요한 특징은 메모리에 대한 프로그래머의 인식과 실제 내용이 서로 다를 수 있다는 점입니다. 프로그래머는 메모리가 하나의 연속적인 공간으로 이루어졌다고 생각할 수 있지만, 실제로는 프로그램은 여러 곳에 프레임 단위로 분산되어 있고, 많은 다른 프로그램들이 존재하고 있습니다.
운영체제는 메모리를 관리하기 때문에, 물리 메모리의 자세한 할당에 대해 파악하고 있어야 한다. 어느 프레임이 사용 가능 한지, 총 프레임이 몇 개인지에 대한 정보가 프레임 테이블(Frame Table)에 존재한다. 운영체제는 모든 프로세스들의 주소들을 실제 주소로 할당 할 수 있어야 하며 이를 기록해야만 합니다. 운영체제에서 시스템 호출을 처리하기 위해 소프트웨어적으로 물리 주소를 알아내기 위하여 페이지 테이블을 사용해야기 때문에 페이징은 context swtich 시간을 증가시킵니다.
8.5.2 Hardware Support
각 운영체제는 페이지 테이블을 저장하기 위한 고유의 방법을 가지고 있습니다. 몇몇 OS는 각 프로세스마다 하나의 page table을 할당합니다. 페이지 테이블이 작은 경우에 레지스터들의 집합으로 구현될 수 있습니다. 페이지 테이블의 크기가 큰 경우에는 페이지 테이블을 주 메모리에 저장하고, 페이지 테이블 기준 레지스터(PTBR)로 하여금 페이지 테이블을 가리키도록 합니다. 이 방식은 context switch 시간을 줄일 수 있지만, 메모리 접근 시간을 늘릴 수 있습니다. 이에 TLB(Translation Look-aside Buffers)로 불리는 특수한 소형 hardware cache가 사용됩니다.
접근하려는 메모리의 page 번호가 TLB에서 발견되는 비율을 적중률(hit ratio)라고 합니다. 예를 들어, 80%의 적중률이란 TLB에서 원하는 page 번호를 발견할 횟수가 80%라는 것을 의미합니다. 만약 메모리에 접근하는데 총 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가 됩니다.
8.5.3 Protection
페이지 테이블의 각 항목에는 valid-invalid bit가 붙어있어 그 값이 valid라면 해당 페이지에 접근이 가능하고, invalid라면 해당 페이지가 논리 주소 공간에 속하지 않아 접근할 수 없다는 것을 의미합니다. 몇몇 시스템은 페이지 테이블의 크기를 나타내기 위해 페이지 테이블 길이 레지스터(PTLR)을 제공합니다. 프로세스가 제시한 주소가 유효한 범위 내에 있는지를 확인하기 위해 모든 논리 주소 값이 PTLR과 비교된다.
8.5.4 Shared Pages
페이징의 또 다른 장점은 코드를 쉽게 공유할 수 있다는 점입니다. 재진입 가능 코드는 수행하는 동안 절대 변하지 않고, 두 개나 그 이상의 프로세서들이 동시에 같은 코드를 수행할 수 있습니다.
8.6 페이지 테이블의 구조(Structure of Page Table)
페이징을 직접 적용하면 페이지 테이블의 크기가 커진다. 페이지 테이블을 효율적으로 구성하는 몇 가지 방법이 있습니다.
8.6.1 Hierarchical Paging
계층적 페이징은 논리 주소 공간을 여러 단계의 페이지 테이블로 분할하는 기법입니다. 2단계 페이징 기법이 그 예시로 페이지 테이블 자체를 다시 페이지화 시키면서 모든 페이지를 로드해야 하는 부담을 줄일 수 있습니다. 이는 논리 주소 공간이 바깥 페이지, 안쪽 페이지, 변위, 총 3개의 구역으로 나누어진 형태를 띄게 될 것입니다.
8.6.2 Hash Page Tables
주소 공간이 32비트보다 커지면, 계층적 페이징보다 효율적인 가상 주소를 hash로 사용하는 해시 페이지 테이블을 많이 사용합니다. 해시 페이지 테이블(Hash Page Table) 알고리즘은 다음과 같이 작동합니다.
- 가상 주소 공간으로부터 페이지 번호가 오면 그것을 hashing 합니다.
- 그 값으로부터 해시 페이지 테이블에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교합니다.
- 일치되면, 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻습니다.
8.6.3 Inverted Page Table
운영체제는 프로세스가 가상 페이지 주소를 제시할 때마다 이 테이블에 와서 그것을 실제 페이지 주소로 변환해주어야 하는데, 이때 테이블이 오름차순으로 정렬되어 있기 때문에, 페이지 테이블이 클 경우 많은 메모리 공간을 점유합니다. 이 문제를 해결하는 방법 중 하나는 역 페이지 테이블(Inverted Page Table)을 사용하는 것 입니다. 역 페이지 테이블에서는 메모리 frame마다 한 항목씩을 할당하고, 각 항목은 그 frame에 올라와 있는 페이지 주소, 페이지를 소유하고 있는 프로세스의 ID를 표시합니다.
역 페이지 테이블을 사용하는 시스템에서 메모리의 공유는 더 어렵습니다. 메모리의 공유는 보통 하나의 물리 메모리에 mapping되는 여러 개의 가상 주소를 통해 구현됩니다. 이 방법은 모든 물리 페이지에 대해 하나의 가상 주소를 갖게 하는 이 구조에서는 사용할 수 없습니다.
'CS > Operation System' 카테고리의 다른 글
| Ch.9. Virtual Memory (0) | 2022.07.05 |
|---|---|
| Ch.7 Deadlocks (0) | 2022.06.18 |
| Ch.6 Synchronization (0) | 2022.06.18 |
| Ch.5 Process Scheduling (0) | 2022.06.18 |
| Ch.4 Multithreaded Programming (0) | 2022.06.17 |