가상 메모리 개념
제한된 물리적 메모리 크기
- 실제 메모리의 사용 가능한 공간보다 큰 프로그램은 실행할 수 없다.
일반 프로그램 실행 패턴
- 프로그램의 일부만 실행되고 전체 프로그램은 실행되지 않는다.
- 오류 코드,예외 코드
- 배열 100x100 요소이지만 10x10 요소만 사용
- 프로그램의 특정 옵션 및 기능은 거의 사용되지 않는다.
- 전체 프로그램이 필요한 경우에도 모든 프로그램이 동시에 필요하지 않을 수 있다.
가상 메모리
- 메모리에 완전히 저장되지 않은 프로세스를 실행할 수 있다.
- 프로그램의 일부는 실행을 위해 메모리에 있어야 한다.
- 논리 메모리 주소 공간과 실제 메모리 주소 공간의 분리
- 논리 메모리 주소 공간은 물리적 메모리 주소 공간보다 클 수 있다.
가상 주소 공간
요구 페이징(Demand Paging)
가상 메모리는 요구 페이징을 통해 구현할 수 있다.
필요한 경우에만 페이지를 메모리로 가져온다.
- 적은 I/O가 필요
- 적은 메모리가 필요
페이지를 주고받을 수 있어야 한다.
페이지를 참조할 때,
- 유효한(valid) 참조 → 참조
- 잘못된(invalid) 참조 → not-in-memory → 메모리로 가져온다.
valid–invalid 비트는 각 페이지 테이블 항목과 연결된다.
- v → in-memory
- i → 메모리에 없거나 올바르지 않습니다(잘못된 주소, 보호 위반)
- 주소 변환 중 valid–invalid 비트가 i인 경우 페이지 오류(page fault)
일부 페이지가 메인 메모리에 없는 경우 페이지 테이블
잘못된 페이지에 액세스하면 페이지 오류(page fault) 발생
→ OS 내의 페이지 오류 처리기(Page fault handler)가 호출
페이지 오류 처리기(Page fault handler)
- 잘못된(invalid) 참조
- 잘못된 주소 또는 보호 위반 → 프로세스 중단
- 메모리에 없는 경우 → 2
- 빈 페이지 프레임을 가져온다.
- 빈 페이지 프레임이 없는 경우 일부 페이지 프레임을 바꾼다.
- 페이지 프레임에 페이지를 읽는다.
- 이 프로세스는 디스크 I/O가 수행될 때까지 차단된다.
- 디스크 I/O가 완료되면 페이지 테이블 항목을 유효(valid)로 설정
- 프로세스를 준비 대기열(ready queue)에 다시 삽입하고 나중에 발송(dispatch)
- 페이지 오류를 발생시킨 명령을 재시작
페이지 오류 처리(Page fault handling)
페이지 오류율(Page Fault Rate) 0 ≤ p ≤ 1.0
- p = 0 : 페이지 오류 없음
- p = 1 : 모든 참조가 오류
유효 액세스 시간(EAT, Effective Access Time)
- EAT = (1 – p) x 메모리 액세스 시간 + p x 페이지 오류 서비스 시간
- 예)
- 메모리 액세스 시간 = 200ns
- 평균 페이지 오류 서비스 시간 = 8ms(=8,000,000ns)
- EAT = (1 – p) x 200 + p x 8,000,000 = 200 + p x 7,999,800
- 1,000개의 액세스 중 하나가 페이지 오류를 유발하는 경우
- EAT = 8,200 ns
- 이는 40배로 둔화된 것
페이지 오류율을 낮게 유지하는 것이 중요
- 좋은 페이지 교체(page replacement) 정책이 필요
페이지 교체(Page Replacement)
페이지 교체
- 실제로 사용하지 않는 페이지를 찾기 → 페이지 교체
- 좋은 페이지 교체 알고리즘
- 페이지 오류의 최소화
참조 위치(Locality of reference)
- 같은 페이지를 여러 번 메모리에 저장할 수 있다.
- 실제 대부분의 프로그램에서 관찰되는 현상
- 일정 시간에 극히 일부 페이지만 집중적으로 참조하는 프로그램 동작
- Loop
- 페이징 시스템이 성능이 좋게 되는 근거
페이지 교체를 포함한 페이지 오류 처리기(Page fault handler)
- 디스크에서 원하는 페이지의 위치를 찾는다.
- 빈 프레임을 찾는다.
- 빈 프레임이 있는 경우 : 사용
- 빈 프레임이 없는 경우 : 페이지 교체 알고리즘 사용, 대상 선택
- 원하는 페이지를 (새로) 빈 프레임으로 가져와서 페이지 테이블을 업데이트
- 프로세스 재시작
이상적인 알고리즘
- 페이지 오류율이 가장 낮다.
알고리즘 평가
- 특정 메모리 참조 문자열에서 실행
- 참조 문자열
- 해당 문자열의 페이지 오류 수를 계산
일부 예에서 참조 문자열
- 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
페이지 오류 수 vs 프레임 수
FIFO 페이지 교체
FIFO(First In First Out) 순서로 대체하는 페이지 교체
참조 문자열
- 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
3프레임
4프레임
벨라디의 변칙(Belady’s Anomaly)
- 더 많은 프레임 → 더 많은 페이지 오류
벨라디의 변칙을 보여주는 FIFO
최적의(Optimal) 페이지 바꾸기
장기간 사용되지 않는 페이지 교체
다른 프레임 예제
- 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
이것을 어떻게 아는가?
알고리즘의 성능을 측정하는 데 사용
- 최적 알고리즘은 페이지 오류율의 하한을 나타낸다.
LRU(Least Recently Used, 가장 최근 사용)
가장 최근에 사용하지 않은 페이지를 바꾼다.
참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
구현 방법
- 각 페이지마다 참조 시간을 기록
- 참조 시간이 가장 오래된 페이지를 찾는다.
- 공간 및 시간 오버헤드가 너무 큼
- → 많은 근사 알고리즘이 제안
카운터 구현
- 모든 페이지 항목에는 카운터 존재
- 페이지가 참조될 때마다 클럭이 증가
- A페이지가 참조되면 A의 카운터에 클럭를 복사
- 가장 작은 카운터 값으로 페이지를 바꾼다.
스택 구현
- 페이지의 스택을 유지
- 페이지가 참조되면 맨 위로 이동
- 교체 검색이 없다.
스택 구현
LRU 근사 알고리즘
LRU 페이지 교체의 경우,
- 많은 시스템이 하드웨어 지원을 제공
참조 비트
- 각 페이지에 대한 비트로, 처음에는 0으로 설정
- 페이지 참조 시 1로 설정
- 0인 것을 교체 (있는 경우)
- 하지만, 우리는 참조 순서를 모른다.
두 번째 기회 페이지 교체 알고리즘(클럭 알고리즘)
- 교체할 페이지에 기준 비트 1이 있을 경우,
- 페이지를 메모리에 남긴다.
- 참조 비트 0을 설정
- 참조 비트가 0인 페이지를 찾을 때까지 다음 대상에 대한 사전 포인터
카운팅 알고리즘
LFU(최빈도 사용) 알고리즘
- 작성된 참조 번호를 유지
- 가장 작은 카운트로 페이지를 교체
할당
이전 교체 알고리즘
- 페이지 오류가 발생하면 대상을 선택
- 그들은 변수 할당이 아닌 고정 할당을 가정
- 페이지 오류 시 페이지 프레임을 하나 더 할당하는 것을 고려?
할당 문제
- 페이지 오류에서 할당 크기를 결정
- 고정 할당(fixed allocation)
- 우선 할당(prioity allocation)
고정 할당(Fixed Allocation)
균등 할당(Equal allocation)
- 프레임이 100개이고 프로세스가 5개인 경우,
- 각 공정에 20프레임을 제공
우선순위 배분(prioity allocation)
- 프로세스 규모에 따른 배분
우선 순위 할당(Priority Allocation)
- 비례 할당 체계 사용
- 크기보다는 우선순위 사용
- 상위 프로세스에 더 많은 메모리 제공
글로벌 vs. 로컬 할당
글로벌 교체
- 프로세스는 모든 프레임 집합에서 교체 프레임을 선택
- 한 프로세스가 다른 프로세스의 프레임을 가져올 수 있다.
로컬 교체
- 각 프로세스는 고유한 할당된 프레임 집합에서만 선택
스레싱(Thrashing)
프로세스에 "충분한" 페이지가 없으면 페이지 오류율이 매우 높다.
- 낮은 CPU 활용률
- 운영 체제 : 멀티프로그래밍의 정도를 높여야 힌다.
- 다른 프로세스가 시스템에 추가
스레싱
- 페이지를 주고받을 때 프로세스가 사용 중
스레싱 발생 이유
- 로컬 사이즈 크기의 합 > 총 메모리 크기
작업 세트(Working-set) 모델
메모리 참조 패턴의 지역성(Locality)
- 시간적 지역성 : 상대적 짧은 시간 내에 특정 데이터 및/또는 리소스를 재사용
- 공간적 지역성 : 비교적 가까운 저장 위치 내에서 데이터 요소를 사용
작업 세트 모델
- 지역성을 전제
- ∆ ≡ working-set window ≡ 고정된 수의 페이지 참조
WSSi(프로세스 Pi의 작업 세트)
- 가장 최근에 참조된 총 페이지 수 ∆
- ∆이 너무 작으면 : 전체 지역을 포함 X
- ∆이 너무 크면 : 여러 지역을 포함
- ∆ = ∞ : 전체 프로그램을 포함
D = Σ WSSi ≡ 총 수요 프레임
- D > m 인 경우 스래싱
- → 프로세스 중 하나를 일시 중단
페이지-오류 빈도 체계
"허용 가능한" 페이지 오류율을 설정
- 실제 비율이 너무 낮으면 : 공정에서 프레임이 손실
- 실제 비율이 너무 높으면 : 공정이 프레임을 획득
요약
- 가상 메모리
- 메모리에 완전히 있지 않은 프로세스를 실행할 수 있는 메커니즘
- 요구 페이징
- 필요할 때만 페이지를 메모리로 가져온다.
- 페이지 오류율을 낮게 유지하는 것이 중요 → 좋은 페이지 교체 정책 필요
- LRU(가장 최근에 사용) : 가장 최근에 사용되지 않은 페이지를 대체
- 프로세스에 페이지 프레임이 충분하지 않으면 스레싱이 발생
'운영체제' 카테고리의 다른 글
| [OS] I/O Systems (0) | 2023.05.15 |
|---|---|
| [OS] 대량 저장 구조(Mass-Storage Structure) (0) | 2023.05.08 |
| [OS] 메인메모리(Main Memory) (0) | 2023.04.24 |
| [OS] 교착상태(Deadlocks) (0) | 2023.04.17 |
| [OS] 동기화 도구 (0) | 2023.04.03 |
