<쉽게 배우는 운영체제> 조성호 지음. 을 읽으며 작성한 개인노트입니다.

01 요구 페이징

가져오기 정책: 프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정한다
요구 페이징 (Demand paging): 프로세스가 요청할 때 메모리로 가져오는 가져오기 정책

1) 요구 페이징의 개요

• 메모리에는 꼭 필요한 프로세스만 유지해야 시스템이 느려지지 않는다
• 용량이 큰 프로세스를 실행할 때 운영체제는 프로세스의 필요한 모듈만 메모리에 올려 실행하고, 나머지는 필요할 때 메모리로 불러온다
  • 메모리를 효율적으로 관리하기 위해서
    • 메모리가 꽉차면 관리하기 어려움
  • 응답 속도 향상

미리 가져오기

• 요구 페이징과 반대
• 앞으로 필요할 것이라 예상되는 페이지를 미리 가져오기
• (예) 캐시
• 미리 가져온 데이터가 쓸모없으면 피해가 큼

Swapping
순수한 스와핑: 프로세스를 구성하는 모든 페이지를 메모리에 올리는 것
게으른 스와퍼 (Lazy swapper): 사용자가 요구할 때 메모리에 올리는 것

2) 페이지 테이블 엔트리의 구조

• 가상 메모리의 크기 = (물리 메모리의 크기) + (스왑 영역의 크기)
  • 스왑 영역: 하드디스크에 존재하거나 메모리 관리자 관리하는 영역
    • 가상 메모리의 구성 요소 중 하나
  • 스왑인 (swap-in): 스왑 영역에서 물리 메모리로 데이터를 가져오기
  • 스왑아웃 (swap-out): 물리 메모리에서 스왑 영역으로 데이터 내보내기
• 가상 메모리 시스템에서 사용자의 프로세스는 물리 메모리와 스왑 영역 중 한 곳에 있다
  • 스왑 영역에 있는 경우
    • 요구 페이징으로 인해 처음부터 물리 메모리에 올라가지 못함
    • 메모리가 꽉차서 스왑영역으로 옮겨짐
  • 페이지가 메모리에 있는지 스왑영역에 있는지 유효 비트로 표시함

[이미지 출처]

• 페이지 번호
  • 직접 매핑 방식에서는 필요 없음
  • 연관 매핑에서는 페이지 번호 & 프레임 번호 모두 필요함
• 플래그 비트
  • 접근 비트
    • access bit, reference bit
    • 페이지가 메모리에 올라온 후 사용한 적 있는지
    • 해당 메모리에 읽기/실행 작업하면 접근 비트가 1이 됨
  • 변경 비트
    • modified bit
    • 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지
    • 해당 메모리에 쓰기/추가 작업을 하면 변경 비트가 1이 됨
    • dirty bit이라고도 불림: 데이터가 새로운 값으로 오염됐다는 뜻
  • 유효 비트
    • valid bit
    • 페이지가 실제 메모리에 있는지
    • 물리 메모리가 부족한 경우 일부 페이지가 스왑 영역으로 옮겨지기 때문에 프로세스가 물리 메모리에 접근했을 때 해당 데이터가 저장장치에 있을 수 있다는 의미
    • 유효비트가 0 >> 페이지가 메모리에 있음
    • present bit이라고도 불림: 해당 페이지가 메모리에 있는지 나타냄
  • 읽기, 쓰기, 실행 비트
    • read bit, write bit, execute bit
    • 페이지에 대한 읽기/쓰기/실행 권한을 나타냄
    • 권한이 부족하거나 없는 프로세스의 접근 차단
• 프레임 번호 (aka 주소 필드, address field)
  • 가상 주소의 해당 페이지가 어느 프레임에 있는지 표시함
  • 메모리 관리자는 프레임 번호를 이용해 가상 주소를 물리 주소로 변환함

3) 페이지 부재

• 유효 비트가 0 >> 페이지가 메모리에 있음 >> 주소 필드에 물리 메모리의 프레임 번호가 저장됨
• 유효 비트가 1 >> 페이지가 스왑 영역에 있음 >> 주소 필드에 스왑 영역 내 페이지의 주소가 저장됨

