[OS/공룡책] Part 4. Memory Management

keep many processes in memory simultaneously to allow multiprogramming

 

메인 메모리

메모리는 고유의 주소를 갖는 바이트의 배열이다. 각 코어에 들어있는 레지스터와 메인 메모리는 CPU가 직접 접근할 수 있는 유일한 스토리지다. CPU는 PC값에 해당하는 메모리 주소에서 명령어를 가져와 실행하는데, 만약 데이터가 메모리에 없다면 실행 전에 메모리에 적재해야 한다.
 

메모리 보호

we must protect the operating system from access by user processes.

우리는 사용자 프로세스로부터 운영체제를 보호해야 한다. 이는 base 레지스터와 limit 레지스터를 이용하여 구현할 수 있다.

1. base 레지스터 : 물리적 메모리의 가장 작은 주소
2. limit 레지스터 : 메모리 공간의 크기

프로세스가 `base`와 `base + limit` 범위를 벗어나는 주소를 참조하려고 하면 trap을 발생시켜 운영체제에게 악의적인 행위를 알린다.
 

주소 바인딩

프로그램은 디스크에서 바이너리 파일로 존재하다가 실행되기 위해 메모리로 로드된다. 프로세스가 실행되면 CPU는 메모리에 적재된 명령어와 데이터에 접근한다.
 
CPU에 의해 생성된 주소를 논리적 주소 (= 가상 주소), 하드웨어 상 주소를 물리적 주소라고 한다. 응용 프로그램은 물리적 주소에 접근할 수 없기 때문에 논리적 주소를 물리적 주소로 변환해주는 과정이 필요하다. MMU (= memory management unit)은 논리적 주소를 물리적 주소로 매핑해주는 하드웨어다.

---

메모리 할당

메인 메모리는 운영체제와 사용자 프로세스를 수용할 수 있어야 한다. 따라서 메모리 공간을 효율적으로 할당하는 것이 중요하다.
 

연속 메모리 할당

연속 메모리 할당은 연속된 메모리 공간에 프로세스를 할당한다. 메모리는 하나의 프로세스만 포함하는, 다양한 크기의 파티션으로 나뉘게 된다.

메모리가 할당되었다가 해제되면 hole이 생긴다. 운영체제는 프로세스의 크기를 고려하여 적절한 hole에 프로세스를 할당한다.

• first-fit : 가장 처음 발견한, 충분한 크기의 hole에 할당
• best-fit : 충분한 크기를 갖고 있으면서 가장 작은 hole에 할당 (= 가장 작은 leftover)
• worst-fit : 가장 큰 hole에 할당 (= 가장 큰 leftover)

 

단편화

연속 메모리 할당에서는 외부 단편화가 발생한다. 외부 단편화는 요청을 만족하는 충분한 메모리 공간이 있어도 메모리 공간이 연속하지 않아 할당할 수 없는 상태를 의미한다.
 
외부 단편화는 압축을 이용하여 해결할 수 있다. 압축은 해제된 메모리를 하나의 큰 공간으로 만들지만, 비용이 비싸 사용할 수 없다.

또 다른 해결책은 프로세스를 불연속적인 메모리에 할당하는 것이다. 이러한 전략을 페이징이라고 부르며, 현재 대부분의 컴퓨터 시스템이 페이징을 사용하고 있다.

외부 단편화	내부 단편화
프로세스가 사용할 수 없는 빈 공간	프로세스가 사용하고 남은 빈 공간
연속 메모리 할당	페이징 (= 불연속 메모리 할당)

 

페이징

페이징을 구현하기 위해서는 물리적 메모리를 고정된 크기로 나누고 (= 프레임), 논리적 메모리도 동일한 크기로 나누어야 한다. (= 페이지) 

CPU는 페이지 번호 `p` (= 페이지 테이블의 인덱스) 와 페이지 오프셋 `d`으로 구성된 논리적 주소 `(p, d)`를 생성한다. 페이지 테이블은 프레임의 base 주소를 가지고 있다. `page_table[0] = 4`는 0번째 페이지가 4번째 프레임을 사용한다는 것을 의미한다.

1. 페이지 테이블의 `p` 인덱스에 접근한다.
2. 프레임 번호 `f`를 얻는다.
3. `f`번째 프레임의 `d`번째 오프셋에 접근한다.

페이지 테이블은 프로세스마다 갖고 있는 데이터 구조이므로 문맥 교환이 발생하면 페이지 테이블도 교체되어야 한다. PTBR (= page table base register)은 페이지 테이블을 가리키는 포인터로, 페이지 테이블은 메인 메모리에 유지하고 PTBR만 PCB에 저장하여 문맥 교환 시간을 줄인다. 하지만 해당 방법은 메모리에 두 번 접근해야 한다는 단점이 있다. (= 페이지 테이블 접근 + 실제 데이터 접근)
 

