[운영체제] Chapter 9. Virtual Memory (2)

[운영체제] Chapter 9. Virtual Memory (2)

2023. 1. 19. 17:00ㆍCS/운영체제

728x90

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

다양한 캐슁 환경, LRU와 LFU 알고리즘의 구현, Paging System에서 LRU, LFU가 가능한가?, Clock Algorithm, Page Frame의 Allocation, Global vs Local Replacement, Thrashing, Thrashing Diagram, Working-Set Model, Working-Set Algorithm, PFF(Page-Fault Frequency), Scheme, Page Size의 결정

3. Page replacement(페이지 교체)

3-6. 다양한 캐슁 환경

캐슁 기법: 한정된 빠른 공간(= 캐시)에 요청된 데이터를 저장해 두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식
- 빠른 공간: D램(physical memory), 느린 공간: 디스크의 스왑 영역(backing store)
페이징 시스템 외에도 cache memory, buffer caching, Web chaching 등 다양한 분야에서 사용된다.
- cache memory: CPU가 메모리를 접근할 때 메인 메모리를 접근하기 전에 요청된 내용이 캐시 메모리에 있는지 살펴보고 없는 경우에만 메인 메모리에 요청하는 방법
- buffer caching: 파일 시스템에 대한 read/write 요청을 메모리에서 빠르게 서비스하는 방법(느린 공간: 디스크의 파일 시스템)
- Web caching: 웹페이지에 대한 요청을 하면 웹서버에서 그 페이지를 가져와서 웹브라우저에 표시하는데, 동일한 요청에 대해서는 내 컴퓨터에 저장해 두었다 빠르게 표시하는 방법
캐시 운영의 시간 제약
- replacement algorithm에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없다.
- buffer caching이나 web caching의 경우 → O(1)에서 O(log n) 정도까지 허용
- Paging system의 경우
  - 페이지가 이미 메모리에 존재하는 경우 OS에게 CPU가 넘어가지 않고 하드웨어적으로 주소 변환을 해서 CPU로 읽어 들이기 때문에 디스크에서 메모리로 올라오는 참조 시각 등의 정보를 OS가 알 수 없다.
  - page fault가 발생한 경우 I/O 작업이 필요하기 때문에 page fault trap이 발생하고 CPU의 제어권이 OS로 넘어간다.
  - OS에게 주어지는 정보는 page fault가 발생할 때뿐인 반쪽자리 정보뿐이기 때문에 O(1)인 LRU의 list 조차 조작 불가능해서 virtual memory의 Paging System에서는 LRU, LFU 등을 사용할 수 없다.
⇒ virtual memory의 Paging System에서는 Clock Algorithm 사용

3-7. Clock Algorithm

시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않은 페이지를 교체하는 방법
LRU(Least Recently Used)의 근사 알고리즘
- LRU 알고리즘이 가장 오래전에 참조된 페이지를 교체하는 것에 비해 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체한다.
- 즉 최근에 참조되지 않은 페이지를 교체 대상으로 선정한다는 측면에서 LRU와 유사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다.
Second change algorithm, NUR(Not Used Recently) 또는 NRU(Not Recently Used) 알고리즘으로도 불린다.
대부분의 시스템에서 페이지 교체 알고리즘으로 클럭 알고리즘을 채택한다.

교체 대상 페이지를 찾기 위해 클럭 알고리즘은 메모리에 현재 올라와 있는 페이지의 참조 비트(reference bit) 정보를 시계방향으로 따라가며 조사한다.
시곗바늘이 가리키는 페이지의 참조 비트가 1인 경우 참조 비트를 0으로 바꾼 후 시곗바늘을 한 칸 진행시키고 참조비트가 0인 페이지를 찾으면 그 페이지를 교체한다.
- 그 페이지가 참조되면 HW의 도움으로 1로 자동 세팅된다.
- 참조비트가 0이라면 그 시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않았다는 뜻
- 페이지가 참조되지 않아서 교체될 때 참조 비트를 1 → 0으로 세팅하는 것은 OS의 몫이다 - (아마도)

Clock algorithm의 개선
- reference bit과 modified bit(= dirty bit)을 함께 사용한다.
- reference bit == 1이면 최근에 참조된 페이지
- modified bit == 1이면 최근에 변경된 페이지를 의미한다. (I/O를 동반한 페이지)
  - modified bit == 0이면 backing store에서 memory로 적재한 후에 write가 발생하지 않아 변경이 없어 메모리에서 그냥 쫓아내도 된다. backing store에 동일한 copy가 존재
  - modified bit == 1이면 적재한 후 적어도 한 번은 CPU에서 write 했다는 것을 의미한다. 쫓겨날 때에는 backing store에 수정된 내용을 반영한 다음 쫓겨나야 한다.
- modified bit == 0이라면 disk로 swap out 되는 페이지를 disk에 써줄 필요가 없기 때문에 0인 페이지를 교체하면 더 빠른 페이지 교체를 할 수 있다.

