[혼공단 10기] 혼공컴운 - 6주차 미션

[스터디 그룹] 혼자 공부하는 프로그래밍 | Facebook

 
 

---

 
혼공단 마지막 주 주제는 가상메모리와 파일시스템
 
 

스와핑(swapping)

메모리에 적재된 프로세스들 중에는 현재 실행되지 않는 프로세스가 있을 수 있다. 예를 들면 입출력 작업의 요구로 대기상태가 된 프로세스 라던지, 오랫동안 실행되지 않은 프로세스가 존재할 수 있다. 이런 프로세스들을 임시로 보조기억장치 일부 영역으로 쫓아내고, 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식을 스와핑 이라고 한다.
 
스왑 영역: 프로세스들이 쫓겨나는 보조기억장치의 일부영역
스왑 아웃: 현재 실행되지 않는 프로세스가 메모리에서 스왑영역으로 옮겨지는 것
스왑 인: 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것
 

참고로 스왑 아웃 되었던 프로세스가 다시 스왑 인 될때는 스왑 아웃 전의 물리 주소와는 다른 주소에 적재될 수있다.

 

 

기본 미션 - 메모리 할당 방식

최초 적합: 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
최악 적합: 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
최적 적합: 프로세스가 적제될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식
 
 
프로세스가 연속 메모리 할당방식으로 스왑 인-아웃을 하다보면 위처럼 프로세스를 할당하기 어려울 만큼 작은 메모리공간들로 인해 메모리가 낭비되는 현상이 생기며 이를 외부단편화라고한다. `외부단편화`가 생긴80MB의 메모리를 할당하기위해서는 압축 방식을 이용하여 흩어져 있는 작은 빈 공간들을 하나의 큰 빈공간으로 만드는 방법이 있으나 압축하는 동안 시스템은 하던 일을 중지해야하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하기때문에 오늘날은 가상메모리 기법중 페이징 기법을 많이 쓴다.
 

 

 

 

가상메모리 (Virtual memory)

실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술이다. 가상 메모리 관리 기법에는 페이징과 세그멘테이션이 있지만 현대는 물리 메모리보다 큰 프로세스를 실행할 수 있을 뿐만 아니라 외부 단편화 문제도 해결할 수 있는 페이징 기법을 많이 사용한다.
 

 

 

 

페이징

프로세스의 논리 주소 공간을 페이지 라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임 이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법

 

한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다는 뜻으로, 실행에 필요한 일부 페이지만을 메모리에 적재 후 당장 필요하지 않은 페이지들은 보조기억장치에 남겨두는 방식으로 물리 메모리보다 더 큰 프로세스를 실행할 수 있게된다.

 

하지만 CPU입장에서는 프로세스가 메모리에 불연속적으로 배치되어있어 페이지가 어느 프레임에 적제되어있는지 알기 어렵다. 때문에 페이징 시스템은 프로세스가 실제 메모리 내의 주소인 물리주소에 불연속 적으로 배치 되더라도 CPU가 바라보는 논리주소에는 연속적으로 배치되도록 페이지 테이블을 이용한다. 프로세스마다 각자의 프로세스 테이블이 존재하며, 페이지 테이블은 페이지 번호와 프레임 번호를 짝지어 CPU로 하여금 페이지 번호만 보고 해당 페이지가 적제된 프레임을 찾을 수 있게 한다.

 

페이징 문제

페이징은 외부 단편화 문제를 해결할 수 있지만 내부단편화(Internal fragmentation)라는 문제를 야기할 수 있다.  페이징이 프로세스의 논리 주소 공간을 페이지라는 일정한 크기 단위로 자른다고 하지만 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것은 아니기 때문이다. 

ex) 108KB의 프로세스를 10KB의 페이지 크기로 자를경우 마지막 페이지는 2KB가 남게된다. => 내부단편화

 

