0. Introduction

• 해당 내용은 운영체제와 정보기술의 원리 -반효경 지음- 와 kocw 이화여자대학교 운영체제 - 반효경 교수 -를 보고 정리한 내용이다.
• 정확하지 않은 내용이 있다면 말씀해주시면 감사하겠습니다.

• 운영체제는 보통 모든 프로그램들에 공평하게 같은 크기의 메모리를 할당하기보다는 몇몇 프로그램들에게 집중적으로 메모리를 할당한 후, 시간이 흐르면 이들로부터 메모리를 회수해서 다른 프로그램들에게 다시 집중적으로 메모리를 할당하는 방식을 채택한다.

• 왜냐하면 프로세스의 빠른 수행을 위해 프로그램마다 최소한 확보해야하는 메모리 크기가 존재 하기 때문이다.

• 하지만 그렇다고 프로세스의 주소 공간 전체가 메모리에 올라와 있어야 하는 것은 아니다. 운영체제는 CPU에서 당장 수행할 부분만을 메모리에 올려놓고, 그렇지 않은 부분은 disk의 swap area에 내려놓았다가 다시 필요해지면 메모리에 올라가 있는 부분과 교체하는 방식을 사용한다.

• 또한, 프로그램은 0번지부터 시작하는 자기 자신만의 메모리 공간을 가정한다. 이러한 공간을 Virtual memory(가상 메모리) 이라 한다. 이 가상 공간 중 일부가 swap area에존재하고, 일부는 물리적 메모리에 존재하는 것이다.

• 이 가상 메모리를 적재하는 단위에 따라 요구 페이징 또는 요구 세그먼테이션 방식으로 나눠진다. 전자는 대부분의 경우에 사용되며, 세부적인 구현에 특히 사용된다. 후자는 paged segmentation 기법을 사용하는 경우를 말한다.

• 그러면 요구 페이징에 대해 먼저 알아보자.

1. 요구 페이징

프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 게 아닌, 당장 사용될 페이지만을 올리는 방식

• 특정 페이지에 대한 CPU 요청이 들어온 후에야 해당 페이지를 메모리에 적재한다.

• 비유: 매 끼니마다 필요한 분량만큼 재료를 구입해서 보관하는 방식

  • 냉장고: 물리적 메모리
  • 식재료: 프로세스를구성하는 페이지
  • 보관 행위: 페이지를 메모리에 적재

• 장점

  • 필요한 부분만을 적재하기 때문에,
    • 메모리 사용량 감소, I/O 양 감소 -> 응답시간 단축
    • 프로세스 전체를 메모리에 올리는데 소요되는 입출력 오버헤드 감소
    • 더 많은 프로세스 수용
    • 물리적 메모리 용량 제약에서 벗어남

• Problem

  • 가상 메모리 중 어떤 페이지가 메모리에 존재하는지 유무를 구별하기 위한 방안 필요

• Solution

  • 유효-무효(Valid - Invalid bit)를 두어 page가 각 memory에 존재하는지 표시
  • 모든 page에 대해 존재해야 하므로, page table의각 항목별로 저장

• Valid - Invalid bit

  • 기본 bit 값: invalid bit

  • 특정 페이지가 참조되어 메모리에 적재 → Valid bit → 적재된 page가 swap area로 쫓겨남 → Invalid bit

  • Invalid bit 는 언제일 때를 말하는가?

    • 해당 페이지가 물리적 메모리에 없는 경우
    • 페이지가 속한 주소 영역을 프로세스가 사용하지 않은 경우
    • 물리적 메모리에 A,C,G가 올라가 있기 때문에, 이에 해당하는 page table의 0, 2, 6이 valid라는 걸 확인할 수 있다.

• Page fault
  • CPU가 한 페이지를 참조하려는데, 요청한 페이지가 메모리에 없어서 invalid bit인 경우를 말한다.

1.1 요구 페이징의 페이지 부재 처리

• CPU가 무효 페이지에 접근 → 주소 변환 담당 MMU가 페이지 부재 트랩(page fault trap) 발생 → kernel mode로 전환 → OS의 페이지 부재 처리루틴(page fault handler)이 호출

