가상 메모리

가상 메모리

운영체제가 메모리를 관리하는 방법

등장배경: 메모리에 많은 프로세스들을 동시에 올려놓고 살행 시키기 위해 등장.

프로그램 일부분만 메모리에 올려놓고 실행한다.

프로세스 전체가 메모리에 올리오지 않아도 실행을 가능케 해준다.

물리 메모리에 제약을 받지 않게된다.

실제 물리 메모리의 개념과 사용자의 논리 메모리 개념을 분리.

가상 메모리 사용시 페이지 공유를 통해 둘 이상의 프로세스에서 파일과 메모리를 공유할 수 있다.

 

 

연속 메모리 할당

프로세스에 연속적인 메모리 공간을 할당하는 것.

프로세스들이 메모리 내에서 연속적으로 할당되는 방식.

프로세스의 크기만큼 메모리를 할당 받아 배치, 다음도 반복

 

 메모리 관리 기능: 스와핑

현재 사용되지 않는 프로세스들을 보조 기적 장치 일부 영역 (스왑 영역) 으로 쫓아내고 이렇게 생긴 빈 공간에 새 프로세스를 적재하는  

swap in = 실행될 프로세스가 메모리에 들어가는 것

swap out =사용되지 않는 프로세스가 스왑영역으로 들어가는 것

지금 당장 사용되는 프로세스만 메모리에 배치된다. 효율적.

프로세스들이 요구하는 메모리 공간 크기가 실제 메모리보다 큰 경우에도 동시에 프로세스들을 실행할 수 있다.

( 당장 쓸 것만 메모리에 적재하고 안쓰는 부분은 스왑 영역에 배치한다.)

 

페이저: 프로세스들의 개별 페이지를 관리하는 주체. 스왑인, 스왑아웃을 주도적으로 처리한다.

스왑인시 페이저는 프로세스가 다시 스왑아웃 되기 전 실제로 사용될 페이지들이 어떤 것들인지 추측한다.

페이저는 프로세스 전체를 스왑인. 즉, 메모리로 읽어드리는 것을 전체의 대상으로 진행하지 않는다.

 

실제로 필요한 페이지들만 메모리로 읽어오기 때문에 사용되지 않을 페이지들을 메모리로 가져오지 않는다 -> 시간, 메모리 공간 낭비를 줄인다.

이를 수행 하려면 하드웨어 지원이 필요하다.

 

연속 메모리 할당

프로세스는 메모리 빈 공간에 할당 되어야 하는데, 빈공간이 여러개 있다면?

외부 단편화라는 문제가 발생하기에 메모리를 효율적으로 사용하는 방식은 아니다.

 

최초 적합first fit:

운영체제가 메모리 내를 검색하다 제일 처음 본 공간에 적재하는 것. 

검색 최소화, 빠른 할당 가능

 

최적 적합 best fit

운영체제가 빈 공간을 모두 검색 후, 적재 가능한 가장 작은 공간 (가장 딱 맞는 공간) 에 적재

모든 메모리를 스캔해야 하는 단점

 

최악 적재 worst fit

운영 체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 할당

모든 메모리를 스캔해야 하는 단점

 

연속 메모리 할당은 외부 단편화 야기 (Q. 동적 메모리 할당 ,연속메모리 할당은 같은 용어?)

외부 단편화: 사용이 끝난 프로세스들이 끝나면 공간이 생김. 근데 이 공간들이 10메가, 2메가, 5메가.. 이면 50메가 프로세스는 적재될 수 없다. 

프로세스 들을 할당하기 어려울 만큼 작은 공간들이 생겨 낭비되는 메모리가 생기는데, 이것이 외부 단편화.

(단편화? 공간 중 사용되지 못하는 공간)

-> 하지만 외부 단편화는 내부 단편화를 야기한다...

공간을 찾아 적재했는데 프로세스보다 큰 공간을 받았다. 이 떄 남는 공간이 내부 단편화

 

외부 단편화 해결 방법

 

메모리 압축:  흩어져있는 빈 공간들을 하나로 압축해 하나의 큰 공간으로 만드는 것

단점은 재배치 과정서 오버헤드가 발생, 프로세스들이 각자 할 일을 못함.

