Algorithm

Merge Sort

• 재귀로 구현하는 정렬 알고리즘

Divide and Conquer

• 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 알고리즘 설계 기법

구현 방법

1. 분할(Divide): 정렬할 배열을 거의 같은 크기의 두 부분 배열로 나눈다.

2. 정복(Conquer): 각 부분 배열을 재귀적으로 정렬한다.

3. 결합(Combine): 정렬된 부분 배열들을 하나의 정렬된 배열로 병합한다.

4. 1 ~ 3을 부분 배열의 크기가 1이 될 때까지 반복한다.

시간 복잡도

• 분할 과정: 배열을 반으로 나누는 과정이 log n번 일어납니다.

• 병합 과정: 각 단계에서 n개의 요소를 비교하고 병합합니다.
  → 전체 시간 복잡도 : O(n) * O(log n) = O(n log n)

장점

• 속도가 빠르다.

  • 시간 복잡도 : O(n log n)

단점

• 병합 과정에서 임시 배열이 필요하여 추가적인 메모리 공간을 사용한다.

• 이해와 구현이 복잡하다.

OS

지역성 이론(90 : 10 법칙)

• 프로그램이 실행될 때 90%의 시간이 10%의 코드에서 소요된다.

• 조만간 쓸 데이터만 메모리로 올리고 당분간 필요하지 않을 것 같은 데이터는 스왑영역으로 보내 성능을 향상시킨다.

디맨드 페이징

• 필요할 것 같은 데이터를 메모리로 가져오고, 쓰이지 않을 것 같은 데이터는 스왑영역으로 이동시키는 정책

• 지역성 이론을 구현한 정책

• 메모리에서 데이터를 가져오는 정책

Swap in

• 스왑 영역에서 물리 메모리로 데이터를 가져오는 과정

Swap out

• 물리 메모리에서 스왑 영역으로 데이터를 보내는 과정

Page Table Entry(PTE)

• 페이지 테이블을 이루고 있는 행
  

접근 비트

• 페이지가 메모리에 올라온 후 데이터에 접근이 있었는지 알려주는 비트

• 메모리에 읽기나 실행 작업을 했다면 1로 변경된다.

변경 비트

• 페이지가 메모리에 올라온 후 데이터에 변경이 있었는지 알려주는 비트

• 메모리에 쓰기 작업을 했다면 1로 변경된다.

유효 비트

• 페이지가 물리 메모리에 있는지 알려주는 비트

• 유효비트 1 : 페이지가 스왑영역에 있음

• 유효비트 0 : 페이지가 물리 메모리에 있음

읽기/쓰기/실행 비트(권한 비트)

• 해당 메모리에 접근권한이 있는지 검사하는 비트

Page Fault

• 프로세스가 가상 메모리에 접근요청을 했을 때 MMU(메모리 관리자)는 페이지 테이블을 보고 물리 메모리의 프레임을 찾아낸다.

  • 물리 메모리에 프레임이 없다면 MMU는 Page Fault라는 인터럽트를 발생시킨다.

• Page Fault가 발생하면 스왑영역에 접근하고 해당 프로세스는 대기 상태가 된다.
  → 스왑 영역의 데이터가 메모리로 올라가는 작업을 수행한다.
  → 데이터가 물리 메모리로 올라가는 경우 해당 프로세스가 실행 상태로 변경된다.

공간의 지역성

• 현재 위치와 가까운 데이터에 접근할 확률이 높다.

시간의 지역성

• 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높다.

페이지 교체 정책

• 메모리가 꽉찼을 때 어떤 페이지를 스왑영역으로 보낼지 결정하는 정책

무작위로 교체하는 방법

• 지역성을 고려하지 않는다.

• 자주 사용되는 페이지가 선택될 수 있어 성능이 좋지 않다.
  → 거의 사용되지 않는다.

FIFO(First-In First-Out)

• 메모리에 들어온지 가장 오래된 페이지를 교체한다.
  → 자주 사용하는 페이지가 교체될 수 있다.

• 구현이 간단하고 성능이 나쁘지 않아 변형해서 사용된다.

