해당 글은
경희대학교 허선영 교수님의 강의 자료 및 내용을 정리한 글입니다
개인적으로 공부하며 작성된 글이라 잘못된 부분이 있을 수 있습니다!
오류가 있다면 알려주세요
Background
Memory
본 노이만 구조에서 CPU-Memory 로 구성이 되어있다.
프로그램이 Process로서 실행이 되기 위해서는 disk로부터 memory로 올라와야함.
Memory는 bytes들의 큰 Array로 구성되어 있고, 각각의 address를 가집니다.
즉 Process address space내에 Program의 insturctuion들이 올라와야 한다는 것
Memory access
Main memory와 register는 Storage CPU만이 직접 엑세스할 수 있다
이떄 register access는 아주 빠르게(one CPU Clock) 처리되며,
Main memory는 많은 cycle을 요구하므로, CPU가 기다리는 상황이 발생하는 memory stall을 발생시킬 수 있다.
Cache
CPU와 Main memory 사이에 Cache가 존재한다.
CPU와 main memory 사이에서 일부 데이터를 미리 가져와서,
더 빠른 접근을 도와준다.
이때, 이는 OS가 아닌 하드웨어 단에서 관리된다.
Memory Protection
Memory는 Process별로 잘 보호되어야한다.
그렇지 않으면 다른 Process가 메모리 영역을 침범하고, instruction을 변형할 수도 있으므로!
따라서 가장 기본적인 방식은,
Base와 Limit register를 사용하는 법이 있습니다
Address space에는 각자만의 stack-heap-data-text section이 존재함
해당 space의 시작과 끝 주소를 저장하는 register를 두는 것임~
따라서 CPU가 memory access를 요청하면
해당 address가 base와 base+limit 사이에 있는지를 Check하여 메모리를 보호합니다!
이때 물론 base와 Limit register를 보호해줘야 하고! kernel mode로 접근하게끔 합니다.
Address 접근이 잘못되었다하면 → Trap(Software interrupt)
Address Binding
Binding = Program이 Disk에 있다가 Memory로 올라갈 때 주소가 부여되는 것
Address는 상태에 따라서 여러 형식으로 표현됩니다.
- Source code: pointer와 같은 상징적인 형식
- Compiled code: relocatable address(start address의 offset으로 표현하는 형식)
- Linker/Loader: absolute address(실제 프로세스의 주소를 반영한 형식)
- Binding map: Address space간 이동하는
Binding은 언제 일어나나요?
- Complie Time에 일어나는 경우
프로세스가 사용할 공간이 미리 정의된다면 Absolute code가 생성될 수 있다. 그러나, Process가 어디 놓일지 모름. location의 변경이 일어나면 recompile 해야한다는 문제
- Load Time에 일어나는 경우
프로세스가 어디에 올라갈지 결정됨. 불러올 때 모든 address가 결정이 되므로 Relocatable code를 생성할 수 있다.
- Execution Time에 일어나는 경우
실행을 하다가 address를 runtime으로 결정한다.
이때 Address를 mapping하기 위한 Hardware support(Register) 필요.
대부분의 OS가 해당 케이스를 사용해요
Logical vs. Physical Address space
Logical address란,
CPU가 바라보는 Virtual Address이다.
각각의 Process가 바라보는 stack/heap/data/text section address 인 것
Physical address란,
실제로 메모리 상에서의 address를 의미한다.
32GB일 때 1byte로 표현되는 각 address인 것 (0 ~ 32G-1)
Compile-time과 Load- time에서는 Logical = Physical
프로그램이 어디서 부터 어디까지 쓸지가 지정된다는 것이므로, Process가 바라보는 것과 실제 올라간 메모리와 동일
Execution-time에서는 Logical ≠ Physical
프로세스가 실행되며 다른 Physical memory에 binding될 수 있기 때문임
Memory Management Unit (MMU)
Logical address → Physical address를 처리하는 하드웨어 모듈 (회로로 구현)
그래서 이를 변환하는 여러가지 방식이 존재합니다!
Memory Menagement Scheme
Simple- Relocation register
Relocation register(앞 내용의 base-register)를 사용해서
User process가 바라보는 logical address의 값이 더해진 값을 활용합니다.
CPU는 실제 Physical address를 알 필요가 없는 것이죠!
Contiguous Allocation
가장 단순한 방식 중 하나입니다.
Main memory 공간을 크게 2개로 나누어 사용합니다.
Operating system(Kernel)과 interrupt vector의 저장은 Low memory에
User process의 저장은 High memory에! 각 프로세스마다 연속적인 공간을 할당받는 것이다
Relocation(base) register가 Physical address의 시작 부분을 가리키고,
Limit register가 Logical address space의 maximum 값을 지정합니다.
따라서 해당 Limit을 넘었다하면 Trap. 넘지 않았다면 가능한 address space에 접근한 것
다음에 relocation register로 physical address로 번역
Problem
Hole
이때 각 프로세스가 필요한 만큼의 section을 할당(Variable Parition)하는 과정에서 Hole 문제가 발생한다
Process를 Hole에 어떻게 할당할까?
- First-fit: Hole의 List에서 가장 먼저 사이즈가 맞는 Hole에 할당함
- Best-fit: Hole의 List에서 가장 꼭 사이즈가 맞는 Hole에 할당함.
- Order가 되있지 않으면 Hole List를 전부 search해야한다는 문제가 있음
- Leftover가 가장 작음
- Worst-fit: 가장 크기가 큰 Hole에 할당함
- Order가 되있지 않으면 Hole List를 전부 search해야한다는 문제가 있음
- Leftover가 가장 큼
보통 Worst-fit이 별로라고 하네요.
Fragmentation
External Fragmentation
메모리 할당과 해제를 반복하는 과정에서 Hole이 분산되어 생성되고,
전체 메모리 내에 존재하는 Hole의 크기는 넉넉함에도 Process가 올라가지 못하는 문제가 발생하는 경우
Internal Fragmentation
할당된 메모리가 실제 프로세스가 요청한 메모리보다 커서,
쓰지 않고 남는(낭비되는) 메모리가 생기는 경우
해결 방법
- Compaction: External fragmentation을 제거하기 위해서 모든 User program을 제배치해서 큰 Hole을 만들어주는 법
- Paging: Noncontiguous하게 메모리를 할당한다. 페이지 단위로 메모리를 나누고, 여러 메모리 공간에 할당해주는 법
Paging
Frame의 사이즈는 OS에 따라서 달라진다.
Physical space를 Frame 단위로 나누며
Logical space를 Frame과 동일한 사이즈인 Page로 나눈다.
Logical memory의 Page가 Frame에 match가 된다는 것!
이때 Frame에 연속적으로 할당되지 않아도 되기 때문에, External fragmentation을 없앨 수 있다는 특징이 있다!
따라서 메모리에 올라간다는 것은
Page들이 실제 Frame에 할당된다는 것
또한 Page는 각 Process마다 가지고 있는 것이다!
Frame는 Unique하게 존재하는 것
Page Table
Page가 Frame에 할당되는 관계를 저장하는 Page Table
이는 프로세스마다 저장하고 있다
Page는 address의 집합이므로,
각 address를 가리키는 Offset과 page를 구분하기 위한 number를 사용
만약 page size가 4,096이라면, $10^12$이므로 address를 page 내에서 구분하기 위해서는 12bit가 필요하다.
만약 Address가 32bit라면, page size에 따라 뒷부분은 offset, 나머지는 number로 사용
MMU의 Traslation 과정
- CPU는 Logical address를 가지고 접근하려고 한다.
- Translation을 위해 Page table을 참조한다.
- Page number와 내부에서의 offset(d)이 있다.
- Page number를 사용해서 어느 Frame에 저장되어 있는지 number를 얻는다.
- Page와 Frame의 사이즈가 동일하므로 Offset은 동일하게 사용할 수 있다.
Page size가 4 byte로 가, 구분을 위해서는 2bit가 필요하다.
이를 통해 00, 01, 10, 11로 Page offset을 표현할 수 있음
나머지 4bit는 Page Number를 표현하는데 사용한다.
따라서 가질 수 있는 총 Page의 개수는 $2^4=16$개 (위 그림에서는 4개까지만 표현했다)
Page와 Frame 내부에서는 데이터가 연속적으로 저장됨을 확인할 수 있음!
따라서 offset를 동일하게 사용할 수 있는 것.
Implementation
Page table은 Main memory에 유지됩니다.
- Page-table base register(PTBR)는 page table를 point
- Page-table length register(PTLR)는 page table의 size를 나타냄
따라서 CPU가 메모리에 접근하기 위해서는 Page table을 읽으러 또 다른 메모리 접근이 발생하게된다.
해당 과정이 썩 ~ 빠르지는 않아서
이를 위한 하드웨어 모듈, TLB이 존재합니다.
Translation Look-Aside Buffer (TLB)
메모리 접근을 빠르게 하기 위해서 캐싱을 해놓는 역할.
우선 TLB에 접근해보고, 없다면 Page table을 참조하여 Frame number를 가져오기 위해 메모리에 접근한다.
TLB의 사이즈가 작음에도 불구하고, 한번 참조한 프로그램을 다시 사용할 확률이 높기에
Tranlation 과정의 속도를 효율적으로 높일 수 있다.
Process마다 Page number는 중복되기 때문에,
TLB는 이를 식별할 수 있는 address-space identifiers (ASIDs)를 가진다.
또는 Contect switching이 발생하면 해당 TLB를 clear하는 방식도 있다.(해당 프로세스 내에서만 유효하니)
Memory Protection
Page table에서 모든 address에 접근가능한 것이 아니다.
따라서 Valid / Invalid bit를 두고 접근가능한지 식별할 수 있게 함
이를 통해 Read-only 구역이나, 아직 할당이 되지 않은 빈 공간 등을 표시할 수 있습니다.
Page Table Structure
32bit machine을 가정
1-dimension array의 경우 Page size는 4,096($2^12$) byte일 경우,
총 Address space는 $2^32$만큼 address 가능
사용할 수 있는 Page의 개수 = $2^{32} / 2^{12}$ = $2^{20}$개
각 Page에 해당하는 Frame number를 저장해야한다.
각 Page에 4byte가 필요하다고 할 때,
$4⨉2^{20}=4MB (1MB = 2^{20}bytes)$ 따라서 Page table에 저장하는 데 4mb가 필요한 것
각 프로세스마다 Page table이 필요하므로, 프로세스가 1000개라고하면 4,000mb가 필요한 것임
이를 하나의 array로 표현하기보다는 2, 3-level로 표현하는 경우가 많다고 하네요
- Hierarchical Paging
- Hashed Page Tables
- Inverted Page Tables
Hierarchical Page Tables
Page table 자체를 Page단위로 나누어서 저장한다
Outer page table은 Page table이 저장되어있는 Page를 가르치고,
Page table 안에 실제 Page 내용이 들어간다.
Two-Level Paging
Linux에서 해당 Hierarchical Paging을 사용하는 방식이다.
Logical address가 3개의 part로 나누어진다
$p_1$을 사용해서 Page에 대한 pointer를 얻어내고,
$p_2$을 사용해서 실제 frame number를 얻어낸다.
Hashed Page table
Hash function을 사용해서 hash table에 접근하고, 해당 table에 Page의 내용이 들어있다.
이때 Funtion에 따라서 나오는 값이 중복될 수 있음!
따라서 하나의 slot에 여러개의 element를 저장하기 위해 Linked List를 활용하기도 한다네요.
$p$로 indexing을 한 뒤에, 해당 p의 값이 어디에 있는지 Linked list를 검색한다.
실제 Logical address entry($r$)를 찾은 뒤, Frame number에 해당하는 값을 찾는다.
어떤 Hash function을 사용하느냐에 따라서 Hash table의 사이즈도 달라집니다.
예) 16으로 나눈 나머지 -> 0~15 (사이즈 16)
Inverted Page Table
기존의 Page table의 경우, 각각의 Process의 Page를 나타내는 것
따라서
Process 0의 Page0은 Frame n에 적용되어 있고~
Process 1의 Page 0은 Frame ?에 매핑되고 ~
Inverted Page table의 경우, Frame을 나타내는 각각의 Index를 가진다.
Frame 0이 어떤 page에 mapping되어 있는가를 나타낸다.
아래는 Frame i가 어떤 Page를 저장하고 있는지를 기록한 것이다.
Process마다 Page num은 겹칠 수 있기 때문에
Process를 식별하기 위한 pid가 존재한다.
Logical address에서 Process, Page number를 사용해서,
Page table에서 처음부터 Search하여 어떤 frame에 해당하는지 알아낸다.
맞는 entry가 존재한다면, 해당 index가 frame number와 일치한다.
Process마다 Page table이 존재하는 경우,
Process의 갯수가 늘어날 때마다 거기에 사용하는 메모리가 늘어나게 된다는 문제가 있다.
Inverted page table은 Entry의 갯수가 Physical memory에 한정될 수 있다는 장점이 있다.
32GB의 physical 메모리이고 frame의 크기가 4kb라고 할 때,
frame의 갯수는 $8*1024$ = Page table의 사이즈!
프로세스마다 Page table을 가지지 않아도 된다~
Swapping
Process가 많아질 수록 남는 메모리의 양이 줄어들고, 너무 많아진다면 메모리를 완전히 가득 채울수도?!
따라서 Swapping을 통해 메모리 사이즈의 한계를 넘어선다.
새로운 Process를 집어넣기 위해 기존에 있던 Process를 Disk에 백업을 해두고
Memory로 올려주어 실행시키는 방식을 사용한다.
Standard Swapping
Process가 필요한 메모리의 전체를 움직이는 방식이다.
메모리에 올려놓은 process를 copy하여 disk에 올려놔야하다 보니
Context switching이 오래 걸릴 수도 있다는 단점이 존재한다.
Modified version (Page)
Page 단위로 프로세스의 일부를 Disk에 백업시키는 방식으로 Linux와 window에서 사용하는 방식임!
'STUDY > 운영체제' 카테고리의 다른 글
| [OS] Chap11. Mass Storage Structure (0) | 2023.12.05 |
|---|---|
| [OS] Chap10. Virtual Memory (1) | 2023.12.03 |
| [OS] Chap07. Synchronization Example (0) | 2023.10.18 |
| [OS] Chap06. Synchronization Tools (0) | 2023.10.16 |
| [OS] Chap05. CPU Scheduling (0) | 2023.10.10 |