[이미지 출처]

프로세스가 페이지 3을 요청했다

• PTE3의 유효비트는 1이다 >> 스왑 영역에 위치
• PTE3의 주소 필드 값이 0이다 >> 스왑 영역의 0번에 있다

페이지를 요청했을 때 그 페이지가 메모리 없는 상황을 페이지 부재(Page fault)라고 한다

페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 가져와야 한다

[이미지 출처]

• 메모리 관리자는 스왑 영역의 0번에 있는 페이지를 메모리의 비어있는 프레임인 5로 가져온다
• 프레임 5에 페이지가 들어오면
  • PTE 3의 유효 비트는 1에서 0으로
  • PTE 3의 주소 필드는 0에서 5로 바뀜
• 프레임 5로 접근해 해당 데이터를 프로세스에 넘긴다

페이지 교체 알고리즘 (Page replacement algorithm): 어떤 페이지를 스왑 영역으로 내보낼지 결정
대상 페이지 (Victim page): 페이지 교체 알고리즘에 의해 스왑 영역으로 내보낼 페이지

메모리가 꽉 찬 상태에서 페이지 부재가 발생했다

[이미지 출처]

프로세스가 페이지 4를 요청했다

1. 페이지 테이블을 확인하니 유효 비트가 1이다 >> 페이지 부재 발생
2. 메모리가 꽉 차있어서 스왑 영역에 있는 데이터를 가져오기 위해 메모리의 페이지 중 하나를 스왑 영역으로 내보낸다
3. 대상 페이지(victim page)의 유효 비트가 0에서 1로, 주소 필드 값이 스왑 주소로 바뀐다
4. 필요한 페이지는 스왑인으로 메모리에 올라온다
5. 페이지 4의 유효 비트가 1에서 0으로, 주소 필드값이 메모리 주소로 바뀐다

세그먼테이션 오류 vs. 페이지 부재

• 세그먼테이션 오류
  • 사용자의 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생
  • 사용자 프로세스에 의해 발생
  • 해당 프로세스를 강제 종료하여 해결
• 페이지 부재
  • 해당 페이지가 물리 메모리에 없을 때 발생
  • 사용자 프로세스와 무관
  • 메모리 관리자는 스왑 영역에서 해당 페이지를 물리 메모리로 옮겨서 해결함

4) 지역성

지역성 (Locality): 기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질

• 공간 지역성
  • spatial locality
  • 현재 위치에서 가까운 데이터에 접근할 확률 > 먼 거리에 있는 데이터에 접근할 확률
• 시간 지역성
  • temporal locality
  • 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 사용될 확률 > 먼 시간에 접근한 데이터가 사용될 확률
• 순차적 지역성
  • sequential locality
  • 여러 작업이 순서대로 진행되는 경향이 있음

---

02 페이지 교체 알고리즘

1) 페이지 교체 알고리즘의 개요

페이지 부재: 프로세스가 요구한 페이지가 현재 메모리에 없으면 발생

페이징 교체 알고리즘

• 페이지 부재가 발생했고 메모리가 꽉 찬 경우, 메모리에 있는 페이지 중 어느 것을 스왑 영역으로 내보낼지 결정한다
• 앞으로 메모리에서 사용할 가능성이 낮은 페이지를 대상 페이지로 선정하고자 한다
  • 페이지 부재 줄이기
  • 시스템 성능 향상

1.1 페이지 교체 알고리즘의 종류

[이미지 출처]

2) 무작위 페이지 교체 알고리즘

• Random page replacement algorithm
• 구현이 가장 간단함
• 특별한 로직 없이 무작위로 대상 페이지 선정
• 성능이 좋지 않음

3) FIFO 페이지 교체 알고리즘

• 선입선출 페이지 교체 알고리즘, First-in First-Out page replacement algorithm
• 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정
• 큐로 구현함
  • 메모리의 맨위에 있는 페이지 == 가장 오래된 페이지
  • 새로운 페이지는 맨 아래에 삽입
• 단점
  • 메모리에 먼저 올라왔어도 자주 사용되는 페이지와 나중에 올라왔어도 한 번만 사용되는 페이지
  • 성능 저하
