ultra_dev
가상메모리 본문
가상메모리
결론 : 연속 메모리 할당 방식은 좋지 않고 페이징 방식을 쓴다.
연속 메모리 할당
- 연속 메모리 할당 : 프로세스에 연속적인 메모리 공간을 할당
프로세스들이 메모리 내에서 연속적으로 할당되는..
스와핑
: 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고(스왑 아웃) 그렇게 생긴 빈 공간에 새 프로세스를 적재하는 것(스왑 인)
즉, 지금 당장 사용하는 프로세스만 메모리에 적재하는 것!
장점
: 프로세스들이 요구하는 메모리 공간 크기 > 실제 메모리 크기 인 경우에도 프로세스들 동시에 사용 가능해짐
가령 프로세스 a,b,c,d가 동시에 실행되고 싶은데 이 4개 프로세스의 크기를 합치면 실제 물리 크기보다 커지는 경우
프로세스 a→b→c 적재 후
프로세스 b를 지금 당장 실행할 필요가 없다면 b 스왑 아웃 후 d 스왑인 해버린다
이런식으로 실제 물리 메모리보다 큰 프로세스들을 동시에 사용 가능해짐
메모리 할당
: 프로세스는 메모리의 빈 공간에 할당되어야 한다.. 만약 빈 공간이 여러 개 있다면?
- 최초 적합, 최적 적합, 최악 적합 방식으로 할당한다.
1.최초 적합(first-fit)
- 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
- 검색 최소화, 빠른 할당
- 빈 공간 보이면 바로 적재하면 되니까
2. 최적 적합(best-fit)
- 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 작은 공간에 할당
3. 최악 적합(worst-fit)
- 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 할당
이 세가지가 연속 메모리 할당 방식임
이렇게 프로세스를 연속적으로 메모리에 할당하는 방식은 비효율 적임
why? 외부 단편화 문제가 생기기 때문이다.
외부 단편화
만약 사용자 영역이 200MB일 때
크기가 50MB인 프로세스 A
30MB인 프로세스 B
100MB인 프로세스 C
20MB인 프로세스 D를 차례대로 적재하고
프로세스 B,D 실행이 끝났다면?
빈 공간의 총합은 50MB(20+30)
이때 50MB 크기의 프로세스 적재가 가능한가?
: NO
이렇게 프로세스들이 실행되고 종료되길 반복하며 메모리 사이 사이에 빈 공간이 발생하고
이러한 공간들로 인해 메모리가 낭비 되는 것이 외부 단편화임!!
즉, 외부 단편화는
프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해서 메모리가 낭비되는 현상이다!!
외부 단편화 해결 방법
1. 메모리 압축(compaction)
여기 저기 흩어져 있는 빈 공간들을 하나로 모으는 방식
프로세스를 적당히 재배치 시켜서 흩어져 있는 작은 빈공간들을 하나의 큰 빈 공간으로 만드는 방법
빈 공간을 합치고, 실행 중인 프로세스들을 재배치하면서 당연히 오버헤드 발생..!!
2. 가상 메모리 기법, 페이징 (외부 단편화 해결 위해 현대 운영체제가 선택한 가장 대중적인 메모리 관리 방식)
연속 메모리 할당의 두 가지 문제점
- 외부 단편화
- 물리메모리 보다 큰 프로세스 실행 불가
가상 메모리
- 실행하고자 하는 프로그램을 일부만 메모리에 적재하여
실제 물리 메모리 크기보다 더 큰 프로세스를 실행 할 수 있게 하는 기술 - 예를 들어 4기가 프로세스를 2기가 물리 메모리에 적재할 때 일부만 적재!
- 대표적으로 페이징(이게 대중적), 세그멘테이션 기법이 있다.
페이징
먼저, 외부 단편화가 발생했던 근본적인 문제는
각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문이다.
만약 모든 프로세스 크기가 똑같았다면 하나가 스왑아웃돼도 이후 적재 되는 애들도 똑같은 크기니까 외부 단편화는 생기지 않았을 것!!
페이징은 이렇게 모든 프로세스를 일정 크기로 자르고, 이를 메모리에 불연속적으로 할당하면서 외부 단편화 해결!!
페이징(paging)
- 프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자르고,
- 메모리의 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 일정한 단위로 자른 뒤
- 페이지를 프레임에 할당하는 가상 메모리 관리 기법
- 페이징에서의 스와핑
- 프로세스 단위의 스왑인, 스왑 아웃이 아닌 페이지 단위의 스왑 인(페이지 인), 스왑 아웃(페이지 아웃)
- 어떤 프로세스를 실행하기 위해 모든 페이지가 전부 다 메모리에 저장될 필요는 없다는 걸 의미
- 즉, 현재 실행 중인 프로세스를 이루고 있는 일부 페이지는 보조 기억 장치의 스왑 영역에 있어도 실행이 가능하다!!
→ 물리 메모리보다 큰 프로세스도 실행이 가능하다!!
- 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃
- 실행에 필요한 페이지들은 메모리로 스왑 인
문제점 :
- 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 cpu가 일일이 알기란 어렵다.
- 프로세스가 메모리에 불연속적으로 배치되어 있다면 cpu 입장에서 이를 순차적으로 실행할 수가 없다.
- cpu 입장에서 ‘다음에 실행할 명령어 위치’를 찾기가 어려워짐
해결책
: 페이지 테이블
페이지 테이블
- 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표
- (실제 메모리 내의 주소인) 물리 주소에 불연속적으로 배치 되더라도
- (cpu가 바라보는 주소인) 논리 주소에는 연속적으로 배치되도록 하는 방법
- 프로세스마다 페이지 테이블이 존재
- 물리적으로는 분산되어 저장되어 있더라도 CPU 입장에서 바라보는 논리 주소는 연속적으로 보임
- cpu는 그저 논리 주소를 순차적으로 실행하면 될 뿐.. 페이지 테이블에 다 짝지어져 있으니까
페이지 테이블의 문제점 : 내부 단편화
내부 단편화
- 만약 페이지 크기가 10kb, 프로세스 크기가 108kb라면 마지막 페이지에서는
- 2kb의 내부 단편화가 생김!
- 하나의 페이지 크기보다 작은 크기로 발생한다.
PTBR
- 프로세스마다 페이지 테이블이 있고,
- 각 페이지 테이블은 CPU 내의 프로세스 테이블 베이스 레지스터(PTBR)가 가리킨다.
- == 페이지 테이블 베이스 레지스터는 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.
But 페이지 테이블이 메모리에 있다면 메모리 접근 시간이 2배로 걸림
- 페이지 테이블 참조하기 위해 1번
- 페이지 참조하기 위해 1번
해결책 : TLB
- TLB : CPU 곁에 페이지 테이블의 캐시 메모리
- 페이지 테이블의 일부를 가져와서 저장하는 특별한 캐시 메모리!
- 현재 자주 참조하는 페이지 테이블의 일부 저장
- 이를 통해, cpu는 굳이 메모리의 페이지 테이블 참조하기 위해서 2번 접근 하는게 아니라
- 자주 참조하는 애들은 TLB 통해서 곧바로 페이지와 프레임을 확인하고 메모리에 접근 가능
- CPU가 접근하려는 논리 주소가 TLB에 있다면 ? TLB 히트
- 메모리 접근 1번
- CPU가 접근하려는 논리 주소가 TLB에 없다면 ? TLB 미스
- 메모리 접근 2번
페이징에서의 주소 변환
- 특정 주소에 접근하고자 한다면 어떤 정보가 필요할까?
- 어떤 페이지 / 프레임에 접근하고 싶은지에 대한 정보
- 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지에 대한 정보
- 페이지 시스템에서의 논리 주소
- 페이지 번호(page number)와 변위(offset)로 이루어짐
- 변위 : 내가 접근하고자 하는 주소는 그 페이지로부터 얼만큼 떨어져 있는지
- <페이지 번호, 변위>로 이루어진 논리 주소는 페이지 테이블을 통해서 물리 주소 상의 <프레임 번호, 변위>로 변환된다.
- 여기서 변위는 서로 같을 것임. 왜냐면 페이지의 크기와 프레임의 크기는 같으니까!
페이지 테이블 엔트리
- 페이지 테이블의 각각의 행 : 페이지 테이블 엔트리(PTE)
- 현재까지 설명한 PTE : 페이지 번호, 프레임 번호
- 이외에 담기는 정보? 운영체제마다 다름
- 유효 비트 : 현재 해당 페이지에 접근 가능한지 여부
- 즉, 현재 페이지가 스왑 영역으로 쫓겨나 있는지 아닌지
현재 페이지가 메모리에 적재되어있는지 아닌지를 나타냄 - 유효 비트가 1이면 현재 메모리에 적재돼있고 0이면 스왑영역에 있다는 걸 의미
- 만약 유효 비트가 0인 페이지에 접근하려고 하면?
- 페이지 폴트(page fault)라는 인터럽트 발생
- 현재 접근하려고 하는 페이지가 메모리에 적재되어 있지 않은 경우 발생!
- cpu는 기존의 작업 내역을 백업
- 페이지 폴트 처리 루틴 실행(인터럽트 서비스 루틴)
- 페이지 처리 루틴은 원하는 페이지를 (보조 기억 장치로부터) 메모리로 가져온 뒤 유효 비트를 1로 변경
- 페이지 폴트를 처리했다면(cpu가 접근하고자 하는 페이지를 메모리에 적재) 이제 cpu는 해당 페이지에 접근 가능
- 페이지 폴트(page fault)라는 인터럽트 발생
- 즉, 현재 페이지가 스왑 영역으로 쫓겨나 있는지 아닌지
- 보호 비트 (페이지에 접근할 권한을 제한하여 페이지를 보호하는 비트)
* 페이지 보호 기능을 위해 존재하는 비트
* 예를 들어서 어떤 페이지는 읽기 전용 페이지, 어떤 페이지는 읽기/쓰기 페이지인 경우, 어떤 페이지는 읽기, 쓰기, 실행이 가능한 페이지가 있을테니 그걸 설정하는 것
r/w/x에 1/0/0/, 1/1/0, 1/1/1 이런식으로 보호비트에서 권한 설정하는 것 - 참조 비트
- cpu가 이 페이지에 접근한 적이 있는지 여부
- 이 페이지가 메모리에 적재된 이후 cpu가 한번이라도 읽거나 쓴 페이지는 참조 비트가 1로 세팅
- 만약 적재된 이후 한번도 cpu가 참조한 적이 없다면 참조 비트는 0이겠지
- 수정 비트 (= dirty bit)
- cpu가 이 페이지에 데이터를 쓴 적이 있는지 여부
- 이 페이지가 수정이 됐는지 아닌지 여부를 알려준다.
- 예를 들어 이 비트가 1이라면 한번이라도 변경된 페이지인 것!
- 왜 존재하는가?
- 스와핑 시, 이 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야하는지 할 필요가 없는지 판단하기 위해서 필요하다.
- 수정된 페이지는 스왑 아웃 될 때 보조기억장치에도 쓰기 작업을 거쳐야 한다!!
- 수정 안됐으면 메모리랑 보조기억장치랑 똑같을테니 굳이 덮어쓰기작업을 할 필요가 없다.
- 유효 비트 : 현재 해당 페이지에 접근 가능한지 여부
페이징 이점
쓰기 시 복사
- 이론적인 fork()
- 프로세스는 기본적으로 자원을 공유하지 않는다.
- → 부모 프로세스가 적재된 별도의 공간에 자식 프로세스가 통째로 복제되어 적재
- (프로세스 생성 시간 지연, 메모리 낭비)
- 이러한 문제를 해결하는 것이 바로 쓰기 시 복사!
쓰기 시 복사
- 부모 프로세스와 동일한 자식 프로세스가 복제되어 생성되면 자식 프로세스는
부모 프로세스와 동일한 프레임을 가리킨다(쓰기 작업이 없다면 이 상태 유지) - 즉, 자식 프로세스도 부모 프로세스의 페이지 테이블과 동일하니까 같은 자원을 공유!
- 만약 부모 프로세스/ 자식 프로세스 둘 중 하나가 페이지에 쓰기 작업 수행 시
쓰기 작업을 한 그 해당 페이지는 별도의 공간으로 복제
(프로세스 생성 시간 절약, 메모리 절약)
계층적 페이징
- 프로세스 테이블의 크기는 생각보다 작지 않다.
- 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 낭비
- 프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않을 방법
- 페이지 테이블 자체를 페이징하여 어러 단계의 페이지 페이지를 두는 방식
- 페이지 테이블을 여러 페이지로 쪼개고 이 페이지를 가리키는 페이지 테이블(Outer 페이지 테이블)을 두는 방식
- 이를 통해 모든 페이지 테이블을 항상 메모리에 둘 필요가 없어짐
- cpu에 가장 가까이 위치한 페이지 테이블(Outer 페이지 테이블)은 항상 메모리에 유지
- 계층적 페이징을 이용하는 환경에서의 논리 주소
- 바깥 페이지 번호 / 안쪽 페이지 번호 / 변위
- 바깥 페이지 번호를 통해 페이지 테이블의 페이지를 찾는다.
- 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더함으로서 물리 주소를 얻는다.
참고 : 계층이 너무 많아지게 되면 페이지폴트(내가 참조하고자 하는 그 페이지가 메모리에 없는 상태) 발생 시 , 메모리 참조해야하는 횟수가 그만큼 많아지기 때문에 계층이 많다고 해서 반드시 좋다고는 할 수 없다!!!!
페이지 교체 알고리즘과 프레임 할당
- 페이징을 통해서 물리 메모리보다 큰 프로세스를 실행할 수 있지만, 그럼에도 불구하고 물리 메모리의 크기는 한정되어 있다.
- 따라서 운영체제 입장에서는 기존에 적재된 불필요한 페이지를 선별해서 보조기억장치로 내보내고, 프로세스들에게 적절한 수의 프레임을 할당해야 한다.
요구 페이징
- 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
- 요구되는 페이지만 적재하는 기법
- cpu가 특정 페이지에 접근하는 명령어를 실행한다.
- 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) cpu는 페이지가 적재된 프레임에 접근한다.
- 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생한다.
- 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
- 다시 1번을 수행한다.
이러한 요구 페이징 시스템이 안정적으로 작동 하려면 해결해야 할 문제?
- 페이지 교체
- 프레임 할당
페이지 교체 알고리즘
- 요구 페이징 기법으로 페이지들을 적재하다보면 언젠가 메모리가 가득 차게 된다
- 당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야 한다
- 이때 어떤 페이지를 내보내야할지를 결정하는 방법이 바로 페이지 교체 알고리즘!!
그렇다면 무엇이 좋은 페이지 교체 알고리즘일까?
- 페이지 폴트가 적은 알고리즘!
- 페이지 폴트가 발생하면 보조기억장치에 접근해야 해서 성능 저하!!!!
- 참고) 페이지 참조열(page reference string)
- cpu가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
- 어떤 cpu가 이 [222355337] 페이지들을 참조했다면
- [23537]로 페이지열을 만드는 것
- why? 어차피 연속된 것에 페이지 폴트가 발생하지 않을테니…
대표적인 페이지 교체 알고리즘
1. FIFO 페이지 교체 알고리즘
- 가장 단순한 방식
- 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
- “오래 머물렀다면 나가라”
페이지 참조열이 [2313523423] 이라면
프레임에는 먼저 2,3,1이 담기고
5번 참조 시, 가장 오래된 페이지가 2니까 5,3,1 (페이지 폴트)
2번 참조 시, 그 다음 오래된 페이지가 3이니까 5,2,1 (페이지 폴트)
3번 참조 시, 그 다음 오래된 페이지가 1이니까 5,2,3 (페이지 폴트)
4번 참조 시, 그 다음 오래된 페이지가 5이니까 4,2,3, (페이지 폴트)
이런식으로 바뀌는 것
단점
: 물론 프로그램 실행 초기에 잠깐 실행될 페이지도 있겠지만
프로그램 실행 내내 사용될 페이지도 먼저 적재되었다고 내쫓아버림!!
FIFO 페이지 교체 알고리즘의 보완책
- 2차 기회(second-chance) 페이지 교체 알고리즘
- 참조 비트 1 : cpu가 한번 참조한 적이 있는 페이지
- 한번 더 기회를 준다. ( 참조 비트를 0으로 초기화 후 적재 시간을 현재 시간으로 설정)
- 참조 비트 0 : cpu가 참조한 적이 없는 페이지
- 내쫓는다.
- 즉, 만약 페이지 참조 비트가 1이라면 바로 내쫓지 않고, 적재된 시간을 현재 시간으로 설정하고
다시 맨 끝으로 보낸다(즉, 가장 최근에 적재된 페이지로 간주) - 그리고 가장 오래된 페이지인데 참조 비트도 0이라면 내쫓아버림!!
2. 최적 페이지 교체 알고리즘
- 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
- cpu에 의해 참조되는 횟수를 고려
- 메모리에 오래 남아야 할 페이지는 자주 사용될 페이지
- 메로리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지
- 가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘
페이지 참조열이 [2313523423] 이라면
프레임에는 먼저 2,3,1이 담기고
5번 참조 시, 가장 오랫동안 사용하지 않을 페이지가 1니까 2,3,5 (페이지 폴트)
4번 참조 시, 가장 오랫동안 사용하지 않을 페이지가 5이니까 2,3,4 (페이지 폴트)
이런식으로 바뀌는 것
단점
: 실제 구현이 어렵다!!!
앞으로 오랫동안 사용되지 않을 페이지를 어떻게 예측할 것인가
다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 간주
3. LRU(Least-Recently-Used) 페이지 교체 알고리즘
- 2번이 구현 어려우니까 한번 틀어봄
- 최근에 사용되지 않은 페이지는 앞으로도 사용 안되지 않을까!?
- LRU 페이지 교체 알고리즘 : 가장 오래 사용되지 않은 페이지 교체
페이지 참조열이 [2313523423] 이라면
프레임에는 먼저 2,3,1이 담기고
5번 참조 시, 가장 오랫동안 사용하지 않은 페이지가 2니까 5,3,1 (페이지 폴트)
2번 참조 시, 가장 오랫동안 사용하지 않은 페이지가 1니까 5,3,2 (페이지 폴트)
4번 참조 시, 가장 오랫동안 사용하지 않은 페이지가 5이니까 4,3,2 (페이지 폴트)
이런식으로 바뀌는 것
+
기타 페이지 교체 알고리즘도 많음
스래싱과 프레임 할당
- 페이지 폴트가 자주 발생하는 이유
- 나쁜 페이지 교체 알고리즘을 사용해서
- 프로세스가 사용할 수 있는 프레임 자체가 작아서
스래싱
- 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저해되는 문제
- 동시 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 높아지는 것이 아니다.
- 멀티프로그래밍의 정도 : 메모리에 동시에 실행되는 프로세스의 수
- 멀티프로그래밍의 정도가 높아지면 어느 정도까지는 cpu가 쉴새없이 일하면서 이용률이 올가가겠지만 특정 시점 이후로는 cpu 이용률이 현저히 떨어지는데 이 지점이 바로 스래싱이 발생하는 시점이다.
즉, 동시에 실행되는 프로세스의 수를 높인다고해서 반드시 cpu의 이용률, 성능이 그에 비례해서 증가하는 것이 아니다. - → 페이지 폴트가 너무 빈번하게 발생해서 막상 실행해야할 프로세스를 실행하지 못하는 상태기 때문*
- 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문에 발생
→ 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 한다.
프레임 할당 방식
- 균등 할당(equal allocation)
- 가장 단순한 할당 방식
- 모든 프로세스들에게 균등하게 프레임을 할당하는 방식
- 문제점 : 실행되는 프로세스들의 크기가 다를텐데, 모두에게 동일한 프레임을 할당하는 것은 비합리적이다.
- 비례 할당(proportional allocation)
- 프로세스의 크기를 고려하자
- 프로세스 크기에 비례하여 프레임 할당
- 문제점 : 결국 프로세스가 필요로 하는 프레임 수는 실행해봐야 안다.
균등 할당, 비례할당 : 정적 할당 방식
→ 프로세스의 실행 과정을 고려하지 않고, 단순히 프로세스의 크기나 물리 메모리의 크기만 고려한 방식
3. 작업 집합 모델 기반 프레임 할당
- 프로세스가 실행하는 과정에서 배분할 프레임 결정
- 스레싱이 발생하는 이유는 빈번한 페이지 교체 때문
- 그렇다면 CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 된다.
- 프로세스가 일정 기간동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지
- 작업 집합 : 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
작업 집합을 구하려면
- 프로세스가 참조한 페이지
- 시간 간격이 필요
만약 프로세스가 참조한 페이지가 아래와 같고, 시간 간격이 7이라면
2112345555667781124
색깔 부분이 t1이라고 한다면 작업 집합은 {5,6,7}
2112345555667781124
색깔 부분이 t2일 때 작업 집합은 {1,2,4,7,8}
4. 페이지 폴트 빈도 기반 프레임 할당
- 프로세스가 실행하는 과정에서 배분할 프레임 결정
- ex) x축에 할당된 프레임 수, y축에 페이지 폴트율
- 두 개의 가정에서 생겨난 아이디어
- 페이지 폴트율이 너무 높으면(상한선 이상) 그 프로세스는 너무 적은 프레임을 갖고 있다.
- 페이지 폴트율이 너무 낮으면(하한선 이하) 그 프로세스는 너무 많은 프레임을 갖고 있다.
- 즉, 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식
작업 집합 모델, 페이지 폴트 빈도 : 동적 할당 방식
→ 프로세스가 실행하는 과정을 관찰하면서 프레임을 할당 하는 방식..!