가상 메모리
가상 메모리는 물리 메모리 크기의 한계를 극복하기 위해 나온 기술이다.
즉, 물리 메모리보다 큰 프로세스(프로그램)를 수행하기 위해 가상 메모리를 사용한다. 예를 들어, 100MB 메모리 크기에서 200MB 크기의 프로세스를 수행할 수 있도록 하는 것
핵심 개념 : 요구 페이징
가상 메모리
•
프로세스들의 실행이 메모리 안에서만 이뤄지지 않도록 하는 기술
◦
물리 메모리보다 큰 프로세스(프로그램)를 수행하기 위해 가상 메모리를 사용
•
메인메모리를 엄청 큰 저장소 어레이로 추상화함으로써 실제의 물리 메모리 개념과 사용자의 논리 메모리 개념(가상 메모리)을 분리
•
파일, 라이브러리를 공유, 프로세스 생성에 효율적인 매커니즘
•
작은 메모리를 가지고도 얼마든지 큰 가상 주소 공간을 프로그래머에게 제공할 수 있음
•
Non-continuous allocation
•
사용자 프로그램을 여러 개의 block으로 분할
•
실행 시, 필요한 가상 메모리 block들만 물리 메모리에 적재
◦
나머지 block 들은 swap device(제 2 저장 장치)에 존재
•
가상 주소 공간(Virtual Address Space)
◦
한 프로세스의 가상 주소 공간은 그 프로세스가 메모리에 저장되는 논리적인 모습(view)
▪
논리 주소 0에서 시작
▪
동적 메모리 할당에 사용되므로 힙이 메모리에서 위쪽으로 증가하도록 허용
▪
연속적인 함수 호출을 위해 스택이 메모리에서 아래쪽으로 커지도록 허용
◦
연속적 메모리 안에 존재
가상 메모리의 이점
•
가상 메모리를 사용하면 페이지 공유를 통해 둘 이상의 프로세스에서 파일과 메모리를 공유할 수 있음
◦
라이브러리가 존재하는 물리 메모리 페이지들은 모든 프로세스에게 공유되고 있음 (라이브러리 - 여러 프로세스 공유)
◦
한 프로세스가 다른 프로세스와 공유할 수 있는 메모리 영역을 생성할 수 있음 (프로세스 간 메모리 영역 공유)
•
단점
◦
성능 (시간과 공간에 관해서)
요구페이징
요구 페이징을 통해 가상 메모리 기술을 사용할 수 있게 된다
실행 가능한 프로그램이 보조 저장소에서 메모리에 적재되는 방법을 생각해볼 때…
1.
프로그램 실행 시 전체 프로그램을 물리 메모리에 적재 ⇒ 낭비 발생
2.
필요한 부분(page)만 swap device(secondary storage)로부터 물리 메모리에 적재 ⇒ 요구 페이징
•
요구 페이징 가상 메모리를 사용하면, 프로그램 실행 중 요청이 있을 때만 페이지가 로드 됨
•
액세스 되지 않은 페이지는 물리 메모리에 적재되지 않음
•
스왑 인, 스왑 아웃을 관리하는 페이저
◦
스왑 인 : 메모리를 읽어드리고
◦
스왑 아웃 : 메모리를 빼는 것
◦
페이저 : 프로세스들의 개별 페이지 관리 주체
•
요구페이징 기본 개념
메모리에 존재하는 페이지와 디스크에 존재하는 페이지를 구별하기 위해 어떤 형태의 하드웨어 지원이 필요
◦
유효-무효 비트(valid-invalid bit)
▪
‘valid(v)’ : 관련 페이지가 메모리에 존재함
▪
‘invalid(i)’: 페이지가 유효하지 않거나, 유효하지만 현재 메모리에 존재하지 않고 보조 저장소(스왑 영역)에 있다는 의미
◦
프로세스가 해당 페이지에 액세스를 시도하지 않는다면, 페이지를 invalid로 표시한다고 해도 아무 효과가 없음
◦
제대로 추측해서 실제로 접근될 페이지만 적재하는 곳은 거의 모든 페이지를 존재한다 느껴질만큼의 동일한 latency
◦
메인메모리에 페이지들이 존재하지 않을 때의 페이지 테이블
페이지 폴트
프로세스가 메모리로 가져오지 않은 페이지에 액세스 하려고 한 경우의 요구 페이징이 실행되는 절차이다.
페이지 폴트(Page fault)
•
페이지 테이블 내 무효로 표시된 페이지에 대한 액세스 → 트랩의 한 종류
•
페이지 테이블의 valid bit값이 0인 경우이다.
•
페이지 폴트 처리절차
1.
유효한 메모리 접근인지 , 무효한 메모리 접근인지 확인을 위해 CPU가 프로세스의 페이지 테이블을 확인 (페이지 폴트 발생)
2.
유효한 경우 프로세스를 종료.
유효하지만 페이지 폴트인 경우, 페이지 인을 한다
무효한 경우(페이지 폴트) → 페이지 인
3.
free frame을 찾는다
4.
backing store에서 찾은 Page를 새로 할당된 프레임으로 읽어 들이기 위해 2차 저장작업을 예약(요청)
5.
저장소 읽기가 완료되면 프로세스와 함께 유지되는 내부 테이블과 페이지 테이블을 수정(갱신)하여 페이지가 현재 메모리에 있음을 나타냄 (Set validation bit = v)
6.
트랩에 의해 중단된 명령을 CPU가 재개.
프로세스는 메모리에 있었던 것처럼 페이지 액세스 가능
순수한 요구페이징(Pure Demanding Paging)
•
순수한 요구 페이징
◦
프로세스가 최초로 실행될 때는 어떤 페이지가 필요한지 알 수 없으므로, 어떠한 페이지도 물리 메모리로 올리지 않는다.
⇒ 프로그램을 실행하자마자 첫번째 명령에서 page fault가 발생
◦
순수하게 필요한(요청된) 페이지만 올리는 것
◦
장점 : 메모리를 최대한 효율적으로 사용할 수 있다.
◦
단점 : 시작부터 매번 page fault가 발생하므로 속도면에서 느리다.
•
요구 페이징에서의 하드웨어 자원
◦
페이지 테이블
▪
(valid / invalid bit)
◦
보조 메모리(보조기억장치, 스왑 공간)
▪
NVM device, 고속 디스크(SSD)
▪
이 메모리는 메인 메모리에 존재하지 않는 페이지를 홀드함(스왑 공간)
◦
Instruction restart
▪
요구 페이징의 중요한 필요사항
▪
페이지 폴트 이후 명령 재실행할 능력
▪
페이지 폴트 발생 시 인터럽트된 프로세스의 상태(레지스터, 조건 코드, instruction counter)가 저장된다
▪
프로세스가 같은 장소와 상태에서 재시작
Free Frame List
•
페이지 폴트 발생 시
◦
OS는 보조 저장장치에서 물리메모리로 요청된 페이지를 가져와야 한다
•
페이지 폴트를 해결하기 위해서 OS는 free frame list라는 것을 유지해야 한다
◦
위의 요청을 만족시키는 free frame들의 풀
•
Free frame들은 stack이나 stack segment를 가지고 관리를 해주어야 한다.
Prepaging
•
Prepaging은 pure demanding paging과 반대대는 개념이다.
•
프로그램을 실행할 때 필요할 것이라 판단되는 페이지를 미리 올리는 것
•
장점 : page fault가 발생할 확률이 적으므로 속도면에서 빠르다
•
단점 : 미리 올라간 페이지를 사용하지 않는다면 메모리가 낭비된다.
Swapping VS Demanding Paging
•
Swapping와 Demanding Paging의 공통점
◦
둘 다 메모리와 backing store 사이를 서로 오고 가는 기능을 수행
•
차이점
◦
Swapping은 프로세스 단위로 이동하고 Demanding Paging은 페이지 단위로 이동하는 차이점 존재
요구 페이징의 성능
유효 접근 시간(Effective Access Time)
•
Demanding Paging은 페이지 테이블에 해당 페이지가 없으면 backing store에서 메모리로 가져오는 과정이 있다.
•
페이지 폴트 하는데 필요한 시간들
◦
페이지 폴트 인터럽트 시간
◦
페이지 읽는 시간 (제일 많이 걸림)
◦
프로세스 재시작 시간
•
그렇기 때문에 페이지 테이블에 해당 페이지가 있을 때와 없을 때 시간 차이가 발생한다. 이러한 시간 차이를 고려하여 평균적으로 어느정도 소요되는지 계산하는 것을 유효 접근 시간(EAT)이라 한다.
◦
p
▪
페이지 부재 확률(probability of a page fault = page fault rate)
◦
Tm
▪
메모리를 읽는 시간(DRAM)
▪
(Time memory)
◦
Tp
▪
(Time page-fault)
▪
Page fault가 발생했을 때 소요되는 시간(대부분 backing store(하드디스크)를 읽는 시간이 차지한다. (seek time + rotational delay + transfer time)
•
예시
◦
Memory access time(Tm) = 200 nanoseconds
◦
Average page-fault service time(Tp) = 8 milliseconds = 8000 nanoseconds
◦
EAT = (1 – p) x 200 + p (8 milliseconds)
= (1 – p) x 200 + p x 8,000,000
= 200 + p x 7,999,800
◦
If one access out of 1,000 causes a page fault, (p=1/1000)
then EAT = 8.2 microseconds.
◦
If want performance degradation < 10 percent
▪
220 > 200 + 7,999,800 x p
20 > 7,999,800 x p
▪
p < .0000025
지역성의 원리(Locality of reference)
page fault는 매우 적은 확률로 발생해야 효율적
그러면 현실적으로 페이지 부재는 어느정도로 발생할까?
이는 지역성의 원리(Locality of reference)로 인해 페이지 부재 확률은 매우 낮다. ⇒ 요구 페이징의 성능이 괜찮은 편
지역성의 원리는 ‘메모리 접근은 시간적 지역성과 공간적 지역성을 가진다‘는 의미
•
시간적 지역성
◦
CPU는 어느 메모리 공간을 읽은 후, 시간이 지나도 그 공간을 다시 읽을 확률이 매우 높다는 것
◦
대표적인 예로 반복문이 있다. 반복문은 하나의 코드 공간을 여러 번 읽는다.
•
공간적 지역성
◦
CPU가 메모리 공간을 읽을 때는 인접한 범위 내에서 읽는다는 의미
◦
프로그램은 대부분 절차적인 순서로 구현되어 있어 순서대로 읽는 경우가 빈번하다.
이와 같이 페이지 부재가 현실적으로 발생할 확률은 매우 낮으므로 예제와 같이 40배로 느려지는 일을 거의 없다. 여기서 더 효율적으로 사용하기 위해서는 페이지 부재일 때 소요되는 시간을 줄일 수 있는데, backing store로 HDD를 사용하기 보다는 더욱 빠르게 동작하는 SSD나 저가 DRAM과 같은 것을 사용하는 방법이 있다.
쓰기 시 복사의 개념(Copy-on-Write (COW))
•
프로세스 중 하나가 공유 페이지에 쓰는 경우, 공유 페이지의 복사본이 생성 (읽는 경우 불필요)
•
fork() & exec() 시, 부모 및 자식 프로세스가 처음에 동일한 페이지를 공유하도록 허용하여 작동
•
프로세스 1이 페이지 C를 수정하기 전 (fork() 직후)
예) 자식 프로세스가 페이지 수정을 시도한다면,
•
운영 체제는 이 페이지의 복사본을 생성하여 자식 프로세스의 주소 공간에 매핑
•
자식 프로세스는 부모 프로세스에 속한 페이지가 아닌 복사된 페이지를 수정
•
프로세스 1이 페이지 C를 수정한 후
페이지 교체
페이지 교체의 개념을 이해
Demanding Paging은 요구되어지는 페이지만 backing store에서 가져온다.
프로그램들이 계속 실행함에 따라 요구 페이지도 계속 늘어나고, 언젠가는 메모리가 가득 차게 될 것이다(memory full, no free frame)
여기서 다른 프로그램이 새로 실행되거나 실행중인 프로세스가 다른 페이지를 요구한다면
이미 메모리에 있는 페이지 중 하나를 다시 backing store에 보내고(page-out),
새로운 페이지를 메모리에 올려야한다.(page-in)
이를 페이지 교체라고 한다.
여기서 backing store로 page-out이 된 페이지를 victim page 라고 한다.
메모리 과잉 할당 문제
•
다중프로그래밍의 정도를 높일수록 물리 메모리 과할당이 발생할 수 있음
◦
다중 프로그래밍 : 프로세스가 여러 개 떠 있는 상태
•
메모리 과할당 발생
◦
유저 프로세스가 실행되는 동안 페이지 폴트가 발생
◦
운영체제는 원하는 페이지가 보조 저장소에 있는 위치를 결정하지만, 모든 메모리가 사용 중이므로 빈 프레임이 없음 을 확인
•
메모리 과도 할당에 대한 옵션들
◦
프로세스 종료
◦
페이지 교체 → 가장 보편적인 솔루션
•
페이지 교체가 필요한 상황
1번 프로세스는 B가 페이지 아웃되어 있음
2번 프로세스는 G가 페이지 아웃되어 있음
페이지 폴트가 발생해서 backing store에서 B 혹은 G를 스왑 인(page in) 하려고 하는 데 물리 메모리에 로드할 자리가 없음 ⇒ 과할당
B를 스왑 인 시키기 위해서는 물리 메모리 중 하나의 프레임을 victim frame으로 만들어서 free frame으로 만들어주어야 한다
•
페이지 교체 기본
1.
보조 저장소에서 원하는 페이지의 위치를 검색
2.
빈 프레임 찾기
a.
빈 프레임이 존재한다면, 사용
b.
빈 프레임이 존재하지 않는다면, 페이지 교체 알고리즘을 사용하여 희생 프레임(victim frame) 선택
•
modify (invalid or dirty) bit 사용
◦
오버헤드 줄임
◦
더 이상 물리 메모리에 존재하지 않는다고 가리킴
c.
victim frame을 2차 저장소(backing store)에 page out(필요 시) 
그에 따라 페이지 및 프레임 테이블을 변경
그에 따라 페이지 및 프레임 테이블을 변경 3.
원하는 페이지를 새롭게 비게 된 프레임으로 페이지 인
그런 후, 페이지 및 프레임 테이블 변경
그런 후, 페이지 및 프레임 테이블 변경 4.
페이지 폴트가 발생한 유저 프로세스를 계속 진행
Victim Page(희생양 페이지)
희생양 페이지는 어떤 페이지로 하는 것이 좋을까?
•
먼저 생각할 수 있는 것은 메모리에 올라가 있는 페이지 중 CPU에 수정(modify)되지 않는 페이지를 고르는 것이 효율적으로 보인다.
•
읽기만 수행하는 페이지를 고르는 것이 이상적이다.
수정되지 않은 페이지는 page-out이 될 때 backing store에 쓰기(write) 연산을 할 필요가 없기 때문이다. backing store는 읽는 시간도 느리지만, 거기에 더해 쓰기 작업까지 한다면 더욱 비효율적일 것이다.
•
해당 페이지가 수정되었는지 안되었는지를 판단할 수 있어야 하는데, 이를 위해 페이지 테이블에 modify bit(=dirty bit)를 추가하여 이를 검사
수정 비트(Modify bit or Dirty bit)
•
프레임이 없다면, 두 번의 전송이 필요(page-out용, page-in용)
•
수정 비트(혹은 더티 비트)를 사용하여 오버헤드를 줄임
◦
해당 페이지가 수정되었다면 이 비트를 1로 두고, 수정되지 않으면 0으로 둔다.
•
페이지의 수정 비트는 페이지의 바이트가 기록 될 때마다 하드웨어에 의해 설정되어 페이지가 수정되었음을 나타냄
•
이 방식은 페이지가 수정되지 않은 경우 I/O 시간을 ½로 줄이기 때문에 페이지 폴트를 처리하는데 필요한 시간을 크게 줄일 수 있음
•
그림 예시
◦
여기서 수정되지 않은 페이지는 0, 2, 3번 3개의 페이지가 존재하는데 이 중에서는 어떤 페이지를 선택해야 할까?
제일 간단한 방법은 랜덤하게 선택하는 것이지만, 이는 성능을 보장할 수 없다.
그 다음은 가장 먼저 메모리에 올라온 페이지를 희생양 페이지로 선택하는 것이다.
이는 아주 유명한 FIFO(First-In First-Out) 방식이다. 이 외에도 여러가지 방법이 존재한다.
프레임 할당 및 페이징 교체 알고리즘
•
요구 페이징을 적용하는데 생기는 두가지 주요 문제점
◦
프레임 할당 알고리즘
▪
어떤 프로세스에 몇 개의 프레임을 할당해야 하는가
◦
페이지 교체 알고리즘
▪
교체되어야할 프레임을 선택
•
보조 저장 장치의 I/O 는 너무 비싸다
◦
요구 페이징의 성능이 조금만 좋아져도 시스템 성능은 크게 개선된다
페이징 교체 알고리즘의 목적 – 페이지 폴트 율을 최소화
Page and Frame Replacement Algorithms
•
프레임 할당 알고리즘 (page allocation)
◦
메모리에 여러 프로세스가 있는 경우, 각 프로세스에 할당할 프레임 수 결정이 필요
•
페이지 교체 알고리즘 (page replacement)
◦
페이지 교체가 필요한 경우 교체할 프레임을 선택해야 함
◦
페이징 교체 알고리즘의 목적 – 페이지 폴트 율을 최소화
•
참조열(reference string) ⇒ 밑에서 더 자세히
◦
메모리 참조열
◦
주소 시퀀스
0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102…
◦
참조 문자열
1, 4, 1, 6, 1, 6, 1, 6, 1
◦
연속된 페이지는 생략하고 하나의 페이지 번호만 나타낸 것
•
프레임 수에 따른 페이지 폴트 그래프
◦
프레임 수가 증가함에 따라 페이지 폴트 수는 최소 수준으로 떨어짐
Page reference string
페이지 교체 알고리즘을 살펴보기 전에 Page reference string 이라는 용어를 알아야 한다.
CPU가 내는 주소는 이진수 단위이지만, 페이지 교체 알고리즘을 계산하기 위해서는 이진수 주소 단위가 아닌 페이지 단위로 계산해야한다.
CPU 논리 주소 | 요청할 페이지 번호 |
100 | 1 |
101 | 1 |
432 | 4 |
612 | 6 |
103 | 1 |
104 | 1 |
611 | 6 |
612 | 6 |
편의를 위해 CPU가 내는 주소를 십진수로 표현했다.
만약 페이지 크기를 100이라 하면, 우측과 같이 된다.
주소 100번지 = 1번 페이지에서 offset이 0인 위치
101 = 1번 페이지의 offset 1인 위치
마지막으로 페이지 번호로 나타낸 것을 page reference string으로 나타내면 {1, 4, 6, 1, 6}이다.
이는 간단히 말하면 연속된 페이지는 생략하고 하나의 페이지 번호만 나타낸 것으로 볼 수 있다.
이 이유는 연속된 페이지를 참조할 때는 한 번 page fault가 발생하면 같은 페이지를 사용하는 동안에는 절대 page fault가 발생할 수 없기 때문이다.
즉, CPU가 가리키는 page의 번호가 연속적으로 동일하다면, disk로 가서 page를 가져올 필요가 없으므로, 위의 번호들만 가지고 판단하는 것이 바람직하다.
페이지 교체 알고리즘 (page replacement)
FIFO 페이지 교체
•
가장 간단한 페이지 교체 알고리즘
•
가장 먼저 page-in 한 페이지를 먼저 page-out 시킨다
•
페이지를 교체해야 하는 경우 가장 오래된 페이지가 선택됨
•
예시
◦
페이지 참조열(page reference string)
▪
{7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 7, 0, 1}
◦
사용가능한 프레임 개수(number of frame): 3
◦
최초의 메모리는 비어있는 상태이다.
•
페이지 폴트 15개
•
이전에 page-out한 페이지를 그 다음 바로 page-in을 하려한다면 다시 page fault가 발생
하기 때문에 비효율적인 모습을 볼 수 있다.
•
참조 문자열에서의 FIFO 페이지 교체를 위한 페이지 폴트 곡선
◦
Belady’s Anomaly
▪
프레임 수가 증가하면(= 물리 메모리 용량이 증가하면) page fault 수가 줄어드는 것이 정상적
▪
위의 FIFO를 사용했을 때, 그래프를 그려보면 위와 같은 결과
▪
특정한 페이지 참조열에 대해서는 프레임 수가 증가해도 page fault 수가 오히려 증가하는 이상 현상이 발생
최적 페이지 교체(Optimal(OPT))
•
모든 알고리즘 중 가장 낮은 페이지 폴트율
•
장기간 사용하지 않을 페이지 교체 ⇒ 가장 오랫동안 사용되지 않을 페이지를 희생양 페이지로 선택
◦
언제 어디까지 페이지 사용 여부를 전부 보아야 함 ⇒ 비현실적 (미래를 볼 수 없음)
◦
어느 프로세스가 가장 오래 사용안되는 지를 계산할 수 없다.
◦
페이지 폴트 9개 (현재까지 중에서는 제일 낮은 페이지 폴트율)
LRU(Least-Recently-Used) 페이지 교체
•
최적 알고리즘의 근사치
•
가장 오랫동안 사용(참조)하지 않은 페이지 교체(victim page로 선택)
◦
최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 개념 (reference locality)
•
LRU 교체는 해당 페이지가 마지막으로 사용된 각 페이지와 연결
◦
12번의 폴트
폴트 수 : FIFO > LRU > 최적
◦
LRU는 근사 해를 구하므로 OPT보다는 page fault가 많이 발생하지만, FIFO보다는 일반적으로 적게 일어난다. 그러므로 현재 대부분 환경에서는 LRU를 사용하고 있다.
▪
Belady’s Anomaly를 겪지 않음(Optimal과 동일)
•
LRU는 하드웨어 지원이 필요
◦
가장 마지막으로 사용(참조)된 프레임의 순서는 어떻게 되는가?
▪
카운터와 스택이 사용됨
▪
Counter 구현
•
페이지가 참조될 때마다, Counter(혹은 clock)를 복사
•
페이지를 가장 작은 값으로 대체(제일 참조 빈도가 적은)
▪
Stack 구현
•
페이지 넘버를 스택 리스트에 보관
◦
Doubled linked list로 구현됨
◦
우리가 아는 스택과 다른 자료 구조
•
요소는 스택 중간에서 제거되어야 한다
•
LRU Approximation 알고리즘
◦
Reference bit 사용
▪
각 페이지 별로 처음에는 0으로 설정
▪
페이지가 참조되면 1로 세팅
▪
페이지가 대체되면 다시 0으로 세팅
◦
Second-chance algorithm
▪
FIFO 대체 알고리즘 사용
▪
만약, 페이지가 교체되면 reference bit를 조사한다
•
reference bit 값이 0 : 페이지를 교체한다
•
reference bit 값이 1 : 페이지에게 second chance를 주어서 다음 FIFO 페이지를 선택
▪
페이지가 second chance를 가지게 되면
•
reference bit는 초기화되고
•
도착 시간이 현재 시간으로 갱신된다
프레임 할당 (Allocation of frame)
page를 메모리에 할당하는 프레임 할당에 대해 알아보자
스래싱 개념
프로세스에 ‘충분한’ 프레임이 없다면 어떤 일이 발생할까? (페이지 폴트 발생 → 페이지 교체)
•
작업을 하는데 필요한 최소한의 프레임도 없을 경우
•
이때, 일부 페이지를 교체해야 함.
그러나, 모든 페이지가 활성되어 사용 중이므로, 즉시 다시 필요한 페이지를 교체해야 함
•
결과적으로, 즉시 다시 가져와야 하는 페이지를 교체하고 반복해서 빠르게 가져와야 하는 오류가 발생
•
이런 과도한 페이징 작업을 스래싱이라고 함
◦
어떤 프로세스가 실제로 실행하는 시간 > 페이징 시간
◦
페이지 폴트율이 높아진다
스래싱 원인
•
(전제) CPU는 보통 이용률이 너무 낮으면
→ 시스템에 새로운 프로세스를 도입하여 다중 프로그래밍의 정도를 높임
◦
일반적으로 메모리에 올라가는 프로세스 개수가 증가할수록 CPU의 이용률은 올라갈 것이라 예상한다. 왜냐하면 프로세스가 많을 수록 CPU의 할 일 역시 증가하기때문이다. 이는 일정 범위까지는 맞는 예상이지만, 그 범위를 넘어서면 오히려 CPU 이용률이 감소하는 현상이 나타난다.
•
프로세스가 증가할수록 메인 메모리의 비어있는 프레임 개수는 줄어들게 되고 결국 모든 프레임이 가득 차게 된다.
◦
계속 프로세스가 증가한다면 메모리와 backing store 사이에 page in/out 작업이 발생
◦
프로세스가 많아질수록 이 작업 역시 증가한다. page in/out은 디스크 I/O 작업으로 CPU를 사용하지 않는 작업
▪
이 폴트 프로세스는 페이징 장치를 사용하여 swap in, swap out.
페이징 장치를 대기할 때, 준비 대기열이 비워짐.
프로세스가 페이징 장치를 기다리면 CPU 이용률이 감소
◦
Thrashing : I/O 작업이 증가하여 CPU 이용률이 떨어지는 현상
•
CPU 스케쥴러는 감소하는 CPU 이용률을 보고 다중 프로그래밍의 정도를 높임 → 악순환
→ 새로운 프로세스는 실행 중인 프로세스에서 프로세스를 가져와 시작하려고 하므로,
페이징 장치에 대해 더 많은 페이지 오류와 더 긴 대기열이 발생
→ CPU 활용도는 더욱↓, CPU 스케쥴러는 다중 프로그래밍 정도를 또 ↑ ⇒ 쓰레싱 발생
→ 시스템 처리량 급감
•
스래싱 발생 그래프
•
스래싱 제한, 방지
1.
스래싱 제한
•
지역교체 알고리즘 : 현재 수행중인 프로세스에게 할당된 프레임 내에서만 교체대상을 선정하도록 함
◦
Global Replacement보다 Local Replacement를 사용하는 것이다.
◦
하지만 이 경우에는 메모리 사용 효율이 떨어지는 단점이 있다.
◦
ex) Working-Set Model
•
우선순위 교체 알고리즘
2.
스래싱 방지를 위해서는, 프로세스가 필요한 만큼의 프레임(메모리)을 프로세스에 제공하면 됨.
적절한 프레임의 수는 어떻게 정하는 것일까?
프레임 할당의 방법
But, 프로세스마다 프레임이 얼만큼 필요한지 어떻게 산정 할 것인지?
프레임 할당은 크게 정적 할당과 동적 할당으로 나뉜다.
정적 할당(Static Allocation)
•
동일 할당(Equal Allocation)
◦
모든 프로세스에게 똑같은 수의 프레임을 할당한다. 이 방식은 프로세스의 크기에 따라 매우 비효율적이다.
•
비례 할당(Proportional Allocation)
◦
프로세스의 크기에 따라 프레임을 할당한다. 이 방식 역시 단점이 있다. 프로세스 크기가 크더라도 모든 기능을 사용하지 않기 때문에 이 방식 또한 비효율적이다.
이처럼 정적 할당은 한계가 뚜렷하다. 따라서 동적 할당의 방법을 사용하는 것이 좋다.
Global VS Local Replacement
•
Local Replacement
◦
메모리 상의 자기 자신의 프로세스 페이지에 대해서만 교체 작업을 수행한다.
◦
지금 요청이 들어온 page가 p1이라면, 메모리상에 올라가 있는 frame 중 p1 frame만 교체의 대상으로 간주한다.
•
Global Replacement
◦
메모리 상의 모든 프로세스 페이지에 대한 교체 작업을 수행한다.
◦
앞에서 배운 FIFO, OPT, LRU 등은 Victim을 정할 때, 모든 메모리에 올려져 있는 frame을 다 확인 후에 교체를 수행했다.
메모리 사용 효율은 일반적으로 Global Replacement가 좋다.
동적 할당(Dynamic Allocation)
작업집합방법(Working set model)
•
프로세스가 실행이 될 때 항상 어떠한 특정 지역에서만 메모리 집중 참조
•
프로세스가 실행 중일 때 어느 페이지를 사용하는지 실험한 결과에서 Locality 성질이 성립한다는 것을 발견할 수 있었다. 즉, 특정 시간에는 일정 범위의 페이지를 주로 참조하는 것을 알 수 있다.
locality model
◦
어떻게 locality를 조사할 수 있을까?
여기서 치명적인 단점이 있다. 바로 프로세스를 미리 수행해봐야 할 수 있다는 것이다. 그리고 프로세스를 수행할 때마다 사용하는 기능이 달라질 수 있으므로, Locality를 이용하는 방법은 비현실적
•
이를 해결하기 위해 나온 것이 working set
◦
working set은 위의 locality의 방식과 유사한데, 미래가 아닌 과거를 보는 것
◦
특정 시간에 따라 사용하는 페이지의 개수만큼 프레임을 할당
⇒ 프로세스의 지역성을 이용해 하나의 작업 집합(working set)으로 만듦
◦
working set은 현재 시간에서 일정 시간(Δ) 이전 동안 사용되었던 페이지의 집합
▪
Δ(델타) : working set window, 운영체제 내부에서 정하는 기준에 따라 다름
◦
working set의 개수만큼 프레임을 할당
▪
예시 ) 현재 시간이 t1이라면 working set = {1, 2, 5, 6, 7}이다.
이 때 working set의 개수는 총 5개이므로 프레임 역시 5개를 할당
◦
반대로 working set 밖에 있는 것을 페이지 교체의 victim page로 선택할 수 있다.
◦
Working set Model을 통해 Thrashing 문제 완화 가능
페이지 폴트 빈도(PFF, Fage-Fault Frequency)
•
페이지 부재의 비율은 프로세스에 할당된 프레임의 수에 반비례
◦
할당된 프레임의 수가 적을수록 페이지 부재 비율은 늘어난다.
•
페이지 폴트를 빈도(폴트율)을 보고 프레임 제공 개수 결정
◦
페이지 폴트율의 상한과 하한을 정해서 제공, 프레임 개수 결정
▪
상한선보다 많은 페이지 폴트가 발생하면 프레임을 더 많이 할당해주고,
하한선보다 적게 페이지 폴트가 발생하면 할당된 프레임 개수를 줄여준다.
•
프레임 적음 ⇒ 페이지 폴트 증가
•
프레임 너무 많음 ⇒ 페이지 폴트 감소
페이지 크기
페이지 크기에 따라 성능에는 어떤 영향을 미치는지 알아보자.
•
페이지 크기(Page Size)
◦
페이지 크기는 일반적으로 2의 거듭제곱. 페이지당 4KB ~ 1GB
◦
외부 단편화 방지
◦
논리 주소 공간 사이즈가 , 페이지 사이즈가 바이트라고 할 때,
논리 주소의 상위 m-n 비트는 페이지 번호를 지정, 하위 n비트는 페이지 오프셋 지정
◦
p는 페이지 테이블의 인덱스, d는 페이지 내의 오프셋
페이지 크기에 따른 성능
•
내부단편화
◦
내부단편화를 줄이려면 페이지 크기는 작은 것이 좋다.
•
Page-in, page-out 시간
◦
페이지의 in/out 시간을 결정하는 가장 큰 요인은 하드디스크 기준으로 하드디스크의 헤더가 움직이는 시간이다.(seek time) 페이지 크기가 크면 클수록 한 번의 seek time마다 큰 페이지를 읽을 수 있으므로, 페이지 부재 빈도가 줄어든다.(데이터를 읽는 시간은 크기에 따라 차이가 매우 적다.)
•
페이지 테이블 크기
◦
페이지 크기가 클수록 페이지 개수가 줄어들기 때문에 그만큼 페이지 테이블 크기도 줄일 수 있다.
•
Memory resolution(해상도)
◦
Memory resolution은 해당 메모리에 필요한 데이터가 있는 확률이다.
이는 페이지 크기가 작을수록 resolution을 높일 수 있다. 만약 페이지 크기가 크면 다른 필요없는 부분이 있을 확률이 크기 때문이다.
•
Page fault 발생 확률
◦
Page fault 발생 확률을 줄이려면 페이지 크기가 큰 것이 좋다. 이는 locality 성질과도 관련이 있는데, 대부분 프로세스는 필요한 부분이 일정 범위 이내인 경우가 많으므로 페이지 크기가 클수록 필요한 부분이 있을 확률이 크다.
page big | page small |
Page fault 발생 확률 ▼ | 내부 단편화 ▼ |
페이지 테이블 크기 ▼ | Page-in, page-out 시간 ▼ |
Memory resolution(해상도) ▲ |
페이지 테이블
반도체 기술의 발달로 TLB 역시 CPU의 내장 칩 형태로 만들어져있다.
버디 시스템
•
가변 분할 방식과 고정 분할 방식을 혼합 → 단점 최소화
•
2의 승수로 메모리를 분할하여 메모리를 할당
•
근접한 메모리 공간을 합치기 쉽다 → 2의 승수로 나눴기 때문에 반대로 조립만 하면 됨