내부 단 편화는 하나의 페이지 크기보다 작은 크기로 발생하지만 그렇다고 해서 너무 작게 설정하면 그만큼 페이지 테이블 크기도 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비된다. 따라서 테이블을 너무 크지않게 설정하며 내부 단편화도 적당히 방지하도록 해야한다.

 

요구 페이징(demand paging)

이름그대로 실행에 요구되는 페이지만 적재하는 기법이다. 페이지가 필요할 때만 메모리에 적재한다.

 

요구 페이징의 기본 양상

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.

2. 해당 페이지가 현재 메모리에 있을 경우 (유효비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.

3. 해당 페이지가 현재 메모리에 없을 경우 (유효 비트가 0일 경우) 페이지 폴트가 발생한다.

4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.

5. 다시 1번을 수행한다.

 

* 순수 요구 페이징(pure demand paging): 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행한다. 이 경우 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생하고, 실행에 필요한 페이지가 어느정도 적재된 이후부턴 페이지 폴트 발생 빈도가 감소한다.

 

 

페이지 교체 알고리즘

요구페이징 기법으로 페이지들을 적재하다보면 언젠가 메모리가 가득차게 된다. 이 때 당장 실행해 필요한 페이지를 적재하기위해 메모리에 적재된 페이지를 보조기억장치로 내보내야한다. 메모리에 적재된 페이지중 어떤 페이지를 내보낼 지 결정하는 방법을 페이지 교체 알고리즘이라 부른다.

 

페이지 교체 알고리즘은 페이지 폴트 횟수를 알 수 있어야 한다. 페이지 폴트 횟수는 페이지 참조열(page reference string)을 통해 알수 있다. 

 

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

 

연속된 페이지를 생략하는 이유: 중복페이지 참조는 페이지 폴트를 발생시키지 않는다. 페이지 교체 알고리즘 평가 시 관심있게 고려할 사항은 페이지 폴트의 발생 횟수이기 때문에 어차피 발생하지 않을 연속된 페이지에 대한 참조를 고려하지 않는 것이다.

 

대표적인 페이지 교체 알고리즘 종류

FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacement Algorithm): 이름 그대로 선입선출. 메모리에 가장 올라온 페이지부터 내쫓는 방식이다. 단점은 자칫 자주 참조되는 페이지가 먼저 적재되었다는 이유만으로 내쫓길 수 있는 문제를 가지고 있다.

 

2차 기회 페이지 교체 알고리즘(Second Chance Page Replacement Algorithm): FIFO의 부작용을 어느정도 개선한 페이지 교체 알고리즘의 변형이다. 메모리에서 가장 오래 머물렀던 페이지를 대상으로 내보낼 페이지를 선별 후 페이지의 참조 비트를 확인한다. 만일 페이지의 참조 비트가 1일 경우, 당장 내쫓지 않고 참조비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정한다.

 

최적 페이지 교체 알고리즘(Optimal Page Replacement Algorithm): CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘이다. 앞으로 사용 빈도가 가장 낮을 페이지를 교체하기 때문에 다른 페이지 교체 알고리즘에 비해 페이지 폴트 발생 빈도가 가장 낮다. 단점은 '앞으로 오랫동안 사용되지 않을 페이지'를 예측하기가 어려워 실제 구현이 어렵다. 따라서 그 자체를 운영체제에서 사용하기 보단 주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용된다. 최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 페이지 폴트 하한선으로 간주하고, 최적 페이지 교체 알고리즘에 비해 얼만큼 페이지 폴트 횟수가 발생하느냐를 통해 평가를 하게된다.

 

LRU 페이지 교체 알고리즘(Least Recently Used Page Replacement Algorithm): 최적 페이지 교체 알고리즘이 '앞으로 사용 빈도가 가장 낮을'이었다면 LRU 페이지 교체 알고리즘은 '가장 오랫동안 사용되지 않은' 페이지를 교체하는 알고리즘이다. 최근 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라는 생각으로 만들어진 알고리즘으로 페이지마다 마지막 사용 시간을 토대로 교체를 진행한다.

 

LRU페이지 교체 알고리즘