• OS의 처리 과정

  • OS는 프로세스의 해당 페이지에 대한 접근이 적법한지 먼저 체크 (reference)

    • 사용되지 않는 주소 영역에 속한 페이지에 접근하려거나, 해당 페이지에 대한 접근 권한 위반(protection violation)을 했을 경우, 해당 프로세스를 종료
    • protection violtaion: read-only file에 write 시도를 한 경우

  • → 적법 판정 → 물리적 메모리의 빈 frame을 할당받아 이 공간에 해당 페이지를 적재.

    • 빈 frame이 없다면, 물리적 메모리에 적재된 페이지 중 하나를 swap out

  • → 요청한 페이지를 디스크로부터 물리적 메모리에 적재하기(disk I/O 작업을 의미)까지 오랜 시간이 걸리므로, CPU를 빼앗기고 봉쇄 상태(block state)가 됨

    • 현재까지 수행되던 프로세스는 CPU register state 및 PC value를 PCB에 저장하여, 나중에 이 프로세스를 재할당 시, 정확히 같은 상태에서 다음 instruction을 수행.

  • → I/O 작업이 완료되어 interrupt가 발생하면 page table에서 해당 page의 valid-invalid bit를 valid bit로 설정 (reset page table)

  • → 봉쇄된 process를 ready queue로 이동

  • → 다시 CPU를 잡고 running 하며 아까 중단되었던 instruction을 재개한다.

1.2요구 페이징의 성능

• 페이지 부재의 발생 빈도
  • 페이지 부재로 인해 페이지 교체가 이뤄지는 과정에서 요청된 페이지를 디스크에서 메모리로 읽어오는 disk input/output 과 각종 overhead가 포함되어 시간이 오래 걸린다.
  • 그래서 유효 접근 시간 이 짧을 수록 성능 향상

2. 페이지 교체

• 페이지 교체(page replacement)란?

  • 페이지 부재가 발생 시, 요청 페이지를 디스크에서 메모리로 불러오기 위에 메모리에 적재된 여러 페이지 중 하나를 swap out하여 요청된 페이지를 메모리에 적재하는 것

• 교체 알고리즘(replacement algoritum)

  • 페이지 교체 시, 어떤 프레임에 있는 페이지를 쫓아 낼지 결정하는 알고리즘
  • 페이지 부재 발생비율(page-fault rate)을 최소화하는 것이 목표
  • 평가 기준: 주어진 페이지 참조열에 대해 페이지 부재를 얼마나 내는지 조사
    • 가까운 미래에 참조될 가능성이 적은 페이지를 내쫓는 것이 성능 향상 방안

• 페이지 참조열(page reference string)

  • 참조되는 페이지들의 번호를 시간 순서에 따라 나열한 것
    • 예) 1,2,3,4,1,2,5,1,2,3,4,5

2.1 최적 페이지(Optimal Algorithum) 교체

• Belady’s optimal algorithum (빌레디의 최적 알고리즘) = MIN, OPT

  • 페이지 부재율을 최소화하기 위해, 메모리에 존재하는 페이지 중 가까운 미래에 참조될 페이지를 쫓아내는 것

• 다른 알고리즘의 Upper bound

  • 어떠한 알고리즘보다도 가장 적은 페이지 부재율을 보장 하므로 다른 알고리즘 성능에 대한 상한선(Upper bound) 를 제공한다.
  • 그래서 어떤 교체 알고리즘이 이 알고리즘과 유사하다면 더 이상의 알고리즘 연구가 필요하지 않음을 시사한다.

• 예시

  • 4 frames example
  • 처음 페이지 참조 시에는 4회까지 페이지 부재가 불가피하다.
  • 5, 6회는 이미 페이지가 존재하기 때문에 발생하지 않는다.
  • 7회에서 페이지 5를 참조 시, 페이지 부재가 발생하여 디스크에서 메모리로 가져오는 작업이 필요하다. 이 때 페이지 교체를 해야 하는데, 가장 먼 미래에 참조될 페이지인 4번 페이지와 교체된다.
  • 그래서 총 6번의 페이지 부재가 발생한다.