• 2차 기회 페이지 교체 알고리즘이 위 단점 해결

4) 최적 페이지 교체 알고리즘

• Optimal page replacement algorithm
• 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮김
• 페이지 교체 선정 시점부터 사용시점까지 가장 먼 페이지를 대상 페이지로 선정
• 실제로는 구현 불가

LRU 페이지 교체 알고리즘

• Least recently used
• 최근 최소 사용 알고리즘
• 페이지에 접근한 시간을 기준으로 대상 페이지 선정
  • 현재와 시간차가 가장 큰 시점에 사용된 페이지

LFU 페이지 교체 알고리즘

• Least frequently used
• 최소 빈도 사용 알고리즘

5) LRU 페이지 교체 알고리즘

• Least recently used page replacement algorithm
• 최근 최소 사용 페이지 교체 알고리즘
• 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮김

5.1 페이지 접근 시간에 기반한 구현

• 메모리 접근 패턴을 변경하면 성능이 저하됨
• 추가 메모리 공간을 필요로 함
  • 0~1024초를 표시하려면 10bit 필요

5.2 카운터에 기반한 구현

• 추가 메모리 공간을 필요로 함
  • 카운트 기록용

5.3 참조 비트 시프트 방식

• reference bit shift
• 각 페이지에 일정 크기의 참조 비트를 만든다
  • 초기값: 0
  • 페이지에 접근할 때마다 1로 바뀜
  • 주기적으로 오른쪽으로 한칸씩 이동(shift)한다
• 추가적인 1B 사용

6) LFU 페이지 교체 알고리즘

• 최소 빈도 사용 알고리즘
• 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지 선정
  • 현재 프레임에 있는 페이지마다 그 동안 사용된 횟수를 센다
  • 가장 적은 페이지를 스왑 영역으로
• LRU와 성능이 비슷함
  • LRU, LFU 모두 FIFO보다 성능이 우수함
• 단점
  • 페이지 접근 횟수를 표시하는 추가 공간이 필요함 >> 메모리 낭비

7) NUR 페이지 교체 알고리즘

• Not Used Recently page replacement algorithm
  • LFU/LRU 알고리즘과 비슷한 성능
  • 불필요한 공간 낭비 문제를 해결함
• 최근 미사용 페이지 교체 알고리즘
• 알고리즘에서 접근 시간/빈도의 정확한 값을 유지하는 것은 공간만 차지하고 의미있는 성능을 내지 않음
  • 그래서 NUR은 추가 비트 2개만 이용함
• 2개의 비트: 참조 비트, 변경 비트
  • 참조 비트: 페이지에 접근 (read/execute)하면 1이 됨
    • PTE의 접근 비트를 가르킴
      • PTE: Page Table Entry
  • 변경 비트: 페이지가 변경 (write/append)되면 1이 됨
    • PTE의 변경 비트를 가르킴
  • 각 비트의 초기 값은 0임 (0, 0)
• 알고리즘에서 대상 페이지를 선정할 때:
  • (0, 0), (0, 1), (1, 0), (1, 1) 중에
  • 1. (0, 0)인 페이지를 가장 먼저 선정한다
  • 2. 그 다음 (0, 1)인 페이지
  • 3. 그 다음 (1, 0)인 페이지
  • 4. 마지막으로 (1, 1)인 페이지
• 알고리즘 원리
  • 우선 참조 비트가 0인 페이지를 찾는다
  • 없으면 변경 비트가 0인 페이지를 찾는다
  • 같은 비트의 페이지가 여러 개면 무작위로 대상 페이지를 선정한다
  • 모든 페이지가 (1, 1)이 되면 모든 페이지 비트를 (0, 0)으로 초기화한다

8) FIFO 변형 알고리즘

FIFO 알고리즘은 메모리에 올라온 순서만 고려해서 성능이 좋지 않음.

2차 기회 페이지 알고리즘과 시계 알고리즘이 이러한 단점을 개선해서 성능을 향상했다

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