오버헤드를 최소화하기 위한 방식을 명확하게 특정 짓기 어렵다는 부작용이 있다.

재배치가 동적이고 실행 시간에 수행되는 경우만 가능하다.

많은 비용 소모

 

 

가상 메모리 기법

가상 메모리란? 실행하고자 하는 프로그램의 일부만 메모리에 적재해 실제 물리 프로세스보다 큰 프로세스를 실행 할 수 있게하는 기술 - 모든 프로그램을 적재할 필요는 없다!

 

페이징과 세그멘테이션 기법이 있다.

 

페이징: 프로세스의 물리 주소 공간이 연속적이지 않도록 하는 메모리 관리 체계

요구 페이징 가상 메모리를 로드하면, 프로그램 실행 요정이 있을 떄만 페이지가 로드된다.

액새스 되지 않은 페이지는 물리 메모리에 적재되지 않는다.

외부 단편화의 근본적인 문제는, 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당 되었기 때문.

만약 메모리에 적재되는 대상이 전부 일정한 크기를 가지고 있었다면, 외부 단편화는 발생하지 않았다.

그래서 페이징은 모든 프로세스를 일정한 크기로 자르고 잘린 프로세스를 불연속적으로 할당한다.

메모리 물리 주소 공간이 연속적이지 않더라도 사용 가능케 한다.

프로세스의 논리 주소 공간을 페이지 page라는 일정 단위로 자르고, 물리-> 프레임

메모리의 물리 주소 공간을 frame이라는 페이지와 동일한 일정 단위로 자른 후, 논리 -> 페이지

이 두개는 같은 사이즈

페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.

페이징의 장점은, 공통 코드를 공유할 수 있다. 같은 코드를 다른 물리 공간에 다시 할당할 필요가 없다.

페이징도 스와핑이 가능하다.

페이징 스와핑이 시사하는 바로는, 프로세스가 실행되기 위해 모든 페이지들이 메모리에 적재되어 있을 필요는 없다는 것이다. -> 물리 메모리보다 큰 프로세스도 실행 가능

하지만 불연속적으로 할당되어 있어 cpu는 프로세스가 어디에 있는지 알기 어렵다.

-> 그래서 페이지 테이블이 생김

논리주소 페이지 0번은 페이지 테이블에 가서 0페이지를 찾음

페이지 테이블에 1번 프레임과 0번

메모리에 가서 1번을 찾아보면 페이지 0이다.

 

1번 페이지는 페이지 테이블서 4번 프레임에 매핑.

메모리가서 4번 프레임에 페이지 1번을 넣어줌.

 

 

페이지 테이블

물리 주소에 불연속적으로 배치되더라도 논리 주소에는 연속적으로 배치되도록 하는 방법

페이지 번호화 프레임 번호를 짝지어주는 이정표.

페이징은 페이지 테이블을 반드시 사용한다.

어떤 프로세스애 어떤 페이지가 어떤 프레임에 할당되어 있는지 적혀있다.

페이지 테이블을 통해 현재 프로세스가 물리주소 내에서 실제로는 불연속적으로 배치되어 있더라도 cpu입장, 논리주소에서는 연속적으로 배치되어 있는 것 처럼 보임. -> cpu는 논리주소 차례대로 실행하면 된다. 

 

페이징은 외부 단편화를 해결하지만, 내부 단편화를 야기한다.

하나의 페이지 크기보다 작은 크기로 발생하는 메모리 낭비 문제를 내부 단편화라고 한다.

메모리 낭비의 크기가 외부 단편화 보다 작은 경우 多

 

PTBR:Process Table Base Register

cpu는 각각의 프로세스에 페이지 테이블이 어디에 저장되어 있는지 알아야 ㅎ한다

페이지 테이블의 저장 정보를 나타내기 위한 레지스터가 PTBR

각 프로세스 페이지 테이블이 적재되어 있는 곳의 주소를 가리킨다.

 

만약 cpu가 프로세스 a를 실행하고 있다. a를 이루는 페이지들이 현재 어떤 프레임에 적재되었는지를 알아야해 페이지 테이블을 참조, 페이지 테이블이 현재 어디에 저장되어 있는지를 알아야하는데 이를 PTBR 이 가리키고 있다.

 

