운영체제입문 - 9장

taehoyoon·2023년 6월 16일

운영체제

목록 보기

6/6

Virtual Memory

전체 프로세스가 메모리에 완전히 올라가 있지 않아도 실행을 가능하게 하는 기술

물리적 주소 공간보다 논리적 주소 공간이 훨씬 클 수 있음
여러 프로세스들이 주소 공간을 공유하게 하므로 더 효율적인 프로세스 생성 가능
더 많은 프로그램들이 동시에 실행될 수 있게 되고, 프로세스를 로드하거나 스왑하는 데 필요한 I/O가 줄어들게 됨
결과적으로 프로그램의 실행 속도를 높이는데 기여함

Virtual address space

프로세스가 메모리에 저장되는 방식의 논리적(또는 가상) 표현

프로세스는 주소 0에서 시작하여 연속적인 메모리 공간에 존재하며, 이 공간은 프로세스의 끝까지 이어짐
반면 물리적 메모리는 페이지 프레임으로 구성되며, 메모리 관리 유닛(MMU)은 논리적 페이지를 물리적 페이지 프레임에 매핑해야 합니다.
가상 메모리는 요구 페이징 또는 요구 세그멘테이션을 통해 구현될 수 있습니다.
프로그램의 가상 주소 공간에서, 스택은 최대 주소에서 시작하여 "아래쪽"으로 성장하고 힙은 "위쪽"으로 성장합니다.
힙과 스택 사이에는 큰 빈 공간(미사용 공간)이 있습니다. 힙 또는 스택이 주어진 새 페이지까지 성장할 때까지 물리적 메모리가 필요하지 않습니다.
이는 성장에 대한 여지, 동적 링크 라이브러리(DLL) 등을 위해 빈 공간을 남기는 희소한 주소 공간을 가능하게 합니다.
가상 메모리를 통해 파일과 메모리는 페이지 공유를 통해 두 개 이상의 프로세스에 의해 공유될 수 있습니다.
- 시스템 라이브러리는 가상 주소 공간에 매핑하여 공유됩니다.
- 페이지는 읽기/쓰기로 가상 주소 공간에 매핑하여 공유 메모리를 제공합니다.
- fork() 동안 페이지를 공유함으로써 프로세스 생성 속도를 높일 수 있습니다.

Demand paging

필요한 페이지만 메모리에 로드하는 기법

이 방식을 통해 액세스되지 않는 페이지는 물리 메모리에 로드되지 않음
- Swapping이 있는 페이징 시스템과 유사
프로세스가 실행되는 동안, 일부 페이지는 메모리에 있고, 일부는 보조 기억장치에 있음
- 각 페이지 테이블 항목에는 유효-무효 비트가 연결되어 있음
- (v : 메모리 내, i : 메모리 외부)
- 초기에는 모든 항목의 유효-무효 비트가 i로 설정됩니다.
MMU 주소 변환 과정에서 페이지 테이블 항목의 유효-무효 비트가 i인 경우, page fault가 발생
- page fault는 해당 페이지가 물리 메모리에 없다는 것을 나타냄

Handling Page Faults

1. 페이지 테이블을 확인하여 참조가 유효한지 무효한지 확인
2. 유효하지 않은 상태로 표시된 페이지에 대한 접근은 운영 체제로의 트랩을 일으킵니다. 이를 페이지 폴트라고 합니다.
3. 여유 프레임을 찾음
4. 페이지를 프레임으로 스왑
5. 페이지가 이제 메모리에 있음을 나타내도록 테이블 유효 비트를 'v'로 설정
6. 페이지 폴트를 발생시킨 명령을 재시작

Aspects of demand paging

"요구 페이징의 측면"에 대한 강의자료는 다음과 같이 요약할 수 있습니다:

순수 요구 페이징 : 메모리에 페이지가 없는 상태에서 프로세스를 시작합니다.
주어진 명령은 여러 페이지에 접근할 수 있습니다.
- 하지만 참조 지역성 때문에 이런 일은 매우 드뭅니다.
요구 페이징에는 하드웨어 지원이 필요합니다.
- 유효/무효 비트를 가진 페이지 테이블
- 보조 메모리 (스왑 공간을 가진 스왑 장치): 고속 디스크 또는 비휘발성 메모리(NVM) 장치
- 페이지 폴트 후 명령 재시작 기능