• second chance page replacement algorithm
• 특정 페이지에 접근해 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외한다
  • 2nd chance: 성공한 페이지를 큐의 맨 뒤로 옮겨서 (대상 페이지가 안될) 기회를 한번 더 준다
• 성능
  • LRU, LFU, NUR 페이지 교체 알고리즘보다 낮음
  • FIFO보다 높음
• 단점
  • 큐를 유지하는 비용이 높음
  • 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가됨

8.2 시계 알고리즘

• clock algorithm
• 알고리즘은 2차 기회 페이지 교체 알고리즘과 유사하지만 실제 구현이 다름
  • 2차 기회 페이지 교체 알고리즘) 큐
  • 시계 알고리즘) 원형 큐
• 시계 알고리즘
  • 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용함
  • 이 포인터가 큐의 맨 바닥으로 내려가면 다음번에는 다시 큐의 처음을 가리키게 됨
  • 포인터가 시계처럼 한 방향으로 돌아서 시계 알고리즘
• 참조 비트
  • 각 페이지에 참조 비트가 하나씩 추가됨
  • 초깃값은 0
  • 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경
• 포인터는 메모리가 꽉 차면 쫓겨날 페이지를 가리킴
• 가리키던 페이지가 스왑영역으로 쫓겨나면 대상 포인터를 밑으로 이동한다
  • 참조 비트가 1인 페이지는 건너뜀
    • 참조된 페이지는 기회를 한 번 더 준다
    • 건너뛸 때 비트를 0으로 바꾼다
      • 큐를 한바퀴 돌아왔을 때 다시 포인터가 이 페이지에 도착하면 더는 기회 없이 내쫓길 수 있다
  • 메모리 바닥에 도착하면 원형 큐처럼 다시 메모리의 상단으로 이동
• 결론
  • 대상 포인터 & 참조 비트만 추가하면 돼서 공간 소모는 적지만,
  • 알고리즘이 복잡하고 계산량이 많음

---

03 스레싱과 프레임 할당

운영체제는 물리 모메리의 공간이 충분하면 프로세스의 요청에 따라 원하는 프레임을 할당하지만,
충분하지 못한 경우 남아있는 프레임을 어떻게 나누어주느냐에 문제가 생긴다

1) 스레싱

1.1 스레싱의 개념

스레싱(Thrashing): 하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태

1.2 물리 메모리의 크기와 스레싱

멀티프로그래밍 정도(Degree of multiprogramming)

• 동시에 실행하는 프로그램의 수
• 멀티프로그래밍 정도가 너무 높으면 스레싱이 발생함

[이미지 출처]

• 프로그램 수가 적으면 CPU 사용률이 계속해서 증가함
• 메모리가 꽉 차면 CPU가 작업하는 시간보다 스왑 영역으로 페이지를 보내고 새로운 페이지를 메모리에 가져오는 작업이 빈번해짐
• 결국 CPU가 작업할 수 없는 상태에 이르게 됨 >> 스레싱 발생 지점 (Thrashing point)

자주 사용하는 프로세스가 필요로 하는 메모리보다 물리 메모리가 작으면 스레싱 발생 지점에 빨리 도달하여 컴퓨터가 전체적으로 느려진다. 물리 메모리를 늘리면 스레싱 발생 지점이 늦춰져서 프로세스를 잘 실행할 수 있다. 하지만 일정 수준의 메모리 크기에 도달하면 그 후부터는 늘려도 성능이 좋아지지는 않는다

1.3 스레싱과 프레임 할당

실행 중인 여러 프로세스에 프레임을 얼마나 나누어주느냐에 따라 시스템의 성능이 달라짐

• 너무 적은 프레임을 할당하면 페이지 부재가 빈번히 일어남
• 너무 많은 프레임을 할당하면 메모리가 낭비됨 >> 전반적인 시스템 성능 저하

2) 정적 할당

정적 할당(Static allocation): 프로세스 실행 초기에 프레임을 나눠준 후 그 크기를 고정함

균등 할당 방식과 비례 할당 방식이 존재함

2.1 균등 할당 방식

균등 할당(Equal allocation)

