[운영체제]
global - data
local - stack
SWAP 연산의 IO 연산은 하드디스크의 IO 연산보다 조금 빠릅니다. 그래서 하드디스크에 있는 프로그램에 있는 컴파일 바이너리 이미지가 이것을 더블클릭을 통해서 실행하면 전체가 스왑영역에 갑니다.
CPU가 Address를 메인메모리에 요청하면 CPU에 보는 나의 메모리는 무한대입니다.
Address를 요청하면 OS가 보고서 무슨 값을 요청하는구나 봅니다. 해당 프로세스의 페이지를 프레임에 적재를 하고 적재를 하고 있는 주소 Physical memory에서 읽어다가 CPU에 전달해주는 것입니다.
어쨋든 Logical Address와 Physical Address를 Mapping 시키는 거는 Memory Management Unit을 통해 하는 것이고 운영체제가 그것을 하는 것입니다.
페이지가 physical memory에 적재되어 있지 않습니다. logical address를 통해서 process 2를 실행시키고자 요청했더니 해당 binary file을 swap에 적재하고 physical memory를 보았을 때 physical memory의 모든 프레임을 다른 프로세스의 페이지들이 차지하고 있기 때문에 process2에 페이지가 적재될 곳이 없으면 기존에 적재되어있던 페이지 중에 하나를 선택해서 제거하는 것입니다.
그리고 새로운 process2 페이지를 올리게 됩니다. 그러면 어떤 프레임을 선택하느냐를 고민해야합니다.
내가 한번 즉 CPU가 한번 참조한 페이지는 아주 짧은 미래에 다시 한번 더 참조할 가능성이 있습니다.
Page Out은 Cost가 너무 큽니다. 해당 페이지가 있었던 모든 페이지의 영역을 0으로 바꾸는 것입니다. 그리고 해당 프레임에 있던 페이지가 modification이 발생했다면 swap 영역 dirty bit이 1이라면 해당 프로세스가 해당 페이지를 수정을 한 것입니다.
그럼 해당 페이지를 다른 페이지로 교체하기 전에 SWAP 영역에 저장을 하고 000000으로 바꾼 다음에 다른 프로세스가 적재되도록 만듭니다. 즉 Cost 굉장한 Cost가 필요한 것입니다.
페이지 아웃을 하기 위해서 비워야 하는 프레임을 선택할 때 그 기준을 잘 선정하지 않으면 Cost가 계속 늘어난다는 것입니다. 최근에 사용되었던 페이지를 다른 프로세스에게 넘겨주었습니다. 그럼 page fault가 일어납니다. 그 다음 적재를 해야하는 것입니다.
Page out 시킬 프레임을 잘못 선택한다면 Frame의 페이지가 있는데 다른 페이지를 할당할 때 Dirty bit이 1이라면 SWAP 영역에 써야하는 것입니다. 그 다음 000000 Fill zero로 채워야 합니다. 그 다음 새로운 프로세스 페이지를 쓰는 것입니다.
다른 프로세스가 실행되는데 지금 방금 page out한 것을 참조하고 싶으면 SWAP 영역에서 비우고자 하는 프레임을 선택하고 ... 0만들고 이걸 반복해야합니다.
하지만 만약 사용하지 않을 것 같은 것을 지우면 Page out을 한다면 page fault가 일어날 가능성이 없습니다.
Page Replacement
Over Allocation 이라고 하는 것은 CPU가 보는 Process1이 실행하고 있는 프레임을 선택하고 Page Out 했다고 가정합시다.
그럼 p2도 이걸 가리키고 있을 것이고 하나의 프레임을 두개의 프로세스가 나누어썼습니다. 하나의 프로세스를 두개에게 양다리를 걸친 것은 하나의 자원을 두개에 할당한 것입니다.
항상 프로세스가 바뀔 때마다 page fault가 발생하며 Prevent 하는 것은 page replacement를 잘하면 over-allocation을 줄일 수 있는 것입니다.
Dirty-bit은 특정 frame 안에 있는 페이지를 교체할 때 dirty bit이 1이라는 것은 페이지에 수정이 가해졌기 때문에 swap 영역에 저장하고 다른 페이지를 적재해야 한다는 것입니다.
오직 modified page에서 disk swap하는 것입니다.
Dirty bit swap 되어있으면 읽어들어야합니다. Dirty bit이 Set 되어 있지 않으면 읽어서 쓰면 됩니다.
Frame-allocation 알고리즘은 각각의 프레임에 최소 몇개를 할당해야 되는지 알려줍니다. 그리고 어떤 프레임이 replace 해야하는지 판단합니다.
Page-Replacement 알고리즘은 Page Fault에 따라서 swap out swap in 과정이 일어나는 것입니다. reference string이라고 해서 page number입니다. 상식적으로 생각했을 때, 당연히 frame이 많으면 많을수록 페이지 fault가 줄어들 것입니다.
사용가능한 메인메모리의 frame들이 많으면 그것을 따라서 가용할 프레임이 많아질 것입니다. CPU가 믿는 것처럼 가용할 사이즈가 크다면 Fault가 잘 일어나지 않습니다.
하나의 프레임을 프레임 수가 많으면 하나의 프레임을 하나의 프로세스의 하나의 페이지가 적재되겠지만 프레임이 많아지면 두개의 프로세스가 하나를 공유할 수 있고 여러개의 프로세스가 공유하기 때문에 이 CPU가 실행가능한 SWAP OUT 등을 발생해서 프로그램들은 느려지는 것입니다.
3개의 프레임을 가지고 있다고 볼 때,
FIFO
기존에 CPU가 엑세스하고자 하는 페이지가 있으면 읽으면 되고 Page Fault가 발생하면 기존에 있던 페이지 중에 가장 메인메모리에 적재된지 오래된 것을 골라서 내보내는 것입니다.
그런데 문제가 되는 것은 Belady's Anomoly가 발생합니다.
Page Fault가 줄어들어야 하는데 유지가 되거나 늘어나는 경우가 있고 이 경우가 Belady's Anomaly라고 합니다. 반드시 사용한다고 page fault가 줄어든느 것은 아닙니다.
page가 언제 나가고 언제 들어오는지 구분하기 위해서 FIFO queue를 사용해도 됩니다.
Optimal Algorithm
아주 짧은 시간에 푸는 것인데 값에 가까운 optimal이라고 하는 것은 시간이 오래 걸리는데 최고의 답인 것입니다. optimum은 정답이 아닌데 짧은 시간에 풀어서 나오는 결과값입니다.
Page를 replace 해야하는데 최근에 가장 먼 미래에 사용될 값부터 바꾸라는 것입니다.
이것이 optimal인데 이것의 단점은 사용자가 다음에 어떤 프로세스를 실행시킬지 아는 것은 불가능합니다. 그래서 현실적이지 않은 것입니다. optimal인데 현실적이지 않습니다.
그러면 현실적이지 않은 얘기를 왜 하는 것이냐면 실제 구현은 불가능한데 다른 좋다고 하는 알고리즘과 성능을 비교할 수 있습니다. 얼마나 근접한 optimum 알고리즘을 개발할 수 있는지를 보는 것입니다.
optimal 한 것이 불가능하기에 optimum 알고리즘을 만들어서 optimal 값에 얼마나 근접한지 이야기할때 알고리즘이 뛰어나다는 것을 알 수 있습니다.
LRU 알고리즘
최근에 가까운 히스토리를 통해서 예측하는 것입니다. 즉 최근에 사용된 것이 앞으로 사용될 가능성이 높다는 것입니다. 가장 최근에 사용되지 않은 것 7번입니다. 가장 최근에 사용되지 않았기에 2번을 넣어야 할 곳은 바로 7번이 위치한 페이지입니다.