현재 포스팅은 반효경 교수님의 운영체제 강의 + 추가적인 내용을 바탕으로 정리된 글입니다 :)
0. 가상 메모리
여러 프로그램이 동시에 수행되는 시분할 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어서 사용합니다. 따라서 운영체제는 어떤 프로그램에게 어느 정도의 메모리를 할당할 것인가 하는 문제에 직면하게 됩니다.
프로그램이 실행되기 위해서 그 프로세스의 공간 전체가 메모리에 올라와 있어야 하는 것은 아닙니다. 따라서 운영체제는 CPU에서 당장 수행해야 할 부분만을 메모리에 올려놓고 그렇지 않은 부분은 디스크의 스왑 영역에 내려놓았다가 다시 필요해지면 메모리에 올라가 있는 부분과 교체하는 방식을 사용합니다.
이와 같이 메모리의 연장 공간으로 디스크의 스왑 영역이 사용될 수 있기에 프로그램 입장에서는 물리적 메모리 크기에 대한 제약을 생각할 필요가 없으며, 나아가 운영체제는 프로그램이 물리적 메모리를 고려할 필요 없이 자기 자신만의 메모리를 사용하는 것 처럼 가정해 프로그램 하는 것을 지원합니다. 이렇게 되면 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 주소 공간을 가정할 수 있는데, 이러한 메모리 공간을 가상메모리라고 부릅니다.
프로세스의 주소 공간을 메모리로 적재하는 단위에 따라 가상 메모리 기법은 요구 페이징 방식과 요구 세그먼테이션 방식으로 구현될 수 있습니다. 대부분의 경우에는 요구 페이징 방식을 사용하고, 요구 세그먼테이션 방식을 사용하는 경우는 대개 하나의 세그먼트를 여러 개의 페이지로 나누어 관리하는 페이지드 세그멘테이션 기법을 사용하는 경우입니다.
혹시 페이징 방식과 세그먼테이션 방식이 무엇인지 모르신다면 앞선 포스팅 운영체제 6강을 참고 해주세요 :)
https://wookjongbackend.tistory.com/26
1. 요구 페이징(demand Paging)
요구 페이징이란 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 올리는 것이 아니라, 당장 사용될 페이지만 메모리에 올리는 방식을 말합니다. 따라서 특정 페이지에 대한 CPU에 요청이 들어온 후에야 해당 페이지를 메모리에 적재합니다.
요구 페이징은 당장 필요한 페이지만을 메모리에 적재하기 때문에 메모리 사용량이 감소하고, 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드를 줄여줍니다.
요구 페이징 기법의 주된 효용은 프로그램이 물리적 메모리의 용량 제약을 벗어날 수 있게 한다는 점입니다. 페이지 중 일부만을 적재하기에 물리적 메모리의 용량보다 큰 프로그램도 실행할 수 있는 것입니다!
각 페이지가 메모리에 존재하는지 여부를 판단하기위해 요구 페이징에서 유효-무효 비트(Valid-InValid Bit)를 표시하게 됩니다. 이러한 비트는 각 프로세스를 구성하는 모든 페이지에 대해 존재해야 하므로 페이지 테이블의 각 항목별로 저장이됩니다.
프로세스가 실행되기 전에는 모든 페이지의 유효-무효 비트가 무효값으로 초기화 되어 있지만, 만약 특정 페이지가 필요에 의해(참조 되어) 메모리에 적재되는 경우 해당 페이지의 유효-무효 비트는 유효값으로 바뀌게 됩니다.
만약 CPU가 현재 참조하려는 페이지가 메모리에 있지 않다면 어떻게 할까요???
이때는 MMU가 페이지 부재(page fault)라는 일종의 소프트웨어 인터럽트를 발생시키게 되며, 페이지 부재 처리루틴을 거쳐 해당 페이지를 메모리에 적재하게 됩니다.
페이지 부재(Page fault)
페이지 부재 처리 과정을 그림과 함께 알아보겠습니다!
- 프로세스가 실행되면서 CPU가 특정 페이지에 접근하려할때, 먼저 해당 페이지가 메인 메모리에 있는지 확인해야 합니다. 이는 페이지 테이블에서 해당 페이지의 Valid bit를 확인함으로써 이루어집니다. valid bit가 1이면 해당 페이지는 메모리에 존재하므로, CPU는 메모리에서 해당 페이지를 참조하여 연산을 수행합니다.
- 만약 valid bit가 0, 즉 invalid 상태라면 MMU는 페이지 부재 트랩(page fault trap)을 발생시킵니다. 그러면 CPU의 제어권이 커널모드로 전환되고, 운영체제의 페이지 처리 루틴이 호출됩니다. 이때 운영체제는 invalid한 경우가 메모리 경계를 넘는 것이거나, 페이지에 대한 접근 권한을 위반 한 경우에는 해당 프로세스를 종료시키고, 페이지 폴트라면 free frame(메모리 빈 공간)을 할당받습니다. 만약 free frame이 없다면 swap out을 진행합니다(이때 어떤 페이지를 swap out 할지 운영체제는 페이지 교체 알고리즘을 바탕으로 진행).
- 할당 받은 프레임에 페이지를 로드하기 위해 운영체제는 디스크에 I/O 요청을 하고, 페이지 부재를 발생시킨 프로세스는 CPU를 빼앗기고 봉쇄 상태가 됩니다. 이때 PCB에 레지스터 상태 및 PC 값을 저장함으로써 나중에 다시 CPU를 할당받았을 때 같은 상태에서 다음 명령을 수행할 수 있습니다.
- 디스크에서 I/O가 완료되어 인터럽트가 발생하면 페이지 테이블에서 해당 페이지의 비트를 valid로 설정하고, 봉쇄 상태에 있던 프로세스를 ready로 변경 시켜 준비 큐로 이동시킵니다.
- 이후 이 프로세스가 다시 CPU를 할당받으면 PCB에 저장되어있던 값을 복원시켜 이전에 중단되었던 명령부터 실행을 재개합니다.
이러한 페이지 부재 발생 시, 요청된 페이지를 디스크로부터 메모리로 읽어오는 막대한 오버헤드가 생기게 됩니다. 따라서 페이지 부재가 적게 발생할수록 요구 페이징의 성능은 향상될 수 있습니다.
페이지 폴트 발생 빈도를 줄이기 위한 방법엔 어떤 것들이 있을까요??
우선 페이지의 크기를 적절히 선택하는 것이 중요합니다. 페이지가 너무 작으면 페이지 테이블이 커져 메모리 사용이 늘어나고, 페이지 폴트 빈도가 증가할 수 있습니다(한번에 로드할 수 있는 데이터 양이 적음, 공간지역성도 고려). 반대로 페이지가 너무 크면 내부 조각화 문제가 발생할 수 있습니다. 따라서 서비스의 특성에 맞게 페이지 크기를 적절히 선택해야 합니다.
그리고 효과적인 페이지 교체 알고리즘을 사용하면 페이지 폴트 발생 빈도를 줄일 수 있습니다.
2. 페이지 교체
페이지 폴트가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 하는데, 이때 free frame이 존재하지 않을 수 있습니다.
이 경우 메모리에 올라와 있는 페이지 중 하나를 swap out 해야하는데, 이를 페이지 교체라고 하며, 어떠한 프레임에 있는 페이지를 쫓아낼 것인지를 결정하는 알고리즘을 페이지 교체 알고리즘이라고 합니다.
2-1) 최적 페이지 교체(Optimal Page Replacement)
페이지 폴트를 최소화려면 페이지 교체 시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 swap out 하면 됩니다. 이를 바탕으로 한 최적의 알고리즘을 발레디의 최적 알고리즘이라고 부릅니다.
이는 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고있다는 전재하에 알고리즘을 운영하므로 현실적으로 구현이 어렵습니다.
2-2) 선입선출(FIFO) 알고리즘
선입선출 알고리즘은 페이지 교체시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는 방식입니다.
이는 페이지의 향후 참조 가능성을 고려하지 않고, 물리적 메모리에 들어온 순서대로 내쫓을 대상을 선정하기 때문에 비 효율적인 상황이 발생할 수 있습니다. 예를 들어 가장 먼저 메모리에 들어온 메모리가 계속해서 많은 참조가 이어진다 하더라도 내쫓기게 되는 것이죠.
일반적으로 페이지 프레임 수가 많아지면 페이지 부재수가 줄어드는 것이 일반적이지만, 선입선출 알고리즘의 경우 페이지 프레임 수를 증가시켰음에도 페이지 부재가 더 많이 발생하는 이상현상 또한 발생할 수 있습니다.
2-3) LRU(Least Recently Used) 알고리즘
LRU 알고리즘은 가장 오래전에 참조가 이루어진 페이지를 쫓아내는 기법입니다. 이는 메모리의 참조 성향 중 하나인 시간 지역성을 활용한 알고리즘이라고 볼 수 있습니다. 여기서 시간지역성이란 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질을 뜻합니다.
2-4) LFU(Least Frequently Used) 알고리즘
LFU 알고리즘은 과거에 참조 횟수(reference count)가 가장 적었던 페이지를 내쫓는 알고리즘입니다.
이때 페이지의 참조횟수를 계산하는 방식에 따라 Incache-LFU와 Perfect-LFU로 나뉘는데, 전자의 경우에는 메모리에 올라온 후부터의 참조 횟수를 카운트 하는 방식인 반면(쫓겨났다가 다시 들어온경우도 1), 후자의 경우에는 메모리에 올라와 있는지 여부와 상관없이 페이지의 과거 총 참조 횟수를 카운트 합니다. 즉 어떤 페이지가 4번 참조된 후 메모리에서 쫓겨났다가 다시 참조되어 메모리에 들어온 경우 참조 횟수가 총 5번이 되는 것입니다.
LRU는 직전에 참조된 시점만을 반영하는 반면, LFU는 참조횟수를 통해 장기적 시간 규모에서의 참조 성향을 고려할 수 있다는 장점이 있습니다. 하지만 시간에 따른 페이지 참조 변화를 반영하지 못하고, 구현이 복잡하다는 단점을 가집니다.
예를들어 페이지 참조열이 (1,1,1,1,2,2,3,3,2,4,5), 페이지 프레임 수가 4개라고 가정해보겠습니다.
5번 페이지가 참조되었다고 할때 LRU 알고리즘의 경우 1번 페이지를 교체 대상으로 선정합니다. 하지만, 1번 페이지는 마지막 참조 시점이 다른 페이지들에 비해 오래되었지만 참조 횟수가 가장 많았음에도 LRU 알고리즘은 이를 인지하지 못합니다.
이에 비해 LFU의 경우엔 참조 횟수가 가장 적은 4번 페이지를 교체 대상으로 선정합니다. 그러나 4번 페이지는 가장 최근에 참조된 페이지로 지금부터 참조가 자주 될 페이지일 수 있지만 LFU 알고리즘은 이를 인지하지 못합니다.
LRU, LFU 알고리즘은 페이지의 최근 참조 시각 및 참조 횟수를 소프트웨어적으로 유지해야 하므로 알고리즘의 운영에 오버헤드가 발생한다.
2-5) NRU(Not Recently used) == NUR(Not Used Recently) == 클럭 알고리즘
NUR 알고리즘은 LRU를 근사시킨 알고리즘으로, 최근에 사용하지 않은 페이지를 교체하는 기법입니다.
LRU 알고리즘은 가장 오래전에 참조된 페이지를 교체하는 것에 비해, 클럭 알고리즘은 오랫동안 사용하지 않은 페이지중 하나를 교체합니다. 즉, 최근에 참조되지 않은 페이지를 교체 대상으로 선정한다는 측면에서 LRU와 유사하지만 교체되는 페이지의 참조시점이 가장 오래 되었다는 것을 보장하지 못한다는 점에서 LRU를 근사시킨 알고리즘으로 볼 수 있습니다.
최근 참조 여부를 확인하기 위해 각 페이지 마다 참조 비트(Reference Bit)와 변형 비트(Modified Bit)를 사용합니다.
참조 비트는 페이지가 참조되지 않았을 때는 0, 호출되었을때는 1로 지정하고, 변형비트는 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1로 지정합니다.
NUR 알고리즘의 동작 방식은 다음과 같습니다.
- 운영체제는 일정 시간 간격으로 모든 페이지의 참조 비트를 검사하며, 이를 0으로 리셋합니다. 이는 최근에 참조된 페이지를 판별하기 위한 것입니다.
- 페이지가 참조될 떄마다 참조 비트가 1로 설정됩니다.
- 페이지가 수정될 때마다 변형 비트가 1로 설정됩니다.
- 페이지 교체가 필요할때 운영체제는 두 비트 모두를 고려하여 교체 페이지를 선정합니다. 참조 및 변형 비트가 각각 0,0인 페이지가 최우선적으로 교체 대상이 되고, 만약 그런 페이지가 없다면 (0,1), (1,0), (1,1) 순서로 검색을 진행합니다.
이러한 NUR 알고리즘은 LRU, LFU와 다르게 하드웨어 적인 지원으로 동작을 하기에 페이지의 관리가 훨씬 효율적이고 빨라서 대부분의 시스템에서 페이지 교체 알고리즘으로 NUR 알고리즘을 채택하고 있습니다!
3. 전역 교체와 지역 교체
교체할 페이지를 선정할 때, 교체 대상이 될 프레임의 범위를 어떻게 정할지에 따라 교체 방법을 전역 교체 방법과 지역 교체 방법으로 구분할 수 있습니다.
전역 교체 방법은 모든 페이지 프레임이 교체 대상이 될 수 있는 반면, 지역 교체 방법은 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법입니다.
이때 지역 교체 방법은 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 하는 반면, 전역 교체 방법은 프로세스마다 메모리를 할당하는 것이 아니라 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해 할당되는 메모리의 양이 가변적으로 변하는 방법입니다.
예를들어 LRU 알고리즘을 바탕으로 전역 교체를 한다면 물리적 메모리 전체에 올라와 있는 페이지 중 가장 오래전에 참조된 페이지를 교체하는 것입니다.
일반적으로 앞서 설명드린 LRU, LFU, NUR 알고리즘들은 기본적으로 전체 페이지 프레임을 대상으로 하여 전역 교체 방식을 채택합니다.하지만 프로세스 별로 독자적으로 운영하고자 한다면 지역 교체 방법을 택할수도 있습니다.
4. 스레싱(thrashing)
스레싱이란 할당받은 페이지 프레임의 크기가 작아, 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재 하지 못하면서 페이지 폴트가 자주 발생하고, 이에 따라 CPU 이용률이 급격이 떨어지는 일련의 과정을 지칭하는 용어입니다.
일련의 상황을 통해 스레싱을 이해해보기 전에 간단한 단어 한개 짚고 넘어가겠습니다 :)
MPD(Multi-Programming Degree)란 메모리에 동시에 올라가 있는 프로세스의 수를 의미합니다.
CPU의 이용률이 낮을 경우 일반적으로 운영체제는 MPD를 높이게 됩니다. 그런데 MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소하게 됩니다. 그렇게 되면 각 프로세스는 그들이 원할하게 수행되기 위해 필요한 최소한의 페이지 프레임도 할당 받지 못한 상태가 되어 페이지 부재가 빈번히 발생하게 됩니다.
이러한 페이지 폴트 발생 시 I/O 작업이 수반되므로, Context Switching을 통해 다른 프로세스에게 CPU가 이양됩니다. 이때 다른 프로세스 역시 할당받은 메모리 양이 지나치게 적으면 페이지 부재가 발생할 수 밖에 없습니다. 그러면 또 다른 프로세스에게 CPU가 할당되겠죠??
결국에는 준비 큐에 있는 모든 프로세스에게 CPU가 한번씩 다 할당되었는데도, 모든 프로세스가 다 페이지 폴트를 발생시켜 시스템은 페이지 부재를 처리하느라 매우 분주해지고 CPU의 이용률은 급격하게 떨어지게 됩니다.
이 상황에서 만약 CPU가 MPD를 높이기 위해 다른 프로세스를 메모리에 추가한다면 어떻게 될까요??
프로세스당 할당되는 프레임 수가 더욱 감소하는 동시에 페이지 부재는 더욱 빈번히 발생하겠죠
이러한 일련의 과정을 스레싱이라고 부르는 것입니다!
위 그림은 MPD와 CPU 이용률의 상관관계를 보여줍니다. 메모리 내에 존재하는 프로세스의 수를 증가시키면, CPU 이용률이 급격하게 증가하지만 어느 순간 부터는 CPU 이용률이 급격하게 떨어지게 됩니다. 이러한 이유를 스레싱에 대해 이해한다면 생각하실 수 있으실 것입니다!
MPD를 적절히 조절해 CPU 이용률을 높이는 동시에 스레싱 발생을 방지하는 방법에는 워킹셋 알고리즘(working-set algorithm)과 페이지 부재 빈도 알고리즘(Page Fault Frequency Scheme : PFF)이 있습니다.
워킹셋 알고리즘은 지역성 집합(자주 참조되는 페이지 집합)이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘이며,
여기서 워킹셋이란 프로세스의 원할한 수행을 위해 한꺼번에 메모리에 올라와야 하는 페이지들의 집합을 말합니다. 이는 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당하고, 그렇지 않은 경우엔 프로세스에게 할당된 페이지 프레임을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 디스크로 스왑아웃 시키는 방식으로 동작합니다.
페이지 부재 빈도 알고리즘(PFF)는 프로세스의 페이지 부재율을 주기적으로 조사하고, 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절하는 알고리즘입니다.
만약 어떤 프로세스의 페이지 부재율이 시스템에서 미리 정해둔 상한 값을 넘게된다면, 이 프로세스에게 프레임을 추가로 더 할당하고, 하한 값 이하로 떨어진다면 필요 이상의 많은 프레임이 할당된 것으로 간주해 프레임의 수를 줄이게 됩니다!
개발자 준비생이 대학 강의를 듣고 정리한 내용입니다
혹시 틀린 내용이 있다면 댓글 부탁드리겠습니다!! 곧바로 수정하겠습니다
'운영체제 > 반효경 교수님 - 운영체제 강의' 카테고리의 다른 글
| 운영체제 8강 - 디스크 관리 (0) | 2023.06.10 |
|---|---|
| 운영체제 6강 - 메모리 관리 (1) | 2023.06.09 |
| 운영체제 5강 - CPU 스케쥴링 (0) | 2023.06.08 |
| 운영체제 4강 - 프로세스 관리 (2) | 2023.06.07 |
| 운영체제 3강 - 프로그램 구조와 실행 (2) | 2023.06.07 |