cpu 는 프로세스 a의 페이지 테이블이 어디에 저장되어 있는지를 알게 되고, 그를 통해 프로세스 a를 이루고 있는 페이지가 현재 어떤 프레임어 적재되어 있는지를 알 수 있음.

 

cpu가 프로세스를 실행하고 있다면 PTBR는 프로세스의 페이지 테이블이 어디에 저장되어 있는지 가리키고 있다.

cpu는 프로세스의 페이지 테이블에 접근해 프로세스의 페이지 각각 어떤 프레임에 할당되어 있는지 알 수 있다.

 

 페이지 테이블이 메모리에 저장되어 있으면

메모리 접근 시간이 두 배로 든다. 페이지 테이블을 참조하기 위해 한 번, 페이지를 참조하기 위해 한 번.

페이지 테이블을 참조하기 위해 한 번 메모리를 참조하고, 페이지 테이블을 보면 어떤 페이지가 어떤 프레임에 할당되어 있는지 알 수 있는데, 이를 통해 알게된 프레임, 즉 페이지를 참조하기 위해 또 한 번. 메모리에 접근을 두 번 한다.

 

페이지 테이블이 메모리에 저장되어 있는 것이 반드시 효율적인 방법은 아니다. 메모리에 접근하는 시간이 레지스터나 캐시 메모리에 접근하는 시간보다도 오래 걸리기 때문

 

그래서 TLB 캐시 메모리: 메모리 접근 시간 문제를 해결하려고 탄생.

TLB는 key (or tag), value로 구성된다.

TLB는 현재 참조하는 페이지 테이블의 일부가 저장된다. 함께 사용

cpu는 메모리에 접근하지 않아도 TLB를 통해 곧바로 페이지와 프레임에 접근한다. - 페이지 번호를 찾으면 프레임 번호를 즉시 사용, 메모리 액세스에 사용한다.

TLB라는 특별한 캐시 메모리, 즉 페이지 테이블에 일부러 저장하고 있는 특별한 캐시 메모리를 통해 불필요한 메모리 접근을 줄일 수 있다.

페이지 번호가 TLB에 없으면, 페이지 테이블에 대한 메모리 참조를 새로 생성한다.

 

cpu에 접근하려는 논리 주소가 TLB에 있다면 - TLB 히트 , 메모리에 접근 한 번

CPU가 접근 하려는 논리 주소가 TLB에 없다면 - TLB 미스, 메모리 접근 두 번

 

페이징 주소 변환

하나의 프레임은 여러 개의 주소를 포괄하고 있기 때문에 접근하고자 하는 주소가 그 페이지에서 얼마나 떨어져 있는 곳에 있는지 알아야 한다.

 

페이징 논리 주소 = 페이지 번호 + 변위 offset

내가 접근하고자 하는 페이지의 번호화 접근하고자 하는 주소는 그 페이지에서 얼마나 떨어져 있는지에 대한 정보를 담고있는 변위.

 

논리주소는 페이지 번호와 변위로 이루어졌고 이렇게 변환된 물리 주소는 프레임 번호 + 변위

 

그렇다면 논리 주소상에서 변위와 물리주소상의 변위는 같을까? -> 같다.

페이지의 크기와 프레임의 크기는 같으니까. 크기가 같으니 내가 접근하고자 하는 주소가 어떤 페이지에서 얼마만큼 떨어져있는지 내가 접근하고자 하는 그 주소가 프레임으로부터 얼마나 떨어져있는지, 이것도 같다.

 

정리 : 페이징 시스템서 논리 주소는 페이지번호 + 변위로 이루어져있고,

이것은 페이지 테이블을 통해 프레임 번호 변위?변이 로 이루어진 물리 주소로 변환된다.

그리고 이 두가지 변위?변이는 같다

 

페이지 테이블 엔트리

페이지 번호, 프레임 번호 + 유효비트, 보호비트, 참조비트, 수정비트

 

유효비트 : 현재 해당 페이지에 접근이 가능이 가능한지, 현재 페이지가 스왑 영역인지, 메모리에 적재되어있는지를 나타냄