• Offline algorithum

  • 미래에 어떤 페이지가 참조될지 미리 알고 있다는 전제 이므로, 온라인에서 사용할 수 없어서 offline algorithum 이라 한다.

• 이 이후에 알고리즘은 미래를 모르는 알고리즘들이다.

2.2 선입선출(FIFO:First In First Out) 알고리즘

• 물리적 메모리에 먼저 올라온 페이지를 우선적으로 내쫓는 알고리즘
  • 향후 참조 가능성 고려 X
  • 물리적 메모리에 들어온 순서대로 대상 선정

• 페이지 프레임을 늘린다고, page fault가 줄어드는 게 아니다.

  • 페이지 프레임 3개

    • 9번의 페이지 부재

  • 페이지 프레임 4개

    • 10번의 페이지 부재

2.3 LRU(Least Recently Used) 알고리즘

• 교체 알고리즘으로 가장 많이 사용된다.
• 시간지역성(Temporal locality)이 낮은 페이지를 쫓아내는 알고리즘
  • 시간 지역성: 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질
  • 가장 오래 전에 참조된 것을 지워서, 참조 횟수는 고려하지 않는다.

2.4 LFU(Least Frequently used) 알고리즘

• 물리적 메모리 내에 존재하는 페이지 중 과거에 참조 횟수(reference count)가 가장 적은 페이지로 교체 페이지를 결정하는 알고리즘

  • 최저 참조 횟수를 가진 페이지가 여러 개일 경우, 상대적으로 더 오래전에 참조된 페이지를 쫓아낸다.

• 참조 횟수를 계산하는 방식에 따라 Incache-LFU 와 Perfect-LFU 로 나눠진다.

• Incache-LFU

  • page가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트하는 방식
  • 그래서 메모리에서 내려갔다가 다시 적재되면 참조 횟수는 초기화된다.

• Perfect-LFU

  • 메모리에 적재여부와 상관없이 그 페이지의 과거 총 참조 횟수를 카운트하는 방식
  • 장점: 페이지의 참조 횟수를 정확히 반영
  • 단점: 메모리에서 쫓겨난 페이지의 참조 기록까지 모두 보관하고 있어야 하므로, 오버헤드가 상대적으로 더 크다.

• 장단점

  • 장점: LFU 알고리즘은 LRU알고리즘보다 오랜 시간 참조 기록을 보기 때문에, 더 정확히 반영 가능
  • 단점: 참조 시점의 최근성을 반영 X, LRU보다 구현 복잡

2.5 클럭(Clock) 알고리즘

하드웨어적 지원을 통해 알고리즘의 운영 오버헤드를 줄인 방식

• 그래서 LRU 비해 페이지의 관리가 훨씬 빠르고 효율적으로 이뤄지기 때문에, 일반적으로 페이지 교체 알고리즘으로 클럭 알고리즘을 선택한다.
• LRU의 근사 알고리즘으로서, 다음과 같이 불린다.
  • Second chance algorithum
  • NUR(Not Used Recently)
  • NRU(Not Recently Used)
• LRU는 가장 오래 전에 참조된 페이지를 교체하는 것에 비해 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체하기 때문에, 가장 오래되었다는 건 보장하지 못한다.

• 그림 설명

  • 직사각형= 물리적 메모리 안에 있는 페이지(= 페이지 프레임)를 의미

• 교체할 페이지 선정을 위해 HW가 세팅한 페이지 프레임들의 참조 비트(reference bit) 를 순차적으로 OS가 조사한다.

  • pointer 이동 중에 reference bit 1은 모두 0으로 바꾼다.
  • reference bit가 0인 것을 찾으면 그 페이지를 교체한다.
  • 한 바퀴 되돌아와서도 (=second chance) 0 이면 그 때 교체된다.
  • 자주 사용되는 페이지라면 second chance가 올 때 1

• Clock algorithum의 개선

  • HW가 bit를 setting
  • reference bit = 0: 한 바퀴 도는 동안 이 페이지에 대한 참조가 없었다는 의미
  • reference bit = 1: 한 바퀴 도는 동안 적어도 한 번 참조된 페이지
  • modified bit = 1: 최근에 변경된 페이지(I/O를 동반하는 페이지)