Stages in demand paging

운영체제에게 인터럽트 신호를 보냅니다.
사용자 레지스터와 프로세스 상태를 저장합니다.
인터럽트가 페이지 폴트임을 확인합니다.
페이지 참조가 올바른지 확인하고 디스크 상에서 페이지의 위치를 결정합니다.
무료 프레임으로 디스크에서 읽기를 요청합니다:
a. 읽기 요청이 처리될 때까지 이 장치에 대한 대기열에서 대기합니다.
b. 디바이스 탐색 및/또는 대기 시간을 대기합니다.
c. 페이지를 무료 프레임으로 전송을 시작합니다.
대기하는 동안 CPU를 다른 사용자에게 할당합니다.
디스크 I/O 서브시스템에서 인터럽트를 받습니다(즉, I/O가 완료되었습니다).
다른 사용자를 위해 레지스터와 프로세스 상태를 저장합니다.
인터럽트가 디스크로부터 발생한 것임을 확인합니다.
페이지 테이블과 다른 테이블을 수정하여 페이지가 이제 메모리에 있음을 표시합니다.
이 프로세스에 다시 CPU가 할당될 때까지 대기합니다.
사용자 레지스터, 프로세스 상태, 그리고 새로운 페이지 테이블을 복원한 후, 인터럽트된 명령을 재개합니다.

Performance of demand paging

페이지 폴트를 처리하는 데는 3가지 작업:
1. 인터럽트를 처리
2. 페이지를 읽기
3. 프로세스를 재시작

Effective Access Time(EAT)은 다음의 식으로 계산됩니다:
- EAT = (1 – p ) x 메모리 액세스 + p x (페이지 폴트 오버헤드 + 스왑 페이지 아웃 + 스왑 페이지 인)

'페이지 폴트 오버헤드': 페이지 폴트를 처리하는 데 드는 시간
'스왑 페이지 아웃': 메모리에서 디스크로 페이지를 이동하는 데 드는 시간
'스왑 페이지 인': 디스크에서 메모리로 페이지를 이동하는 데 드는 시간

Demand paging example

메모리 접근 시간은 200 나노초이고, 평균 페이지 폴트 서비스 시간은 8 밀리초입니다.
- 그러므로, 효과적인 액세스 시간(EAT)는 (1 – p) x 200 + p x 8,000,000 = 200 + p x 7,999,800 입니다.
1,000번의 액세스 중 1번이 페이지 폴트를 일으키면, EAT는 8.2 마이크로초입니다. 이는 40배의 속도 저하를 의미합니다.
성능 저하를 10% 미만으로 유지하려면, 다음 조건을 만족해야 합니다:
- 220 > 200 + 7,999,800 x p → 20 > 7,999,800 x p → p < .0000025
- 이는 400,000번의 메모리 액세스 중 1번만 페이지 폴트가 발생해야 함을 의미합니다.

Copy-on-Write

부모 프로세스와 자식 프로세스가 초기에 메모리 내의 동일한 페이지를 공유하게 해주는 것

둘 중 어느 프로세스가 공유 페이지를 수정하면 그때 페이지가 복사됨
vfork() 시스템 호출은 fork()의 변형으로, 부모 프로세스는 자식 프로세스가 실행을 완료할 때까지 일시 중단하며 둘 다 같은 주소 공간을 공유함
vfork()는 copy-on-write를 사용하지 않으며, 주로 자식 프로세스가 생성 직후에 exec()를 호출하도록 설계됨

Page replacement

대부분의 운영체제는 swapping과 page replacement 섞어 씀
메모리 과할당을 방지
오버헤드를 줄이기 위해 수정 비트(또는 dirty 비트)가 사용
페이지 교체는 논리 메모리와 물리 메모리 사이의 분리를 완성

Page fault service routine