4. 페이지 프레임의 할당

Allocation Problem: 프로세스 여러 개가 동시에 수행되는 상황에서는 각 프로세스에 얼마만큼의 메모리 공간을(= page frame)을 할당할 것인가를 결정해야 한다.
Allocation Scheme
- Equal allocation: 모든 프로세스에 똑같은 개수의 페이지 프레임을 할당
- Proportional allocation: 프로세스의 크기에 비례해 페이지 프레임을 할당
- Priority allocation: 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당
Allocation의 필요성
- 현재 수행 중인 프로세스의 수가 지나치게 많을 경우 프로세스당 할당되는 메모리 양이 과도하게 적어질 수 있다.
- CPU에서 명령을 실행할 때 프로세스의 주소 공간 중 코드, 데이터, 스택 등 각기 다른 영역을 동시에 참조하는데, 코드 영역만 메모리에 올라와있다고 해서 page fault가 나지 않는 것이 아님
  → 명령어 수행을 위해 적어도 일정 수준 이상의 페이지 프레임을 각 프로세스에 할당해야 한다.
- 반복문을 구성하는 페이지들을 한꺼번에 메모리에 올려놓은 것이 유리하다 → 반복문을 구성하는 페이지의 수보다 적은 양의 프레임을 할당한다면 매 반복마다 page fault 발생한다.

5. 전역(Global) 교체와 지역(Local) 교체

교체할 페이지를 선정할 때, 교체 대상이 될 프레임의 범위를 어떻게 정할지에 따라
Global replacement: 모든 페이지 프레임이 교체 대상이 될 수 있는 방법
- 프로세스마다 메모리를 할당하는 것이 아니라 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법 - 미리 할당하지 않음
- 페이지 교체 시 다른 프로세스에 할당된 프레임을 빼앗아올 수 있는 방식
- FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용 시
- Working set, PFF 알고리즘 사용
- 문제점) 특정 프로그램이 메모리를 독식할 수 있음
Local replacement: 자기 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법
- FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시

6. Thrashing, 스레싱

프로세스의 원활한 수행에 필요한 최소한의 페이지 프레임 수를 할당받지 못한 경우 발생한다.

Thrashing이 발생
- → page fault rate이 매우 높아짐
- → CPU utilization이 낮아짐
  - 메모리에 올라와 있는 프로세스의 수가 너무 적어 이들 프로세스가 모두 I/O 작업을 함으로써 준비큐가 비는 경우가 발생했다는 뜻
- → OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
  - CPU 이용률이 낮으면 운영체제는 메모리에 올라가는 프로세스의 수를 늘리게 된다.
- → 또 다른 프로세스가 시스템에 추가됨 (higher MPD)
- → MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리의 양이 지나치게 감소된다.
- → 프로세스는 page의 swap in / swap out으로 매우 바쁨
  - 최소한의 페이지 프레임도 할당받지 못하는 상태가 되어 page fault가 빈번히 발생하게 된다.
  - page fault가 발생하면 디스크 I/O 작업을 수반하므로 문맥교환을 통해 다른 프로세스에게 CPU 이양
  - 다른 프로세스 역시 할당받은 메모리 양이 적어 page fault ~ 문맥 교환
- → 대부분의 시간에 CPU는 한가함
  - 모든 프로세스가 다 page fault를 발생시켜 시스템은 page fault를 처리하느라 매우 분주해지고 CPU의 이용률은 급격히 떨어진다.
- → low throughput
메모리 내에 존재하는 프로세스의 수를 증가시키면 CPU 이용률은 이에 비례해서 증가하지만 어느 한계치를 넘어서면 CPU 이용률이 급격하게 떨어진다. 따라서 스레싱이 발생하지 않도록 하면서 CPU 이용률을 높일 수 있도록 MPD를 조절하는 것이 필요하다.

6-1. Working-Set Model

지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘
- 지역성(locality of reference): 프로세스는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다. 이렇게 집중적으로 참조되는 페이지들의 집합을 locality set이라 한다.
working set: 지역성에 기반하여 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합
- Working set window를 통해 알아낼 수 있다. 미리 알 수 없고 과거로 추정한다.
- working set의 결정: (window size가 Δ인 경우) Time interval [t-Δ, t] 사이에 참조된 서로 다른 페이지들의 집합으로 정의
  - working set에 속한 페이지는 메모리에 유지하고 속하지 않은 것은 버린다.
  - 참조된 Δ 시간 동안 해당 페이지를 메모리에 유지한 후 버린다.
  - working set의 크기는 시간이 흐름에 따라 변한다 → 일종의 동적인 프레임 할당 기능까지 수행
Working Set 모델에서는 프로세스의 working set 전체가 메모리에 올라와있어야 수행되고, 그렇지 않을 경우 모든 프레임을 반납한 후 swap out
Working Set 알고리즘이 Global replacement를 사용하지만, (이 프로그램에게 몇 개의 프레임을 할당하겠다) + (스왑 아웃 시키겠다)의 개념이 같이 들어가 있음 = 미리 할당하지 않고, 그때그때 필요한 만큼 할당을 하면서 필요 없으면 메모리를 줄이고 늘리고