0 비트: 스왑 영역

1비트: 메모리 영역, 프로세스 논리 주소 공간에 속하지 않음

 

보호비트: 페이지 보호 기능을 위해 존재함

읽기만 가능한 코드 영역 read only : 0비트

수정 write 가능 : 1비트

 

참조비트 : cpu 의 접근 여부

1비트: 한 번이라도 접근했다면

0비트: 한 번도 접근하지 않았다

 

수정비트 dirty bit: cpu가 이 페이지 데이터를 사용 한 적 있는지 여부

1비트 : 변경된 적 있음

0비트: 변경 안됨

왜 존재하나? 스와핑과 관련.

이 페이지가 메모리에서 사라질 때 보조기억장치의 쓰기 작업을 해야 하는지, 필요 없는지 판단.

수정 경험이 있다면, 보조 기억 장치에도 변경된 페이지 내용을 쓰기 작업을 통해 반영해야함.

이걸 수정비트를 통해 판단한다. 1이라면 페이지의 내용을 보조기억 장치에 반영해야.

 

쓰기 시 복사

fork 시 단점: 자식 프로세스를 생성하는데 오래걸린다. 동일 내용 메모리 중복 적재 -> 메모리 낭비

이를 쓰기 시 복사로 해결

 

부모 및 자식 프로세스가 처음엔 페이지를 공유하도록 허용하여 작동.

프로세스중 하나가 공유 페이지에 쓰기 시 공유 페이지의 복사본 생성

부모 프로세스가 fork를 사용하면 프로세스가 복재되어 생성되지만 자식 프로세스는 일단 부모 프로세스와 동일한 프레임을 가리킨다. 쓰기 작업이 없다면 이 상태를 유지 하고

쓰기 작업 발생 시, 작업을 한 그 페이지는 별도의 공간에 복제된다.

 

이런 식으로 부모, 자식 프로세스가 별도의 자원을 유지하면서, 중복해서 메모리를 저장하지 않는 방식을 사용, 메모리를 더 효율적으로 관리할 수 있게 한다. 

 

계층적 페이징: 페이지 테이블을 페이징 해 여러 단계의 페이지를 두는 방식, 여러 단계의 페이지를 둔다

프로세스 테이블의 크기는 작지 않다.

프로세스를 이루는 모든 페이지 테이블엔트리를 메모리에 두는 것은 낭비. 

프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않는 방식.

outer페이지 테이블 : 페이지 테이블을 가리키고 있는 최상단의 페이지 테이블

outer페이지 테이블은 메모리에 적재한다. 그리고 셋 중 당장 써야하는 페이지 테이블만 메모리에 적재한다.

 

페이지 테이블을 여러 페이지로 나누고 이 페이지를 가리키는 페이지 테이블, 아우터 페이지 테이블을 두는 방식이 계층적 페이징이다. 메모리를 효율적으로 관리 가능하다.

 

계층적 페이징을 이용하는 환경에서의 논리 주소 = 아우터 페이지 번호 + 안쪽 페이지 번호 + 변위

 

계층이 많을 시, 페이지 폴트가 발생했을 때 메모리를 참조해야 하는 횟수가 그만큼 많아짐. 계층이 많다고 좋은 것은 아님.

 

 페이지 폴트: 무효로 표시된 페이지에 대한 액세스

내가 참조하고자 하는 그 페이지가 현재 메모리에 없는 상태를 말한다.

유효 메모리인지, 무효 메모리인지 확인하기 위해 프로세스 내부 테이블 확인한다.

무효시 프로세스를 중단, 유효시 아직 메모리에 없다면 디스크로부터 가져와 입력한다.

 

페이징 교체와 프레임 할당

 

페이징: 물리 메모리보다 큰 프로세스를 할당 할 수 있지만,  그럼에도 물리 메모리 크기는 한정되어 있다.

그래서

기존에 적재된 불필요한 페이지를 선별, 보조기억 장치로 내보내고 ( 페이지교체알고리즘),

프로세스들에게 적절한 수의 프레임을 할당해야 한다.( 프레임 할당)

 

요구 페이징

