혼공단 6주차 (1) Ch14.가상메모리 (유투브 37강~40강)

 

 

목차

Chapter 14.  가상 메모리

14-1. 연속 메모리 할당

14-2. 페이징을 통한 가상 메모리 관리

 

14-3. 페이지 교체와 프레임 할당

 

[ 기본미션 ] p.400, 확인 문제 1번.

메모리 할당 방식에 대한 설명으로 올바른 것을 다음 보기에서 찾아 써 보세요.

보기) 최초 적합, 최적 적합, 최악 적합

(① 최초 적합) 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
(② 최악 적합) 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
(③ 최적 적합) 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식

 

 

[ 선택 미션 ]

Ch.14 (14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2414523423'일 때 FIFO, 최적 페이지, LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기

 

FIFO : 4번

2, 4, 1, 4, 5 (←2), 2 (←4), 3 (←1), 4 (←5), 2, 3 

 

최적 : 2번

2, 4, 1, 4, 5 (←1), 2, 3, 4, 2 (←5), 3

 

LRU : 4번

2, 4, 1, 4, 5 (←2), 2 (←4), 3 (←1), 4(←5), 2, 3

 

 

 

연속 메모리 할당 방식

프로세스에 연속적인 (사용자) 메모리 공간을 할당

 

스와핑

• 운영체제가 메모리를 관리하는 기본적인 기능 중 하나
• 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고 생긴 빈 공간에 새 프로세스 적재
• swap in / swap out
• 프로세스들이 요구하는 메모리 공간의 크기가 실제 메모리 크기 보다 크더라도 실행 가능
• 리눅스에서 free, top 을 이용하면 Swap 메영역의 크기를 확인할 수 있음

 

 

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

 

1. 최초 적합, First-Fit

운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 바로 배치

검색을 최소화하고 빠름

 

2. 최적 적합, Best-Fit

운영체제가 빈 공간을 모두 검색하고 적재 가능한 최적의 공간에 배치

 

3. 최악 적합, Worst-Fit

빈 공간을 모두 검색해보고 적재 가능한 가장 큰 공간에 할당

 

1, 2, 3 모두 연속 메모리 할당 방식

메모리를 효율적으로 할당하는 방식이 아님

=> 외부 단편화 external fragmentation 발생!

 

외부 단편화 External Fragmentation

사용자 영역이 200MB 일 때, A (50), B(30), C(100), D(20) 을 할당한다면?

처음에는 A + B + C + D 를 순서대로 할당해서 200MB 를 꽉 채워 사용 가능.

이때, B, D 가 끝나면, 남은 공간은 50MB (= 30 + 20)

50MB 짜리 프로세스를 할당해야되는 상황이 온다면?

공간이 나눠져 있어서 할당할 수 없음...

 

외부 단편화는 프로세스들이 실행되고 종료되길 반복하면서 메모리 사이사이에 빈 공간이 발생하게 되어 새로운 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들이 생겨 사용하지 못하게 되는 현상을 말함

 

해결 방법 1 : 메모리 압축 Memory Compection

흩어진 빈 공간들을 하나로 모으는 방식

적당히 재배치시켜 흩어진 빈 공간들을 하나의 큰 빈공간으로 만드는 방법

그러나 어떤 식으로 압축할 것인가... 가 문제

 

 

 

해결 방법 2 : 페이징 Paging

가상 메모리 관리 기법 중 하나로 실행하고자 하는 프로그램의 일부만 메모리에 적재하고 나머지는 가상 메모리에 적재

물리 메모리보다 큰 프로세스를 실행할 수 있음

 

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

그럼 모든 프로세스를 일정한 크기로 자르고 불연속적으로 할당하면 되지 않을까?

 

페이징은

1. 프로세스의 논리 주소 공간을 페이지 Page 라는 일정한 단위로 자름

2. 메모리의 물리 주소 공간을 프레임 Frame 이라는 페이지와 동일한 일정 단위로 자름

3. 페이지를 프레임에 할당

 

 

페이징에서의 스와핑 : Page In, Page Out

프로세스 단위의 스와핑을 메모리 단위로 바꾼 스와핑 형태

메모리에 적재될 필요가 없는 페이지들을 보조 기억 장치로 Swap Out ( = Page Out )

실행에 필요한 페이지는 Swap In ( = Page In )

 

CPU 는 불연속적인 페이지들이 어디에 어떻게 있는지 어떻게 알 수 있을까?

 

페이지 테이블 Page Table

페이지 번호와 프레임 번호를 짝지어 주는 일종의 테이블

프로세스마다 각각의 페이지 테이블을 가짐

CPU 가 어떤 페이지가 어떤 프레임에 들어있는지 알게 됨!!

CPU 는 논리 주소인 페이지만 순서대로 실행하면 물리 주소의 프레임을 순서대로 실행하는 것 같이 됨

 

또 다른 문제.. 내부 단편화 

하나의 페이지 크기보다 작은 크기로 발생한 단편화

예를 들어, 페이지 크기가 10, 프로세스 크기가 108 인 경우 11개의 페이지가 사용되어야 하는데 그 중 1개의 페이지는 2 만큼 단편화 발생

리눅스에서 getconf PAGESIZE 명령어를 이용하면 페이지 크기를 확인해볼 수 있음

 

프로세스 테이블 베이스 레지스터, PTBR

프로세스마다 각각 페이지 테이블을 가지고 있는데 이는 CPU 내의 PTBR 가 가리킴

그런데 페이지 테이블이 메모리에 있으면 메모리 접근 시간이 2배가 됨 (페이지 테이블 접근 + 페이지 참조)

그래서 TLB 라는 캐시 메모리를 사용

 

CPU 가 접근하려는 논리 주소가 TLB에

있으면? TLB Hit

없으면? TLB Miss → 메모리에서 다시 찾아봐야 함

 

페이징에서의 주소 변환: 특정 주소에 접근하고자 한다면 어떤 정보가 필요할까?

어떤 페이지/프레임에 접근하고 싶은지, 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는가

→ 페이지 번호 (Page Number) + 변위 (Offset)

 

 

페이지 테이블 엔트리 PTE

페이지 테이블의 행

페이지 번호, 프레임 번호 외 여러 정보들이 포함되어 있음

 

유효 비트 Valid Bit

현재 해당 페이지에 접근 가능한지 여부

유효함 (1) : 메모리에 적재된 페이지

유효하지 않음 (0) : 메모리에 적재되지 않은 페이지, 보조기억장치 스왑 영역에 있음

→ 이 경우 페이지 폴트 인터럽트 발생

(1) CPU 는 기존 작업 내역을 백업

(2) 페이지 폴트 처리 루틴 실행

(3) 페이티 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트는 1로 변경

(4) 페이지 폴트 처리 후 CPU 가 접근 가능해짐

 

보호 비트

R, W, X bit 이용해 페이지에 접근할 권한을 제한하여 페이지를 보호

 

참조 비트 Reference Bit

CPU 가 이 페이지에 접근한 적 있는지 여부

 

수정 비트 Dirty Bit

CPU 가 이 페이지에 데이터를 쓴 적이 있는지 여부

Swaping 이 발생할 때 메모리에 변경 사항이 있다면 (수정 비트가 있다면) 보조 기억장치에도 반영해야 함

 

 

 

물리 메모리보다 큰 프로세스를 실행할 수 있지만 어쨌든 한정되어 있음

그래서 기존의 적재된 불필요한 페이지를 선별해 보조 기억 장치로 보내고 적절한 수의 프레임을 할당해야 함

 

요구 페이징 Demand Paging

처음부터 모두 적재하지 않고 요구되는 (필요한) 페이지만 적재하는 기법

* 순수 요구 페이징 : 아무것도 적재하지 않고 일단 실행. 페이지 폴트가 발생하면서 채워나감

페이지 교체와 프레임 할당이 잘 이루어져야 함

 

 

페이지 교체 알고리즘

가득 차 있는 메모리에서 어떤 페이지를 보조 기억 장치로 돌려보낼 것인가?

무엇이 좋은 페이지 교체 알고리즘인가?

일반적으로 성능 저하를 일으키는 페이지 폴트가 적은 알고리즘이 좋다!! 

 

페이지 참조열 Page Reference String

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

e.g. 2 2 2 3 5 5 5 3 3 7 는 2 3 5 3 7 로 표현

 

FIFO 페이지 교체 알고리즘

가장 먼저 올라온 페이지부터 내쫓기

프로그램 실행 내내 사용될 페이지는 내쫓아서는 안되는데 FIFO 는 쫓아낼 수도 있음

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

기회를 1번 더 줌. 참조 비트가 1이면 한번 더 줌

 

최적 페이지 교체 알고리즘

CPU 가 참조하는 횟수를 고려

자주 사용될 페이지는 남기고 아닌 건 날리기

실제 구현이 어려움... 앞으로 어떻게 사용될지 말지 알지?

성능 평가를 위한 하한선으로 간주

 

LRU Least-Recenty Used 페이지 교체 알고리즘

최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것 같은데?

 

 

프레임 할당

페이지 폴트가 자주 발생하는 이유는 근본적으로 프레임이 넉넉하지 않기 때문임

나쁜 페이지 교체 알고리즘 때문이기도 함

 

스래싱

프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요

즉, 동시에 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 올라가는 것은 아님

각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 적절한 양을 할당해주어야 함

 

균등 할당 Equal Allocation

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

 

비례 할당 Proportional Allocation

프로세스의 크기에 비례하여 프레임 할당

실행해봐야 결국 알게 되는 경우가 많음

 

작업 집합 모델

실행하는 과정에서 배분할 프레임 결정

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

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

작업 집합은 프로세스가 참조한 페이지와 시간 간격으로 구할 수 있음

 

 

페이지 폴트 빈도

페이지 폴트율이 너무 높으면 너무 적은 프레임

페이지 폴트율이 너무 낮으면 너무 많은 프레임

상한선 하한선을 구해 그 내부 범위 안에서만 프레임을 할당

 

 

끝.