디스크에서 원하는 페이지의 위치를 찾습니다.
빈 프레임을 찾습니다:
a. 만약 빈 프레임이 있다면, 이를 사용합니다.
b. 빈 프레임이 없다면, 페이지 교체 알고리즘을 사용해 희생될 프레임을 선택합니다.
c. 해당 프레임이 수정된 경우(즉, dirty인 경우), 디스크에 이를 기록합니다.
원하는 페이지를 새롭게 비어있는 프레임에 읽어들이고, 페이지와 프레임 테이블을 업데이트합니다.
트랩을 발생시킨 명령을 다시 시작하여 프로세스를 계속 진행합니다.

이제 페이지 폴트의 경우 두 번의 페이지 전송이 이루어질 수 있습니다. 이는 EAT(Effective Access Time, 효과적인 접근 시간)을 증가시킵니다.

Demand Paging Algorithms

Demand Paging을 구현하기 위해 해결해야 할 주요 문제는 두 가지입니다.

Frame 할당: 각 프로세스에 대해 얼마나 많은 프레임을 할당할지 결정해야 합니다.
페이지 교체: 어떤 프레임을 교체할지 결정해야 합니다.
- 페이지 폴트 비율이 가장 낮은 프레임을 선택하고자 합니다.

각 알고리즘을 평가하기 위해 특정한 메모리 참조 문자열(참조 스트링)을 실행하고 해당 문자열에서의 페이지 폴트 수를 계산합니다.

FIF0 Page Replacement

페이지를 교체해야 할 때, 가장 오래된 페이지가 선택됨

알고리즘 시뮬레이션 예시:

프레임 수: 3 (한 번에 3개의 페이지까지 메모리에 올릴 수 있음)
페이지 폴트 횟수: 15

이 알고리즘은 가장 오래된 페이지를 교체하기 때문에, 최근에 사용되지 않은 페이지가 계속해서 메모리에 남아있을 수 있습니다. 따라서 페이지 폴트가 빈번하게 발생할 수 있습니다.

Belady's anomaly

할당된 프레임 수가 증가함에 따라 페이지 폴트 비율이 증가할 수 있는 현상

즉, Belady의 이상 현상은 일반적으로 페이지 교체 알고리즘에서는 프레임 수가 증가할수록 페이지 폴트 비율이 감소하는 것이 기대되지만, 일부 경우에는 프레임 수가 증가함에 따라 페이지 폴트 비율이 오히려 증가할 수 있다는 것을 의미합니다.

Optimal page replacement

든 알고리즘 중에서 가장 낮은 페이지 폴트율
Belady’s anomaly에 영향 X
OPT알고리즘은 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체
참조 문자열의 미래 지식을 필요

LRU page replacement

최근 과거를 가까운 미래의 근사치로 사용
각 페이지와 해당 페이지의 마지막 사용 시간을 연결
가장 오랫동안 사용되지 않은 페이지를 교체
일반적으로 좋은 알고리즘이며 자주 사용됨

LRU 구현

Counter 구현법:
- 모든 페이지 항목에는 타임스탬프가 있음
- 페이지가 참조될 때마다 시간을 타임스탬프에 복사
- 가장 작은 타임스탬프 값을 가진 페이지를 교체
  이때 테이블을 통한 검색이 필요
Stack 구현법:
- 페이지 번호의 스택(이중 링크 형태)을 유지
- 페이지가 참조될 때마다 스택(가능하면 중간)에서 페이지를 제거하고 맨 위에 놓습니다. 이 과정은 최대 6개의 포인터 변경이 필요합니다.
- 각 업데이트는 비용이 많이 들지만, 페이지 교체를 위한 검색이 필요하지 않습니다