3. 페이지 프레임의 할당(allocation)

프로세스 여러 개가 동시에 수행되는 상황에서 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인지 결정해야 한다. 이를 위한 알고리즘을 3가지로 나눌 수 있다.

• 첫 번째, 균등할당(equal algorithum)

  • 모든 프로세스에게 페이지 프레임을 균일하게 할당하는 방식

• 두 번째, 비례할당(proportional allocation)

  • 프로세스의 크기에 비례해서 페이지 프레임을 할당하는 방식

• 세 번째, 우선순위 할당(priority allocation)

  • 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당하는 방식
  • 당장 CPU에서 실행될 프로세스와 아닌 프로세스를 구분하여 전자 쪽에 더 많은 페이지 프레임을 할당하는 방식

할당 알고리즘만으로는 process의 페이지 아래의 참조 특성을 제대로 반영하지 못한다.

• 첫 번째, 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 존재
• 두 번째, Loop(반복문)를 구성하는 page들은 한꺼번에 할당되는게 유리하다.
  • 최소한의 allocation이 없으면 매 loop마다 page fault 발생
• 세 번째, 프로세스에게 최소한으로 필요한 메모리의 양은 시간에 따라 다르다.

그래서, 종합적인 상황을 고려해서 각 프로세스에 할당되는 페이지 프레임의 수를 결정해야 한다.

경우에 따라서는, 최소한의 메모리 요구량을 충족시키기 위해 일부 프로세스에게 메모리를 할당하지 않아야 한다.

4. 전역교체와 지역교체 (Global vs. Local replacement)

교체할 페이지를 선정할 때, 교체 대상이 될 프레임의 범위에 따라 다음 2가지로 구분된다.

• 전역 교체(global replacement)

  • 프로세스마다 미리 메모리를 할당하는 게 아닌, 전체 메모리를 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법

    • 그래서 replace 시, 다른 process에게 할당된 frame도 빼앗아 올 수 있다. (경쟁)
      = 모든 페이지 프레임이 교체 대상 = Process 별 프레임 할당량을 조절하는 또 다른 방법

  • FIFO, LRU, LFU 등의 알고리즘을 사용하다보면 전체 시스템 차원에서 특정 페이지가 알아서 메모리에 올라가기 때문에 frame 할당량이 알아서 조절된다.

  • 다음 절의 working set, PFF 알고리즘의 경우, 프로그램이 최소한 필요로 하는 할당 효과가 있는 알고리즘이기 때문에, 전역교체 방법으로 사용될 수 있다.

• 지역 교체(local replacement)

  • 프로세스마다 페이지 프레임을 미리 할당하는 것
  • 현재 수행 중인 프로세스에게 할당된 frame 내에서만 빼앗아올 수 있는 방법
    • frame 할당 알고리즘은 균등할당, 비례할당, 우선순위 할당으로 프로세스에게 미리 할당한다.
  • 프로세스가 FIFO, LRU, LFU 등의 알고리즘을 독자적으로 운영할 때, 사용되는 방법

5. 스레싱(thrashing)

프로세스가 원활히 수행되기 위한 일정 수준 이상의 페이지 프레임을 할당받지 못하여 page fault가 지나치게 발생하는 상황

Thrashinig의 자세한 발생 과정

프로세스에게 일정 수준 이상의 페이지 프레임 할당 X → 페이지 부재율이 크게 상승 → CPU 이용률이 급격히 하락

→ 낮은 CPU 이용률 -> OS가 메모리에 올라가는 프로세스의 수 증가 = 다중 프로그래밍의 정도(Multi-Programming Degree: MPD) 증가 →

MPD를 OS가 높이는 이유는 OS에게 CPU 이용률이 낮다는 건, 프로세스의 수가 너무 적고, 프로세스가 모두 I/O 작업을 하여 ready queue가 비는 경우를 의미한다.

→ 과도한 MPD 상승 -> 프로세스 당 할당되는 메모리 양이 지나치게 감소 -> 빈번한 페이지 부재 발생 → 페이지 교체하며 swap in & swap out이 지속적으로 발생 -> CPU 이용률 다시 감소 → 2번 과정 다시 수행

