이 글은 KOCW에 공개되어있는 '반효경 교수님'의 운영체제 강의 및 강의 교재 Operation System Concepts(a.k.a 공룡책🦕)의 내용을 기반으로 작성했습니다.
이번 챕터에서는 프로세스 관리에 관해 정리해보겠습니다
오류가 있다면 댓글로 정정 부탁드립니다
Demand Paging
- 페이지가 요청 됐을 때 실제로 필요한 page를 메모리에 올리는 것
- IO 양이 상당히 줄어들게 된다
- 멀티 프로그램의 경우 더 많은 사용자를 수용할 수 있다
- system wide하게 생각했을 때 한정된 메모리를 더 잘 사용하고 메모리의 서비스를 더 잘 사용하기 때문에 빠른 응답 시간을 기대
valid/invalid bit의 사용
- invalid : 사용되지 않는 주소 영역, 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 page entry가 invalid로 초기화된다
- address translation시에 invalid bit이 set 되어있으면 page fault이다
Page Fault
| Memory에 없는 page의 page Table
논리적 메모리, 페이지 테이블, 물리적 메모리 <-> backing store
- invalid 의 경우 backing store에서 메모리에 올려야 한다(IO 작업을 해야함)
- page default 현상 발생(요청된 페이지가 메모리에 없다)
-> CPU가 운영체제에게 넘어가게 된다(page fault trap에 걸린다)
| Page Fault
- invalid page에 접근하면 MMU가 trap을 발생시킴(page fault trap)
- kernel mode로 들어가서 page fault handler가 invoke 됨
page fault 처리 순서
- Invalid reference(bad address, protection violation) 일 경우 process 중단
- empty page frame을 가져온다(없으면 뺏어온다 : replace)
- 해당 페이지를 disk 에서 memory로 읽어온다
3-1) disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함(block)
3-2) Disk read가 끝나면 page table entry 기록, valid/invalid bit을 valid 로 바꿈
3-3) ready queue에 process를 insert -> dispatch later - 이 프로세스가 CPU를 잡고 다시 running
- 아까 중단 되었던 instruction을 재개
- Page fault가 얼마나 나느냐에 따라 메모리 접근 시간이 크게 좌우된다(시간이 많이 걸리는 작업)
Page Replacement
- 어떤 frame 을 빼앗아올지 결정해야 함
- 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있다
- 메모리에 올라왔을 때 write가 발생했다면 메모리에서 쫓아낼 때 backing store에 변경된 내용을 써줘야 한다
Replacement Algorithm
- page fault rate를 최소화 하는 것이 목표
- page reference string 에 대해 page default를 얼마나 내는 지를 조사하며 평가하게 된다
| Optimal Algorithm
- MIN(OPT) : 미래에 참조되는 페이지를 다 안다고 가정한다(offline algorithm, 실제 시스템에서는 사용할 수 없다)
- 가장 먼 미래에 참조하는 페이지를 쫓아낸다
- 아무리 좋은 알고리즘을 만들어도 이것 보다는 성능이 좋을 수 없다
| FIFO(First In First Out) Algorithm
- 메모리에 먼저 들어온 것을 먼저 쫓아낸다
- frame 수가 늘어난다고 page default가 덜생기는 것은 아니다 (FIFO Anomaly, Belady's Anomaly)
| LRU (Least Recently Used) Algorithm
- 가장 오래 전에 사용한 페이지를 쫓아내는 알고리즘
- 최근에 참조되는 페이지가 가장 참조되는 성향이 높다는 것을 가정하고 만든 알고리즘
| LFU(Least Frequently Used) Algorithm
참조 횟수(reference count)가 가장 적은 페이지를 지움
* 최저 참조 횟수인 page가 여럿 있는 경우
- LFU 알고리즘 자체에서는 여러 page중 임의로 선정한다
- 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다
- LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
- 참조 시점의 최근성을 반영하지 못함
- LRU보다 구현이 복잡함
| LRU vs LFU
- LRU는 방금 참조된 페이지가 가장 뒤로 간다
- LFU는 참조 횟수를 비교한다 -> 힙을 이용해 구현하게 된다(쫓아낼 때는 Root를 쫓아내고 재구성하게 된다)
- 뒤에 나올 캐슁 기법 중 MRU는 위의 방식을, MFU는 아래의 방식을 사용한다
캐싱
- 한정된 빠른 공간(캐쉬)에 요청된 데이터를 저장해두었다가 후속 요청시 캐쉬로부터 직접 서비스 하는 방식
- Paging System 외에도 Cache memory, Buffer Chaching, Web Caching(웹페이지 요청 시 멀리 있는 웹 서버에서 들고와서 해야하는데, 여러번 요청을 한다면 읽어온 웹페이지를 저장했다 보여준다)등 다양한 분야에서 사용
| 캐쉬 운영의 시간 제약
- 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
Buffer Cache, Web Cache : O(1) ~ O(logn) 정도 허용
Paging System
- page fault인 경우에 OS가 관여
- 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
- O(1)인 LRU의 list 조작조차 불가능
| Paging System에서 LRU, LFU 가능?
- Process A running 중 Process A의 논리 메모리에서 매 순간마다 instruction을 하나씩 읽어서 실행을 할 것이다
- 논리적인 메모리를 물리적인 메모리로 바꿔 읽어서 CPU에 전달할 것이다
- 만일 요청한 페이지가 메모리에 올라가 있다면 운영체제는 하는 일이 없고, 메모리에 올라가있지 않다면 운영체제가 메모리에 올라가 있는 것을 쫓아내고 지금 요청한 페이지를 메모리에 올려야 할 것이다
- 운영체제는 참조횟수를 알 수 없고, 메모리에 올라와 있다면 운영체제는 CPU 접근 시간을 모를 것이다
- 만약 메모리에 올라와 있지 않다면 운영체제는 접근 시간을 알 수 있다(그래서 정보가 반밖에 없다)
- 자료구조를 연결하는 것은 CPU를 가지고 Instruction을 실행해야 할 수 있는 일이며, 이는 운영체제가 하는 일이다(Virtual System에서는 운영체제가 할 수 없다)
Clock Algorithm
Second chance Algorithm, NUR(Not Used Recently), NRU(Not Recently Used)
- Paging System 에서는 LRU, LFU 조차 사용할 수 없기 때문에 LRU의 근사 알고리즘인 Clock Algorithm을 사용한다
- 시계 방향으로 움직이게 된다
- Page를 참조하면 옆에 reference bit이 붙어있고, 이를 이용해 교체 대상 페이지를 선정한다(circular list)
- 최근에 참조가 되면 reference bit을 1로 세팅(하드웨어가 한다)한다
- reference bit가 0인 것을 찾을 때 까지 포인터를 하나 씩 앞으로 이동하며, 이동하는 중 reference bit 1인 것은 0으로 바꾼다
- 한바퀴 되돌아와서도 0이면 replace 당하게 된다
- page default 가 생기면 운영체제가 쫓아내려고 하는데 1은 0으로 바꾸고, 0은 쫓아내게 된다
- modified bit(dirty bit)을 함께 사용하는데 메모리에서 write로 참조가 되면 modified bit 을 1로 설정하게 된다
- 페이지가 쫓겨날 때 지우는 것이 아니라 backing store에 수정된 내용을 반영한 후 쫓아낸다
Page Frame Allocation
- Allocation problem : 각 process에 얼마만큼의 page frame을 할당할 것인가
- 프로그램마다 page default가 안나도록 하는 적정한 페이지 할당량이 있다
- 잘 실행이 되려면 일련의 페이지들이 메모리에 같이 올라와 잇는 것들이 좋다(최소한의 allocation이 없으면 각 loop마다 page fault)
| Allocation Scheme
- Equal allocation : 모든 프로세스에 똑같은 갯수 할당
- Proportional allocation : 프로세스 크기에 비례하여 할당
- Priority allocation : 프로세스의 priority에 따라 다르게 할당
Global vs Local Replacement
| Global Replacement
- Replace 시 다른 process에 할당된 frame을 빼앗아올 수 있다
- allocation을 안해줘도 replacement 해주면서 할당이 되는 경우가 있다(할당량 조절이 된다)
- FIFO, LRU, LFU 알고리즘을 global replacement로 사용시에 해당
- Working set, PFF(프로그램이 최소로 필요로 하는 페이지를 동시에 올려놓는 할당 효과가 있음) 알고리즘 사용
| Local Replacement
- 자신에게 할당된 frame 내에서만 replacement
- FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영 시 해당
Thrashing
프로그램에게 최소 페이징을 할당하지 않았을 경우 page fault가 자주 일어나는 상황을 스레싱이라고 한다
- 프로그램 하나만 올리면 CPU Utilizatoin 낮아짐
- OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
-> 다른 프로세스가 시스템에 추가됨(higher MPD), 프로그램 계속 올리면 CPU utilization이 매우 높아짐
-> 프로세스 당 할당된 frame의 수가 더욱 감소 - 프로세스는 page의 swap in/swap out으로 매우 바쁨(IO를 계속 해야하기 때문에 CPU가 일을 못함)
-> 대부분의 시간에 CPU는 한가함, 낮은 throughput - 이를 막기 위해서는 동시에 올라가는 프로세스의 개수를 조절해줘야 한다
| Working-set Algorithm
working set 결정
- working set window를 통해 알아냄 (window size a일 경우 시각 t에 Time inverval [t-a, t] 사이에 참조된 서로 다른 페이지들의 집합이 working set)
- 프로그램이 실행되면 특정 시간동안 일정 장소만을 집중적으로 참조한다(working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림)
- 집중적으로 참고되는 page를 locality set이라고 하고, 워킹 셋 알고리즘에서는 특별히 working set 이라고 한다
- 스레싱이 발생하면 working set을 보장해줄 수 없는 상황이 발생한다
- 만약 5개가 필요한 프로그램이 있는데 3개만 받는 상황이 오면 구차하게 진행하지 않고(?) swap out 시키고 그냥 suspend 된다(working set을 보장하지 못할 때는 swap out)
| PFF (Page- Fault Frequency) Scheme
- working set을 추정하는 것이 아니라 page fault를 직접 측정하는 것
- page-fault를 많이 내면 메모리에 워킹셋이 보장되지 않는구나 해서 페이지를 더 주게 된다
- page-fault rate 의 상한값과 하한값을 둔다
- Page fault rate이 상한값을 넘으면 frame을 더 할당하고, Page fault rate이 하한값 이하이면 할당 frame 수를 줄인다
- 빈 frame이 없으면 일부 프로세스를 swap out
- 메모리 크기가 커지게 되면 page fault가 발생하는 비율이 줄어들게 된다(page default가 너무 안 생기면 page를 뺏는다)
Page Size의 결정
Page Size 감소 시
- 페이지 수 증가, 페이지 테이블 크게 증가
- Internal fragmentation 감소
- Disk transfer 의 효율성 감소 -> Seek/rotation vs transfer
-> disk 는 기본적으로 seek을 해야하는데 이 때 시간이 오래걸린다 -> 디스트 헤드가 이동을 해서 많은 양의 뭉치를 옮기는 것이 좋다 - 필요한 정보만 메모리에 올라와 메모리 이용이 효율적 -> Locality의 활용 측면에서는 좋지 않음
Trend
- 큰 page size를 사용
- page size는 보통 4KB를 쓰게 된다(메모리 주소는 32 bit -> 64bit로 바뀌게 됨)
- 메모리 사이즈가 커지면 페이지 사이즈도 따라서 바꿔줘야 할 것이다
나는야 누워있는 개발머신