1. Address Space
2. Base-and-Bound
3. Segmentation
4. Paging
5. 물리메모리 크기 극복
1. Address Space
- 정의
- 실행중인 프로세스가 가정하는 선형적인 메모리의 모습. 실제로는 임의의 물리주소에 산재되어 탑재되어 있다
- address space는 실행 프로그램의 모든 메모리 상태를 갖는다 : code, stack, heap
- virtualizing memory, VM, 메모리 가상화
- 프로세스로 하여금 자신이 특정주소의 메모리에 탑재되고 자신만의 address space를 가지고 있다는 환상을 만드는 것
- VM의 목표 1 : transparency -> 프로그램은 메모리가 가상화되었다는 사실을 인지해서는 안된다
- VM의 목표 2 : efficiency -> OS는 가상화가 시간과 공간 측면에서 효율적이도록 해야 한다
- VM의 목표 3 : protection -> OS는 다른 프로세스로부터 프로세스 및 자신을 보호해야한다. 이를 위해 프로세스들을 서로 고립, isolation 시켜야 한다
- address translation, 주소 변환
- "효율적"이고 "유연성"있는 메모리가상화를 구현하기 위한 기법
- 하드웨어는 명령어 반입, 탑재, 저장등의 가상주소정보를 정보가 실제로 존재하는 물리 주소로 변환
- OS는 메모리의 빈 공간과 사용중인 공간을 항상 알고, 메모리 사용을 제어 및 관리
- 주소변환을 통해 프로그램이 자신의 전용 메모리를 소유하고 그 안에 자신의 코드와 데이터가 있다는 환상을 만든다
2. Base-and-Bound ( = dynamic relocation )
- 정의
- address translation 기법을 구현하기 위해 사용되는 기술
- 각 cpu마다 "base register"와 "bound register"라고 불리는 2개의 하드웨어 레지스터를 이용
- OS가 프로그램이 탑재될 물리 메모리 위치를 결정하고 base register를 그 주소로 지정한다. 그러면 프로세스 실행시 프로세스에 의해 생성되는 모든 주소가 프로세서에 의해 다음과 같이 변환 : physical address = virtual address + base
- 프로세스가 생성하는 메모리 참조는 모두 가상주소 이며 하드웨어는 베이스 레지스터의 값을 이 주소에 더하여 물리 주소를 생성한다
- 가상주소에서 물리주소의 변환을 address translation이라고 하며 이 주소의 재배치는 실행 시에 일어나고, 프로세스가 실행을 시작한 이후에도 address space를 이동할 수 있기 때문에 dynamic relocatoin이라고 한다
- 베이스와 바운드 레지스터는 cpu칩 상에 존재하는 하드웨어 구조처럼 주소변환에 도움을 주는 프로세서의 일부를 MMU (메모리 관리 장치)라고 부른다
- H/W support
- 하드웨어는 processor status word 레지스터의 한 비트로 cpu의 현재 실행 모드 ( kernel mode or user mode)를 나타낸다
- 하드웨어는 base register와 bound register를 자체적으로 제공하며 프로세스가 생성한 가상주소에 base register값을 더하여 주소를 변환, bound register와 cpu 내부 일부 회로를 사용하여 주소가 유효한지 검사한다
- 하드웨어는 base register와 bound register 값을 변경하는 명령어를 제공한다
- cpu는 user program이 bound를 벗어난 주소로 불법적인 메모리 접근을 시도하는 상황에서 예외를 발생시킨다.
- OS issue
- 프로세스가 생성될 때, OS는 새로운 주소 공간 할당에 필요한 영역을 찾기위해 free list 자료구조를 검색
- 프로세스가 종료할 때, OS는 프로세스가 사용하던 메모리를 회수하여 다른 프로세스나 운영체제가 사용할 수 있도록 한다
- 운영체제는 프로세스 전환시 base와 bound쌍을 저장/복원해야 하므로 OS가 process를 중단하기로 결정하면 메모리에 존재하는 프로세스 별 자료구조 안에 base register와 bound register 값을 저장한다
- OS는 예외핸들러 또는 호출될 함수를 제공해야 한다
- base-and-bound 문제점
- address space 전체를 physical memory에 올리는 base-and-bound 방식은 스택과 힙 사이의 빈공간도 physical memory를 차지하므로 메모리 낭비가 심하다.
- address space가 physical memory 보다 큰 경우 프로세스 실행이 불가능하므로 유연성이 없다
3. Segmentation
- 정의
- base-and-bound 문제를 해결하기 위해 고안된 기법
- 주소 공간의 논리적인 segment (코드, 스택, 힙) 마다 base와 bound 쌍이 각각 존재함으로써, OS는 각 segment를 physical memory의 각기 다른 위치에 배치할 수 있다.
- address translation
- offset : 주소가 참조하는 바이트가 세그먼트 안에서 세그먼트 시작으로부터 몇번째 바이트인지 나타내는 값
- 하드웨어는 가상주소에서 offset을 구하고 여기에 base register값을 더함으로써 실제 physical address를 구한다.
- code sharing
- protection bit : 세그먼트마다 protection bit를 추가하여 세그먼트를 읽기 전용으로 설정할 수 있도록 한다
- 코드세그먼트를 읽기 전용으로 설정하면 주소 공간의 독립성을 유지하면서 여러 프로세스가 주소 공간의 일부를 공유함으로써 메모리를 절약할 수 있다
- 각 프로세스는 자신의 전용 코드세그먼트를 사용하고 있다고 생각하지만 OS는 변경 불가능한 메모리 영역을 비밀리에 공유시킴으로써 환상 구현
- external fragmentation, 외부 단편화 문제
- 정의 : 물리메모리에 임의의 위치에 세그먼트들이 할당됨으로써 중간중간에 작은 크기의 free space들이 남게 되고 이는 새로 생성된 세그먼트를 할당하기에 너무 작아 메모리 낭비 발생
- 해결책 1 compact : OS는 현재 실행중인 프로세스를 모두 중단하고 세그먼트들을 물리메모리상에 연속적으로 재배치 하여 하나의 큰 빈공간을 확보 -> 압축비용이 많이 든다
- 해결책 2 free list : free space들을 리스트 형태로 관리하여 메모리할당시 외부단편화를 최소화 하도록 한다
- free list management
- 분할 : 메모리할당 요청이 free space보다 작은 경우 free space를 분할하여 할당한다
- 병합 : 메모리해제된 free space가 다른 free space와 인접하면 하나의 큰 free space로 병합
- free space 마다 그 크기와 다음 free space의 주소값을 가지고 있는 헤더블럭을 유지함으로써 free list 자료구조를 구현
- free space allocation strategies
- best fit : 요청 크기와 가장 비슷한 메모리를 가지는 free space를 free list에서 검색하여 할당
- worst fit : free list에서 가장 큰 크기의 free space를 찾아 요청된 크기만큼 할당하여 최대한 큰 free space를 유지
- first fit : 요청 크기보다 큰 첫번째 free space를 free list에서 찾아 할당하여 빠르게 할당
- next fit : 마지막으로 할당된 free space 다음부터 요청크기보다 큰 free space를 검색하여 free list의 앞부분에서만 external fragmenation이 발생하는 것을 방지
4. Paging
- 정의
- 메모리를 동일크기의 조각으로 분할하여 공간관리하는 방법
- 프로세스의 주소공간을 논리 세그먼트로 나누는 것이 아니라, 고정크기의 단위로 나눈다. 고정크기단위로 나눈 가상메모리 블럭을 "Page"라고 하고, 같은 단위로 나눈 물리메모리 블럭을 "Page frame"이라고 한다
- address space의 각 가상 page에 대한 물리메모리 위치를 기록하기 위해 OS는 프로세스마다 "Page Table"이라는 자료구조를 유지하고 여기에 address translation 정보를 저장한다. 다른 프로세스를 실행해야 한다면 OS는 해당 프로세스를 위해 또 다른 Page Table이 필요하다.
- 프로세스가 생성한 virtual address의 변환을 위해서는 먼저 가상주소를 VPN (가상페이지번호)과 offset 2개의 구성요소로 분할한다.
- 장점
- 유연성 : paging은 프로세스의 address space가 어떻게 사용되는 지에 상관없이 효율적으로 주소 공간 개념지원 가능
- free space 관리의 단순함 : OS는 물리메모리의 비어있는 page의 free list를 유지하고 프로세스 실행시 리스트의 첫부분에서 부터 해당 크기의 page frame만 선택하면 된다.
- page table
- 정의 : VPN (가상페이지번호)를 PFN (물리페이지번호)으로 mapping 하는데 사용되는 자료구조이다
- 가장 간단한 page table은 linear page table로 vpn을 index로 하는 배열이다
- OS는 vpn으로 배열항목에 접근하여 PTE ( page table entry) 를 검색. PTE에는 PFN 뿐만 아니라 다른 정보를 담고 있는 비트들(valid bit, protection bit, present bit, dirty bit, reference bit)도 존재
- 문제점
- 성능 저하 : 페이지에 접근하기 위해 페이지 테이블에 먼저 접근 // TLB로 해결
- 메모리 낭비 : 페이지테이블의 크기가 크면 물리메모리상의 공간 낭비 // multi-level page table로 해결
- TLB, translation-lookaside buffer
- paging의 속도저하 문제 해결을 위해 MMU의 일부인 TLB를 도입
- TLB는 자주 참조되는 가상주소-실주소 변환 정보를 저장하는 "하드웨어 캐시"이다.
- 가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 변환 정보가 있는지를 확인한다. 만약 TLB에 있다면 페이지테이블을 참조하지 않고 변환을 빠르게 실행
- TLB는 VPN, PFN, 다른 비트들(valid bit, protection bit, dirty bit, address-space identifier등)로 구성되어 있다
- TLB 히트율은 spatial locality와 temporal locality에 영향을 받는다
- TLB algorithm
- 가상주소에서 VPN을 추출
- 해당 VPN이 TLB에 존재하는지 검사
- 존재하는 경우 : TLB 히트
- 해당 페이지에 대한 접근 권한 검사
- 접근권한이 있는 경우, 그 정보를 오프셋과 합쳐서 물리주소 구성
- 메모리접근
- 존재하지 않는 경우 : TLB 미스
- 하드웨어는 변환정보를 찾기위해 페이지테이블에 접근
- 가상메모리가 유효하고 접근 가능한지 검사
- 해당 변환정보를 TLB로 읽어들임
- TLB가 갱신되면 다시 TLB 검색
- TLB 히트
- Multi-level Page Table
- paging의 메모리낭비 문제 해결을 위해 사용되는 기법
- 페이지테이블을 페이지 크기의 단위로 나눈 다음, 페이지 테이블의 페이지가 유효하지 않은 항목만 있으면 해당 페이지를 할당하지 않는다.
- PDE (page directory entry)로 구성된 page directory는 valid bit(페이지테이블의 각 페이지 할당 여부 정보)와 PFN 정보를 갖고 있다.
- PDI ( page directory index)를 이용하여 PDE address를 알수 있다 : PDE address = PageDIrBase + (PDI * sizeof(PDE))
- PTI (page table index)를 이용하여 PTE address를 알 수 있다 : PTE address = PDE.PFN + (PTI * sizeof(PTE))
- 페이지 디렉토리가 너무 크면, 트리의 단계를 증가하여 메모리공간을 효율적으로 사용할 수 있지만 메모리주소를 구하는 작업비용이 증가한다
- Multi-level Page Table 장단점
- 장점1 : 멀티레벨 테이블은 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당되므로 메모리를 효율적으로 사용
- 장점2 : 페이지테이블을 페이지 크기로 분할함으로써, 메모리 관리가 용이하고 페이지 테이블을 위한 공간 할당이 유연하다
- 단점1 : 주소변환을 위해 두 번이상의 메모리 로드가 발생( 페이지 디렉터리 접근 + PTE접근)하므로 작업비용 증가
- 단점2 : 페이지 테이블 검색이 복잡해진다
5. 물리메모리 크기 극복
- 물리메모리 한계
- 주소공간이 물리메모리에 탑재되지 못하는 경우 큰 주소공간을 지원하기 위해 OS는 주소 공간중에 현재 필요하지 않는 일부를 보관해 둘 "공간"이 필요.
- 보조기억장치 ( HDD, SSD 등)에서 "공간"을 확보하고 이 공간을 "swap space"라고 한다
- swap space
- 정의 : 디스크에 페이지를 저장할 수 있는 공간
- swap space 의 입출력 단위는 페이지 크기
- OS는 swap psace에 있는 모든 페이지들의 디스크 주소를 기억
- swap spce를 이용하면 시스템에 실제 물리메모리 공간보다 더 많은 공간이 존재하는 것처럼 가정
- swap은 swap space에서 뿐만 아니라 물리페이지에서도 가능
-present bit
- 하드웨어 기반 TLB를 사용하는 시스템은 page swap을 위해 하드웨어는 present bit를 사용하여 각 페이지 테이블 항목에 어떤 페이지가 존재하는 표현한다
- 메모리 참조 알고리즘
- 프로세스가 가상 메모리 참조
- 하드웨어가 가상주소를 물리주소로 변환하기위해 가상주소에서 VPN 추출, TLB에 변환정보가 있는지 검색
- TLB 히트
- 물리주소를 얻은 후 메모리로 가져옴
- TLB 미스
- 페이지 테이블의 메모리 주소 파악
- PTE항목 추출
- PTE가 유효하고(valid bit = 1) 물리메모리에 존재 (present bit = 1)
- PFN 정보를 추출하고 TLB에 저장
- TLB 갱신되면 TLB 재검색
- TLB 히트
- PTE가 유효하지만(valid bit =1) 물리메모리에 존재 하지 않음 ( present bit = 0)
- page fault (물리메모리에 존재하지 않는 페이지 접근) 발생
- OS에게 제어권이 넘어가고 OS는 page-fault handler 실행
- OS는 디스크에 있는 페이지를 물리메모리로 swap-in 한다
- 물리메모리에 공간이 없는 경우, 물리메모리에 있는 페이지중 swap-out될 페이지는 replacement policy에 의해 결정된다
- 디스크 I/O가 완료되면 OS는 해당 PTE의 PFN값을 탑재된 페이지의 메모리 위치로 갱신하고 page fault를 발생시킨 명령어를 재실행
- TLB 히트
- swap-out이 일어나는 시기
- 물리메모리의 여유공간이 고갈된 후에 교체 알고리즘이 작동하는 것은 비효율적이므로 OS는 항상 일정한 수준의 여유공간을 유지한다
- OS는 HW (high watermark)와 LW ( low watermark)를 설정
- swap demon 이라고 불리는 백그라운드 쓰레드가 여유공간의 크기가 LW보다 작으면 HW에 이를 때까지 페이지 제거 수행하고 완료후 슬립모드로 전환
- replacement policy
- evict될 page는 OS의 replacement policy에 의해 결정됨
- replacement policy 목표1 : 디스크로부터 swap-in 횟수 최소화
- replacement policy 목표2 : 접근할 페이지가 이미 메모리에 존재하는 횟수 최대화
- Optimal replacement policy : 가장 나중에 접근될 페이지를 evcit -> 가장 최적이며 가장적은 미스 발생하지만 미래의 정보는 알수 없으므로 구현 불가능
- Least Recently Used : 가장 오래전에 접근된 페이지를 evict -> 과거의 정보를 활용하므로 구현 가능
- Approximating LRU
- LRU 알고리즘은 구현은 가능하지만 과거의 메모리 참조 정보를 모두 기록하고 시간정보배여을 순차탐색해야 하므로 매우 큰 작업비용을 가진다
- 몇몇 비트(use bit, dirty bit)를 추가하는 하드웨어 지원으로 LRU에 근사하는 저비용 알고리즘 구현 가능
- Clock Algorithm
- use bit를 추가, 페이지가 참조될 때마다 H/W는 use bit를 1로 설정
- 페이지들을 노드로 하는 circular list를 구성
- 페이지 교체시 OS는 현재 clock hand가 가리키는 페이지의 use bit를 검사
- use bit가 1이면 해당 페이지는 최근에 참조된 페이지 이므로 물리메모리에 그대로 두고( temporal locality) OS가 use bit를 0으로 재설정
- 다음 페이지를 검사하여 use bit가 0인 페이지를 찾으면 해당 페이지를 evict
- Corbato Algorithm
- 주기적으로 use bit를 지우고, 교체 페이지를 선택하기 위해 use bit가 1인지 0인지 검사
- use bit가 0인 페이지를 찾으면 evict
- Enhanced Clock Algorithm
- dirty bit를 추가하여 페이지의 변경 여부 정보를 저장
- 교체할 페이지 선택시 use bit와 dirty bit 둘다 고려
- 페이지가 최근에 수정되어 dirty bit = 1 이면 그 페이지를 swap-out할 때 디스크에 있는 원본 페이지에 수정된 내용을 기록해야 하므로 추가비용 발생, dirty bit = 0 인 페이지는 추가적인 I/O 비용 없음
- use bit = 0, dirty bit = 0 인 페이지를 먼저 찾고 evict 하고 이를 만족하는 페이지가 없으면 use bit = 0, dirty bit = 1인 페이지를 evict
- Thrashing
- 발생과정
- 물리메모리가 요구를 감당할 수 없을만큼 많은 프로세스 실행중이면 많은 페이지폴트 발생
- CPU 사용률 감소
- OS는 CPU 사용율 증가를 위해 더 많은 페이지를 물리메모리에 탑재
- 페이지폴트가 계속 발생하면서 page-in, page-out 반복
- cpu 사용률이 급감하는 thrashing 문제 발생
- 해결방법
- admission control : 다수의 프로세스가 존재할 때, 일부 프로세스의 실행을 중지
- out-of-memory killer : 과다한 메모리 요청시, 메모리를 요구하는 프로세스를 kill
'CS > Operating System' 카테고리의 다른 글
| #4 Concurrency (0) | 2020.01.22 |
|---|---|
| #2 Virtualizing CPU (0) | 2020.01.22 |
| #1 Introduction to OS (0) | 2020.01.22 |