처음부터 모든 페이지를 적재 않고, 필요한 페이지만을 메모리에 적재하는 기법. 

요구되는 페이지만 적재함

 

순수 요구 페이징: 필요할 때까지 페이지를 메모리에 적재하지 않는다. 페이지 적재 하지 않고 일단 실행, 아무 것도 적재되어 있지 않으니 페이지 폴트 발생, 실행에 필요한 페이지가 적재되며 페이지 폴트 발생이 낮아진다.

 

페이지 교체 알고리즘

요구 페이징 기법. 

불필요한 페이지를 선별, 스왑구역으로 보낸다.

다중 프로그래밍의 정도를 높일 수록 메모리의 과할당이 발생 할 수도 있다.

가상 메모리가 커도, 물리 메모리엔 한계가 있다. 물리서 여러 프로그램이 돈다면 과할당이 발생한다. 안쓰는 페이지를 교체해야한다.

 

페이지 교체의 기본: 빈프레임 찾기 , 있다면 쓰기. 없다면 물리에서 사라질 프레임을 선택한다. 새롭게 페이지 적재한다. 페이지 프레임 테이블 변경 한다. 유저 프로세스 진행한다. 

 

빈 프레임이 없다면, 두 번의 전송이 필요하다 (page out, page in)

수정 비트를 사용해 오버헤드를 줄인다.

 

좋은 페이지 교체 알고리즘이란, 페이지 폴트가 적은 알고리즘이다. 페이지 폴트 발생 시, 보조 기억 장치에 접근해야해 성능이 저하된다.

 

페이지 폴트의 횟수를 아는 방법은, 

페이지 참조열: cpu가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열,

연속된 페이지를 생략하는 이유? 연속된 페이지에 접근을 하면 이미 페이지 폴트 처리 루친이 끝난 직후에 처리가 되기 때문에 연속 페이지가 있다고 해서 페이지 폴트가 발생될 필요는 없다.

 

연속된 페이지에 대해선 페이지 폴트가 발생하지 않기 때문에 연속된 페이지를 생략한 페이지열을 페이지 참조열 이라고 한다.

 

페이지 교체 알고리즘의 종류

 

FIFO first in first out

가장 단순한 알고리즘, 메모리에 가장 먼저 들어온 페이지부터 내보냄

벨라디의 모순 발생. 항상 반비례는 아니다.

 

프로그램 초기에 적재되어 프로그램 내내 사용될 페이지는?

-> 2차 기회 페이지 교체 알고리즘

fifo 보완.

오래 머물렀지만

참조비트가 1이라면, 다시 맨 끝으로 보내 가장 최근에 적재된 페이지로 간주

0이라면, 내보낸다.

참조비트를 통해 기회 줌

 

최적 페이지 교체 알고리즘

cpu에 의해 참조되는 횟수 고려

앞으로 사용 빈도가 가장 낮은 페이지 교체 (미래를 예측해야)

가장 낮은 페이지 폴트를 보장하지만 구현이 어렵다

 

최적 페이지 근사치 LRU Least Recently Used

가장 오래 사용되지 않은 페이지 교체, 과거 참조.

 

스레싱과 프레임 할당

페이지 폴트가 자주 발생하는 근본적인 이유? 프로세스가 사용할 수 있는 프레임 자제가 적어서.

 

스레싱

과도한 페이징 작업.

프로세스가 실행되는 시간보다 페이징 하는데 더 많은 시간을 사용, cpu이용율 성능이 저해되는 문제.

더 많은 프레임 요구 -> 폴트, 다른 프로세스서 프레임 가져옴 -> 잠시 중지했는데 cpu는 어? 사용률이 낮네? 더 할당 -> 더 많은 프레임 요구.. 이게 반복

 

초기 다중프로그래밍 정도가 높아지면 cpu 사용률도 높아진다. 하디만 다중프로그래밍 정도가 일정이상 높아지면 cpu는 감당 불가, 페이징이 시작된다. cpu 이용률이 급감.

 

스레싱이 발생하는 근본적인 문제는, 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문.

해결방법 : 각 프로세스가 필요로 하는 최소한의 프레임 수를 할당해줘야함

-> 이걸 어떻게 아나?