해당 문제를 해결하기 위해 TLB (= translation look aside buffer)라는 캐시를 사용한다. TLB는 페이지 테이블의 엔트리 일부를 저장하고 있다.

MMU는 TLB에 페이지 번호가 있는지 확인하는데, 번호가 있으면 프레임 번호를 바탕으로 실제 메모리에 바로 접근한다. (= TLB hit) 페이지 번호가 없는 경우 (= TLB miss), 페이지 테이블에 접근하여 프레임 번호를 가져오고, TLB에 페이지 번호와 프레임 번호를 저장하여 다음 참조부터 빠르게 찾을 수 있도록 한다.

🚨 TLB가 가득 찬 경우, 존재하는 엔트리 중 하나를 선택하여 교체해야 한다.

⭐ 캐시 메모리
CPU와 메모리 사이의 속도 차이를 완화하는 메모리로, 앞으로 사용될 것으로 예상되는 데이터를 미리 저장해둔다.

 
연속 메모리 할당 방식은 base 레지스터와 limit 레지스터를 이용하여 메모리를 보호한다. 페이징의 경우, protection bit (= valid-invalid bit)를 사용하여 메모리를 보호할 수 있다.

• valid : 프로세스의 논리적 주소 공간에 포함되어 있다.
• invalid : 프로세스의 논리적 주소 공간에 포함되어 있지 않다.

---

스와핑

프로세스의 데이터는 프로세스가 실행되기 위해 메모리에 반드시 존재해야 한다. 프로세스는 일시적으로 메모리에서 backing store로 나갔다가 다시 메모리로 들어올 수 있다.

• standard swapping : 프로세스 전체를 swap in & out (현대 운영체제에서는 더 이상 사용하지 않음)
• swapping with paging : 페이지를 swap in & out (현대 운영체제에서 사용하는 방법)

---

가상 메모리

programs can be larger than physical memory

가상 메모리는 논리적 메모리와 물리적 메모리를 분리하여 메인 메모리를 아주 큰 스토리지로 추상화한다. 즉, 프로그램은 더 이상 물리적 메모리 크기에 제한받지 않는다. 또한, 두 개 이상의 프로세스가 페이지 공유를 통해 파일과 메모리를 공유할 수 있도록 한다.
 

Demand Paging

프로세스는 프로그램 전체를 한 번에 필요로 하진 않는다. demand paging은 실제로 필요할 때 페이지를 로드하는 전락으로, 각 프로그램이 메모리 공간을 적게 차지하도록 만든다. 이로 인해 시스템은 동시에 더 많은 프로그램을 실행할 수 있다.

프로세스의 페이지는 메모리에 있을 수도, 세컨더리 스토리지에 위치할 수도 있다. 적재 여부를 확인하기 위해 valid-invalid bit을 사용한다.

• valid : 페이지가 유효하고 메모리에 존재한다.
• invalid : ① 페이지가 유효하지 않거나 (= 프로세스에서 아예 접근할 수 없는 영역) ② 유효하지만 세컨더리 스토리지에 위치한다.

⭐ Demand Paging

• 현재 필요한 부분만 메모리에 적재하는 방식
• 프로세스의 페이지는 메모리에 있을 수도, 세컨더리 스토리지에 있을 수도 있다.
• 페이지가 메모리에 올라와 있는지 구별할 때, valid-invalid bit을 사용한다.

 

Page Fault

프로세스가 메모리에 없는 페이지에 접근하려고 하면 어떤 일이 벌어질까? (= page fault) 페이지가 유효하지 않은 경우는 곧바로 프로세스를 종료한다. 유효하지만 메모리에 적재되지 않은 경우에는 페이지를 메모리로 불러와야 한다.

1. free 프레임을 찾는다.
2. 세컨더리 스토리지 (= swap space) 에서 페이지를 불러와 free 프레임에 할당한다.
3. 읽기 작업이 완료되면, 페이지 테이블 값을 수정하여 해당 페이지가 메모리에 적재되었음을 표시한다. (= valid)
4. 인터럽트에 의해 중단된 명령을 재시작한다.

🚨 page fault 후에 명령을 다시 실행하는 이유는 일관성을 유지하기 위함이다. 페이지 폴트에 의해 이미 수행된 단계들에 대한 데이터도 영향을 받을 수 있기 때문이다.

 

페이지 교체

free 프레임이 없다면 현재 사용하지 않는 프레임을 찾아 해제해야 한다.

1. 페이지 교체 알고리즘을 이용하여 victim 프레임을 찾는다.
2. victim 프레임을 세컨더리 스토리지에 작성하고, 페이지 테이블을 invalid 값으로 변경한다.
3. 새로운 free 프레임에 페이지를 읽어오고, 페이지 테이블 값을 valid로 변경한다.

위 과정에서 알 수 있듯이 하나의 페이지가 나가고, 하나의 페이지가 들어온다.

