메모리는 각각 주소가 할당된 일련의 바이트들로 구성된다. CPU는 PC가 지시하는 대로 메모리로 다음 수행할 명령어를 가져온다.
- CPU자원, 메모리 자원은 중요하기에 어떻게 할당해주어야 할지(스케줄링) 알아야 한다.
- 어떤식으로 메모리에 적재되는지(프로세스에게 메모리를 얼마나 할당해줘야 하는지)
Background
- CPU가 직접적으로 접근할 수 있는 메모리 공간 Cache까지
- Protection이 필요
- base register: process가 시작하는 지점
- limit register: 시작하는 지점부터 얼마만큼까지 메모리에 접근할 수 있는지 나타내는 지점
- 주소는 base 보다 크거나 같고 base+limit보다 작아야 한다.
Address Binding
- binding: 주소를 이해하는 프로세스(CPU와 OS가 이 process가 메모리의 어떤 주소에 있는지 알아가는 과정)
- 메모리 상 실질적 주소
- CPU가 매긴 주소
- 메모리에 어디 올라갈지 아는 경우와 그렇지 않은 경우
- compile time binding:
- load time binding:
- execution time binding: 매번 실행시킬 때마다 주소가 어떻게 되는지를 확인하고 최적의 주소에 적재시키는 과정 → demand paging을 사용한다면 꼭 필요하다.
- 요약:
프로그램은 동작하기위해 메모리에 적재되어야 한다. 어디에 ? 메모리 특정 주소에만 올라가야 하는 경우, 어디든 상관 없는 경우 특정 주소: 프로그램 자체에 어떤 주소에 넣어달라고 명시(OS는 이대로 실행) compile할 때 정해짐 어디든 상관 없는 경우: 한 번 load시키면 끝까지 그곳에서 계속 load되는 경우와 실행될 때마다 위치가 계속 바뀌는 경우
프로그램에 따라 3가지 경우 중 하나가 적용됨.
- Logical address(virtual address): CPU가 생성
- Physical address: 메모리에서 보여지는 실제 주소 둘은 1 : 1 mapping 존재 compile time과 load time -> 실행 전에 수행되는 단계들로, 실행하기 전에 주소가 정해지기에 logical = physical
- compile time binding & load time binding
- program이 종료될 때까지 바뀌지 않음, logical=physical이기에 변경사항이 그대로 적용됨.
- 일관성을 위해 logical이 있다고 생각하면 된다.
- execution time binding인 경우는 실행될 때마다 physical 주소가 바뀔 수 있기에 logical 주소를 고정된 값으로 가질 수 없음. 두 주소를 다르게 관리 logical과 physical 사이에 mmu가 이를 통역해줌. - logical은 보통 0부터 시작, logical 범위에서만 관리하면 계속 바뀌는 physical 주소를 신경쓰지 않아도 변경사항이 적용된다. - MMU: memory 관리의 핵심 - physical과 logical 사이의 mapping을 담당 - CPU의 부담을 덜어줌
Swapping
실행되지 않은 프로세스를 뺐다가 그 자리에 실행되는 프로세스를 넣는 방식, 제한된 메모리를 사용하기 위함이다. 제한된 메모리에서 많은 응용 프로그램을 실행시키기위해 필요하다.
- backing store : 모든 메모리 복사본을 수용하기에 충분히 큰 빠른 디스크로 메모리에 직접 접근이 가능
- roll out, roll in : 이 용어보다 swap in, swap out이 많이 사용된다. 메모리에 들어갈 때와 나올 때를 의미
주된 swap 시간은 프로세스를 옮기는 시간
프로세스를 swap in할 때 같은 주소로 가져와야 하는가 ?
Load time binding만 지원한다면 같은 주소 그렇지 않다면 어디든 상관없다.
Schematic view
main memory에 OS가 있고 다른 공간은 swapping에 사용
Context Switch time in swapping
100MB process, 50MB/sec transfer rate일 때
swapping time에 비해 context switch time은 작은 시간이다. 그렇기에 swapping time을 줄이는게 관건 !
게임팩을 살 때 최소 권장사항이 이런 swapping이 많이 발생하지 않고 게임이 실행될 수 있게 하는 환경을 말한다. (권장사항을 만족하지 않아도 실행되지만...swapping이 미친듯이 일어날 것이다 !)
또한 작업 관리자에서 메모리 사용량이 넘치는 프로그램을 종료하면 swapping time을 대폭 줄이기에 빨라지는 것도 이제 이해할 수 있을 것이다.
Pending I/O : bus 구조에서 발생
iOS는 background에서 오랫동안 사용하지 않은 프로세스나 메모리를 많이 차지하는 프로세스를 알아서 종료해주고 Android는 사용자가 언제든 실행할 수 있도록 state만 저장해놓는다. state를 저장해놓았기에 이전 상태에서 재시작이 가능하다.
왜 mobile system에서는 swapping을 지원하지 않을까 ?
모바일 장치들은 영구 저장장치로 공간(물리적)을 많이 차지하는 하드디스크 보다 플래시 메모리를 사용하기 때문이다.
Allocation
어떻게 할당할 것인가? 연속적인 공간을 핟당해준다. (contiguous allocation)
OS는 0부터 시작해서 연속적으로 공간을 할당받고 나머지는 사용자 공간을 위해서 할당된다. 이를 다시 표현하자면, OS는 low memory(0부터니까)에 사용자 프로세스는 high memory에 할당된다.
단점은 많은 fragmentation이 발생 !!
Relocation register
Multiple-partition allocation
메모리 사이의 빈 공간들을 memory hole이라고 한다. (말그대로 비어있으니 구멍난...)
→연속적으로 할당된 공간들이 적재되고 제거되다 보면 구멍이 생김
프로그램이 hole에 들어갈 때를 생각해보자. hole이 1개라면 크기만 비교해서 넣을 수 있으면 넣으면 된다. 하지만 2개 이상이라면 ?...
hole이 각각 100, 80으로 2개가 존재하고 넣을 프로그램이 30이면 ?
정답은 OS 마음이다.
OS는 어떤 정책에 따라 이를 수행한다. hole도 링크드 리스트로 구현되어 있다는 것을 생각하며 정책을 바라보자. 넣을 수 있는 hole은 프로그램 크기보다 당연히 커야한다.
- First-fit : 첫 번째 hole에 할당해라.
- Best-fit : 가장 작은 hole에 할당해라.
- Worst-fit : 가장 큰 hole에 할당해라.
Fragmentation
조각이 많이난 상태라서 contiguous allocation이 불가능한 상태
분명히 공간들이 있는데, 이 공간들은 각각 너무 작아
Windows에서 "디스크 조각 모음"이 바로 이런 것을 수행하는 것이다. 작은 공간들을 모아서 연속적인 공간으로 만드는 작업으로 compaction(압축)이라고 한다. compaction을 통해 external fragmentation(외부 단편화)을 해결할 수 있지만 compaction이 항상 가능한 것은 아니다. 또한 가능한다고 해도 비용이 매우 많이 든다.
Compaction은 재할당이 동적으로 수행되고 실행 시간에 수행되어야 가능하다.
외부 단편화를 해결할 수 있는 다른 방법은 한 프로세스의 논리 주소 공간을 연속적인 공간이 아닌 여러 개의 비연속적인 공간에 할당하는 방법이다. 이에 해당하는 방법 2가지를 살펴보자.
Segmentation
논리 주소 공간은 segment들(프로그램이 갖고 있는 특성의 조각들)의 집합으로 이루어진다.
사용자 공간에서 여러 개의 segment로 나누고 각 segment를 메모리 공간에 재할당하는 방식이다.
MMU의 역할이 중요해진다. → segment table
Segment table을 만들어 이를 통해 할당이 수행된다. 그렇기에 이 table이 어디에 있는지 시작 주소와 끝 주소를 가리키는 register가 필요하다. 이 register가 바로 Segment-table base register(시작 주소)와 Segment-table length register(끝 주소)이다.
메모리에 두 번 접근해야되기 때문에 기존의 MMU보다 느리고 스압 아웃되는 다양한 크기의 segment를 예비 저장장치에 저장해야 하는 문제가 생긴다. (이런 문제는 paging에서 해결)
예비 저장장치 역시 main memory와 같은 단편화 문제가 있으며 접근 속도가 느리기에 압축 하는 것이 불가능하다.
Segmentation은 (compaction을 통해) external fragment를 어느정도 해결할 수는 있고 internal fragment를 완전히 해결한다. 또한 논리적인 내용 단위로 나뉘어져 보호와 공유 측면에서 좋다.
모든 프로그램이 같은 크기가 아니기에 불가능하다. 이를 해결하는 방법이 paging이다.
Paging
하나의 프로그램을 같은 크기의 chunk로 나눈다. 메모리 또한 같은 크기의 chunck로 나눈다.
그러면 메모리의 모든 slot을 활용 가능하기에 external fragment가 완벽히 해결된다.
물리적 주소를 동일하게 나눈 하나의 부분을 frame이라고 한다. 총 몇 개의 frame이 존재하고 몇 개의 frame을 사용하고 있는지만 알면 된다. (좀 더 단순해짐)
frame 크기는 보통 4KB이다. (이럴 때 프로그램 최소 크기는 4KB)
논리적 주소를 동일하게 나눈 하나의 부분을 page라고 한다. 논리적 주소를 물리적 주소 mapping(상응)하기 위해 page table을 만든다. backing store도 page단위로 나누어진다.
하지만 항상 frame의 정수 배로 할당되기 때문에 internal fragment는 아직 남게된다.
결국 세그먼트로 나누어 보호와 공유 등의 권한을 지정할 수 있고 이를 다시 paging하는 방식으로 내부, 외부 단편화를 해결할 수 있다. (단, 세그먼트 테이블, 페이지 테이블 모두 존재하므로 속도 면에서 조금 떨어질 수 있다.)
Address Translation Scheme
논리적 주소의 크기와 page 크기가 다음과 같을 때
m = 4, n =2라고 가정해보자.
Paging 예시
- 하나의 프로세스가 실행되기 위해 도착하면 크기가 page 몇 개 분에 해당하는지 조사한다.
- 프로세스가 n개의 page를 요구하면 메모리에서 이용할 수 있는 frame도 n개 있어야 한다.
- 사용할 수 있다면 n개의 frame들을 프로세스에 할당한다.
- 그 프로세스의 1번째 page부터 n번째 page가 각자 할당된 frame에 적재된다.
- 적재된 그 frame 번호가 page table에 기록된다. (1 page~n page)
Paging의 문제점
page size = 2048 bytes, process size = 72766 bytes 라고 가정하자.
그러면 72766/2048 = 35.530으로 35 pages + 1086 bytes가 나온다. 1086 bytes를 위해 page를 하나 더 추가해야 한다는 점에 주목하자. 그래서 총 page의 개수는 36이고 internal fragmentation이 발생한다는 것을 알 수 있다.
internal fragmentation = 2048-1086 = 962 bytes
그러면 page를 작게 해주면 되지 않을까 ? → 최선이 아님
page table은 메모리에 있는데, page 크기가 줄어들 수록 이 page table은 늘어나 overhead가 발생할 수 있다. 오히려 page table은 줄여 검색 속도를 빠르게, overhead를 줄이도록 하는게 좋을 수도 있다.
Paging 구현
위에서 설명했던대로 PTBR, PTLR이 필요하다고 했지만... 문제 (메모리에 2번 접근해야 한다 : page table에 접근하기 위해 메모리 접근[1], 실제 주소 계산해서 메모리에 접근[2] )
TLB를 통해 이를 어느정도 해소하면서 구현이 가능하다. TLB는 일종의 캐시로, Translation Look-aside Buffer 의 약어이다.
TLB 내의 항목은 <key(page number), value(frame number)>의 쌍으로 구성된다. TLB에 요청이 들어오면 동시에 여러 개의 key를 비교하여 해당되는 value를 알려준다. page table의 일부를 메모리에 저장하지 않고 접근이 빠른 cache(CPU 근처에 있음)인 TLB에 저장한다. 그렇기에 상당히 제한적이다. 자주 쓰이는, 자주 쓰일 것 같은 page number를 TLB에 저장한다.
그런 page number를 잘 판단하는게 중요하다. 만약 TLB가 가득 차 있다면 교체될 항목도 잘 선택해야 한다. 보통 중요 커널 코드 항목들이 TLB에 고정된다.
page가 어떤 프로세스에 할당 되어있는지 모르기에 정보를 비우고(TLB flush) 다시 채워넣는 작업을 수행해야 한다. 이런 작업은 context switching이 자주 발생하는 문제를 야기한다.
이를 위해 프로세스를 식별할 수 있는 ASIDs(Address-Space Identifiers)가 TLB에 저장된다. 이 덕분에 한 TLB 안에 여러 프로세스들의 정보를 동시에 함께 보관할 수 있어 flush 될 필요가 없어진다.
TLB hit 비율이 늘어날 수록(cache에서 memory로 이동하는 횟수) 접근이 빠르다. TLB hit 비율은 접근하려는 메모리의 page 번호가 TLB에서 발견되는 비율이다.
- 접근하려는 메모리의 page number가 TLB에서 발견되는지 확인한다.
- 찾지 못 한 경우, page table에 접근하여 frame number를 얻어낸다.(메모리 접근)
- 원하는 데이터를 메모리에서 읽어온다. (메모리 접근)
Effective Access Time
TLB 크기를 키우는 것은 한계가 있기에 최근에는 multi-layer(다중 계층)을 구현하기도 한다. 앱실론: TLB에 접근하는데 걸리는 시간
Memory Protection
각 page에는 protection bits를 통해 메모리 보호가 이뤄진다. 이 bits는 보통 page table에 속하며 page가 read-only나 read-write와 같은 메타 data를 저장한다.
page table에 valid-invalid bit가 있는데 이는 해당 page가 프로세스의 유효한 page인지 무효한 page인지(잘못된 주소 참조일 때)에 대한 정보를 담고 있다.
PTLR(Page Table Length Register)은 page table의 크기를 나타내기 위해 몇몇 시스템에서 사용된다. PTLR은 프로세스가 제시한 주소가 유효한지 확인하기 위해 모든 논리 주소 값이 PTLR 값과 비교된다.
Shared Pages
재진입 가능 코드(reentrant or pure code)라면 프로세스들은 이 코드 부분을 서로 공유할 수 있다. 물론 동기화 문제가 발생하지 않도록 각각의 프로세서들은 레지스터들의 복사 값과 data를 따로 data 저장소에 저장한다.
코드는 page table에 mapping, data는 서로 다른 page frame에 mapping하는 방식이다.
pages를 공유하면 필요한 공간이 줄어들어 메모리 효율성이 높아진다.
각 프로세스의 shared data에 같은 page table을 가지면 공유가능하며 각 프로세스마다 독립적인 data도 존재할 수 있다.
Structure of the Page Table
page table은 앞으로 컴퓨터가 더 큰 공간을 가질수록 상당히 커질 것이다. 이럴 경우 모든 page table을 main memory에서 연속적으로 할당하는 것은 무리가 있다. 그렇기에 page table을 여러 개로 나누는 방법이 존재한다.
Two Level Page Table
page table 자체가 paging 되는 것을 말한다.
outer page table이 있고 이곳에 있는 값을 통해 메모리의 다른 위치로 이동하는데, 그곳은 page table이 있는 곳이다.
pros : 연속적으로 큰 공간이 아니라 메모리 관리가 용이하다.
cons : page table에 두 번 접근해야 한다.
총 접근은 3번(outer page, page of page table, physical memory)
outer page는 page table에 대한 valid-invalid, page of page table은 page에 대한 valid-invalid가 존재
64bit machine이면 page offset 12 나머지 52... 총 6번 접근해야 한다. 64 bit system은 관리가 어렵다.
접근 횟수를 줄이기위해 4KB가 아닌 8KB로 2^10이 아닌 2^13로 시도할 수 있지만 너무 많은 메모리 접근을 요하기에 이 방법을 적용하기는 힘들다.
Hashed Page Table
주소 공간이 32비트보다 커지면 논리 주소를 hash로 사용하는 hashed page table을 주로 사용한다.
Hashed Page Table을 만들고 hash function으로 접근횟수를 많이 줄일 수 있다.
- 논리 주소 공간으로부터 page 번호가 오면 이를 해싱(hashing)한다.
- Hashed page table에서 연결 리스트를 따라가며 page 번호를 비교한다.
- 일치하면 그에 해당하는 page frame 번호를 가져와 물리 주소를 얻고, 일치하지 않으면 다음 번호 비교
사실 프로세스 하나당 page table이 존재하기에 이런 문제들이 발생했던 것 !!!
그럼 이 frame은 어떤 프로세스의 몇 번 page인지 역으로 접근하면 안되나 ?
Inverted Page Table
기존 방법들의 가장 큰 단점은 page table 크기이다. 그 크기로 인해 엄청난 메모리 공간을 점유할 수 있게 된다. 이를 해결하는 방법이 Inverted Page Table(역 페이지 테이블)이다.
역 페이지 테이블에서는 메모리 프레임마다 한 항목씩 할당한다. (항목 : frame에 할당된 page 주소, page를 소유하고 있는 process id)
이렇게 되면 시스템에서는 단 하나의 page table만이 존재하게 되고, table 내 각 항목은 메모리 한 프레임씩을 가리키게 된다.
- <pid, p>의 쌍으로 이루어진 논리 주소의 일부가 메모리 하부 시스템에 전달된다.
<process id, page number> - 역 페이지 테이블에서 일치하는 것이 있는지 검색한다.
- i번째 entry에서 발견되면 물리주소는 <i, d(offset)>이 되고 그렇지 않으면 잘못된 접근이다.
pros
- 논리 page마다 항목을 가지는 대신 물리 frame에 대응되는 항목만 table에 저장하기 때문에 메모리에서 훨씬 작은 공간을 점유한다.
cons
- page search time 증가
- mapping(주소변환) 시간 증가
- 메모리의 공유가 어렵다
공유 page는 하나의 물리 주소에 mapping되는 여러 개의 논리 주소 구조인데, 모든 물리 page에 대해 하나의 논리 주소를 갖는 역 페이지 테이블에서는 이런 구조가 불가능하다. → 만약 공유를 시도하면 page fault가 일어난다.
