[문과 코린이의 IT 기록장] 운영체제(OS) - Virtual Memory (Deamand Paging, Page Fault 처리 루틴, Replacement Algorithm, Page Frame의 Allocation, Global vs Local Replacement, Trashing, Working-Set Model, PFF(Page-Fault Frequency) Scheme, Page size의 결정)
운영체제
운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각
www.kocw.net
[문과 코린이의 IT 기록장] 운영체제(OS) - Deadlock(교착상태) (The Deadlock Problem, Deadlock 발생의 4가지
[문과 코린이의 IT 기록장] 운영체제(OS) - Deadlock(교착상태) (The Deadlock Problem, Deadlock 발생의 4가지 조건, Resource-Allocation Graph (자원할당 그래프), Deadlock의 처리 방법)..
vansoft1215.tistory.com
[문과 코린이의 IT 기록장] 운영체제(OS) - Memory Management (Logical Address vs Physical Address, 주소 바인딩(A
[문과 코린이의 IT 기록장] 운영체제(OS) - Memory Management (Logical Address vs Physical Address, 주소 바인딩(Address Binding) : 주소를 결정하는 것, Memory-Management Unit (MMU..
vansoft1215.tistory.com
1. Deamand Paging
* Physical Memory의 주소변환은 OS가 관여하지 않는다고 배움
* 그러나 Vritual Memory의 주소변환은 OS가 관여하고 있음
- Demand Paging : 실제로 필요할 때(요청이 있으면) 그 page를 메모리에 올리는 것
* 메모리 관리 기법 중, paging기법을 사용하는 것으로 가정
* paging기법 : 프로그램이 실행될 때 그 프로세스를 구성하는 주소공간의 page를 전부 메모리에 한번에 올리는 것
* demand paging기법 : 요청되었을 때 메모리에 해당 page를 올리는 것
- Deamand Paging 장점
a. I/O 양의 감소
b. 물리적 메모리 사용량 감소
c. 빠른 응답 시간
d. 더 많은 사용자 수용
| - 프로그램을 구성하는 주소공간 중 실제로 빈번히 사용되는 공간은 제한적임 * 좋은 소프트웨어일수록 방어적으로 만들어지기 때문에, 방어적인 코드가 프로그램에서 대부분을 차지 - 즉, 빈번히 사용되는 코드만 메모리에 올릴 수 있도록 하는 이점을 가짐. - 이로 인해, 물리적 메모리에 올리는 사용량이 감소하고, 동시에 다수의 프로그램/사용자가 올라갈 수 있도록 하며, 빠른 응답시간을 가져다줌. * 응답시간 : 한번에 올려놓는다고 좋은 것 X, system wide한 관점에서 한정된 메모리 공간에 더 의미있는 정보를 올려놓는 다는 관점에서, 디스크의 I/O가 줄어들고 메모리에서 직접 서비스하는 비율이 높아지기 때문에 응답시간이 줄어든다는 것 |
[ Memory에 없는 Page의 Page table ]
# invaild의 의미
- 이 page가 물리적인 메모리에 없는 경우 * backing store에 있는 경우
- 사용되지 않는 주소 영역인 경우 * backing store에도 없는 경우
** 처음에는 모든 page entry가 invaild로 초기화
- 주소변환시에 invild bit이 set되어 있으면
=> page fault 발생 (디스크에서 메모리로 해당 page를 올리는 I/O작업을 진행해야 하기 때문에, cpu는 자동으로 운영체제로 넘어감)
2. Page Fault 처리 루틴
- invaild page를 접근하면, MMU가 trap(page fault trap)을 발생시킴
- Kernel mode로 들어가서 page fault handler가 invoke됨.
- 다음과 같은 순서로 page fault를 처리한다.
1. 잘못된 요청이 아닌가? -> 잘못된 요청이라면 강제로 abort
ex. 이 프로세스가 사용하지 않는 주소인가(address가 잘못되어있음), 접근 권한에 대한 violation의 경우
2. 정상적인 메모리 요청이라면, 빈 페이지 프레임을 얻는다.
* 만약 페이지 프레임이 꽉 차있다면, page 하나를 쫓아내야 함. (빈 페이지 획득 과정)
3. 빈페이지가 획득되었다면, 해당 페이지를 disk에서 memory로 읽어온다.
1) Disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt당함 (block)
* Disk I/O를 하게 되면 이 프로세스가 cpu를 가지고 있어봤자 낭비됨. 따라서 block상태로 프로세스를 만들어주고, 당장 cpu를 사용할 수 있는 ready상태의 프로세스에게 cpu를 넘겨줌.
2) Disk read가 끝나면, page tables entry 기록, vaild/invaild bit = "vaild"
* Disk I/O가 끝나면, interrupt가 걸려서 운영체제가 cpu를 가지고, page table entry로 가서 vaild로 변경시키고, 해당 프레임 번호 적어놓는다.
3) ready queue에 프로세스를 insert -> dispatch later
4. 이 프로세스가 cpu를 잡고 다시 running
5. 아까 중단되었던 instruction을 재개
* MMU에 의해 자동적으로 메모리 주소변환을 다시 실행
1) Performance of Demand Paging
1. Page Fault Rate
0 <= p <= 1.0
if p=0 : no page faults (메모리에서 모두 참조되는 경우)
if p=1 : every reference is fault (매번 참조를 하러 나가야하는 경우)
* 일반적으로 0.0x정도 난다. (메모리로부터 보통 직접 주소변환이 가능하다)
2. Effective Access Time
* 대부분의 경우는 page fault가 잘 나지 않지만, 한번 나게 되면 엄청난 시간이 낭비됨. 메모리 접근하는 시간을 page fault까지 감안해서 생각해보자.
= (1-p) x memory access + p(OS&HW page fault overhead + [sawp page out if needed] + swap page in + OS&HW restart overhead)
= 페이지 폴트가 나지 않는 비율 x 메모리 접근시간 + 페이지폴트가 나는 비율(운영체제/하드웨어 서로 넘어가는 오버헤드 시간, 뺏어올 때 메모리 공간이 없다면 쫓아내는 시간, 읽어온 페이지를 올리는 시간, OS가 page table을 변경하는 작업시간 + cpu를 얻는 시간)
2) Free frame이 없는 경우 -빈 페이지가 없는 경우
1. Page replacement
* OS의 업무
- 어떤 frame을 빼앗아올지 결정해야 함.
- 즉, 어떤 page를 메모리에서 쫓아내고 그 자리에 새로운 page를 올려놓을 것인지 결정하는 일을 하는 것
- 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
- 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음
2. Replacement Algorithm
- Page replacement를 해주는 알고리즘
- page-fault-rate를 최소화하는 것이 목표 * 0에 가깝도록 하는 것
- 알고리즘의 평가 : 주어진 page reference string에 대해 page fault를 얼마나 내는지
* page reference string : 시간 순서에 따라, page들에 대해 서로 다른 번호를 붙여놓고, 참조되는 순서를 나열해놓는 것
# 즉 어떤 page를 쫓아낼 것인지를 결정하고, 쫓아낸 페이지와 올려놓는 페이지에 대한 page table을 변경시키는 역할들을 운영체제가 하게 된다.
3. Replacement Algorithm
1) Optimal Algorithm (= Belady's optimal algorithm, MIN, OPT)
- 운영방법 : 가장 먼 미래에 참조되는 page를 쫓아낸다.
- page fault가 가장 적은 알고리즘이다.
- optimal algorithm은 미래에 참조되는 페이지들을 미리 다 안다고 가정한다.
* 즉 page reference string을 알고있다는 가정 하에 이 알고리즘을 운영한다.
- 따라서, 실제 시스템에서는 활용될 수 없는 알고리즘이다.
- 그러나, 아무리 좋은 알고리즘을 만들어도 이보다 성능이 뛰어날 수는 없으므로, 비교를 위한 알고리즘으로 사용된다.
ex.
# 이 알고리즘은 총 6번의 page fault를 발생시킨다.
# 어떤 알고리즘을 쓰더라도 page fault를 6번보다 더 적게 사용할 수는 없다.
2) FIFO(First In First Out) Algorithm
- FIFO : 먼저 들어온 것을 먼저 내쫓음
- 실제 시스템에서 활용 가능한 알고리즘이다. (미래에 대해 알 수 없을 경우에 활용)
# FIFO 알고리즘에서의 특이점
- 메모리 크기를 늘려주면, 일반적으로 성능이 좋아져야 한다.
- 그러나 오히려 이 알고리즘을 쓰면 훨씬 성능이 안좋아지는, FIFO Anomaly 상태가 발생할 수 있다.
* 즉 메모리 frame을 증가시켰는데, 성능이 더 작아질 수 있다.
3) LRU (Least Recently Used) Algorithm & LFU(Least Frequently Used) Algorithm
1. LRU : 가장 오래 전에 참조된 것을 지움
- 실제 시스템에서 활용 가능한 알고리즘이다. (미래에 대해 알 수 없을 경우에 활용)
- 단점 : 마지막 참조시점만 살펴보기 때문에, 그 이전에 어떤 기록을 가지고 있었는지는 생각하지 않는다.
# page fault 8번 발생
2. LFU : 참조횟수(reference count)가 가장 적은 페이지를 지움
- 최저 참조 횟수인 page가 여럿 있는 경우
: LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다.
: 만약 성능을 높이고 싶다면, 성능향상을 위해 가장 오래 전에 참조된 page를 지우게 구현한다.
- 장단점
a. 장점 : LRU처럼 참조 시점만 보는 것이 아니라, 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있다.
b. 단점 : 참조 시점의 최근성을 반영하지 못하며, LRU보다 구현이 복잡하다.
ex. 만약 이제부터 참조가 여러번 시작될 상황이었었다면 문제가 될 수 있음.
3. LRU와 LFU 알고리즘의 구현
a. LRU
b. LFU
* LFU는 LRU와 비슷하게 한 줄로 구현하면 안 된다
: 어떤 페이지가 참조가 되었다고 가정할 때, 즉 참조횟수가 1이 늘어난다고 해서 가장 참조횟수가 많은 페이지가 될 수는 없기 때문
: 다시 말해 자리를 찾을 때까지, 계속 비교하면서 한 줄로 내려가야 한다는 것.
: 이런 식으로 구현하게 되면, page 개수가 n개라고 할 때 O(n)이라는 너무 큰 시간이 소요됨.
- 따라서, LFU 알고리즘은 이진트리 형식으로 구현해야 함.
# 위와같은 알고리즘 환경이 항상 virtual memory system에서만 있는 것이 아니라, 컴퓨터 내부에서는 캐슁이라고해서 다양한 곳에서 실시되고 있다.
- 캐슁 기법
: 한정된 빠른 공간 (=캐쉬)에 요청된 데이터를 저장해 두었다가, 후속 요청시 캐쉬로부터 직접 서비스하는 방식
* 한정된 빠른 공간 : physical memory
* 느린 저장장치 : swap area
: paging system 외에도 cache memory, bufferr caching, Web caching 등 다양한 분야에서 사용됨.
* paging system, buffer caching : 빠른 공간 (physical memory), 느린 저장장치 (disk)
* web caching : 이미 읽어온 웹페이지를 저장해놨다가 화면에 먼저 보여주는 식으로 활용됨.
- 캐쉬 운영의 시간 제약
: 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우, 실제 시스템에서 사용할 수 없음
: Buffer caching이나 Web caching인 경우, O(1) ~ O(long n)정도까지 허용. 너무 많은 시간을 투자 X
: Paging system인 경우 page fault의 경우에만 OS가 관여하며, page가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없다.
| # 즉, Paging System에서 실제로 LRU, LFU를 사용할 수 없다. - page fault trap이 발생해서 cpu 제어권이 운영체제에게 넘어가고, 메모리에 공간이 없어 하나의 page를 쫓아내기로 결정했다고 가정하자. - 이 때 LRU 알고리즘을 사용하면, 가장 오래전에 참조된 페이지를 쫓아내야 하는데, 운영체제는 이를 알지 못한다. - 왜냐하면, 프로세스가 사용하는 page가 메모리에 올려져 있는 경우에는, 운영체제에게 cpu가 넘어가지 않아 이 page들의 실제 접근시간을 알 수 없기 때문이다. 단지 page fault가 났을 때 메모리에 올리는 그 시간만 알 수 있을 뿐이다. - 즉, 운영체제가 자료구조를 유지하면서 위치를 끊고 연결하는 작업들을 수행하지 못한다는 것이다. |
4) Clock Algorithm (= Second chance algorithm = NUR = NRU)
* paging system에서는 그렇다면 어떤 알고리즘을 사용해야 할까? : Clock Algorithm
- LRU의 근사 알고리즘
- Reference bit을 사용해서, 교체 대상 페이지를 선정한다. (circular list)
- Reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동시킨다.
- 포인터를 이동시키는 도중에 reference bit 1은 모두 0으로 바꾼다.
- Reference bit이 0인 것을 찾으면 그 페이지를 교체한다.
- 한 바퀴를 돌아와서도 (=second chance) 0이면, 그때에는 쫓긴다.
- 자주 사용되는 페이지라면 second chance가 올 때 1일 것이기 때문이다.
# Clock algorithm의 개선
- reference bit과 modified bit(dirty bit)을 함께 사용
- reference bit = 1
: 최근에 페이지가 참조되었다는 것을 나타냄.
- modified bit = 1
: 최근에 변경된 페이지 (I/O를 동반하는 페이지)
: write로 참조되는 경우. (backing store에서 올라온 이후로 데이터의 변경이 이루어졌던 적이 한 번이라도 있던 경우)
: 그냥 내쫓으면 안 되며, 그 값을 다시 backing store에 반영하고 쫓아내야 한다.
4. Page Frame의 Allocation
* 지금까지 여러가지 Replacement algorithm에 대해 배움
* 현재까지 배울 때는, 어떤 프로세스에 속한 page인지 상관 없이, 특정 정해진 방식으로 쫓아냄.
* 그러나 실제로 어떤 프로그램이 원활하게 실행되기 위해서는, 즉 cpu가 page fault를 잘 내지 않으려면, 일련의 메모리는 함께 묶여 올라오게 해야 효율적이다.
ex. for문 실행 : 내부 구성 page가 3개인데 메모리에 1개만 올라와있는 상황이라면, for문을 반복하는 동안에 page fault가 지속적으로 발생할 것이다.
- Allocation Problem : 각 프로세스에 얼마만큼의 page frame을 할당할 것인가?
- Allocation의 필요성
a. 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시 참조
: 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
b. Loop를 구성하는 page들은 한번에 allocate되는 것이 유리함
: 최소한의 allocation이 없으면 매 loop마다 page fault 발생 가능
* 프로그램별로 page allocation을 해주지 않으면, 메모리에서 특정 프로그램이 페이지 프레임들을 완전히 장악해버리는 문제가 생길 수 있다. (즉 서로 다른 프로그램들을 동시다발적으로 요청함으로써, 다른 프로그램의 페이지들을 다 쫓아냄)
- Allocation Scheme(방법)
1) Equal allocation : 모든 프로세스에 똑같은 page frame개수 할당
* 단점 : 어떤 프로그램은 page frame이 많이 혹은 적게 필요할 수 있기 때문에, 비효율적임
2) Proportional allocation : 프로세스 크기에 비례하여 page frame 할당
* 단점 : 같은 크기 프로그램이라도, 시간에 따라서 필요로 하는 페이지 개수가 달라질 수 있음
3) Priority allocation : 프로세스의 priority에 따라 다르게 page frame 할당.
5. Global vs Local Replacement
1) Global replacement
# 미리 할당을 하지 않고, 알고리즘을 사용할 때 프로세스별로 메모리 할당량이 적절히 조절되기 때문에 굳이 할당하지않겠다.
- replace시 다른 프로세스에 할당된 frame을 빼앗아 올 수 있다.
- 프로세스별 할당량을 조절하는 또 다른 방법이다.
- FIFO/LRU/LFU 등의 알고리즘을 global replacement로 사용시에 해당된다.
- Working set, PFF 알고리즘을 사용한다
2) Local replacement
# 프로세스에게 미리 메모리 할당을 해주는 것
- 자신에게 할당된 frame 내에서만 replacement를 실시한다.
- FIFO/LRU/LFU 등의 알고리즘을 프로세스 별로 운영시 사용한다.
6. Trashing
- 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우 발생
* 프로그램에게 메모리가 너무 적게 할당되어서, page fault가 너무 자주 일어나는 상황을 이야기한다.
- 이것을 막기 위해서는, multiprogramming의 개수를 조절해주며, 프로그램이 어느정도는 메모리 확보를 할 수 있도록 해줘야 한다.
# 이러한 조절을 해주는 알고리즘
1) Working-Set Model
2) Page fault frequency algorithm
7. Working-Set Model
# 어느 정도의 메모리 공간은 프로그램이 가지도록 한다.
1) Locality of reference
- 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조하는데, 이것을 Locaility of reference라고 한다.
ex. for loop가 실행되고 있을 때
* 이는 바뀔 수 있다.
- 집중적으로 참조되는 해당 page들의 집합을 locality set이라고 함.
2) Working-set model
- Locality에 기반하여, 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working Set(= Working set algorithsm에서의 Locality set)이라 정의함.
* 즉, 어떤 프로그램이 실행되면서, 메모리에 빈번히 참조되는 page들의 집합을 의미함.
- Working Set 모델에서는 프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspended)
- Multiprogramming degree를 결정함.
* multiprogramming degree가 너무 커지면, working set을 보장할 수 없는 경우가 생기는데, 이 경우에 해당되는 모든 page를 반납하고 suspeded 상태로 변환시킨다.
- 이를 통해 Trashing을 방지함
3) Working-set Algorithm
[ Working set의 결정방법 ]
- Working set window를 통해 알아냄
- window size가 Δ인 경우
a. 시각 t에서의 working set WS(t)
: Time interval[ t - Δt ] 사이에 참조된 서로 다른 페이지들의 집합
b. working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림.
: 즉 참조된 후 Δ시간동안 해당 page를 메모리에 유지한 후 버림.
* 있으면 재참조되는 것
- 프로세스들의 working set size의 합이 page frame보다 큰 경우, 일부 프로세스를 swap out시켜 남은 프로세스의 working set을 우선적으로 충족시켜 준다. (Multiprogramming degree를 줄임)
- Working set을 다 할당하고도, page frame이 남는 경우, swap out되었던 프로세스에게 working set을 할당 (Multiprogramming degree를 키움)
8. PFF(Page-Fault Frequency) Scheme
# 즉 working set을 추정하는것이 아닌, 직접 page fault rate을 시스템에서 보고 결정하는 것
- page fault rate의 상한값과 하한값을 둔다.
a. page fault rate이 상한값을 넘으면 frame을 더 할당한다.
b. page fault rate이 하한값 이하이면 할당 frame수를 줄인다.
- 빈 frame이 없으면 일부 프로세스를 swap out 시킨다. => page fault rate을 일정수준 이하로 떨어뜨려 trashing을 방지
9. Page size의 결정
- paging system에서는 동일한 크기 단위로, Physical Memory 및 Virtual Memory에 프로그램을 구성하는 페이지들도 자르곤 함. 일반적으로 Page size는 4KB
- 최근 메모리 주소체계가 32bit -> 64bit로 변경되며 커지면서, page size도 점차 더 커지며, 이와 함께 page table size도 커지는 형태가 나타나곤함. (그러나 page table이 커지면 메모리 낭비가 발생할 수 있음)
[ Page size에 따른 파급효과 ]
- Page size를 감소시키면
: page 수 증가
: page table entry(페이지 테이블 크기) 증가
: internal fragmentation 감소
: Disk transfer의 효율성 감소 *I/O장치의 시간이 너무 오래 걸려, Disk의 경우는 많은 양을 묶어서 들여오는게 더 효율적
: 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
: 그러나 Locality의 활용측면에서는 좋지 않음.
| * 유의사항 - 아직 공부하고 있는 문과생 코린이가, 정리해서 남겨놓은 정리 및 필기노트입니다. - 정확하지 않거나, 틀린 점이 있을 수 있으니, 유의해서 봐주시면 감사하겠습니다. - 혹시 잘못된 점을 발견하셨다면, 댓글로 친절하게 남겨주시면 감사하겠습니다 :) |
