이 글은 고려대학교 김민호 교수님의 운영체제강의를 토대로 작성한 글입니다.
This post is based on the operating system lecture by Prof. Kim Min-ho of Korea University.
#10. Virtual Memory
Background
❖ 코드는 실행을 위해 메모리에 있어야 하지만, 전체 프로그램이 거의 사용되지 않습니다.
• 예를 들어, 에러 코드, 이상한 루틴, 대규모 데이터 구조 등
❖ 전체 프로그램 코드가 동시에 필요하지 않음
❖ 부분적으로 로드된 프로그램을 실행할 수 있는 능력을 고려
• 프로그램은 더 이상 물리적 메모리의 제한에 구속되지 않음
• 각 프로그램이 실행 중에 적은 메모리를 차지하며 -> 동시에 더 많은 프로그램 실행 가능
• 응답 시간 또는 처리 시간 증가 없이 CPU 활용률과 처리량 증가
• 프로그램을 메모리로 로드하거나 스왑하기 위해 필요한 I/O 감소 -> 각 사용자 프로그램 실행 속도 향상
❖ 가상 메모리 - 사용자의 논리적 메모리를 물리적 메모리로부터 분리
• 실행을 위해 메모리에 프로그램의 일부만 있으면 됨
• 논리적 주소 공간은 물리적 주소 공간보다 훨씬 크게 설계될 수 있음
• 여러 프로세스에 의해 주소 공간을 공유할 수 있도록 함
• 더 효율적인 프로세스 생성 가능
• 동시에 실행되는 프로그램 수가 더 많아짐
• 프로세스를 로드하거나 스왑하기 위해 필요한 I/O가 줄어듦
❖ 가상 주소 공간 - 프로세스가 메모리에 저장된 논리적인 관점
• 보통 주소 0에서 시작하여 연속적인 주소가 공간의 끝에 이르기까지
• 한편, 물리적 메모리는 페이지 프레임으로 구성됨
• 메모리 관리 장치(MMU)가 논리적 주소를 물리적 주소로 매핑해야 함
❖ 이러한 분리는 프로그래머들에게 극도로 큰 가상 메모리를 제공합니다.
❖ 프로그래머는 이제 물리적 메모리의 양을 걱정할 필요가 없습니다.
요구 페이징
❖ 프로세스 전체를 로드 시간에 메모리로 가져올 수 있음
❖ 또는 페이지가 필요할 때만 메모리로 가져올 수 있음
• 더 적은 I/O 필요, 불필요한 I/O 없음
• 더 적은 메모리 필요
• 더 빠른 응답 시간
• 더 많은 사용자
❖ 페이지가 필요하면 해당 페이지를 참조
• 무효한 참조시 중단
• 메모리에 없는 경우 메모리로 가져옴
요구 페이징
❖ 요구 페이징 시스템은 스와핑이 있는 페이징 시스템과 유사하며, 프로세스는 보조 기억장치(디스크)에 존재합니다.
❖ 프로세스 주소 공간은 요구 페이징에서 일련의 페이지로 구성됩니다.
❖ 프로세스가 생성될 때, Lazy swapper(페이지 관리자)가 사용됩니다.
• 해당 페이지가 필요하지 않으면 페이지를 절대 메모리에 스왑하지 않습니다.
• 이러한 페이지를 구별하기 위해 하드웨어 지원이 필요합니다.
유효-무효 비트
❖ 각 페이지 테이블 엔트리와 함께 유효-무효 비트가 연결됩니다.
• v: 메모리에 존재함 – 메모리 상주
• i: 메모리에 존재하지 않거나 논리적 주소 공간에 없음(무효)
❖ 처음에는 모든 엔트리의 유효-무효 비트가 i로 설정됩니다.
❖ 페이지 테이블 스냅샷의 예:
❖ MMU 주소 변환 중 페이지 테이블 엔트리의 유효-무효 비트가 i인 경우 => 페이지 폴트 발생
❖ 페이지가 메모리에 로드될 때
• 유효-무효 비트가 설정됩니다.
❖ 페이지가 디스크에 있을 때 • 유효-무효 비트가 해제됩니다.
• 프레임 값은 디스크에 있는 페이지의 주소를 포함합니다.
❖ 페이지 폴트
• 프로세스가 메모리에 없는 페이지에 접근하려고 할 때
• 페이지 폴트 트랩이 발생합니다.
페이지 폴트 처리 단계
- 페이지에 대한 참조가 있으면, 해당 페이지에 대한 첫 참조가 운영 체제로 트랩됩니다. • 페이지 폴트 발생
- 운영 체제가 내부 테이블을 확인하여 결정합니다: • 무효한 참조인 경우 → 중단 • 단순히 메모리에 없는 경우 → 3단계로 이동
- 빈 프레임을 찾습니다.
- 예약된 디스크 작업을 통해 페이지를 프레임으로 스왑합니다.
- 테이블을 재설정하여 페이지가 이제 메모리에 있음을 나타냅니다. • 유효화 비트 = v로 설정
- 페이지 폴트를 발생시킨 명령을 재시작합니다.
요구 페이징의 측면
❖ 극단적인 경우 – 메모리에 페이지가 하나도 없는 상태로 프로세스를 시작
• 운영 체제는 프로세스의 첫 번째 명령으로 명령 포인터를 설정하고, 메모리 비상주 -> 페이지 폴트 발생
• 그리고 다른 모든 프로세스 페이지도 첫 접근 시에 페이지 폴트 발생
• 순수 요구 페이징: 필요할 때까지 절대 페이지를 메모리에 가져오지 않음
❖ 실제로, 주어진 명령은 여러 페이지에 접근할 수 있음 -> 여러 페이지 폴트 발생
• 참조의 지역성 때문에 이러한 고통이 줄어듦 → 나중에 10.6장에서 다룸
❖ 요구 페이징을 위해 필요한 하드웨어 지원
• 유효/무효 비트가 있는 페이지 테이블
• 보조 기억 장치(스왑 공간이 있는 스왑 장치 → 나중에 11장에서 다룸)
프리-프레임 리스트
❖ 페이지 폴트가 발생하면 운영 체제는 보조 기억 장치에서 원하는 페이지를 메인 메모리로 가져와야 합니다.
❖ 대부분의 운영 체제는 이러한 요청을 충족시키기 위해 프리-프레임 리스트를 유지합니다 - 자유 프레임의 풀.
예시: head -> 7 -> 97 -> 15 -> 126 -> ... -> 75
❖ 운영 체제는 일반적으로 zero-fill-on-demand라는 기법을 사용하여 자유 프레임을 할당합니다
- 할당되기 전에 프레임의 내용이 0으로 지워집니다.
❖ 시스템이 시작될 때, 사용 가능한 모든 메모리가 프리-프레임 리스트에 배치됩니다.
요구 페이징의 성능 ❖ 세 가지 주요 활동
- 페이지 폴트 인터럽트 서비스
- 페이지 읽기 – 많은 시간 소요
- 프로세스 재시작 ❖ 페이지 폴트율 0 ≤ p ≤ 1
- p = 0이면 페이지 폴트 없음
- p = 1이면 모든 참조가 폴트 발생 ❖ 유효 접근 시간(EAT) EAT = (1 – p) x 메모리 접근 시간
- p (페이지 폴트 오버헤드
- 페이지 스왑 아웃
- 페이지 스왑 인)
요구 페이징 예제
❖ 메모리 접근 시간 = 200 나노초
❖ 평균 페이지 폴트 서비스 시간 = 8 밀리초
❖ 유효 접근 시간(EAT) = (1 – p) x 200 + p x 8,000,000 = (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 < 0.0000025
- 400,000번의 메모리 접근 중 하나의 페이지 폴트 이하
❖ Copy-on-Write(COW)은 부모 프로세스와 자식 프로세스가 초기에는 메모리의 동일한 페이지를 공유하도록 합니다.
- 어느 프로세스든 공유된 페이지를 수정하면, 그때서야 페이지가 복사됩니다.
❖ COW는 수정된 페이지만 복사되기 때문에 더 효율적인 프로세스 생성을 가능하게 합니다.
Before Process 1 Modifies Page C
• 부모 프로세스와 자식 프로세스는 메모리의 동일한 페이지를 공유합니다.
• 페이지 C는 공유된 상태로 있습니다.
After Process 1 Modifies Page C
• 프로세스 1이 페이지 C를 수정합니다.
• 수정 시에만 페이지 C가 복사됩니다.
• 이제 부모 프로세스와 자식 프로세스는 독립된 페이지 C를 가지게 됩니다.
❖ 과다할당: 다중 프로그래밍의 정도를 높이기 위해 메모리를 과다할당합니다. (Over-Allocation)
• ∑ (각 프로세스의 페이지 수) > 물리적 메모리의프레임 수
• 예: 물리적 메모리에 40개의 페이지가 있고, 부분적으로 5개의 페이지를 가진 8개의 프로세스(각각 10개의 페이지)를 할당가능.
❖ 요구 페이징 시스템에서는 활성 페이지만이 물리적 메모리에 상주합니다.
• 페이지는 사용될 때까지 로드를 연기합니다.
❖ 새 페이지를 로드할 때 사용 가능한 프레임이 없는 경우
• 메모리에 있는 페이지 중 하나를 새 페이지로 교체해야 합니다.
→ 페이지 교체
❖ 페이지 교체는 논리적 메모리와 물리적 메모리 간의 분리를 완료합니다.
• 작은 물리적 메모리에 대규모 가상 메모리를 제공할 수 있습니다.
( 만약 빈 프레임이 없는 경우 어떻게 될까요?)
❖ 물리적 메모리
• 총 8개의 프레임
• 그 중 2개는 운영 체제를 위해 사용됨
• 6개는 사용자를 위해 사용됨
❖ 두 개의 사용자 프로세스
• 각각 4개의 페이지가 있음
• 그 중 3개가 로드됨
❖ 모든 프레임이 사용됨
❖ PC가 명령을 나타냄:
• B를 로드
• 페이지 B가 디스크에 있음
❖ 페이지 교체 필요.
기본 페이지 교체
1. 디스크에서 원하는 페이지의 위치를 찾습니다.
2 빈 프레임을 찾습니다:
- 빈 프레임이 있는 경우 사용합니다.
- 빈 프레임이 없는 경우 페이지 교체 알고리즘을 사용하여 희생 프레임을 선택합니다.
- 변경된 페이지가 있는 경우(페이지 아웃) 희생 프레임을 디스크에 기록합니다.
3.원하는 페이지를(새롭게) 빈 프레임으로 가져와서 페이지 및 프레임 테이블을 업데이트 합니다.
4. 트랩을 발생시킨 명령을 재시작하여 프로세스를 계속합니다.
잠재적으로 두 페이지 전송이 필요할 수 있습니다.(페이지 인 & 페이지 아웃).
변경 비트(수정 비트)를 사용하여 이를 줄일 수 있습니다.
페이지의 변경 비트는 보조 저장소에서 읽혔을 때 수정된 경우에 설정됩니다.
→ 변경 비트가 설정된 페이지를 페이지 아웃해야 합니다.
페이지 교체 절차
• 디스크에서 대상 페이지와 페이지 교체 알고리즘을 사용하여 희생 페이지를 찾은 후
1. 희생 페이지를 페이지 아웃 합니다.
2. 희생 페이지의 유효- 무효 비트를 해제합니다.
3. 원하는 페이지를 페이지 인 합니다.
4. 대상 페이지의 유효 - 무효 비트를 설정합니다.
페이지 및 프레임 교체 알고리즘
❖ 프레임 할당 알고리즘은 다음을 결정합니다
• 각 프로세스에 몇 개의 프레임을 할당할 것인가
• 어떤 프레임을 교체할 것인가
❖ 페이지 교체 알고리즘
• 첫 번째 액세스와 재액세스에서 가장 낮은 페이지 폴트 비율을 원합니다
❖ 알고리즘을 평가하는 방법
• 특정한 메모리 참조 문자열(참조 문자열)에서 실행
• 해당 문자열에서 발생하는 페이지 폴트의 수를 계산
❖ 참고사항
• 문자열은 페이지 번호만 포함하며 전체 주소가 아닙니다.
• 동일한 페이지에 반복 액세스는 페이지 폴트를 일으키지 않습니다.
• 결과는 사용 가능한 프레임 수에 따라 달라집니다.
❖ 모든 예제에서 참조된 페이지 번호의 참조 문자열은 다음과 같습니다
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
❖ 페이지 교체 알고리즘
• FIFO 페이지 교체
• 최적 페이지 교체
• LRU 근사 페이지 교체
• 추가 참조 비트 알고리즘
• 두 번째 기회 알고리즘
• 페이지 버퍼링 페이지 교체
❖ 참조 문자열: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
❖ 3개의 프레임 (프로세스 당 동시에 메모리에 있을 수 있는 페이지 수)
❖ 참조 문자열에 따라 다를 수 있음: 1,2,3,4,1,2,5,1,2,3,4,5를 고려
• 더 많은 프레임을 추가하면 페이지 폴트가 더 많이 발생할 수 있다 !
• 벨라디의 이상현상
❖ 페이지의 나이를 어떻게 추적할까?
• 단순히 FIFO 큐를 사용합니다.
❖ 사용 가능한 프레임 수에 따른 페이지 폴트 수의 곡선
❖ 벨라디의 이상현상
• 4개의 프레임(10)에 대한 페이지 폴트 수가 3개의 프레임(9)에 대한 것보다 큽니다.
• 프레임 수가 증가함에 따라 페이지 폴트 비율이 증가할 수 있습니다.
❖ 가장 긴 시간 동안 사용되지 않을 페이지를 교체합니다.
• 예시에서는 9가 최적이다
❖ 이것을 어떻게 알 수 있을까?
• 미래를 읽을 수 없으므로 미래의 지식이 필요
❖ 알고리즘이 얼마나 잘 수행되는지 측정하는 데 사용
❖ 미래 대신 과거 지식을 사용합니다.
❖ 가장 오랫동안 사용되지 않은 페이지를 교체합니다.
❖ 각 페이지와 마지막 사용 시간을 연결합니다.
❖ 12개의 폴트 - FIFO보다는 나은 결과지만 OPT보다는 좋지 않다.
❖ 일반적으로 좋은 알고리즘으로 자주 사용된다.
❖ 하지만 이를 어떻게 구현해야 할까?
❖ 카운터 구현
• 각 페이지 항목에는 카운터가 있으며, 이 항목을 통해 페이지가 참조될 때마다 시계를 카운터로 복사합니다.
• 페이지를 변경해야 할 때, 가장 작은 값의 카운터를 찾기 위해 카운터를 확인합니다.
• 필요한 테이블을 검색해야 합니다.
또는,
❖ 스택 구현
• 페이지 번호의 스택을 이중 링크드 리스트 형태로 유지합니다:
• 페이지가 참조될 때:
• 스택의 맨 위로 이동합니다.
• 그러나 각 업데이트는 더 비용이 많이 듭니다.
• 교체를 위한 검색이 없습니다.
❖ LRU와 OPT는 벨라디의 이상현상이 없는 스택 알고리즘의 경우입니다.
• 스택 알고리즘은 항상 n+1 프레임의 부분 집합입니다.
페이지 참조를 기록하기 위한 스택의 사용 참조 문자열: 4 7 0 7 1 0 1 2 1 2 (a) 7 (b) 1 2
• 스택 내용
• 4
• 7 4
• 0 7 4
• 7 0 4
• 1 7 0 4
• 0 1 7 4
• 1 0 7 4
• 2 1 0 7 4 // a = 변화 전 스택
• 1 2 0 7 4 // b = 변화 후 스택
• 2 1 0 7 4
• 7 2 1 0 4
• 1 7 2 0 4
• 2 1 7 0 4
top <-> bottom
❖ LRU는 특별한 하드웨어가 필요하며 여전히 느립니다.
❖ 참조 비트
• 각 페이지는 비트와 연결되며, 처음에는 0입니다.
• 페이지가 참조되면 해당 비트가 1로 설정됩니다.
• 페이지 폴트가 발생하면, 참조 비트가 0인 (존재하는 경우) 임의의 페이지를 교체합니다.
• (그러나 순서를 알 수는 없다)
❖ 두 번째 기회 알고리즘
• 일반적으로 FIFO에 하드웨어 제공 참조 비트를 추가한 것
• 시계 교체
• 교체할 페이지가
• 참조 비트 = 0 인 경우 -> 교체합니다.
• 참조 비트 = 1 인 경우:
• 참조 비트를 0으로 설정하고 이 페이지를 건너 뜁니다 (두 번째 기회를 제공)
• 동일한 규칙에 따라 교체할 다음 페이지를 선택하빈다.
Second-Chance (Clock) 페이지 교체 알고리즘
• 원형 큐를 사용하여 구현됩니다.
• 포인터가 다음으로 교체될 페이지를 나타냅니다.
• 프레임이 필요한 경우 포인터는 0 참조 비트가 있는 페이지를 찾을 때까지 이동합니다.
• 포인터가 이동할 때마다 참조 비트를 지웁니다.
• 희생 페이지를 찾으면 해당 페이지를 교체하고 새 페이지를 삽입합니다.
향상된 Second-Chance 알고리즘
❖ 참조 비트와 수정(더티) 비트를 사용하여 알고리즘을 개선합니다.
❖ (참조, 수정) 쌍을 사용합니다:
• (0, 0) 최근에 사용되지 않고 수정되지 않음 - 교체하기에 가장 좋은 페이지
• (0, 1) 최근에 사용되지 않았지만 수정됨 - 다소 좋지만, 교체 전에 기록해야 함
• (1, 0) 최근에 사용되었지만 깨끗함 - 아마도 곧 다시 사용될 것입니다
• (1, 1) 최근에 사용되고 수정됨 - 아마도 곧 다시 사용될 것이고 교체 전에 기록해야 함
❖ 페이지 교체가 호출될 때, 시계 방식을 사용하지만 네 가지 클래스를 사용하여 가장 낮은 비어 있지 않은 클래스의 페이지를 교체합니다. • 원형 큐를 여러 번 탐색해야 할 수 있습니다.
페이지 버퍼링 알고리즘
❖ 항상 여유 프레임의 풀을 유지합니다.
• 그럼 필요할 때 프레임을 사용할 수 있으며, 폴트 시간에 찾을 수 없습니다.
• 먼저 빈 프레임으로 페이지를 가져옵니다 → 희생자를 선택하고 여유 풀에 추가합니다.
• 편리할 때, 희생자를 제거합니다.
❖ 가능하다면, 빈 프레임의 내용을 유지하고 그 내용을 알립니다.
• 재사용되기 전에 다시 참조되면, 디스크에서 다시 내용을로드 할 필요가 없습니다.
• 일반적으로 잘못된 희생 프레임이 선택된 경우 벌칙을 줄이는 데 유용합니다.
프레임 할당
❖ 각 프로세스는 최소한의 프레임 수가 필요합니다.
❖ 예: MOVE 명령을 처리하기 위해 6개의 페이지가 필요한 경우:
• 명령은 2개의 페이지에 걸쳐 있을 수 있습니다.
• 출발지를 처리하는 데 2개의 페이지가 필요합니다.
• 도착지를 처리하는 데 2개의 페이지가 필요합니다.
❖ 물론, 시스템 전체의 총 프레임이 최대입니다.
❖ 최소 값은 아키텍처에 따라 다릅니다.
❖ 최대 값은 물리적 메모리에 따라 다릅니다.
고정 할당
❖ 동등한 할당 -
예를 들어, OS에 프레임을 할당한 후에 100개의 프레임이 있는 경우, 5개의 프로세스에 각각 20개의 프레임을 할당합니다.
• 일부를 자유 프레임 버퍼 풀로 유지합니다.
❖ 비례 할당 - 프로세스의 크기에 따라 할당합니다.
• 다중 프로그래밍 정도에 따라 동적으로 변경됩니다. 프로세스 크기가 변경됩니다.
• 프로세스 우선 순위도 고려할 수 있습니다.
전역 vs 지역 할당
❖ 전역 교체 - 프로세스가 모든 프레임 집합에서 대체 프레임을 선택합니다. 한 프로세스가 다른 프로세스의 프레임을 가져갈 수 있습니다. • 그러나 프로세스 실행 시간이 크게 달라질 수 있습니다.
• 그러나 처리량이 더 크기 때문에 더 일반적입니다.
❖ 지역 교체 - 각 프로세스는 할당된 프레임 세트에서만 선택합니다.
• 프로세스 당 일관된 성능을 제공합니다.
• 그러나 메모리의 사용률이 낮을 수 있습니다.
전역 할당 - 페이지 회수
❖ 전역 페이지 교체 정책을 구현하는 전략
❖ 모든 메모리 요청은 자유 프레임 목록에서 충족됩니다. 페이지 교체를 선택하기 전에 목록이 0으로 떨어지기를 기다리지 않습니다.
❖ 페이지 교체는 목록이 특정 임계값 아래로 떨어질 때 트리거됩니다.
❖ 이 전략은 항상 새로운 요청을 충족시킬 충분한 자유 메모리가 항상 있는지 확인하려고 시도합니다.
페이지 회수 예시
❖ 만약 자유 메모리의 양이 매우 낮은 수준으로 떨어진다면, 메모리가 부족한 경우(OOM) 킬러 루틴이 종료할 프로세스를 선택합니다.
❖ Linux에서는 메모리 사용률이 높은 프로세스가 높은 OOM 점수를 가집니다. → 먼저 높은 점수의 프로세스를 종료합니다.
스래싱
❖ 프로세스에 충분한 페이지가 없으면 페이지 폴트 비율이 매우 높아집니다.
• 페이지 가져오기 위한 페이지 폴트
• 기존 프레임 대체
• 그러나 빠르게 교체된 프레임이 필요합니다.
• 이로 인해 다음이 발생합니다.
• 낮은 CPU 활용률
• 운영 체제는 CPU 활용률을 높이기 위해 다중 프로그래밍 정도를 증가시켜야 한다고 생각합니다.
• 시스템에 다른 프로세스가 추가됩니다.
페이지 폴트 빈도
❖ "허용 가능한" 페이지 폴트 빈도(PFF)를 설정하고 지역 교체 정책을 사용합니다.
• 실제 속도가 너무 낮으면 프로세스가 프레임을 잃습니다.
• 실제 속도가 너무 높으면 프로세스가 프레임을 얻습니다.
'Computer Science' 카테고리의 다른 글
| Chapter 9: Main Memory (0) | 2024.06.07 |
|---|---|
| Chapter 8: Deadlocks (0) | 2024.05.28 |
| Chapter 7: Synchronization Examples (0) | 2024.05.22 |
| Chapter 6: Synchronization tools (0) | 2024.04.29 |
| 운영체제[OS] 5. CPU Scheduling (1) | 2024.04.17 |
