* 사실 종강하고 복습 겸 배운 내용을 정리하고자 했는데,
공부에 집중이 안되어서 글을 쓰면서 생각을 정리하자는 마음으로 글을 씁니다.
수업 교재를 참고하였으며 오류에 대한 지적은 언제나 환영입니다.
Background 지식들
Program Execution
프로그램이 실행되기 위해서는 메모리에 옮겨져야 한다.
그리고 사용자 프로그램은 다음과 같은 과정을 거쳐 실행된다.
1. Instruction fetch from memory
메모리로부터 명령어들을 가져온다.
2. Instruction decode
명령어들을 해석하여 어떻게 수행할지 결정한다.
3. Operand fetch
피연산자를 가져온다.
4. Instruction execute
명령어를 실행한다.
5. 실행 결과를 메모리에 저장한다.
Memory Access Speed
프로세스에 있는 메인 메모리와 레지스터는 유일하게 CPU에 직접 접근이 가능한 저장 장치이다.
레지스터는 CPU clock의 1cycle, 혹은 그 이하의 속도로 접근한다. 반면 메인 메모리는 더 많은 cycle을 요구한다.
이러한 경우, 프로세스는 명렁을 완료하는 데에 필요한 데이터가 없기 때문에 일반적으로 stall(정지)을 해야 한다.
Cache는 메인 메모리와 CPU register 사이에 존재한다.
Memory Protection Hardware
올바른 작동을 보장하기 위해서는 메모리 보호가 요구된다.
base와 limit 레지스터는 논리 주소 공간을 정의한다.
base register은 시작 주소를, limit rester는 프로세스의 크기를 가리킨다.
Address Binding
보통 프로세스를 생성하면 프로세스를 위한 독자적인 메모리 공간이 할당되는데, 이것이 logical address이다. 물리적 주소와 별도의 공간에 생성됨으로써 효율적인 메모리 관리를 돕는다.
Logical address - CPU에 의해 생성되며 virtual addresss라고도 불린다.
Physical address - 실제 memory unit 주소이다.
Logical address에는 Instruction과 data가 저장이 된다. 이 논리적 주소를 실제 물리적 주소에 연결시켜주는 과정을 Address Binding이라고 한다.
물리적 메모리 주소가 결정되는 시기에 따라 다음 3가지로 나눌 수 있다.
Compile time: 컴파일을 할 때 물리적 메모리 주소가 결정된다. 즉, 프로그램 내부에서 사용하는 주소와 물리적 주소가 같다.
만약 시작 주소가 변하면 다시 컴파일해야 한다. 비효율적인 방법으로 많이 쓰지는 않는다고 한다.
Load time: 컴파일할 때 메모리 위치를 알 수 없는 경우 relocatable code로 생성해야 한다. relocatable code는 absolute code와 반대 개념으로, 컴파일러가 재배치 가능한 코드를 의미한다.
compile binding과 다르게 multiprogramming이 가능하다.
Execution time: 바인딩이 런타임 이후에도 진행될 수 있다. process가 실행 중에 한 memory segment에서 다른 segment로 이동할 경우, 이 방식을 취해야 한다. 대부분의 운영 체제에서 이 방식을 사용한다. 하드웨어 지원이 필요하다. 논리적주소와 물리적 주조가 다르다.
=> MMU (memory management unit)
runtime때 virtual address에서 physical address로 매핑해주는 하드웨어 장치를 의미한다.
user process에서 생성되는 각각의 register + relocation register (재배치 레지스터) => 물리적 메모리주소
MMU를 사용하여 주소를 재배치하는 것을 Dynamic relocation(동적 재배치)라고 한다.
컴파일 과정
compile을 통해 목적파일 생성 => link time에서 목적파일을 하나의 목적파일로 묶어 exe 파일 생성 => 로더가 읽고 프로세스 생성
Static Library vs Dynamic Link Library
어느 시점에 메인 프로그램에 연결되느냐에 따라 다음 두가지로 나뉜다.
Static library
간단히 말하자면 compile time에 링커에 의해 연결되는 라이브러리이다.
Dynamic link libirary
runtime에 링커에 의해 연결되는 라이브러리이다.
매번 전부 복사해야하는 정적 라이브러리와 달리 최소한의 정보만 링크될 수 있기에 메모리 공간을 적게 차지한다는 장점이 있다.
dynamic loading이나 dynamic linking에 의해 invoked될 수 있다.
Dynamic Loading vs Dynamic Linking vs Swapping
모두 execution(실행)하는동안 API를 통해 진행된다. 위에서 얘기한 binding은 dlopen()을 호출하거나 symbol이 참조될 때 제어할 수 있다.
Dynamic loading
우선 loading은 프로그램에서 메모리로 데이터를 옮기는 것(적재하는 것)을 의미한다.
Dynamic loading은 메모리 낭비를 방지하기 위해 실행때 필요한 루틴, 데이터만 loading하는 것이다.
<-> 메모리에 모두 loading하는 것을 Static loading이라고 한다.
Dynamic linking
여러 프로그램이 동시에 같은 라이브러리를 참조할 때 각각 라이브러리를 메모리에 올리면 메모리 낭비가 있을 수 있다.
이러한 중복을 방지하기 위해 필요한 경우에만 라이브러리만 불러와서 메모리에 적재하는 방식을 Dynamic linking이라고 한다.
이것이 이루어지기 위해서, 실행 프로개름은 small piece of code(stub)를 포함하는데, 이것은 적절한 라이브러리 루틴을 찾는데 사용된다.
정적 링킹에 비해 메모리 측면에서 효율적이지만, 실행에 있어 약간의 오버헤드가 발생할 수 있다.
(OS가 루틴이 프로세스의 메모리 주소에 있는지 계속해서 확인해주어야하므로)
Swapping
위에서 프로세스는 실행되려면 메모리에 옮겨져야 한다고 말한 바 있다. 그런데 이미 메모리에 프로세스로 꽉 차 있을 경우나 당장 필요하지 않은 프로세스가 메모리를 낭비하는 상황일 수 있다. swapping이란 위와 같은 경우에서 사용하며, 기존에 메모리에 있던 data를 별도의 공간에 옮겨놓았다가 다시 메모리에 가져오는 것을 의미한다. 이 별도의 공간을 backing store이라고 부른다.
roll out, roll in: 우선순위가 있는 swap in, swap out이다. 낮은 우선순위는 swap out되고, 높은 우선순위 프로세스는 load되고 실행된다. 이러한 swap 과정에서 가장 많은 시간을 차지하는 것이 transfer time(전송 시간)이다. 그리고 transfer time은 메모리 양과 비례한다.
Memory Allocation
메모리에 프로세스를 할당하는 방식은 다음 두 가지 방식이 있을 수 있다.
Contiguous Allocation (연속적 할당) : 메모리에 프로세스를 연속적으로 할당하는 방식이다.
1.Two Partition Allocation: 보통 메모리 할당은 이분할로 진행되는데 OS는 인터렙트 벡터와 함께 낮은 메모리 주소에 load되는 반면 user process는 높은 메모리 주소에 load된다.
2. Multiple-partition allocaiton (fixed size) : 메모리를 고정 크기를 가진 partition으로 분할한다. 각 partion은 하나의 프로세스를 가질 것이다. degree of multiprogramming이 partion의 개수에 달려있다. IBM OS/360에서 사용되었으나 지금은 사용되지 않는다.
3. Multiple-partition allocation (variable size): 프로세스 크기만큼의 가변적인 크기로 분할한다. 그런데 그중 하나의 프로세스가 끝나면 Hole이 발생한다. Hole은 위 아래와 같이 이용가능한 메모리의 block을 의미한다. process가 도착하면 process가 할당될 수 있을만한 크기의 Hole을 찾아 할당한다. 보통 운영체제는 allocated partions와 free partitions(free)에 대한 정보를 계속해서 갖고 있다.
free holes list로부터 n만큼의 사이즈 요청이 들어왔을 때 어떻게 만족할 지는 다음 3가지의 방법이 있다.
1. First fit: 요청을 만족시키는 첫번째 hole 할당
2. Best fit: 요청을 만족시키는 hole들 중 가장 작은 hole 할당
-> 남는 hole의 크기가 최소화된다는 장점이 있으나 크기와 관계 없이 항상 전체 list를 살펴봐야 한다는 단점이 있다.
3. Worst fit: 가장 큰 hole을 할당한다. 이것 또한 전체 list를 봐야하며 남은 hole의 크기가 최대가 된다.
당연히 1번 2번 방법이 3번 방법보다는 효율적이다.
50 percent rule: N개의 할당된 block이 있다고 가정할 때, 약 0.5N block은 fragmentation에 의한 손실이 발생한다.
Fragmentation
그런데 위와 같은 할당이 이루어지면 Fragmentation 문제가 발생한다. Fragmentation이 발생하면 메모리 측면에서 비효율적이다.
External Fragmentation (외부 파편화) : 전체 메모리는 충분히 요청을 수행할 만큼의 공간이 남아있지만, 연속적이지 않아 할당할 수가 없는 경우를 말한다.
compaction 과정을 통해 어느정도 외부 파편화 문제를 해결할 수 있다. compaction은 모든 free memory들을 하나의 큰 block으로 만드는 방법이다. 이것은 dynamic relocation일때만 가능하며 execution time에 이루어진다.
Internal Fragmentation (내부 파편화) : 할당된 메모리 영역이 프로세스 크기보다 큰 경우, 즉 남은 hole이 발생한 경우 프로세스에서 사용할 수는 없으나 할당된 메모리 공간이 존재하게 된다.
Non-contiguous Allocation(비연속적 할당): 메모리에 프로세스를 비연속적으로 할당하는 방식이다.
Paging
external fragmentation을 해결하기 위한 방법이다. 프로세스를 고정된 크기로 비연속적으로 할당하는 방식이다.
pages: Logical memory를 고정된 크기의 block으로 나눴을 때 단위이다.
frames: physical memory를 page와 같은 크기의 block으로 나눴을 때 단위이다.
또한 logical address에서 physical address로 옮기기 위해 page table을 설정한다.
보통 page 크기는 하드웨어의 의해 결정된다. 크기는 2의 제곱이며, 보통 4KB(2^12)에서 1GB(2^30) 사이이다.
*1KB = 2^10, 1GB = 2^30
external fragmentation은 방지하지만 internal fragmentation은 발생할 수 있다.
Address Translation Scheme
CPU로 생성된 (논리적) 주소는 다음과 같이 나뉜다.
ㅍpage number(p): page table에서 page의 인덱스로 사용된다. 각 페이지 별로 physical memory의 base address(시작 주소)를 가지고 있다. logical address에서 page size를 나눈 몫
page offset(d): base address에 이 값을 더하면 physical address가 된다. logical address에서 page size를 나눈 나머지
logic address이 m, page offset은 n이라 가정할 때 page size는 2^n이고 page table은 2^(m-n)이다.
주소 공간의 크기에서 page size를 나누면 page 개수가 나올 것이다. page 개수 = page tabel 개수이므로 page number를 page table index라고 볼 수 있을 것.
page는 보통 4KB 혹은 8KB인데 몇몇 더 큰 page size도 있다.
ex. Linux에서 디폴트 page 크기는 4KB였으나 huge pages라고 불리는 큰 page size도 있었다.
참고사이트: https://charles098.tistory.com/106
전체적인 과정: logical address에서 p, d를 구한 다음 p를 통해 f로 변환하고, (f * page size)+d로 물리적 주소를 구한다.
계산 방법은 예제를 찾아서 더 공부하자
Memory Loading and Free Frames
프로세스가 실행되는 system에 도착할 때, 페이지 단위의 크기를 확인한다. 일반적으로 n pages만큼의 프로그램을 실행하기 이ㅜ해서는 m free frame을 찾고나서 program을 load해야 한다. (여기서 n과 m은 같아야 한다.)
모든 free frame을 추적해야 한다. free frame에 load된 이후에는 frame number는 page table에 입력되어야 한다.
가상 메모리를 사용하면, n은 m과 같거나 더 클 수 있다. (chapter 10에서 계속!)
Page Table Implementation
page table는 프로세스마다 존재하는 자료구조이고 main memory에 포함되어있다.
PTBR (page table base register) : page table을 가리킨다.
PTLR (page table limit register) : page table의 크기를 가리킨다.
이 register들은 각 프로세스의 PCB에 저장되고 앞뒤로 context switching이 이루어진다.
CPU가 physical memory에 접근하기 위해서는 2번의 memory access가 이루어져아 한다.
한번는 page table이고 다른 한번는 실제 data/instruction이다. 두번 접근하기 때문에 속도가 느려질 수 있다는 문제가 있다.
The two memory access problem: associative memory/TLBs(translation look aside buffers) 라고 불리는 special fast-lookup hardware cache 로 속도를 높일 수 있다. TLBs는 보통 크기가 작고, key(page 번호)와 value(frame 번호)를 가지고 있다. 몇몇 entries는 fast access. TLB entries는 wired down.
Associative Memory/TLB Structure
: page numbr와 frame number 사이에 병렬 탐색 (parallel search)을 하며 address translation을 수행한다. TLB는 일종의 cache와 같은 것으로, 자주 쓰이는 page들만 담겨있다.
원하는 page 번호가 associative regjster에 있는 경우 -> TLB hit : frame num을 바로 돌려준다.
없는 경우 -> TLB miss : 직접 memory에 있는 page table로부터 frame을 얻는다.
병렬 탐색하므로 메인 메모리에 1번만 접근해도 된다.
Effectibe Access Time
Hit ratio: page number가 associatibe register에서 발견되는 비율이며 associative register의 개수와도 관련이 있다.
a(알파)라고 한다. 이 값이 높을 수록 메모리 접근 시간이 향상될 것이다.
EAT 계산 공식은 다음과 같다.
Memory Protection
각 frame별로 protection bit를 부여함으로써 메모리를 보호할 수 있다.
valid: associated page가 logical address space 안에 있음을 의미한다.
invalid: 없음을 의미한다.
이 방법 외에 page table length register(PTLR)을 정의하여 보호할 수도 있다.
Shared Pages
reentrant code(재진입 가능 코드) : 동기화 문제로 read만 가능하다. 프로세스끼리 공유하는 경우 재진입이 가능한 코드여야 한다.
Private code and data: 각 프로세스는 독립된 code와 data를 갖는다.
각각 존재하는 메모리들 (ex. 12개) → 공유 frame을 사용하면 더 효율적이다. (6개)
Structure of the Page Tablepage table의 사이즈가 너무 클 경우 줄이기 위한 방법이다. 구조는 다음과 같이 3개로 나뉜다. 1. Hierachical Paging 계층 구조를 가지는 page table. logic address space를 multiple page tables로 나눈다. page table 자체를 page화 시킨다. a) 2-level page table logical addrss가 32bit이고 page size가 4KB일 경우, page number은 20bit, page offset은 12bit일 것이다.
2-level page table은 여기서 page number을 한번 더 분리해서, 각각 10bit를 가지도록 한다.
여기서 p1은 outer page table의 인덱스이고, p2는 해당 inner page, 즉 page table내부의 displacement를 나타낸다.
forward-mapping page table : 내가 사용하는 부분만 mapping하고 사용하지 않는 부분은 비워두는 방식
b) For a System with Larger Address Space 64비트 주소 공간에서는 two level paging으로도 부족할 수 있다. 그러할 경우 three level, four level도 쪼갤 수 있으나 늘릴 수록 메모리 접근을 위한 수행량도 많아지기에 좋은 방법은 아니다. 2. Hashed Page Table
보통 주소공간이 32bit보다 클 때 많이 쓴다. 해시 페이지 테이블의 각 항목은 연결리스트로 이루어져있다. 해시 페이지 테이블에는 virtual page number인 p가 포함되어 있다. 각 해시 원소는 virtual page number과 매핑될 page frame number, 다음 포인터를 가지고 있다.
다음과 같은 방식으로 이루어진다.
1. page number을 hashing 한다.
2. 해시형 페이지 테이블을 따라가며 첫번째 원소와 가상 페이지 번호를 비교한다.
3. 일치하면 그에 대응하는 프레임 번호를 얻어서 물리적 주소를 얻는다.
4. 일치하지 않으면 다음 연결리스트로 이동한다.
변형버전: clustered page table 각 entry는 multiple frames를 가리킨다. 각 hash table 항목에는 작은 테이블에 대한 포인터가 있으며 논리 주소는 작은 테이블의 해시 입력과 offset을 수정하도록 할 수 있다. (?) 3. Inverted Page Table
프로세스별로 Page table이 따로 있는 것이 아니라, 요소에 pid를 추가하여 하나의 Page table만을 이용한다. 각 entry(항목)들은 memory의 한 frame을 가리킨다. 페이지 테이블을 줄일 수 있지만, pid도 검사해야 해서 search time이 증가한다. 이 문제를 해결하기 위해 hash table을 이용할 수도 있다.
Segmentation
paging기법이 고정 분할 방식을 이용한 메모리 관리 기법이라면, segmentation은 가변 분할 방식을 이용한 메모리 관리 기법이다. 따라서 segment마다 크기가 모두 다르다. program은 segment의 집합인데, 각 segment는 main program, procedure, local variable, global variable, stack, symbol table, array..등이 들어 있는 하나의 프로세스이다. page table과 마찬가지로 segment table을 이용하는데, 여기에는 base register와 legth가 담겨 있다. (paging은 고정 분할 방식이라 legth를 따로 담아둘 필요가 없었으나, segmentation은 모두 크기가 다르므로 길이를 저장해주어야 한다.)
Segmentation Architecture
logical address를 <segment-number, offset>dml 튜플 형식으로 표기한다.
Segment table은 base register와 limit으로 구성되는데, length는 physical address의 시작 주소를 의미하고 limit은 segment의 길이를 의미한다.
Segment-table base register (STBR) : segment table의 메모리 주소를 가리킨다.
Segment-table length register (STLR) : 프로그램에서 사용하는 setment의 수를 나타낸다. 만약 세그먼트 번호 s < STLR이면 legal하다.
특징
1. Sharing
같은 segment 주소값을 가리킴으로써 공유할 수 있다.
2. Protection
Paging과 마찬가지로 segment table의 각 entry마다 valid/invalid bit가 있다.
read/write/execute 권한을 부여할 수 있다.
=> 공유 및 보호가 간편하다.
3. Allocation
다양한 길이를 할당하므로 dynamic storage allocation problem이 발생할 수 있다. 즉 외부 단편화가 발생한다.
4. Relocation (?)
dynamic 혹은 segment table를 통해 이루어진다.
segmentation은 외부 단편화가, paging은 내부 단편화가 발생한다는 단점이 있다. 이를 해소하기 위해 segmentation과 paging을 혼용하는 방법도 있다. 대부분의 운영체제에서는 이 방식을 사용하고 있다고 한다. 사용자 입장에서는 segmentation 기법을 사용하고 메모리 관리자 입장에서는 paging 기법을 사용하는 것이다. 그 과정은 밑 이미지와 같다.