⇒ 이와 같은 방법으로 Working-Set 알고리즘은 MPD를 조절하고 스레싱을 방지한다.

working set 알고리즘은 메모리에 올라와 있는 프로세스들의 working set 크기의 합이 프레임의 수보다 클 경우 일부 프로세스를 스왑 아웃시켜 남은 프로세스의 워킹 셋이 메모리에 모두 올라가는 것을 보장한다.
- working set size의 합 > page frame의 수 - MPD를 줄임
- working set을 다 할당하고도 page frame이 남는 경우 - MPD를 키움
window size Δ
- Δ가 너무 작으면 지역성을 모두 수용하지 못함
- Δ가 너무 크면 MPD가 감소해 CPU 이용률이 낮아질 수 있음

6-2. PFF(Page-Fault Frequency) Scheme, 페이지 부재 빈도 알고리즘

PPF(Page-Fault Frequency: 페이지 부재 빈도) 알고리즘은 프로세스의 page fault rate를 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리의 양을 동적으로 조절한다.
page-fault rate > 상한선: 프로세스에 할당된 프레임의 수가 부족하다고 판단하여 프레임을 추가로 할당
- 추가로 할당할 빈 프레임이 없다면 일부 프로세스를 스왑 아웃시켜 메모리에 올라가 있는 프로세스의 수를 조절
page-fault rate < 하한선: 프로세스에게 필요 이상으로 많은 프레임이 할당된 것으로 간주해 할당된 프레임의 수를 줄인다.
- 프레임이 남는 경우 스왑 아웃되었던 프로세스에게 프레임을 할당함으로써 MPD를 높인다

⇒ PPF 알고리즘에서는 이러한 원리로 MPD를 조절하면서 CPU 이용률을 높이는 동시에 스레싱을 방지한다.

7. page size의 결정

보통 page size는 4KB
page size를 감소시키면
- 페이지 수 증가
- 페이지 테이블 크기 증가 ~ 페이지 테이블을 위한 공간 낭비 심화
- 내부 조각 감소 ~ 메모리 사용의 효율성 증대
- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적이지만 - (범위가 좁아) 지역성의 활용 측면에서는 좋지 않음
- Disk transfer의 효율성이 감소한다. Seek 시간이 많이 소요 ~ 한 번 이동할 때 많이 가져오면 효율적이다.
32 bit → 64 bit, 메모리의 증가로 더 큰 크기의 페이지의 트렌드가 있다.

[복습]

주소 변환 시 OS는 page fault가 발생했을 때만 swap in 참조 시각 등의 정보를 확인할 수 있기 때문에 virtual memory의 paging system에서는 LRU, LFU 등을 사용할 수 없다. ⇒ Clock Algorithm 사용
Clock Algorithm: 시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않은 페이지를 교체하는 방법
- 오랫동안 참조되지 않은 페이지 중 하나를 교체
- 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다.
- reference bit, modified bit
페이지 프레임의 할당: 각 프로세스에게 얼마만큼의 에모리 공간을 할당할 것인가를 결정해야 한다. page fault 발생 빈도를 최소화하는 것이 목표
전역 교체: 모든 페이지 프레임이 교체 대상
지역 교체: 자기 프로세스에게 할당된 프레임 내에서만 교체 대상 선정
스레싱: 프로세스의 원활한 수행에 필요한 페이지 프레임 수를 할당받지 못한 경우 발생
- page fault rate이 높아짐, CPU utilization이 낮아짐, OS는 MPD를 높여야 한다고 판단, 프로세스는 page swap in, out으로 매우 바쁨, CPU는 대부분 한가함, low throughput
워킹 셋: 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합
- 크기는 시간의 흐름에 따라 동적으로 변한다.
- working set 모델에서는 프로세스의 워킹 셋 전체가 메모리에 올라와 있어야 수행할 수 있다. 그렇지 않은 경우 모든 프레임을 반납한 후 swap out 되어 남은 프로세스의 워킹 셋이 메모리에 모두 올라가는 것을 보장한다.
PFF(Page-Fault Frequency): page fault rate를 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리의 양을 동적으로 조절하는 방법
- page-fault rate > 상한선: 프레임을 추가로 할당
- page-fault rate < 하한선: 할당된 프레임 수를 줄임

이화여자대학교 반효경 교수님의 [2014년 1학기 운영체제], [2017년 1학기 운영체제] 강의 정리입니다.

반효경 교수님의 [운영체제와 정보기술의 원리] 교재를 참고하였습니다. 감사합니다.

https://core.ewha.ac.kr/publicview/C0101020140513133424380501?vmode=f

반효경 [운영체제] 23. Virtual Memory 2

설명이 없습니다.

core.ewha.ac.kr