• 프로세스의 크기와 상관 없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당함
• 단점
  • 크기가 큰 프로세스는 필요한 만큼 프레임을 할당받지 못함
  • 크기가 작은 프로세스는 메모리가 낭비됨

2.2 비례 할당 방식

• proportional allocation
• 프로세스의 크기예 비례하여 프레임을 할당
• 프로세스의 크기를 고려하지 않는 균등할당보다는 현실적임
• 단점
  • 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못함
    • 작은 프로세스도 실행 중에 많은 메모리를 필요로 할 수도 있음
      • (예) 동영상 플레이어는 프로그램이 작지만 재생되는 동영상의 크기 때문에 플레이어 자체보다 훨씬 큰 메모리를 필요로 함
  • 사용하지 않을 메모리를 처음부터 미리 확보해서 공간을 낭비함
    • 메모리 낭비

3) 동적 할당

• 실행 중의 메모리 요구를 반영하지 못하는 정적 할당 방식의 문제점을 개선
• dynamic allocation
• 종류: 작업집합 모델, 부재 빈도 방식

3.1 작업집합 모델

• working set model
• 지역성 이론: 가장 최근에 접근한 프레임이 이후에도 또 참조될 가능성이 높다
• 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고, 이 집합에 있는 페이지들을 물리 메모리에 유지하여 프로세스의 실행을 도움
• 작업집합 크기(Working set size): 물리 메모리에 유지할 페이지의 크기
  • 작업집합에 들어갈 최대 페이지 수
  • 페이지 접근 횟수가 작업집합 크기에 도달하면 작업집합을 갱신한다
• 작업집합 윈도우(Working set window, WSW): 작업집합에 포함되는 페이지의 범위
  • 현재 시점에 최대 어느 범위까지의 페이지를 살펴볼 것인지 결정함
  • 델타로 표현
• 작업집합 윈도우의 크기에 따라 프로세스의 실행 성능이 결정됨
  • 작업집합 윈도우가 너무 크면 필요 없는 페이지가 메모리에 남아 다른 프로세스에 영향을 미침
  • 윈도가 너무 작으면 필요한 페이지가 스왑 영역으로 옮겨져서 프로세스의 성능이 떨어짐

3.2 페이지 부재 빈도

작업집합 모델은 프로세스에 프레임을 얼마나 할당해야 하는지는 알수 없음

• 프로세스의 성능을 높일 수는 있음
• 스레싱 문제는 해결하지 못함

페이지 부재 빈도 (page fault frequency)

• 페이지 부재 횟수를 기록해서 페이지 부재 비율을 계산
• 페이지 부재 비율의 상한선과 하한선을 설정해서
  • 상한선을 초과하면 할당한 프레임이 적다는 뜻
    • 프레임 추가
  • 하한선 밑으로 내려가면 메모리가 낭비된다는 뜻
    • 할당한 프레임 회수

---

04 프레임 관련 이슈

1) 전역 교체와 지역 교체

• 전역 교체 (Global replacement): 전체 프레임을 대상으로 교체 알고리즘 적용
• 지역 교체 (Local replacement): 현재 실행 중인 프로세스의 프레임을 대상으로 교체 알고리즘 적용
  • 장점
    • 자신에게 할당된 프레임의 전체 개수에는 변화가 없음
    • 페이지 교체가 다른 프로세스에 영향을 미치지 않음
      • 다른 프로세스의 페이지 교체 때문에 스레싱이 발생하지는 않을 것
  • 단점
    • 자주 사용하는 페이지가 스왑 영역으로 옮겨져 시스템의 효율이 떨어짐
• 결론) 전체 시스템의 입장에서는 전역 교체 방식이 더 효율적임

2) 페이지 테이블 크기

• 메모리에 있는 모든 프로세스마다 각각의 페이지 테이블이 필요함
• 페이지 테이블의 크기를 줄이기 위해 한 페이지의 크기를 크게 하면 좋겠지만 무작정 페이지의 크기를 늘리면 내부 단편화 문제가 일어날 수 있음

내부 단편화(Internal fragmentation): 실행 프로그램보다 남은 메모리 공간이 더 커서 사용공간을 할당한 후에도 작은 남는 공간이 생기는 현상

---