Background
Basic Hardware
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 보호 기법을 제공할 수 있다.
Address Binding
일반적으로 프로그램은 디스크에 binary executable 파일로 저장되어 있다. 프로그램을 실행하기 위해서는 메모리에 로드해 프로세스로 만들어야 한다. 이때 디스크에서 메인 메모리로 로드되기를 대기하는 곳이 input queue다. 운영체제는 input queue에서 프로세스를 선택해 메모리에 로드한다.
명령과 데이터를 메모리 주소로 binding하는 시점에 binding이 구분된다.
- Compile time
만약 compile time에 프로세스가 메모리의 어느 위치에 들어갈지 미리 알고 있다면 absolute codel를 생성할 수 있다. 위치가 변경된다면 코드를 다시 컴파일해야 한다. - MS-DOS .COM 형식 프로그램이 예시다. - Load time
프로세스가 메모리의 어느 위치에 들어갈지 미리 알 수 없다면 컴파일러는 relocatable code를 만들어야 한다. 이 경우 최종 바인딩은 로드의 소요 시간만큼 지연될 수 있다. - Execution time
프로세스가 실행 중 메모리의 한 세그먼트에서 다른 세그먼트로 이동할 수 있다면 바인딩은 runtime까지 지연되어야 한다.
Logical Versus Physical Address Space
CPU가 생성하는 logical address이고, 메모리에 의해 취급되는 주소는 physical address이다. compile-time과 load-time에서 주소를 binding할 때는 logical address와 physical address가 같게 생성되는 반면 execution-time에서는 다르게 생성된다. 이 경우 logical address를 virtual address라고 한다. virtual address를 physical address로 대응시키는 것은 하드웨어 디바이스인 MMU(Memory-Management Unit)가 한다.
Dynamic Loading
지금까지 프로세스가 실행되기 위해서는 그 프로세스 전체가 미리 memory에 올라와 있어야 했다.
이 경우, 프로세스의 크기는 memory의 크기보다 커서는 안 된다.
이에, memory 공간의 보다 효율적인 이용을 위해서는 동적 적재(Dynamic Loading)이 필요하다.
동적 적재(Dyanmic Loading)의 장점은 Routine이 필요한 경우에만 적재되는 것이다.
이러한 구조는 오류 처리 루틴과 같이 아주 간혹 발생하면서도 많은 양의 코드를 필요로 하는 경우에 유용하다.
Dynamic Linking & Shared Libaries
동적 연결 라이브러리(Dynamically linked libraries)는 사용자 프로그램이 실행될 때, 해당 프로그램에 연결되는 시스템 라이브러리이다.
동적 연결에서는 library를 부르는 곳마다 stub이 생기게 된다.
- stub
라이브러리를 어떻게 찾을 것인가에 대해 알려주는 small code piece
Swapping
프로세스가 실행되기 위해서는 memory에 있어야 하지만, 프로세스는 실행 중에 임시로 예비 저장 장치(backup store)로 내보내어졌다가 실행을 계속하기 위해 다시 Memory로 되돌아올 수 있다.
모든 프로세스의 물리 주소 공간 크기의 총합이 시스템의 실제 물리 memory 크기보다 큰 경우에도 swapping을 사용하면, 동시에 실행하는 것이 가능하여 Multi-programming의 사용도를 높일 수 있다.
Contiguous Memory Allocation
Memory Protection
만일 시스템이 limit register와 relocation register를 가지고 있다면, 프로세스가 자신이 소유하지 않은 memory를 접근할 수 없게 강제할 수 있다.
CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, 디스패처(dispatcher)는 context switch의 부분으로 relocation register와 limit register에 정확한 값을 load 한다.
Memory Allocation
프로세스를 메모리에 로드할 때는 먼저 메모리 상에 프로세스를 넣을 수 있는 공간을 찾는다. 메모리을 분할하는 각 단위는 block이고, 이 중 사용 가능한 block을 hole이라고 한다. 이때 할당하는데 여러 방법이 있다.
- First fit: 첫 번째 hole을 할당
- Best fit: hole 중에서 가장 작은 곳을 할당
- Worst fit: 가장 큰 곳을 할당
Fragmentation
- external fragmentation
각 block의 크기를 순서대로 30k, 60k, 20k, 40k, 60k라고 해보자. hole은 60k 두 곳뿐이다. 그런데 만약 70k 프로세스가 들어와야 한다면? 실제 메모리 공간은 120k가 비어있지만 어디에도 70k가 들어갈 수는 없다
해결하는 방법으로는 압축(Compaction)이 있다.
이 방법은 memory의 모든 내용을 한 군데로 몰고, 모든 free space들을 다른 한 군데로 몰아서 큰 block을 만드는 방법이다.
- internal fragmentation
실제 프로세스 공간보다 큰 메모리를 할당하게 되는 경우를 말한다. 일반적으로 메모리가 시스템 효율을 위해 고정 크기의 정수 배로 할당되기 때문에 생기는 현상이다.
Paging
paging에서는 physical memory의 각 block을 frame이라고 하고, logical memory의 각 block을 page라고 부른다. frame을 작게 나눌수록 fragment가 적게 생기며, 실제로 external fragmentation은 거의 생기지 않는다. logical address를 physical address로 변환하는 page table이 필요하다.
Basic Method
CPU에 의해 만들어진 주소는 page number(p)와 page offset(d) 두 부분으로 나뉜다. page number는 page table의 index로써 page table에 접근할 때 사용된다. page offset은 physical address를 얻을 때 쓰이며, page table의 base address에 page offset을 더하면 physical address를 구할 수 있다.
운영체제는 memory를 관리하기 때문에, 물리 Memory에 Allocation Details에 대해 파악하고 있어야 한다.
어느 프레임이 사용 가능 한지, 총 프레임이 몇 개인지에 대한 정보가 프레임 테이블(Frame Table)에 존재한다.
운영체제는 모든 프로세스들의 주소들을 실제 주소로 mapping 할 수 있어야 한다.
Hardware Support
page table은 메모리에 저장되어 있다.
PTBR(Page-Table Base Register)가 page table을 가리키고, PTLR(Page-Table Length Register)가 page table의 크기를 가지고 있다.
따라서 매번 데이터에 접근할 때마다 한 번은 데이터에, 한 번은 page table에 접근해야 한다.
TLB(Translation Look-aside Buffers)로 불리는 특수한 소형 hardware cache가 사용된다.
TLB는 key-value pair로 데이터를 관리하는 acssociative memory이며, CPU는 page table보다 TLB을 우선적으로 참조한다.
Protection
메모리 할당이 contiguous한 경우 limit만 비교해도 메모리를 보호할 수 있었다. 하지만 paging은 contiguous하지 않기 때문에 다른 방법을 쓴다. page table의 각 항목에는 valid-invalid bit가 붙어있어 그 값이 valid라면 해당 페이지에 접근이 가능하고, invalid라면 해당 페이지가 logical address space에 속하지 않아 접근할 수 없다는 것을 의미한다.
Shared Pages
paging의 또 다른 장점은 코드를 쉽게 공유할 수 있다는 것이다. 만약 코드가 reentrant code(또는 pure code)라면 공유가 가능하다. reentrant code는 runtime 동안 절대로 변하지 않는 코드이며, 따라서 여러 프로세스들이 동시에 같은 코드를 수행할 수 있다.
Structure of the Page Table
paging을 직접 적용하면 page table의 크기가 커진다. 페이지 테이블을 효율적으로 구성하는 몇 가지 방법이 있다.
Hierachial Paging
hierachical paging은 logical address space를 여러 단계의 page table로 분할하는 기법이다. two-level paging scheme이 예시인데, page table과 메모리 사이에 page table을 하나 더 둠으로써 모든 페이지를 로드해야 하는 부담을 줄일 수 있다.
Hashed Page Tables
말그대로 hash table을 이용해 page table을 관리하는 기법. address space가 32비트보다 커지면 hierachial paging이 비효율적이기 때문에 주로 이 방법을 쓴다. virtual page number를 hashing해 page table을 참조하는 데 사용한다. hashed page table에서는 linked list를 따라가며 page number를 비교하고, 일치하면 그에 대응하는 page frame number를 얻는다. hash table은 검색에 O(1) 시간이 걸려 매우 빠르지만 구현이 어렵다.
Inverted Page Tables
지금까지 page table은 각 page마다 하나의 항목을 가졌다. inverted page table은 메모리의 frame마다 한 항목씩 할당하는데, 이렇게 하면 physical frame에 대응하는 항목만 저장하면 되기 때문에 메모리를 훨씬 적게 사용하게 된다. 다만 탐색 시간이 오래 걸리기 때문에 대부분의 메모리는 inverted page table과 hased page table을 결합하는 방식으로 구현되어있다.
Segmentation
segmentation은 하나의 프로세스를 여러 개로 나누는 것을 말한다. segment는 main, function, method, object 등의 논리적 단위로, 인간의 관점으로 프로세스를 나눈 것이다.
Segment table의 각 항목은 Segment의 base와 limit를 가지고 있다.
Segment base는 Segment의 시작 주소를 나타내며, Segment limit은 Segment의 길이를 명시한다.
