Logical address(= virtual memory)
- 프로세스마다 독립적으로 가지는 주소 공간
- 각 프로세스마다 0번지부터 시작
- CPU가 보는 주소는 logical address임 => 실행파일 안의 코드는 동일하기 때문에 CPU는 logical address를 봐야할 필요가 있음
Physical address
- 메모리에 실제 올라가는 위치
address binding(주소 변환)
- 가상 메모리의 논리적 주소를 메인 메모리의 물리적 주소로 변환하는 것
- 주소 변환은 OS가 관여하는게 아니라 HW적으로 이루어짐
- Symbolic Address -> Logical Address -(이 시점이 언제인가)-> Physical Address
*Symbolic Adress: 프로그래머가 메모리의 번지 수를 언급하는게 아니라 숫자가 아닌, 이름같은 symbol을 사용해서 메모리에 접근하는데 이를 Symbolic Address라고 함
주소 바인딩의 종류
- Logical Address -> Physical Address가 언제 이뤄지냐에 따라 크게 3가지로 나눠질 수 있음
- Complie time binding
- 물리적 메모리 주소가 컴파일 시점에 알려짐
- 시작 위치 변경시 재컴파일
- 컴파일러는 절대 코드(absolute address) 생성 => 한번 올라간 메모리 위치는 바꿀 수 없음
- Load time binding
- Loader의 책임하에 물리적 메모리 주소를 부여함
- 컴파일러가 재배치 가능 코드(relocateable code)를 생성한 경우에 가능 => 비어있는 주소면 어디든지 올릴 수 있음
- Execution time binding (= Run time binding)
- compile time binding, load time binding 은 이미 메모리에 올라간 주소는 변경할 수 없지만 execution time binding 은 실행중에도 바꿀 수 있음
- 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
- CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table)
- H/W 적인 지원이 필요함 (e.g base and limit registers, MMU)
MMU(Memory-Management Unit)
- logical address를 physical address로 매핑해주는 H/W device
- MMU는 cpu로부터 logical address를 받으면 메모리의 TTB(Translation Table Base address) 를 통해 Page table에 접근하게 된다.
- base register(= relocation register)와 limit register(프로그램의 크기)를 이용해서 주소를 변환한다
- base register: 물리적 주소의 최솟값
- limit register: 논리적 주소의 범위
- e.g) CPU로부터 p1의 346번지 logical address를 요청하면, MMU는 14000(base)+346(logical)=14346(physical)로 매핑해준다
- limit를 넘어가는 요청이 들어오면
trap이 걸리고, 프로그램의 CPU가 OS로 넘어가서 이를 검사함
MMU scheme- 사용자 프로세스가 CPU에서 수행되면서 생성해내는 모든 주소값에 대해서 base register(= relocation register)의 값을 더함
user program- logical address만을 다룬다
- 실제 physical address를 볼 수 없으며 알 필요도 없다
주소 변환의 용어
주소 변환의 용어에는 크게 4가지가 있다.
- Dynamic Loading: 프로세스 전체를 메모리에 미리 다 올리는게 아니라 해당 루틴이 불려질 때마다 메모리에 load하는 것
- memory utilization이 향상됨
- 가끔식 사용되는 많은 양의 코드인 경우에 유용햠 (e.g 오류 처리 루틴)
- OS의 특별한 지원 없이 프로그램 자체에서 구현이 가능, OS가 라이브러리를 지원함(= 프로그래머가 직접 사용하는 방식)
- Dynamic Linking: linking을 실행시간까지 미루는 기법
linking: 컴파일된 소스파일들을 하나로 묶어서 실행파일로 만드는 것- Static linking
- 라이브러리가 프로그램 실행 파일 코드에 포함됨
- 실행 파일 크기가 커짐/ 동일한 라이브러리를 각각의 프로세스가 자신의 메모리 주소 공간에 올리기 때문에 메모리가 낭비됨
- Dynamic linking
- 라이브러리가 실행시에 연결됨
- 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 일종의 포인터인 stub이라는 작은 코드를 둠 (= 실행 파일 코드에 포함되지 않음)
- 라이브러리가 이미 메모리에 있으면 그 루틴 주소로 가고 없으면 디스크에서 읽어옴
- OS의 도움이 필요
- Overlays: 메모리에 프로세스의 부분 중 실제로 필요한 부분만을 올리는 것
- 프로세스 크기가 메모리보다 클 때 유용함
- OS 지원없이 사용자에 의해서 구현
- OS가 라이브러리를 지원하지 않는다는 점에서 Dynamic loading과 차이가 있음
- 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현함 (=> 'Manual Overlay' 프로그래밍이 매우 복잡함)
- Swapping: 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
backing store(=swap area): 디스크를 말함, 많은 사용자가 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간- Swap in/Swap out: 일반적으로 중기 스케줄러(swapper)에 의해서 swap out 시킬 프로세스 선정
- compile time 혹은 load time binding 에서는 원래 메모리 위치로 swap in 해야 함
- execution time binding 에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
- swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임 => swapping의 경우 file I/O와 다르게 양이 굉장히 방대함. 양이 워낙 많기 때문에 전송에 들어가는 시간이 상당히 많음.
물리적 메모리의 할당
- 메모리는 일반적으로 두 영역으로 나뉘어서 사용됨
- OS 상주 영역
- 사용자 프로세스 영역
- 사용자 프로세스 영역의 할당 방법은 크게 두 가지가 있음
- contiguous allocation(연속적 할당)
- 각각의 프로세스가 메모리의 연속적인 공간에 적재됨
- Fixed partition allocation 과 Vairable partition allocation이 있음
- Noncontiguous allocation(불연속적 할당)
- 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라감
- paging, segmentation, paged segmentaion 이 있음
Contiguous Allocation (연속적 할당)
프로세스를 메모리의 주소 공간에 연속적으로 할당하는 방식에는 크게 고정 분할 방식과 가변 분할 방식이 있음
고정 분할 방식
- 외부 조각(= 외부 단편화): partition이 작아서 프로그램이 올라가지 못해 생기는 메모리 낭비 공간
- 내부 조각(= 내부 단편화): partition이 커서 프로그램이 올라가도 사용되지 않아 생기는 메모리 낭비 공간
- 물리적 메모리를 몇 개의 영구적 분할(partition)으로 나눔
- partition의 크기가 모두 동일한 방식과 서로 다른 방식이 존재함
- partition당 하나의 프로그램 적재
- 융통성 없음
- 동시에 메모리에 load되는 프로그램 수가 고정됨
- 최대 수행 가능 프로그램 크기가 제한됨
- internal fragmentation 발생 (external fragmentation도 발생)
가변 분할 방식
- 연속적으로 할당하다 보니 프로세스의 순서에 따라서 낭비되는 공간이 발생하게 됨
- 프로그램 크기를 고려해서 할당
- 분할의 크기, 개수가 동적으로 변함
- 기술적 관리 기법이 필요함
- external fragmentation 발생
- 가변 분할 방식에는 가장 적절한 hole(= 가용 메모리 공간) 을 찾는 문제가 발생함
- First-fit: 최초로 찾아지는 hole에 할당
- Best-fit: 프로세스의 크기와 차이가 가장 적은 hole에 할당
- Worst-fit: 가장 큰 hole에 할당
compaction으로 external fragmentation 문제를 해결할 수도 있음- 사용중인 메모리 영역을 한군데로 몰아 넣고 hole들을 다른 한 곳으로 몰아서 매우 큰 block을 만드는 방법
- 매우 비용이 많이 들고 프로세스의 주소가 실행 시간에 동적으로 재배치(runtime binding)가 가능한 경우에만 수행이 될 수 있음
Noncontiguous Allocation(불연속적 할당)
하나의 프로세스를 나누어서 물리 메모리에
물리적 메모리를 불연속적으로 할당하는 방식에는 크게 다음과 같은 세가지 방법이 있음
- Paging
- Segmentation
- Paged Segmentation
1. Paging
- Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
- virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
- 일부는 backing store, 일부는 physical memory에 저장
Basic Method
- physical memory를 동일한 크기의
frame으로 나눔 - virtual memory를 동일한 크기의
page로 나눔(frame과 같은 크기) - 모든 가용 frame들을 관리함
- page table을 사용해 logical address를 physical address로 변환함
- external fragmentation 발생 안함
- internal fragmentation 발생 가능 => virtual memory를 page로 나누다 보면 자투리 공간이 생길 수 있음
Page Table
- Page table은 main memory에 상주함
- 페이지를 보통 4KB로 자르면 엔트리가 100만개정도가 필요하게 됨. 거기다 프로세스마다 하나씩 필요하기 때문에 많은 용량이 필요함. => cache memory 나 register에 들어가기에는 용량이 너무 크고, 당연히 disk에도 넣을 수는 없음
- Page table이 main memory에 존재하기 때문에 page table을 가리키는 register가 필요함
- page-table base register(PTBR): page table의 위치를 가리킴
- page-table limit register(PTLR): page table의 크기를 보관함
- 모든 메모리 접근 연산에는 2번의 memory access가 필요함
- page table에 접근하는데 한번
- data/instruction 접근하는데 한번
- memory access가 두번이 필요하기 때문에 성능을 향상시키기 위해서
associative register혹은TLB라고 불리는 고속의 lookup hardware cache를 사용함TLB: main memory와 cpu 사이에서 주소를 변환해주는 캐시메모리- 모든 엔트리를 매핑시키는게 아니라 빈번히 참조되는 몇 개의 엔트리만 갖고 있음
Associative Register(TLB)
- parallel search가 가능함 -> TLB에는 page table중 일부만 존재하기 때문
- TLB도 프로세스마다 하나씩 존재해야 함
- 주소 변환
- page table 중 일부가 associative register에 보관되어 있음
- 만약 해당 page #가 associative register에 있으면 곧바로 frame #를 얻음
- 그렇지 않으면, main memory에 있는 page table로 부터 frame #를 얻음
- TLB는 context switch 시 flush 됨 (remove old entries)
Two-Level Page Table
- inner page table 의 하나의 page table은 memory의 page와 크기가 동일함
- 2단계 page table은 시간은 더 걸리지만, 공간은 더 줄일 수 있음
- 32bit address를 사용하는 경우 logical memory는 최대 2^32B=4GB가 되는데, 현재 컴퓨터는 64bit까지 사용하고 있음.
- page size가 4KB라면 1M개 이상의 page table entry가 필요함
- 각 page entry가 4B면 프로세스당 4M의 page table이 필요함
- 그러나 대부분 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하기 때문에 4G의 주소 공간이 낭비되는 상황이 발생함
-> page table 자체를 page로 구성함
-> 사용되지 않는 주소 공간에 대해서 outer page table의 엔트리 값은 NULL(= 대응되는 inner page table이 없음) => logical memory 만큼 outer page table이 만들어지지만, 사용되지 않는 주소 공간에 대해서는 inner page table이 만들어지지 않음 => 공간을 줄일 수 있는 결정적인 이유
Two-Level Paging Example
- local address(on 32bit machine with 4K page size)의 구성
- 20 bit의 page number
- 12 bit의 page offset
- page size = 4KB = 2^12bit 이고, memory에 있는 page의 2^12개의 주소를 구분하기 위해서는 12bit가 필요함
- page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉨(각 page table entry가 4B)
- 10 bit의 page number
- 10 bit의 page offset
- inner page table 에 있는 하나의 page의 크기는 memory의 page와 동일하기 때문에 4K 이고, inner page table에 있는 page 의 하나의 entry의 크기는 4B이므로 4KB/4B = 1K = 2^10B 를 표현하기 위해서는 10bit가 필요함
Multilevel Paging
- Address space가 더 커지면 다단계 페이지 테이블이 필요함
- 각 단계의 페이지 테이블이 메모리에 존재하기 때문에 logical address의 physical address 변환에 더 많은 메모리 접근이 필요하다
- TLB를 통해 메모리 접근 시간을 줄일 수 있음
- e.g) 4단계 페이지 테이블을 사용하는 경우
- 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns, TLB hit ratio가 98%인 경우
- effective memory access time = 0.98 x 120 + 0.02 * 520(= 100x4 + 120) = 128ns
=> 결과적으로 주소 변환을 위해서 28ns(= 128ns - 100ns)만 소요됨
Inverted Page Table
- page table은 프로세스마다 page table이 존재해야 하면서 주소 변환을 위한 page table 자체에만 공간을 너무 많이 할당해야 한다는 단점이 있었고 이를 보완하기 위한 방법 중 하나임
- 사실 이 방법은 logical address 를 보고 physical address 로 변환하기 위한 것이 아니라, physical address 를 보고 logical address 로 변환하기 위한 page table임
- logical address를 physical address에 매핑하는 방법
- inverted page table의 모든 entry 를 확인함
- [pid, p]와 일치하는 entry를 찾으면 page frame의 base인 f번째에 존재한다는 것을 알게 되고, 이를 physical address로 매핑할 수 있음
- page table이 프로세스마다 하나씩 존재하는게 아니라 시스템 안에 page table 이 딱 하나만 존재함
- page table 의 entry가 memory의 page frame 갯수만큼 존재함
=> page table을 하나만 사용하기 때문에 공간적인 장점은 있지만, overhead의 단점과 p가 여러개 있을 수도 있어서 pid를 갖고 있어야 한다는 단점이 있음
=>TLB를 사용해 병렬적으로 entry를 탐색시키는 방법으로 시간적 단점을 줄일 수 있음
- page table 의 entry가 memory의 page frame 갯수만큼 존재함
Shared Page
- 공유할 수 있는 code에 대해서는 같은 memory frame을 사용함으로써 page table의 공간을 줄인다
- read-only로 하여 프로세스 간 하나의 code만 메모리에 올림(e.g text editors, compilers, window systems)
- Shared code(= Re-entrant code)는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
- private code and data는 각 프로세스마다 독자적으로 메모리에 올림
2. Segmentation
- 프로그램을 의미 단위인 여러 개의 segment로 구성함
- 작게는 프로그램을 구성하는 함수 하나하나를 segment로 정의
- 크게는 프로그램 전체를 하나의 segment로 정의
- 일반적으로는 code,data,stack 부분이 하나씩의 segment로 정의됨
- logical address를 <segment-number, offset> 으로 구성함
Segment table사용- 엔트리마다
base와limit를 갖고 있음 base: segment의 physical memory 시작 주소limit: segment의 길이 =>Paging과 다른 부분임, <s,d> 에서 d <= limit 여야 함
- 엔트리마다
- Segment-table base register(STBR)
- 물리적 메모리에서의 segment table의 위치
- Segment-table length register(STLR)
- 프로그램이 사용하는 segment의 수 ( <s,d> 에서 s < STLR.length 여야 함)
Segmentation Architecture
Protection
- 각 세그먼트 별로 protection bit가 있음 (read/write/read-only 권한 bit)
- Valid bit = 0 => illegal segment
Sharing
- segment는 의미 단위이기 때문에 Protection 과 Sharing에 있어서 paging보다 더 효과적임
Allocation
- first fit/ best fit
- external fragmentation 발생 => segment의 길이가 동일하지 않기 때문에 가변 분할 방식에서와 동일한 문제점들이 발생함
Example of Segmentation
3. Paged Sementation
- 메모리에 올릴 때 segment를 page로 쪼개서 메모리에 올리는 방식 => external fragmentation 문제 해결
- 즉 segment 하나 당 하나의 page table을 가지게 됨
- sharing, protection은 page로 쪼개기 전 segment 단위로 이루어짐
- pure segmentation 과의 차이점
- segment-table entry가 segment의 base address를 가지고 있는 것이 아니라, segment를 구성하는 page table의 base address를 갖고 있음
- logical address -> segment table -> page table -> physical address
- <s, d> -> (segment table) -> <p, d'> -> (page table) -> <f, d'> -> memory
Memory Protection
Pabe table의 각 entry마다 아래의 bit를 둔다.
Protection bit
- page에 대한 접근 권한(read/write/read-only) => 어떤 연산에 대한 권한을 나타냄
- page마다 code를 담고 있는 부분, stack 부분을 담고 있는 부분, data를 담고 있는 부분이 있고, 담고 있는 내용마다 변하지 않아야 하는 page도 있기 때문에 사용한다.
Valid/Invalid bit
valid: 해당 주소의 frame에 그 프로세스를 구헝하는 유효한 내용이 있음 => 접근 허용invalid: 해당 주소의 frame에 그 유효한 내용이 없음 => 접근 불허- 프로세스가 그 주소 부분을 사용하지 않음
- 해당 페이지가 메모리에 올라와 있지 않고, swap area(= backing store)에 있는 경우
출처: http://www.kocw.net/home/search/kemView.do?kemId=1046323
내 머릿속 지우개