해당 글은
경희대학교 허선영 교수님의 강의 자료 및 내용을 정리한 글입니다
개인적으로 공부하며 작성된 글이라 잘못된 부분이 있을 수 있습니다!
오류가 있다면 알려주세요
Background
프로그램을 사용하기 위해서는 Memory에 올려야했다.
이때, 프로그램의 모든 부분이 항상 사용되는 것은 아니므로!
사용하고 있는 것만 메모리 위에 올려두자!가 Virtual의 개념입니다.
Virtual Memory
- Logical memory (Page)
- Physical memory(Frame)
의 2개의 파트로 나누어지며,
프로그램의 실행되는 부분만 메모리에 올라가면 됩니다.
무조건 모든 Page가 Frame에 매핑되지 않고, 일부는 Disk에 있을 수도 있는것이죠
따라서 physical memory의 한계에서 벗어날 수 있는 것쉼
👍 장점 👍
- 여러 process 간의 address spaces 공유가 가능함: Logical page가 같은 Frame을 가리키면 된다
- 더 많은 프로그램이 concurrent하게 실행 가능 (CPU 사용률 good)
- 더 효율적인 process creation
- process를 load하고 swap하는 과정에서 발생하는 I/O 요청 감소
Virtual Address Space
memory 내에 process가 어떻게 저장되어 있는지에 대한 logical view!
주소는 0에서 시작되고요, 연속적입니다.
해당 Logical view를 MMU를 통해 Physical하게 변환합니다.
Virtual memory는 어떻게 구현될 수 있을까요?
Demand Paging
요구할 때 Paging을 진행하는 것
일반적으로 Page는 Disk에 존재하며
요청이 들어오면(접근할 때) 필요한 부분을 Page 단위로 main memory에 올린다.
따라서
Page 접근 요청이 들어옴
-> 유효한 주소? (invalid reference라면 abort)
-> not-in-memory?
-> bring to memory
Lazy swapper라고 명명하기도 합니다
with Valid-Invalid Bit
Demand Paging을 위해서는 해당 Page가 메모리/디스크 중 어디에 존재하는 상태인지가 파악되어야함
따라서 valid / invalid bit를 사용합니다
- v → in-memory이므로 frame number(physical memory)를 확인할 수 있다
- i → not-in-memory이므로 디스크에 존재한다면, 메모리에 올려줘야하는 경우이거나. 잘못된 접근일 수 있다. (Page Fault)
Handling Page Fault
(1)
Page에 접근했다 = Page가 포함하는 Address 중, 하나의 data에 접근했다. = Byte 단위의 접근이다
(2)
Page내의 어떤 address로 접근하게 되면, Trap(software interrupt)가 발생.
page fault interrupt number에 따라서 OS로 Handling이 넘어간다.
Page number에 해당하는 entry를 확인 (Valid? invalid?)
만약 접근하지 못하는 구역이라면 abort.
아니라면 Disk에 있는 경우로, page를 불러들여와야함
(3~5)
Disk에 있는 것을 사용하기 위해서
Main memory에서 Free Frame을 찾고,
해당 frame에 그 page를 Disk에서 읽어와서 올린다.
(6)
invalid bit 업데이트, frame table number 업데이트,
Performance of Demand Paging
Page fault가 자주 발생하게 되면,
page를 Disk에서 main memory로 가져오는 과정을 자꾸 반복해야 하므로
성능 이슈가 발생할 수 있다.
Page Fault Rate를 줄이는 것이 중요하다고 하네요!
$0 ≤ p ≤ 1$
$p=0$, page fault가 발생하지 않는 것을 뜻함
$p=1$, 매번 page fault가 발생하는 것을 뜻함
Effective Access Time (EAT)
= 메모리를 접근하는 데 걸리는 시간(성능)
$(1-p) × memory access + p$
따라서 page fault rate이 0.8일 경우,
0.2는 기존의 메모리 access time이 들어가고
0.8은 page fault가 발생하므로 해당 overhead를 함께 고려해주어야 한다.
Copy-on-Write (COW)
앞서 virtual memory의 장점 중에 Process creation 관련 내용이 있었다!
parent에서 fork하여 child process를 생성하는 경우,
같은 page를 share하게 생성한다.
이후 내용에 수정이 발생하는 경우에만 서로 다른 page를 가질 수 있도록 변경한다.
Free-Frame List
어떤 Frame이 비어있는지 check하기 위함
가장 간단하게는 위와 같은 Linked List 형식이 있다.
OS는 주로 zero-fill-on-demand를 사용하여 free frame을 할당한다.
Frame을 초기화한 뒤에 Page 값을 넣어주는 것을 의미함
지금까지는 free frame이 존재하는 상황이었는데,
만약 free frame이 없다면 어떡함요?
Page Replacement
메모리에 올라간 Page 중에, 잘 사용되고 있지 않은 것을 선택하여 바꾸어줘야겠죠
사용되지 않을 것 같은 page를 선택하여 Page fault의 발생를 줄여야하므로,
다양한 알고리즘 방법이 있다고 하네요
Modify / Dirty bit → 메모리에 올라간 상황에서 데이터가 수정되었다면, 이를 디스크에 반영해줘야한다
Basic page replacement
Page fault가 발생했는데 Free frame이 없는 경우
하나를 victim page로 설정하여 대체한다.
만약 해당 frame이 dirty(수정됨)이라면 이를 Disk로 write해주고 free frame
Page table update!
따라서 하나의 Page Fault에 2번의 page transfer가 발생하는 것쉼
Page Replacement Algorithm
어떤 page를 victim으로 선정해야 page fault 발생을 줄일 수 있을까?
자주 접근하지 않는 page를 target으로 해야 re-access할 일이 적어지겠죠
page number의 sequence인 reference string을 이용해서
Page fault가 얼마나 발생할 것인지를 확인하며 성능을 평가합니다.
FIFO Page Replacement
들어온 (disk→memory) 순서대로 Queue되며, 오래된 순서로 내보냄.(memory→disk)
가장 단순한 형태의 구현이다.
기본적으로 Memory frame 개수가 늘어나면, page fault 개수가 줄어드는 것이 보편적이다.
그러나, FIFO에 경우 그렇지 않은 Belady's Anomaly 현상이 발생하기도 한다.
즉 reliable한 알고리즘이 아니라는 단점이 있다.
Optimal Page Replacement
가장 긴 기간 동안 사용되지 않을 page를 선택하여 대체하는 알고리즘으로,
최적이다.
그러나 미래를 예측하는 것은 불가능하므로 현실적으로 구현은 불가능하다.
Least Recently Used (LRU) Page Replacement
과거의 history를 보고, 최근에 사용되지 않은 것을 선택하여 대체하는 알고리즘이다.
일반적으로 not bad한 성능으로, FIFO보다는 낫고 OPT보다는 별로라고 하네요
보편적으로 자주 사용됨 ~
그렇다면, 과거 History를 어떻게 파악할 것쉼?
- Counter implementation
매 Page entry마다 counter를 가진다.
접근될 때마다 clock time을 넣어 마지막에 접근된 시간을 set한다.
그러나 Page replacement를 위해서는 Page table의 처음~끝을 search하며 minimum을 찾아야한다는 문제가 있다.
- Stack implementation
page를 순서대로 stack하다가, 접근이 다시 발생하면 stack의 가장 위로 다시 넣는 식이다.
따라서 stack의 가장 아래에 있는 것이 가장 예전에 접근한 page가 된다.
replacement를 위해서 search를 수행하지 않는다는 점에서 좋아요.
그러나 stack을 update하는데 overhead가 발생한다.
그렇다면 정확하게는 말고
걍 빠르게 대강 파악할 수 있는 방법은 없을까?
- Reference Bit
각 page마다 reference bit가 존재하고 0으로 초기화
최근에 접근되었는지, 아닌지만을 tracking하기 위해 접근되면 1로 바꾼다.
Page fault가 발생하면 bit=0, 최근에 방문한 놈이 아니군! 하고
아무거나 들어간다.
- Second chance algorithm
각 page마다 reference bit가 존재하고 0으로 초기화. pointer를 옮겨가며 victim을 선정한다.
reference bit이 1인 경우가 나오게 되면
이것을 0으로 바꾸고 next로 넘어간다. (최근에 접근이 되었더라도, 한 번 더 확인해본다.)
그러다가 0인 page를 만나면, 이것을 잡고 대체한다.
기존의 reference bit보다는 좀 더 골고루 들어갈 수 있겠네요
Global vs. Local Replacement
Global Replacement
해당 process가 가지고 있는 전체 Frame을 대상으로 victim 찾아 replacement
Throughtput(시간 당 처리량)이 좋다는 장점이 있으나,
메모리를 많이 잡아먹는 Process에 의해 handling이 어려워져 실행 시간이 길어질 수 있다.
Local Replacement
각 Process가 가지는 Frame이 있고, 그 안에서 victim 찾아 replacement
일정한 성능을 꾸준히 낼 수 있다는 장점이 있으나,
처리량이 떨어질 수도 있다는 단점이 있다.
Thrashing
Process is busy swapping pages in and out
메모리의 사이즈가 작아서 page fault를 처리하는 데에 너무 바쁜 상태를 의미한다.
메모리에 접근하는 I/O brust에서 page fault의 발생이 잦아지게 되면
OS의 입장에서는 CPU의 활용도가 낮은 상황이기 때문에
더 많은 process를 실행해도 ㄱㅊ겠다고 판단할 수 있고
그러면 더 많은 메모리를 요하므로,,, so bad
Locality model
시간이 지나면 Process가 사용하는 메모리의 구역이 변화하는 것을 확인할 수 있다.
모든 process의 locality size를 더했을 때, 이것이 Total memory size보다 크다면
⇒ Thrashing 발생
따라서 프로세스가 사용하는 memory size를 제한해 놓는 방식으로 완화할 수도 있습니다.
Working-Set Model
Working-Set Window($ Δ $)란,
고정된 크기의 Page reference를 묶어 일컫는 말이다.
Working-Set Size란,
Window 내에서 최근에 얼마나 많은 Page가 reference 되었는지를 확인하는 것이다.
${WSS}_i$는 Process $P_i$의 working-set size이다.
이때 Δ가 너무 작다면, 전체 locality를 대변하지 못하고,
Δ가 너무 크다면, 각각의 localities를 반영하지 못한다.
$D = ∑ {WSS}_i $
모든 프로세스의 WSS를 더하면
그것이 모든 프로세스가 원하는 Frame의 개수와 동일하다.
만약 $D > m$이라면, Thrashing이 발생한다.
Page-Fault Frequency (PFF)
각 Page Fault의 발생 빈도를 주시하면서, 이것이 일정 이상을 넘기는지 체크한다.
각 Process가 할당받은 Frame이 존재하는 local replacement policy이다.
Page-fault rate이 너무 작은 경우, 프로세스가 과하게 할당받았다는 뜻이므로 해당 page를 분배하고
Page-fault rate가 너무 큰 경우, 프로세스가 부족하게 할당받았다는 뜻이므로 page를 더 할당한다.
Page fault를 고려하는 Direct approach이다!
Allocating Kernel Memory
위 내용까지는 User memory에 대한 내용이었고,
지금부터는 Kernel memory에 대해 설명합니다.
kernel은 주로 free-memory pool로 부터 메모리를 할당받는다.
다양한 data structure를 생성 및 활용하므로 dynamic하게 메모리를 할당받으며,
또한 device I/O 와 같은 일부는 무조건 contiguous하게 저장되어야 하는 경우도 있다.
Buddy System Allocator
이때 메모리는 언제나 $2^n$으로 할당한다.
예를 들어 256KB의 memory chunk가 존재할 때, Kernel이 21KB를 요청한다.
기존의 메모리를 계속해서 반으로 쪼개고
요청 메모리 size에 fit할 때까지 반복하며, 할당한다.
해당 방식으로 만들어진 chunk는 다시 뭉치기가 좋아서(coalesce) 관리에 용이하다는 장점이 있으나,
chunk에 할당되고 남은 메모리가 낭비되는 internal fragmentation이 발생할 수 있다.
Slab Allocator
Slab이란, 연결된 page의 묶음이다. 이때 고정된 사이즈는 아니다.
Cache란, 여러개의 Slab으로 구성된 것이다.
Kernel은 다양한 data structure를 다룬다.
이때 한 번 정의되고 나면, 다른 형태의 structure가 생길 일이 없다는 특징이 있다.
따라서 Unique Kernel Data Structure에 대해서 미리 할당을 해둔다.
Process가 생성되면, 해당 cache 내에 Free object를 미리 할당 해둔 것 중
하나의 PCB를 활용하는(Used). Pool 방식
미리 사용할 데이터를 할당해두었기에
Fragmentation이 발생하지 않고
memory request를 굉장히 빠르게 처리할 수 있다는 장점이 있다
In Linux
에서는 struct task_struct를 통해서 Cache내에 struct를 할당한다고 하네요
끝 :)
'STUDY > 운영체제' 카테고리의 다른 글
| [OS] Chap12. I/O Systems (0) | 2023.12.08 |
|---|---|
| [OS] Chap11. Mass Storage Structure (0) | 2023.12.05 |
| [OS] Chap09. Main Memory (0) | 2023.11.30 |
| [OS] Chap07. Synchronization Example (0) | 2023.10.18 |
| [OS] Chap06. Synchronization Tools (0) | 2023.10.16 |