LRU(Least Recently Used)와 OPT(Optimal) 알고리즘은 벨라디 이상현상(Belady's Anomaly)이 발생하지 않는 스택 알고리즘

Second-Chance Algorithm

FIFO (First-In-First-Out) 알고리즘에 참조 비트(reference bit)를 추가한 알고리즘

규칙:

참조 비트(reference bit)가 0이면 해당 페이지를 교체
참조 비트가 1이면:
- 두 번째 기회(second chance)를 줍니다
- 참조 비트를 0으로 설정하고 도착 시간을 현재 시간으로 재설정합니다.
- 다음 FIFO 페이지로 이동하며 동일한 규칙을 적용합니다.

원형 큐로 구현
페이지들은 순환적으로 순회하며 참조 비트와 도착 시간을 확인하고 교체 여부를 결정합니다. 이를 통해 참조된 페이지는 더 많은 기회를 가지고 교체되지 않을 수 있습니다.

Enhanced second-chance Algorithm

개선된 Second-Chance 알고리즘은 (참조 비트, 수정 비트)라는 순서쌍을 사용하여 성능을 향상시킨 알고리즘입니다.

각 페이지는 다음 네 가지 클래스 중 하나에 속합니다:
1) (0, 0) - 최근에 사용되지 않았으며 수정되지 않음 - 교체하기 가장 좋은 페이지
2) (0, 1) - 최근에 사용되지 않았지만 수정됨 - 약간 좋지 않으며 교체하기 전에 기록을 해야 함
3) (1, 0) - 최근에 사용되었지만 깨끗함 - 곧 다시 사용될 것으로 예상됨
4) (1, 1) - 최근에 사용되었고 수정됨 - 곧 다시 사용될 것으로 예상되며 교체하기 전에 기록을 해야 함

Page-buffering

페이지 버퍼링은 특정 페이지 교체 알고리즘과 함께 사용됩니다.
항상 무료 프레임 풀을 유지합니다.
페이지 오류가 발생하면 제거할 대상 페이지를 선택합니다.
미리 무료 프레임에 페이지를 읽어옵니다.
편리할 때 대상 페이지를 쓰고 무료 프레임 풀에 추가합니다.
가능하면, 수정된 페이지의 목록을 유지합니다.
백업 저장소가 유휴 상태일 때 수정된 페이지를 쓰고 비교기를 비 수정 상태로 리셋합니다.
페이지 교체를 선택할 때 페이지를 더 이상 쓸 필요가 없습니다.
가능하면, 무료 프레임의 내용을 그대로 유지하고 그 안에 어떤 것이 있는지 주목합니다.
다시 사용하기 전에 다시 참조되면, 디스크에서 다시 내용을 로드할 필요가 없습니다.
일반적으로 잘못된 대상 프레임이 선택될 경우 발생하는 페널티를 줄이는 데 유용합니다.

Allocation of frames

각 프로세스는 최소한의 프레임 수를 필요로 함
프로세스에 할당된 프레임 수가 줄어들면 페이지 폴트 비율이 증가함
최소 프레임 수는 컴퓨터 아키텍처에 따라 정의됨

프레임의 최대 수는 사용 가능한 물리적 메모리의 양에 따라 결정
1. 고정 할당(Fixed allocation)
2. 우선순위 할당(Priority allocation)

1. Fixed Allocation

Equal Allocation

모든 프로세스에 동일한 수의 프레임을 할당하는 방식

Proportional Allocation

프로세스의 크기에 따라 프레임을 할당하는 방식

프로세스의 크기가 변하면 동적으로 할당이 조정될 수 있음

2. Priority allocation

프레임의 할당이 우선순위에 따라 결정되는 방식

프로세스의 우선순위나 크기로 우선순위 결정

Global vs. local Replacement

Global replacement

모든 프레임의 집합에서 대체할 프레임을 선택하는 방식

다른 프로세스로부터 프레임을 가져올 수 있음
이로 인해 프로세스의 실행 시간이 크게 달라질 수 있으며,
실행 시간의 예측이 어려울 수 있음
시스템 처리량이 더 크므로 일반적으로 더 많이 사용됨

Local replacement

각 프로세스가 자신에게 할당된 프레임 집합에서만 대체 프레임을 선택하는 방식

각 프로세스의 성능이 일관되게 유지
메모리가 제대로 활용되지 않을 수 있음

Reclaiming Pages

A strategy to implement global page-replacement policy

빈 프레임 목록이 제로로 감소하기 전에 대체할 페이지를 선택
빈 프레임 목록이 특정 임계값 아래로 떨어지면 페이지 대체가 트리거됨

Reapers라고 불림

Thrashing

프로세스가 실행하는 것보다 페이지를 스왑 인/아웃하는데 더 많은 시간을 보내는 상황

