스래싱
- 어떤 프로세스가 수행에 보내는 시간보다 페이지 교체에 보내는 시간이 더 길면 ‘스래싱을 하고 있다’고 표현
다중 프로그래밍에 따른 스래싱 현상
다중 프로그래밍 정도를 어느 정도 높이면 cpu 유효성이 높지만 그 후에는 스래싱이 나타납니다.
스래싱의 발생 원인
어떨때? 다중 프로그래밍 정도가 너무 많을 때
각 프로세스가 꼭 필요한 메모리 용량 > 모든 메모리 용량
그래서 각 프로세스가 메모리 용량이 부족하게 됩니다.
전역 페이지 교체 경우
- 다른 프로세스의 프레임도 뺏어서 교체할 수 있습니다.
- 이렇게 되면 수행 중이 페이지 부재가 더 발생합니다.
스래싱을 예방하려면
프로세스에 적절한 개수의 프레임을 할당해야 합니다.
여기서 적절한 개수란 "작업 집합 모델"이라고 합니다.
작업 집합이란?
프로세스가 자주 사용하는 기억장치 부분
지역성과 비슷하죠
즉, 스래싱을 예방하려면 프로세스에 작업 집합 만큼 할당하면 됩니다.
3번 입니다.
작업 집합
지역성
복습해 봅시다
- 프로세스가 메모리의 동일하거나 가까운 주소를 연속해서 참조하는 현상
- 프로세스가 메모리를 특정 시간 동안에는 특정 페이지만 집중적으로 사용하는 현상
지역성은 2가지 종류가 있습니다.
- 같은 주소를 가까운 시간 내에 반복해서 참조하는 현상
- 순환 recursion, 루프 (for, while), 서브루틴 반복 호출, 스택, 합계에 사용하는 변수
- 근처 주소를 가까운 시간 내에 반복해서 참조하는 현상
- 배열 검색, 순차적 코드의 실행, 근처에 관련 변수 선언
- 순차적 지역성
같은 공간을 시간이 지남에 따라 계속 액세스 합니다.
작업 집합 모델 자세히 알아보기
- 작업 집합만 메모리에 있으면 프로세스 실행 가능
- 작업 집합은 시간에 따라 점차 변함
10번 동안 액세스 한 페이지 번호를 모아서 작업 집합으로 봅니다.
t2 시점에서 10번동안 엑세스한 집합을 작업 집합으로 봅니다.
작업 집합 크기
- 작업 집합 창 동안 사용하는 페이지 수
작업 집합 창(페이지 참조 횟수)
- 최근의 일정 시간, 정해진 페이지 참조 수
ti의 작업 집합은?
5, 100, 101, 103
사이즈는 4
ti+1의 작업 집합은?
5, 6, 100, 101, 103
사이즈는 5
tj의 작업 집합은?
7, 101, 103
사이즈는 3
작업 집합 모델을 이용해서 프레임을 어떻게 할당하나요
- 각 프로세스에게 작업 집합 크기 이상의 프레임들을 할당
- 새 프로세스는 작업 집합 공간이 있을 때 시작
- 프로세스들의 작업 집합 크기 합이 너무 크면 일부 프로세스 중단 suspend
작업 집합 모델 프레임 할당 목표
- 자주 사용 페이지 집합은 메인 메모리 상주
- 페이지 부재 최소화
- 스래싱을 방지
- 다중 프로그래밍의 정도 최대화
- 프로세서의 사용률 증가
우리가 작업 집합을 잘 모릅니다.
중요한 건 작업 집합 창을 잘~ 설정해야 합니다.
- 너무 작으면 실제 작업 집합을 모두 포함 못함
- 너무 크면 실제 작업 집합을 여러 개 포함 -> 낭비
그럼 최적의 작업 집합 창을 어떻게 설정해야 할까요
만약 최적의 작업 집합 창을 설정했다면 적당한 크기의 프레임수를 할당할 수 있습니다.
작업 집합 창을 이용하면 문제점이 있습니다.
시간에 따라 페이지 부제 비율이 들쑥날쑥 합니다.
새로운 working set을 메모리에 올려야 하니 그때 부재 비율이 높아집니다.
근데 working set을 바꿔줘야 하니 그때마다 들 쑥 날 쑥 합니다.
- 과거의 참조가 미래의 참조를 보장하지 않음
- 과거를 보고 미래에도 사용될 거다 라도 예측하는 것입니다.
- 그래서 틀린 경우도 있습니다.
-
모든 프로세스의 작업 집합 크기를 측정하는 것은 현실적으로 불가능
4번입니다.
용이성 = 편리하게 사용하는 것
프로그래머 입장에서는 모릅니다.
가상 메모리 주소를 이용해서 하는 것이고
이건 운영체제가 생각하는 것입니다.
2번입니다.
구성이 일정하지 않습니다.
쉽게 하고자 하는 방법이
페이지 부재 비율을 조절하는 방법입니다.
부재 비율이 높아지면 ➡-> 프레임수 높이자
부재비율이 낮아지면 -> 프레임수 낮추자
단순한 이야기입니다.
부재 비율에 상한선과 하한선을 두어서 넘어가면 동작하게 합니다.
전역 교체 / 지역 교체
전역 교체 - 다른 프로세스의 프레임을 사용할 수 있습니다.
지역 교체 - 프로세스들 간의 칸막이가 있습니다.
전역 교체는 가변 프레임 할당 알고리즘과 관계가 많습니다.
전역 교체에서 각각 프로세스의 페이지 부재비율을 조절하려면 다른 프로세스들과 영향을 주기 때문에 교체하지 어렵습니다.
요구 페이징, 프리 페이징
요구 페이징 - 페이지 부재 시에만 페이지에 적재
프리 페이징 - 예측하면서 미리 페이지에 적재
페이지 크기에 대해서
- 하드웨어 디자인에서 매우 중요한 요소
- 페이지 크기는 메인 메모리의 크기와 프로그램 크기에 영향을 받음
페이지를 작게 한다
- 페이지 개수가 커짐
- 내부 단편화(남는 공간)가 없어짐
- 같은 내용을 메모리에서 가져오려 하면 작은 페이지를 디스크에 많이 보내야 합니다.
- 내가 꼭 필요한 부분만 가져올 수 있습니다.(=지역성 활용도 증가)
1번입니다.
4번이었습니다. 전역 페이지의 장점을 골라야 합니다.
- 페이지 크기를 크게 할수록 페이지 개수가 작아집니다.( 페이지 테이블 크기 감소)
- 페이지가 커지니 빈 공간도 많이 나옵니다.( 내부 단편화 커짐)
- 한번 디스크에 갈 때 뭉텅이로 갑니다.( 디스크 입출력 횟수 적음)
- 한번 훑으면 많이 훑어야 합니다.(지역성 활용도 낮음)
페이지 테이블이 너무 커질 때 문제가 있습니다.
가상 주소가 64비트 = 주소의 개수는 2^64
한 페이지의 크기는 2^12입니다.
그러면 페이지의 개수를 알 수 있습니다.
(2^64 / 2^12) = 2^52개
실제 메모리 크기 : 2^28B
실제 메모리 크기는 가장 메모리보다 작습니다.
한 프레임의 크기는 2^12입니다.(페이지 크기와 같음)
프레임의 개수는 (2^28 / 2^12) = 2^16개
프레임 번호 길이는 16bit가 됩니다.
페이지 테이블 항목 길이 = 4B
페이지 테이블 한 줄에 4B 식 있다는 뜻입니다.
페이지 테이블의 항목 수는 페이지의 개수(=2^52)와 같습니다.
페이지 테이블 구조입니다.
- Page Table(=페이지 개수만큼 가지고 있습니다.)
- Inverted Page Table
- Hashed Page Table
- Hashed inverted page table
각 크기를 비교하면 점점 작아집니다.
페이지 테이블의 개수는 페이지의 개수만큼 있습니다.
Inverted Page Table은 모든 프로세스에 1개만 있으면 됩니다.
작은 메모리를 차지합니다.
Hash table은 적절히 테이블을 구성합니다.
해쉬 테이블에서는 오픈 addressing과 chaning으로 충돌을 해결합니다.
역 페이지 테이블(inverted page table)을 자세히 봅시다.
프로세스 id까지 필요하니, 프로세스 수만큼 페이지에 들러붙어있어야 합니다.
테이블의 각 항목은 프레임 개수로 나눠집니다.
즉, 항목 수는 프레임의 수입니다.
우리가 원하는 건
페이지 번호를 알 때 -> 프레임 번호를 알고 싶습니다.
(프로세스 id + 페이지 번호)를 가지고 프레임을 찾습니다.
왜 프로세스 id 가 필요할까요?
많은 프로세스가 섞여있습니다.
테이블을 순서대로 쭉 내려가면서 프레임을 찾습니다.
제일 문제는 검색하는 시간입니다.
PID가 필요한 것을 보니 역 테이블인 거 같습니다.
PID와 VPN을 가지고 테이블을 순서대로 검색하는 것도 보입니다.
테이블 숫자는 프레임 수만큼 있습니다.
헤쉬 페이지 테이블 자세히 알아보기
테이블 구조가 뭐든지 간에 우리 목적은
논리 주소가 있을 때 물리 주소를 얻어내야 하는 것입니다.
페이지 숫자를 보고 hash function을 이용해서 프레임 넘버를 얻어 냅니다.
이때 충돌 해결하는 방법이 있어야 합니다.
Chaining과 Open addressing
이건 chaing으로 보여줍니다.
ex) q? 아니네 -> s? 아니네 -> 다음 -> p? 아니네 -> r 맞다!
해쉬 역 페이지 테이블
역 페이지 테이블과 비슷합니다.
테이블의 항목 수는 프레임 개수입니다.
역 페이지 테이블은 검색 시간이 오래 걸렸습니다.
보완하기 위해서 Hash function을 적용해서 검색시간을 단축시킨 것입니다.
결괏값이 다르다면 next라는 link를 타고 가라고 붙여줍니다.(=내가 원하는 프레임 번호로 보내줍니다.)
Pid와 VPN을 가지고 해시 테이블의 결괏값으로 역 테이블을 검색합니다.
즉, 해쉬 역 테이블입니다.
1번입니다.
페이지 테이블 항목 수 = 프레임 수
Inverted Page Table, Hashed inverted page table입니다.
Inverted Page Table
하나하나 순차적으로 검색해야 하니깐