작업집합모델, 워킹셋 : 프로세스가 실행될 때 특정 지역 메모리만 집중적으로 참고한다.  이걸 지역성이라고 한다. 일정 시간 내 활발하게 사용된 곳 참조.

페이지 폴트 빈도: 페이지 폴트율을 보며 빈도 조절, 폴트율 높다면 프레임 더 줌. 

 

 

운영 체제의 프레임 할당 방식

 

 정적 할당 방식: 프로세스의 실행 과정을 고려 않고 프로세스의 크기, 물리 메모리. 크기가 고정되어 있는 것만 고려함

균등 할당 eqal allocatoin

가장 단순한 방식, 모든 프로세스에게 균등한 프레임 할당.

프로세스들의 크기는 다 다른데 동일 프레임을 할당하는 것은 비합리적이다

 

프레임 수가 증가함에 따라 페이지 폴트 수는 최소 수준으로 떨어진다. 물리적으로 프레임을 늘리면 페이지 폴트는 자연히 떨어진다.

 

비례 할당 porportional allocation

프로세스의 크기를 고려해 프레임 할당. 

하지만 프로세스가 필요로 하는 프레임 수는 실행해봐야 안다.

 

 

동적할당모델: 프로세스가 실행하는 과정을 통해 할당

 

작업 집합 모델기반의 프레임 할당 방식

작업 집합: 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합

이것을 구현하려면, 1) 프로ꂌ스가 참조한 페이지 2) 어떤 시간 간격 동안 참조한 페이지를 구할 것인지에 대한 시간 간격

 

워킹셋 모델 : 프로세스가 실행하는 과정서 배분할 프레임 결정.

일정 시간 동안 참조했던 페이지의 집합, 이미 참조한 구역을 집중적으로 참조 <- 이것을 참조 지역성의 원리라고

cpu가 특정 시간 동안 주로 참조한 페이지 개수만큼 프레임 할당

 

페이지 폴트 빈도 기반의 프레임 할당 방식

프로세스가 실행하는 과정에서 배분할 프레임 결정 (동적 할당)

페이지 폴트율이 너무 높다? 그 프로세스는 너무 적은 프레임을 가지고 있다. 더 많은 프레임을 할당한다.

페이지 폴트율이 너무 낮다? 그 프로세스는 너무 많은 프레임을 가지고 있다. 프레임 회수

 

페이지 폴트 빈도 기반의 프레임 할당 방식은 페이지 폴트율의 상한선과 하한선을 정해 그 안에서 프레임을 할당한다.

 

 

---------리뷰-----------

메인 메모리가 하는 일 : cpu에 직접 접근, 프로그램 적재 시켜줌

 

메모리 할당 방식 : 다중 파티션 방식, 가변 분할

 

단변화 : 내부(할당받은 프로세스보다 더 큰 메모리, 남은 공간 문제)

외부 : 사용할 수 있는 공간이 연속적이지 않아 (10메가, 20메가,,) 메모리 사용 불가 -> 압축과 페이징으로 해결

 

페이징: 프로세스 물리 주소 공간이 연속적이지 않도록 하는 메모리 관리 체계

TLB: 히트시 물리 주소로 매핑, 미스시 페이지 테이블 가서 찾기

 

가상 메모리: 모든 프로그램을 메모리에 올려두지 않고 쪼개서, 물리 메모리에 제약 받지 않을 수 있다. 더 많은 프로그램 동시 수행 가능

메모리 적재, 스왑,IO가 감소헤 속도 측면에서도 좋음

 

가상 메모리 이점: 페이지 공유 가능, 둘 이상의 프로세스서 파일, 메모리 공유 가능.

 

요구 페이징: 필요 때만 페이지 적재, 적은 메모리 사용

쓰기 시 복사 : 부모 자식은 페이지 공유, 쓰기 시 복사본 생성 별도 참조

페이지 교체: 유효, 무효 비트 참조. 알고리즘 LPU, fifo, 

 

스레싱: 

할 일보다 스레싱을 더 많이할 때. 비효율

제안 : 지역교체 알고리즘, 우선 순위 교체

방지: 작업집합, 페이지 폴트