modify bit (= dirty bit) 은 page fault 시간을 줄인다. 이는 하드웨어에 의해 설정되는 값으로, 페이지의 수정 여부를 나타낸다.

페이지가 victim으로 선정되면 해당 페이지의 modify bit을 확인한다. modify bit이 설정된 경우, 메모리에 적재된 이후로 페이지가 수정되었음을 의미한다. 따라서 스토리지에 페이지를 작성해야 한다.

반면, modify bit가 설정되지 않은 경우, 페이지가 변경되지 않았으므로 스토리지에 작성할 필요가 없다. (= 이미 스토리지에  같은 값이 존재한다!) 즉, modify bit은 페이지가 수정되지 않았을 때 I/O 시간을 반으로 줄여 결과적으로 page fault 시간을 줄인다.

💡 Belady's Anomaly
프레임의 수가 증가할 수록 page fault가 증가하는 현상

페이지 교체 알고리즘에는 세 종류가 있다.

1. FIFO : 가장 오래된 페이지를 교체한다.
2. OPT (= MIN) : 앞으로 가장 오랜 기간 사용하지 않을 페이지를 교체한다.
3. LRU (= Least Recently Used) : 가장 오랫동안 사용되지 않은 페이지를 교체한다.

FIFO는 가장 간단한 페이지 교체 알고리즘이지만, Belady's Anomaly가 발생한다. 일반적으로 프레임의 수가 많으면 더 많은 페이지를 보관할 수 있다. 하지만 FIFO는 페이지의 사용 빈도를 고려하지 않기 때문에 프레임 수의 증가가 오히려 더 많은 페이지 교체를 유발할 수 있다.
 
OPT는 가장 적은 page fault를 보장하지만 미래의 페이지 참조 내역을 알아야 하기 때문에 구현할 수 없는 알고리즘이다. 따라서 LRU가 좋은 페이지 교체 알고리즘으로 평가받고 있다. LRU를 구현하기 위해서는 하드웨어가 필요하다.

1. clock : 페이지 참조가 발생할 때마다 카운터를 증가시키고, 페이지 테이블에 그 값을 옮겨 적는다. 페이지의 마지막 참조 시간을 파악할 수 있지만 페이지 테이블 조회/검색 작업이 필요하고, 오버플로우가 발생할 수 있다.
2. stack : top은 가장 최근에 사용된 페이지, bottom은 가장 오래 전에 사용된 페이지를 가리킨다. 스택에 들어있는 페이지가 참조되면 해당 페이지를 스택의 top으로 옮겨야 한다.
3. reference bit : 페이지가 참조될 때마다 하드웨어에 의해 조작된다.

🚨 참조 값을 소프트웨어가 처리하면 매 참조마다 인터럽트가 발생하게 되어 성능 저하로 이어진다.

reference bit 방법에 대해 좀 더 자세히 살펴보자. 각 페이지에는 reference bit이 존재한다. 페이지가 참조되면 해당 값은 `1`로 설정된다. clock 알고리즘 (= second chance algorithm) 은 순환 큐를 따라 reference bit을 확인하는데, 값이 `0`이면 교체 대상이 된다.

 

프레임 할당

각 프로세스에 할당된 프레임 수가 줄어들면 page fault가 빈번하게 발생하고 결과적으로 실행속도가 느려진다. 따라서 프로세스는 충분한 프레임을 가져야 한다.

• equal allocation : 모든 프로세스에게 동일한 개수의 프레임 부여
• proportional allocation : 프로세스의 크기에 따라 부여

 

Thrashing 

Thrashing occurs when a system spends more time paging than executing.

프로세스가 적절한 개수의 프레임을 가지지 못하면 page fault의 비율이 높아진다. 즉, 프로세스의 실행보다 페이지 교체에 더 많은 시간을 할애하게 된다. CPU 스케줄러는 CPU utilization을 높이고자 더 많은 프로세스를 실행하는데 이로 인해 page fault 비율이 더욱 높아진다.

thrashing을 방지하기 위해서는 프로세스에게 충분한 프레임을 할당해야 한다. 하지만 프로세스에게 필요한 프레임의 수를 어떻게 알 수 있을까?

프로세스는 일정 시간동안 동일한 메모리 영역을 반복적으로 접근하는 경향이 있다. 따라서 프로세스에게 locality를 수용할 수 있는 프레임을 할당한다면, locality가 바뀌기 전까지 페이지 폴트가 발생하지 않을 것이다.
 
working-set은 locality에 기반한 모델로, 가장 최근에 참조된 페이지의 집합을 의미한다. 운영체제는 프로세스별 working-set을 모니터링하여 충분한 개수의 프레임을 할당한다. 만약 working-set 크기의 합이 증가한다면 일부 프로세스를 중단하여 CPU utilization을 높인다.