프레임 수가 적으면, 페이지 폴트 비율은 높아짐
- 페이지 폴트와 페이지 교체의 악순환
- 이는 CPU 이용률을 낮춥니다.
- 프로세스는 작업 집합에 최소한의 페이지 수를 가지고 있지 않습니다.
- 로컬 또는 우선 순위 페이지 교체를 사용하여 스레싱의 영향을 제한할 수 있습니다.

Locality model

함께 활발하게 사용되는 페이지의 집합

프로세스는 한 로컬리티에서 다른 로컬리티로 이동합니다.
로컬리티는 서로 겹칠 수 있습니다.
이는 프로그램 구조와 데이터 구조에 의해 결정됩니다.
스레싱이 왜 발생하나요?
- 로컬리티의 크기의 합이 전체 메모리 크기를 초과할 때 스레싱이 발생

Working-set model

Working-set model은 지역성(locality) 가정에 기반한 모델입니다.

각 프로세스 Pi의 working set은 다음과 같이 정의됩니다:

working-set window에 참조된 전체 페이지 수: Δ
- 만약 Δ가 너무 작다면, working-set은 전체 지역성을 포함하지 않을 수 있습니다.
- 만약 Δ가 너무 크다면, working-set은 여러 지역성을 포함할 수 있습니다.
- 만약 Δ = ∞ 라면, working-set은 전체 프로그램을 포함할 것입니다.
프로그램의 지역성의 근사값입니다.

D는 전체 프레임의 수를 의미하며, 다음과 같이 계산됩니다:

D = ∑ WSSi (여기서 WSSi는 Pi의 작업 집합 크기를 의미합니다)

만약 D가 사용 가능한 전체 프레임 수인 m보다 크다면, Thrashing(스래싱)이 발생합니다.

정책: 프로세스 중 하나를 중단하거나 스왑아웃합니다.

Keeping track of the working-set

워킹셋 윈도우는 프로세스의 워킹셋, 즉 특정 시간 동안 프로세스가 활발히 참조하는 페이지의 집합을 근사화하는 동적 개념입니다. 워킹셋을 추적하기 위해 고정 간격의 타이머 인터럽트와 참조 비트 메커니즘을 사용할 수 있습니다.

이 접근 방식에서 워킹셋 윈도우인 Δ는 특정한 참조 횟수로 설정됩니다. 예를 들어 10,000번의 참조로 윈도우를 구성할 수 있습니다. 타이머 인터럽트는 일정한 간격으로 발생하며, 예를 들어 5,000번의 참조마다 인터럽트가 발생합니다. 각 페이지는 현재 인터벌을 나타내는 참조 비트와 이전 인터벌을 나타내는 참조 비트 두 개를 가지고 있습니다.

타이머 인터럽트가 발생하면 시스템은 모든 페이지의 참조 비트 값을 복사하고 0으로 설정합니다. 메모리에 있는 어떤 페이지의 기존 인터벌 참조 비트 중 하나라도 1인 경우 해당 페이지는 워킹셋에 속할 가능성이 높다는 것을 나타냅니다.

이러한 방식은 워킹셋을 근사화하는데 도움을 주지만 완전히 정확하지는 않습니다. 정확도를 향상시키기 위해 기록 비트의 수를 늘리거나 타이머 인터럽트의 빈도를 조정할 수 있습니다. 예를 들어 10개의 기록 비트와 1000 단위의 인터럽트 빈도를 사용하면 더 정교한 워킹셋 추정이 가능합니다.

Page-fault frequency

Working-Set 모델보다 더 직접적인 접근법입니다.
"수용 가능한" 페이지-결함 빈도 (PFF)를 설정하고, 로컬 교체 정책을 사용합니다.
- 만약 실제 PFF가 하한을 밑돌면, 프로세스로부터 프레임을 제거합니다.
- 만약 실제 PFF가 상한을 초과하면, 프로세스에게 추가 프레임을 할당합니다.
- 만약 PFF가 증가하고 사용 가능한 프리 프레임이 없다면, 어떤 프로세스를 선택하여 스왑아웃합니다.

taehoyoon

어흥🦁

이전 포스트