• H/W 적으로 접근비트를 지원하지 않는다면 FIFO를 사용해야 한다.

Belady's Anomaly

• Page Fault를 줄이려고 메모리를 더 늘려서 프레임의 수를 늘렸는데 오히려 Page Fault가 더 많이 발생하는 현상

• FIFO에서만 발생한다.

2차 기회 페이지 교체 알고리즘

• FIFO 방식에서 자주 사용하는 페이지에게는 또 한번의 기회를 준다.

• FIFO와 동일하게 동작하지만 Page Fault 없이 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장시켜 준다.

Optimum

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다.
  → 이후에 어떤 요청이 들어올지 알고 있어야 한다.
  → 사실상 구현이 불가능한 이론적인 방법

• 다른 알고리즘과 성능 비교를 할 때 참고용으로 사용된다.

LRU(Least Recently Used)

• 시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다.

• Optimum 알고리즘에 근접한 성능을 갖는다.

• 프로그램이 지역성을 띄지 않을 때는 성능이 떨어진다.

• PTE에 시간을 기록하려면 비트가 많이 필요하다.
  → 비트를 많이 사용하는 것은 어렵기 때문에 접근비트를 이용하여 LRU에 근접하게 구현한다.

Clock Algorithm

• 접근 비트 하나만을 사용하여 구현하는 알고리즘

• 일정 시간 간격마다 모든 페이지의 접근 비트를 0으로 초기화한다.

  • 페이지가 참조되는 경우 1로 설정된다.
    ⇒ 일정 시간 간격마다 페이지가 참조되었는지 참조되지 않았는지 알 수 있다.

• 페이지를 원형으로 연결한다.

• Page Fault가 발생해서 스왑영역으로 보내야 하는 경우

  • 클락 핸드는 현재 참조하고 있는 접근 비트를 본다.

  • 해당 비트가 1인 경우 해당 비트를 0으로 변경하고 다음 비트를 바라본다.

  • 접근 비트가 0인 페이지를 발견하면 해당 페이지를 스왑 영역으로 보낸다.

Clock Hand

• 스왑영역으로 옮길 페이지를 가르키는 포인터

• 시계 방향으로 돈다.

Enhanced Clock Algorithm

• 접근 비트만 이용하는 것이 아니라 변경 비트도 함께 사용하는 알고리즘

• 스왑 영역으로 보내지는 가장 우선순위

  1. 접근 비트 : 0, 변경 비트 : 0

  2. 접근 비트 : 0, 변경 비트 : 1

  3. 접근 비트 : 1, 변경 비트 : 0

  4. 접근 비트 : 1, 변경 비트 : 1

스레싱

• 프로세스들이 실제 실행되는 시간보다 페이지를 교체하는 데에 더 많은 시간을 사용하고 있는 현상
  ⇒ 페이지 부재(page fault)가 과도하게 발생하여 CPU 이용률이 급격히 떨어지는 현상

• 다중 프로그래밍의 정도가 높아져 각 프로세스에 할당된 메모리가 부족해지면서 발생

• CPU 이용률 저하 → 운영체제의 다중 프로그래밍 증가 → 페이지 부재 증가의 악순환이 반복

• 근본적인 원인 : 물리 메모리의 크기가 부족한 것
  → 메모리의 크기를 늘려서 해결(H/W 수준)할 수 있다.

S/W 수준의 해결 방법

• 프로세스가 실행되면 일정량의 페이지를 할당한다.
  → Page Fault가 빈번하게 발생하는 경우 : 더 많은 용량의 페이지를 할당한다.
  → Page Fault가 거의 없는 경우 : 적은 용량의 페이지를 할당한다.

워킹셋

• 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합

• 프로그램의 지역성(Locality) 특성을 이용한 개념

• 자주 참조되는 워킹셋을 주기억장치에 유지함으로써 페이지 부재와 교체를 줄인다.

• 시간에 따라 자주 참조하는 페이지들의 집합이 변화하므로 워킹셋도 동적으로 변한다.

• 컨텍스트 스위칭에서 사용된다.