• swap in & swap out 작업 과정

  • I/O 작업을 수반 → 문맥교환을 통해 다른 프로세스에게 CPU 이양 → 다른 프로세스에게도 할당받은 메모리 양이 적으면 페이지 부재 발생
  • 그래서 ready queue에 있는 모든 프로세스에게 CPU가 한 차례씩 할당되었는데도 모든 프로세스가 다 페이지 부재가 발생.

• 결국 낮은 처리량(low throughput)을 가진다.

• 이렇게 1번에서 5번 과정이 계속 반복되는 것을 스레싱이라 한다.

Thrashing graph

• 위 과정을 그래프로 나타낸 것이 다음과 같다.

• 프로그램이 1개일 때는 메모리를 쓰다가 I/O 하는 동안 CPU가 쉰다.

• 그래서 프로그램이 I/O 작업 시, 다른 프로세스에게 CPU 이양하여 CPU 이용률을 높인다.

• 하지만, 프로세스의 수를 증가시키면 오히려 CPU 이용률이 뚝 떨어진다.

• 왜냐하면 thrashing이 발생했기 때문이다.

• 그래서 CPU 이용률을 최대한 높이면서 MPD를 조절하는 게 중요하다.

• 이를 조절하는 알고리즘이 워킹셋(working-set algorithum) 과 페이지 부재 빈도 알고리즘(page-fault frequency scheme) 이 있다.

5.1 워킹셋(working-set) 알고리즘

지역성 집합이 메모리에 동시 올라갈 수 있도록 보장하는 메모리 관리 알고리즘

• Locality of reference

  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조하는 현상

• Locality set(지역성 집합)

  • 집중적으로 참조되는 해당 page들의 집합

• Working-set 이란?

  • 프로세스가 일정 시간 동안 원활히 수행되기 위해, 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합
  • working-set에서의 locality set

• MPD 조절 방법

  • 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만, 그 프로세스에게 메모리를 할당
  • 그렇지 않으면 프로세스에게 할당된 페이지 프레임들을 모두 반납한 후, 프로세스의 주소 공간 전체를 disk로 swap out한다.

5.1.1 Working-set algorithum 구현

• Working Set(WS) 결정하기

  • working-set window를 사용한다.
  • window의 크기: Δ
  • time interval 사이에 참조된 서로 다른 페이지들의 집합
  • WS 크기는 변한다.

• working set 크기와 frame 수에 따른 MPD 제어

  • 워킹셋 크기 합 > frame 수 → 일부 프로세스를 스왑 아웃 → 남은 프로세스의 워킹셋이 메모리에 모두 올라가는 것을 보장 ⇒ MPD 감소 효과
  • 워킹셋 크기 합 < frame 수 → swap out한 프로세스를 다시 메모리에 적재 → working set을 할당 → MPD를 증가
  • 위 두 가지 방식으로 thrasing을 방지
  • window의 크기가 너무 작으면, 지역성 집합을 모두 수용 X
  • window의 크기가 너무 크면, 여러 규모의 지역성 집합 수용 가능하지만, MPD가 감소 → CPU 이용률 감소

5.2 페이지 부재 빈도(page fault frequency: PFF) 알고리즘

프로세스의 페이지 부재율을 주기적으로 조사하고, 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 조절하여 MPD를 조절하면서 CPU 이용률을 높이는 알고리즘

• page-fault rate의 상한값과 하한값을 둔다

  • Page fault rate이 상한값을 넘으면 frame을 더 할당한다.
  • Page fault rate이 하한값 이하이면 할당 frame 수를 줄인다.

• 빈 frame이 없으면 일부 프로세스를 swap out한다.

• 모든 프로세스에게 프레임을 다 할당한 후에도 프레임이 남는 경우, 위의 swap out된 process에게 frame을 할당하여 MPD를 높인다.

Reference

• kocw 이화여자대학교 운영체제 - 반효경 교수 -
• 운영체제와 정보기술의 원리 - 반효경 지음 -