10.1 배경
가상 메모리란? 프로세스 전체가 메모리에 올라오지 않고 실행이 가능하게 하는 기법이다. 이 기법은 물리 메모리보다 더 큰 양을 가질 수 있다.
프로그래머의 관점의 논리 메모리를 물리 메모리로 부터 분리하면 메인 메모리는 균일한 크기의 저장공간인 엄청 큰 배열로 추상화 된다.
장점 :
- 메모리 크기에 제약이 자유로워진다.
- 파일과 라이브러리의 공유가 쉬워지고, 공유메모리 구현을 가능케 한다.
- 프로세스의 효율적인 생성 처리가 가능해진다.
단점 :
- 구현하기 얿다
- 잘못 사용하면 성능이 현저히 저하된다.
9장까지에서는 코드는 반드시 물리 메모리에 존재하고, 이에 가장 쉬운 방법이 전체 프로세스가 메모리에 올라가는 것이었다.
물론 dynamic loading이 어느정도 완화시켜 주지만 이 방법은 프로그래머에게 주의와 추가작업을 요구한다.
가상 메모리의 구현을 가능하게 하는 경우들
- 잘 일어나지 않는 오류 상황을 처리하는 코드
- 배열, 리스트, 테이블등이 실사용 이상으로 많은 용량으로 선언
- 프로그램의 어떤 옵션이나, 기능이 거의 쓰이지 않음
- 전체 프로그램의 모든 부분이 모두 동시에 요구되지 않음.
프로그램을 일부분만 메모리에 올려놓게 된다면 다음과 같은 장점이 있다.
- 물리 메모리 크기에 제약이 없어 프로그래밍 작업이 간단해진다.
- 각 프로그램이 사용하는 메모리 크기가 작아져 더 많은 프로그램이 동시 수행된다. 응답 시간이 그대로이면서 cpu이용률, 처리율이 높아진다.
- 프로그램을 메모리에 올리고 swap하는데 필요한 I/O횟수가 줄어든다.
(왜인지 모르겠음) https://ch4njun.tistory.com/124
논리적 메모리의 구조는 위 그림과 같다. 힙, 스택 사이의 공간을 sparse 주소 공간이라고 하는데, 이 공백은 힙, 스택이 확장되거나 동적으로 라이브러리를 링크할때 사용된다.
그 외에도 가상 메모리는 둘 이상의 프로세스가 파일, 메모리를 공유할 수 있게 한다. (페이지 공유)
- 표준C 라이브러리 같은 시스템 라이브러리가 여러 프로세스에 읽기 모드로 공유된다.
- 프로세스끼리 공유할 수 있는 영역을 만들어 공유메모리를 통해 통신한다.
- fork() 등으로 프로세스 생성 과정에도 페이지가 공유 가능해 프로세스 생성 속도가 높아진다.
10.2 요구 페이징
보조 저장장치(백업) -> 메모리로 실행프로그램 적재하기
- 전체 프로그램 물리 메모리에 적재
-> 아까 말했던 모든 옵션 등이 모두 물리 메모리에 적재됨.
- 요구페이징 기법 - 필요한 페이지만 적재
-> 프로그램 실행 중 필요할 때에만 페이지에 적대됨.
10.2.1 기본 개념
- valid-invalid 비트 기법
: 해당 페이지가 물리 메모리에(유효) 있는지, 없거나 보조 저장장치에만 있는지 (무효) 구분한다.
그림 10.4) 만약 B, D같이 메모리에 없는 페이지를 접근한다면? page-fault 트랩이 발생해 처리된다.
page-fault 발견-해결 과정
-
프로세스에 대한 내부 테이블을 검사해 그 메모리 비트가 유효/무효인지 알아낸다.(페이징 하드웨어가 페이지 테이블로 주소변환 중 발견, 트랩 걸기)
-
무표한 페이지라면 그 프로세스는 중단된다. 실제로는 있는데 메모리에 없다면(무효비트) 보조 저장장치로 가져와야한다.
-
빈 공간, free frame을 찾는다.
-
보조 저장장치에 이 프레임에 이 페이지를 달라고 요청한다
-
보조 읽기가 끝나면 페이지 테이블을 갱신하고 프로세스 내부 테이블을 고친다.
-
트랩에 의해 중단되었던 명령어를 다시 수행한다.
극단적으로 모든 페이지가 하나도 없어도 수행할 수 있다. pure demand paging 은 어떤 페이지가 필요해지기 전까지 그 페이지를 메모리로 적재하지 않는다.
요구 페이징은 특히 locality of reference 덕분에 만족할만한 성능을 보인다. (한 명령어에서 여러 페이지를 참조하는 경우가 잘 없다.)
- 페이지 테이블 : protection bit들을 i/u 비트로 특정 항목을 무효로 설정할 수 있다.
- 보조 저장장치 : swap space라고도 한다. 메인메모리에 없는 모든 페이지를 가지고 있다.
요구 페이징을 위한 필수적인 요구 사항은 페이지 부재 오류 처리 후에 명령어 처리를 다시 시작할 수 있어야 한다.
C=A+B
1. 명령어(ADD) 인출
2. A인출
3. B인출4. A+B
5. C에 저장
이 외에도 블록들이 겹치거나, 페이지 경계에서 두 페이지에 걸치는 블록 등에서 문제가 발생한다.
해결책 :
1. 마이크로코드 : 미리 페이지 폴트 가능성이 있다면 트랩 발생시켜 이동하기
2. 임시 레지스터 : 이동때문에 이전 내용의 값을 보존했다가 복구
10.2.2 가용 프레임 리스트
페이지 폴트가 일어날 때 운영체제는 요청된 페이지를 보조저장장치 -> 메인 메모리로 가져온다. 이 작업을 수용하기 위해 가용프레임 풀인 가용 프레임 리스트를 유지하는데, 프로젝트의 스택, 힙이 확장될때도 가용 프레임이 할당된다. 운영체제는 이때 zero-fill-on-demand기법으로 할당한다. 이 방법은 할당되기 전 프레임을 모두 0으로 채운다.(보안을 위함.)
가용 프레임이 요구되면 가용 프레임 리스트 크기는 하나씩 줄어든다. 만약 리스트 크기가 0이 된다면? (10.4절에서 이어짐..)
아휴..
...
끝이안난다..
10.2.3 요구페이지의 성능
- 페이지 폴트가 없을 때
실질 접근 시간 == 메모리 접근 시간 - 페이지 폴트가 발생할 때
실질접근시간 == 페이지 폴트 처리 시간 - 페이지 폴트 확률이 p 일때 총 실질 접근 시간
(1-p) x(메모리접근시간) + p x(페이지폴트 시간)
그렇다면 페이지 폴트 시간은 얼마나 걸리는가? 다음을 고려해라
- 운영체제에 트랩 요청
- 레지스터, 프로세스 상태 저장
- 인터럽트 원인?-> 페이지 폴트 확인
- 페이지 참조가 i?v? -> 백업장치에 페이지 위치 확인
- 저장 장치에 가용프레임으로 읽기 요청
- 읽기 차례가 돌아올때까지 대기큐에 있다가 -> 디스크에서 찾는 시간, 회전 지연시간 동안 기다림 -> 가용 프레임으로 페이지 전송을 시작함
- 기다리는 동안 CPU코어를 다른 사용자에게 할당
- 저장장치가 다 읽으면 인터럽트 발생(I/O 완료)
- 6에서 사용한 다른 프로세스의 레지스터, 프로세스 상태 저장
- 인터럽트가 보조 저장장치에서 발생한 것 확인
- 새 페이지가 메모리로 올라온것을 페이지 테이블, 다른 테이블들에 기록(업데이트)
- CPU코어가 자기 차례로 오기까지 기다림.
- 저장해두었던 레지스터....페이지 테이블 모든 상태를 복원시키고 명령어 다시 수행
요약하자면
1. 인터럽트 처리
2. 페이지 읽기(백업 장치의 종류별로 다르다)
3. 프로세스 재시작
즉, 실제 접근 시간은 페이지 폴트율(page fault rate)에 비례한다. 따라서 페이지 폴트율을 낮게 유지하는 것이 상당히 중요하다 !!
요구 페이징의 또 다른 특성인 스압 공간의 관리를 알아보자.
칸이 부족해서 생략하기로 했다..
10.3 Copy-on-Write
fork()를 통해 프로세스 생성 시 10.2에서 나온 첫 요구 페이징도 생략할 수 있다. (이게 뭐게요?)
그렇다면 새롭게 할당할 페이지 수도 최소화시킬수 있겠지?
잠깐!! 근데 fork()가 어떻게 작동하더라..
- 부모와 똑같은 자식프로세스가 부모페이지를 복사 한다.
- 자식 페이지가exec() 하면 페이지는 금방 사라진다.
-> 복사하지 말고 copy-on-write 한다.
copy-on-write
자식이 시작하면 당분간 부모 페이지를 같이 쓴다. 부모/자식이 write를 시도할 떄 그 페이지의 copy를 만든다
그림10.7, 8) 물리 메모리 상태
이렇게 하면 수정하는 페이지에 대해서만 자식용copy가 생기고, 페이지 수를 아낄 수 있다.
10.4 페이지 교체
시스템 메모리는 프로그램 페이지 저장만 하는 것이 아니다. I/O버퍼, 프로세스등등..다중 프레임 정도를 올리다 보면 메모리 과할당(over-allocating)이 발생한다.
또, 여러 프로세스가 프레임 풀 보다 더 큰 수의 프레임을 요구할 수도 있다.
그림에서 보이는 ? 물음표. 운영체제는 트랩이 발생해 페이지 위치를 백업에서 찾았지만 가용프레임이 더이상 없음을 발견했다.
이때에 해결방법은?
- 프로세스 종료하기. -> 사용자가 어이없어짐. 당연함
- 표준 스와핑 하기 -> 9장에서 더이상 안 쓸거라고 했다. ㄱㅡ
그렇다면... 페이지 스와핑 + 페이징 교체 하기
10.4.1 기본적인 페이지 교체
현재에서 안쓰고 있는 프레임은 비워버리자!
위 과정에서 디스크는 두번 접근된다.
1. 비우는 프레임을 백업에 저장
2. 가져올 프레임을 읽음
이때 1번은 modify bit(또는dirty bit(를 하드웨어에 적어놓아 감소시킬 수 있다. -> 변경 되지 않았으면 디스크에 저장안함. 그럼 2번할거 1번만 하니까 페이지 폴트 시간이 줄어든다.
요구 페이징의 기본은 페이지 교체이다. 따라서 요구 페이징 시스템은 두가지 중요한 문제를 해결해야 하는데, 바로 프레임 할당 알고리즘과 페이지 교체 알고리즘이다.
- 프레임 할당 : 어떤 프로세스에 얼마나 프레임을 할당할 것인가?
- 페이지 교체 : 어떤 페이지를 교체할 것일까? (보조저장장치 I/O비용 높아서)
일반적으로 페이지 교체 알고리즘은 페이지 폴트율이 가장 낮은 것을 선정한다.
10.4.2 FIFO 페이지 교체
가장 간단한 페이지 교체 알고리즘.
큐로 페이지를 관리한다.
- 장점 : 구현하기 쉽다
- 단점 : 성능이 항상 좋지는 않다.
여기서 퀴즈!! 다음 참조열에서 프레임이 3개일때 페이지 폴트는 몇 번 발생할까?
.
.
.
.
.
.
.
정답 :
성능이 더 안좋아 질 수 도 있는 이유 :
프레임이 4개일때 -> 10번의 페이지 폴트
프레임이 3개일때 -> 9번의 폴트
으잉?? 분명히 프레임이 늘어나면 페이지 폴트가 일어난다고 했는데!! 이 현상을 Belady의 모순이라고 한다.
10.4.3 최적 페이지 교체
앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하라
장점 : 프레임 수가 고정된 경우 가장 낮은 페이지 폴트율을 보장한다.
단점 : 구현이 어렵다. (7이 18회 후 사용될걸 내가 어떻게 알아?) -> 실제 사용보단 비교 연구 목적을 위해 사용한다.
10.4.4 LRU 페이지 교체
least-recently-user 알고리즘
.3 방법을 근사해보자.. 최근의 과거를 가까운 미래의 근사치로 본다면(이 말이제일 모순이지..) 가장 오랜 기간동안 사용되지 않은 페이지를 교체할 수 있다.
페이지마다 마지막 사용 시간을 유지한다. 페이지 교체시에는 가장 오랫동안 사용되지 않은 페이지를 선택한다.
장점 : 물론, 예측이 정확하진 않지만 큐보다는 낫다.
덤 : 하드웨어의 지원이 필요하다(계수기나 스택)
+) 스택의 경우 : 최근의 사용된 페이지 번호가 top에 들어온다.
10.4.5 LRU 근사 페이지 교체
.4에서 하드웨어 지원이 안될때 쓰는 방법.
참조비트 라는걸 만들어서 일정시간동안 참조되는 페이지는 하드웨어가 1로 세팅한다. 사용순서는 몰라도 한동안 어떤 페이지가 사용되고, 사용되지 않았는지 알 수 있다.
자세하게는
- 부가적 참조 비트 알고리즘
- 2차 기회 알고리즘
- 개선된 2차 기회 알고리즘
이 있는데.. 생략하기로 한다.
10.4.6 Counting-Based 페이지 교체
- LFU 알고리즘(least frequently)
: 참조 횟수가 가장 작은 페이지 교체하기
장점 : 활발하게 사용하는 페이지 쓴다
단점 : 초반 반짝하게 활발하게 사용된 페이지도 쓴다.
해결방법 : 참조 횟수를 시간에 따라 지수적(쉬프트연산)으로 영향력을 감소시킨다. - MFU 알고리즘(most frequently)
: 가장 작은 참조 횟수가 제일 최근에 사용한거다. 앞으로도 사용할꺼다.
사실.. 이 방법은 둘다 잘 안쓰인다. 구현하는데 시간이 많이 드는데 딱히 최적도 아님.. 왜만들었지
10.4.7 페이지-버퍼링 알고리즘
어?이해못했다
10.4.8 응용과 페이지 교체
어 ? 어어 ??
