기본미션📣
14-1 확인문제 1번 | ① 최초 적합 ② 최악 적합 ③ 최적 적합
선택미션📣
14-3 확인문제 1번 | 3번
14-1 연속 메모리 할당
지금까지 배운 내용은 프로세스 A는 A의 크기만큼 메모리 주소를 할당받아 연속적으로 배치되고, 프로세스 B는 프로세스 A 이후에 또 B의 크기만큼 연속적인 메모리 주소를 할당받는 방식의 연속 메모리 할당 방식을 사용하였다. 그럼 연속 메모리 할당 방식은 메모리를 할당할 때 무엇을 고려하
고, 어떤 문제가 있는지 알아보겠다.
스와핑
메모리에 적재된 프로세스들 중에는 입출력 작업으로 인해 대기 상태가 된 프로세스처럼 현재 실행되지 않는 프로세스가 있다. 이러한 프로세스들은 오랫동안 사용되지 않기 때문에 임시로 보조기억장치 일부 영역을 쫓아내고, 그렇게 해서 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는데, 이 방식을 스와핑이라 한다.
이때 프로세스들이 쫓겨나는 보조기억장치의 일부 영역을 스왑 영역이라 하고, 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃, 반대로 다시 스왑 영역에서 메모리로 옮겨오는 것은 스왑 인이라 한다. 스왑 아웃되었던 프로세스가 다시 스왑 인될 때는 스왑 아웃되기 전의 물리 주소와는 다른 주소에 적재될 수 있다.
스와핑을 이용하면 프로세스들이 요구하는 메모리 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시에 실행시킬 수 있다.
메모리 할당
프로세스는 메모리 내에 빈 공간에 적재되어야 한다. 그런데 메모리 내에 빈 공간이 여러 개 있다면 프로세스를 어디에 배치해야 할까. 여기에는 대표적으로 최초 적합, 최적 적합, 최악 적합 세 가지 방식이 있다.
최초 적합
최초 적합은 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식이다. 최초 적합 방식은 프로세스가 적재될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식이므로 검색을 최소화할 수 있고 결과적으로 빠른 할당이 가능하다.
최적 적합
최적 적합은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중
가장 작은 공간에 프로세스를 배치하는 방식이다.
최악 적합
최악 적합은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중
가장 큰 공간에 프로세스를 배치하는 방식이다.
외부 단편화
프로세스를 메모리에 연속적으로 배치하는 연속 메모리 할당은 사실 메모리를 효율적으로 사용하는 방법은 아니다. 왜냐하면 연속 메모리 할당은 외부 단편화라는 문제를 내포하고 있기 때문인데,
외부 단편화는 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상을 의미한다.
예를 들어 실행이 끝난 프로세스가 나가고 각각 30MB, 20MB에 빈 공간이 생겼다. 그래서 현재 메모리에 남아 있는 빈 공간의 총합은 50MB이다. 하지만 빈 공간의 총합이 50MB라고 해도 각각 떨여져 있으므로 50MB 크기의 프로세스가 적재될 수 없다.
프로세스들이 메모리에 연속적으로 할당되는 환경에서는 위와 같이 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이 사이에 빈 공간들이 생긴다. 프로세스 바깥에 생기는 이러한 빈 공간들은 분명 빈 공간이지만 그 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래하고, 결국 메모리 낭비로 이어진다. 외부 단편화 현상이 일어나는 것이다.
외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리를 압축하는 방법이 있다.
압축은 여기저기 흩어져 있는 빈 공간들을 하나로 모으는 방식으로 메모리 내에 저장된 프로세스를 적당히 재배치시켜 흩어져 있는 작은 빈 공간들은 하나의 큰 빈 공간으로 만드는 방법이다.
다만 압축에는 여러 단점이 있다. 빈 공간을 모으는 동안 시스템은 하던 일을 중지해야 하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기한다.
14-2 페이징을 통한 가상 메모리 관리
외부 단편화를 없앨 수 있는 해결법은 압축 외에도 가상 메모리 기법, 그 중에서도 페이징 기법이 있다. 페이징 기법을 이용하면 앞서 말한 외부 단편화 문제를 해결할 수 있을 뿐만 아니라 연속 메모리 할당에 또 다른 문제인 물리 메모리보다 큰 프로세스를 실행할 수 없다는 점을 해결할 수 있다.
가상 메모리는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 만드는 기술인데, 이를 가능케 하는 가상 메모리 관리 기법에는 크게 페이징과 세그멘테이션이 있다.
페이징이란
외부 단편화가 생긴 근본적인 원인은 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문인데, 만약 메모리와 프로세스를 일정한 단위로 자르고 이를 메모리에 불연속적으로 할당하면 외부 단편화는 발생하지 않는다. 그래서 나온 것이 페이징이다.
페이징은 프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 기법이다.
페이징에서도 스와핑을 사용할 수 있는데, 페이징을 사용하는 시스템에서는 프로세스 전체가 아닌 페이지 단위로 스와 아웃/스왑 인된다. 페이징 시스템에서의 스왑 아웃은 페이지 아웃, 스왑 인은 페이지 인이라고 부르기도 한다.
이는 다시 말해 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다는 말과 같다. 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 필요하
지 않은 페이지들은 보조기억장치에 남겨둔다.
페이지 테이블
그런데 여기서 문제가 있다. 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서 이를 순차적으로 실행할 수가 없다. 즉, 프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 '다음에 실행할 명령어 위치'를 찾기가 어려워진다.
이를 해결하기 위해 페이징 시스템은 프로세스가 비록 (실제 메모리 내의 주소인) 물리 주소에 불연
속적으로 배치되더라도 (CPU가 바라보는 주소인) 논리 주소에는 연속적으로 배치되도록 페이지 테
이블을 이용한다.
페이지 테이블은 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표로, 현재 어떤 페이지가 어떤 프레임에 할당되었는지 알려준다. 즉 프로세스들이 메모리에 분산되어 있어도 CPU는 논리 주소를 순차적으로 실행하기만 하면 된다.
프로세스마다 각자의 프로세스 테이블을 가지고 있고 각 프로세스의 페이지 테이블들은 메모리에 적재되어 있다. 그리고 CPU 내의 페이지 테이블 베이스 레지스터(PTBR)가 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.
그런데 이렇게 페이지 테이블을 메모리에 두면 문제가 있다. 메모리 접근 시간이 두 배로 늘어난 다는 점이다. 이와 같은 문제를 해결하기 위해 CPU 곁에 TLB라는 페이지 테이블의 캐시 메모리를 두는데, TLB는 페이지 테이블의 캐시 메모리 역할을 수행하기 위해 페이지 테이블의 일부를 저장한다. 그러면 CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 메모리에 접근할 필요가 없어지게 된다. 이 경우를 TLB 히트라고 한다. 반대로 페이지 번호가 TLB에 없을 경우 메모리 내의 페이지 테이블의 직접 접근해야 하는데, 이를 TLB 미스라고 한다.
내부 단편화
여기서 문제는 페이징이 외부 단편화 문제를 해결할 수는 있지만, 내부 단편화 문제를 야기할 수 있다는 것이다. 페이징은 프로세스의 논리 주소 공간을 페이지라는 일정한 크기 단위로 자른다고 했다. 그런데 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것은 아니다. 예를 들어 페이지 크기가 10KB인데, 프로세스의 크기가 108KB라고 한다면 마지막 페이지는 2KB만큼의 크기가 남는다. 이러한 메모리 낭비가 내부 단편화이다.
내부 단편화는 하나의 페이지 크기보다 작은 크기로 발생하기 때문에 하나의 페이지 크기가 작다면 발생하는 내부 단편화의 크기도 작아질 것이다. 하지만 하나의 페이지 크기를 너무 작게 설정하면 그만큼 페이지 테이블의 크기도 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비된다. 그렇기에 내부 단편화를 적당히 방지하면서 너무 크지 않은 페이지 테이블이 만들어지도록 페이지의 크기를 조정하는 것이 중요하다.
페이징에서의 주소 변환
하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있다. 그렇기에 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호와 변위로 나뉘어 있다. CPU가 어떤 페이지 혹은 프레임에 접근하고 싶은지, 접근하려는 주소가 그 페이지로부터 얼마나 떨어져있는지 알기 위해서이다.
거기서 페이지 번호가 말 그대로 접근하고자 하는 페이지 번호를 뜻하고, 변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보다. 즉, 논리 주소 <페이지 번호, 변위>는 페이지 테이블을 통해 물리 주소 <프레임 번호, 변위>로 변환된다.
이 과정은 말보다 예제를 통해 이해하는 것이 빠른데, 하나의 페이지/프레임이 네 개의 주소로 구성되어 있는 간단한 상황을 보겠다.
CPU가 5번 페이지, 변위 2라는 논리 주소 <5,2>에 접근하고 싶어 한다고 가정해 보겠다.
5번 페이지는 현재 1번 프레임에 있기 때문에 CPU는 1번 프레임 변위 2에 접근하게 된다.
그러면 1번 프레임은 8번지부터 시작하므로 CPU는 10번지에 접근한다.
페이지 테이블 엔트리
페이지 테이블을 조금 자세히 들여다보면 페이지 테이블의 각 엔트리, 다시 말해 페이지 테이블의 각각의 행들을 페이지 테이블 엔트리라고 한다. 지금까지 페이지 테이블 엔트리에 페이지 번호와 프레임 번호만 설명했지만, 실은 페이지 테이블 엔트리는 이외에도 중요한 것들이 있다. 대표적으로 유효 비트, 보호 비트, 참조 비트, 수정 비트이다.
유효 비트
유효 비트는 현재 해당 페이지에 접근 가능한지 여부를 알려준다. 페이징에서도 스와핑을 사용할 수 있기 때문에 모든 페이지가 메모리에 있지 않다. 그렇기 때문에 유효 비트는 페이지가 메모리에 적재되어있으면 1, 보조기억장치에 있다면 0으로 페이지 접근 가능 여부를 알려준다. 페이지 테이블 엔트리에서 프레임 번호 다음으로 중요한 정보라고 볼 수 있다.
만일 CPU가 메모리에 적재되어 있지 않은 페이지로 접근하려고 한다면 페이지 폴트라는 예외가 발생한다. CPU가 페이지 폴트를 처리하는 과정은 하드웨어 인터럽트를 처리하는 과정과 유사하다. CPU는 기존 작업 내역을 백업한 후, 페이지 폴트 처리 루틴을 실행하여 페이지를 메모리로 가져온다. 그 후 유효 비트를 1로 변경해주어 해당 페이지에 접근할 수 있게 만든다.
보호 비트
보호 비트는 페이지 보호 기능을 위해 존재하는 비트이다. 앞서 프로세스를 이루는 요소 중 코드 영역은 읽기 전용 영역이라 하였다. 보호 비트는 해당 페이지가 읽고 쓰기가 모두 가능한 페이지인지 알려주는데, 읽기만 가능한 페이지일 때는 0, 읽고 쓰기가 모두 가능할 때는 1로 알려주어 읽기 전용 페이지에 쓰기를 시도하면 운영체제가 이를 막아준다.
보호 비트는 세 개의 비트로 조금 더 복잡하게 구현할 수 있다. 읽기(Read)를 나타내는 r, 쓰기(Write)를 나타내는 w, 실행(eXecute)을 나타내는 x의 조합으로 읽기, 쓰기, 실행하기 권한의 조합을 나타낼 수 있다.
참조 비트
참조 비트는 CPU가 이 페이지에 접근한 적이 있는지 접근 여부를 나타낸다. 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1로 세팅되고, 적재 이후 한 번도 읽거나 쓴 적이 없는 페이지는 0으로 유지된다.
수정 비트
수정 비트는 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려준다. 더티 비트라고도 불린다. 이 비트가 1이면 변경된 적이 있는 페이지, 0이면 변경된 적이 없는 페이지(한 번도 접근한 적 없거나 읽기만 했던 페이지)임을 나타낸다.
수정 비트는 좀 더 자세히 말하자면 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단하기 위한 존재이다. CPU가 한 번도 접근하지 않았거나 읽기만 한 페이지의 경우 보조기억장치에 저장된 해당 페이지의 내용과 메모리에 저장된 페이지 내용이 서로 같다. 이런 경우 페이지가 스왑 아웃될 때 아무런 추가 작업 없이 페이지를 덮어쓰기만 하면 된다.
하지만 CPU가 쓰기 작업을 수행한 페이지(수정 비트가 1인 페이지)인 경우 보조기억장치와 메모리에 저장된 내용이 서로 다른 값을 갖게 된다. 이렇게 수정된 적이 있는 페이지가 스왑 아웃될 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 하기 때문에 페이지 테이블 엔트리에 수정 비트를 두는 것이다.
14-3 페이지 교체와 프레임 할당
요구 페이징
프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징이라고 한다.
요구 페이징의 기본적인 양상은 다음과 같다.
1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2. 해당 페이지가 현제 메모리에 있을 경우 CPU는 페이지가 적재된 프레임에 접근한다.
3. 해당 페이지가 현재 메모리에 없을 경우 페이지 폴트가 발생한다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
5. 다시 1번을 수행한다.
심지어 아무런 페이지도 메모리에 적재하지 않은 무작정 실행부터 할 수 있다. 이 경우 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생하게 되고, 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어진다. 이를 순수 요구 페이징 기법이라 한다.
다시 요구 페이징으로 돌아와서, 요구 페이징 시스템이 안정적으로 작동하려면 필연적으로 다음 두 가지를 해결해야 한다. 바로 페이지 교체와 프레임 할당이다.
페이지 교체 알고리즘
요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가 메모리가 가득 차게 된다. 이때 당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내야 하는데, 이를 결정하는 방법이 페이지 교체 알고리즘이다.
일반적으로 페이지 폴트를 가장 적게 일으키는 알고리즘을 좋은 알고리즘으로 평가하는데, 페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 메모리에 적재된 페이지를 가져오는 것보다 느려지기 때문이다.
예를 들어 '한 페이지 교체 알고리즘을 선택했더니 페이지 폴트가 자주 발생했다'는 말은 '보조기억장치로 내쫓을 페이지를 잘못 골랐다'라는 뜻이기 때문에 컴퓨터의 성능을 저해하는 나쁜 알고리즘이다. 반면 '어떤 알고리즘을 통해 고른 페이지를 스왑 아웃시켜도 페이지 폴트가 자주 발생하지 않는다'라는 말은 컴퓨터의 성능 저하를 방지하는 좋은 알고리즘으로 평가할 수 있다.
그렇기에 페이지 교체 알고리즘을 제대로 이해하려면 페이지 폴트 횟수를 알아야 한다. 페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있는데, 페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미한다.
여기서 연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문이다. 페이지 교체 알고리즘을 평가할 때 관심있게 고려할 것은 오직 페이지 폴트의 발생 횟수이기 때문에 어차피 페이지 폴트가 일어나지 않을 연속된 페이지에 대한 참조는 고려하지 않는다.
FIFO 페이지 교체 알고리즘
첫 번째로 소개할 알고리즘은 FIFO 페이지 교체 알고리즘이다. 이는 가장 단순한 방법으로 이름 그대로 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식이다.
FIFO 페이지 교체 알고리즘은 아이디어와 구현이 간단하지만, 마냥 좋지만은 않다. 프로그램 실행 초기에 실행되었다가 사용되지 않을 페이지도 있겠지만, 프로그램 실행 내내 사용될 페이지가 메모리에 먼저 적재되었다고 해서 먼저 쫓겨날 수도 있기 때문이다.
2차 기회 페이지 교체 알고리즘
이러한 FIFO 페이지 교체 알고리즘에 문제를 해결하기 위해서 나온 것이 2차 기회 페이지 교체 알고리즘인데, 2차 기회 페이지 교체 알고리즘은 이름 그대로 한 번 더 기회를 주는 것이다.
2차 기회 페이지 교체 알고리즘은 FIFO 페이지 교체 알고리즘과 같이 기본적으로 메모리에서 가장 오래 머물렀던 페이지를 대상으로 내보낼 페이지를 선별한다. 하지만 차이가 있다면 페이지의 참조 비트가 1일 경우, 참조 비트를 0으로 만든 뒤 기회를 한 번 더 주는 것이다.
최적 페이지 교체 알고리즘
최적 페이지 교체 알고리즘은 CPU에 의해 참조되는 회수를 고려하는 페이지 교체 알고리즘이다. 메모리에 오랫동안 남아야 할 페이지는 자주 사용될 페이지고, 반대로 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지이다. 그렇기에 보조기억장치로 내보내야 할 페이지를 사용 빈도가 가장 낮은 페이지로 결정하는 것이 가장 합리적이다.
최적 페이지 교체 알고리즘은 이름 그대로 가장 낮은 페이지 폴트율을 보장하는 알고리즘이다.
다만 최적 페이지 교체 알고리즘은 실제 구현이 어렵다. 이 알고리즘을 사용하려면 프로세스가 앞으로 메모리 어느 부분을 참조할지 미리 알아야 하는데, 이는 현실적으로 불가능에 가깝다. 그렇기 때문에 최적 페이지 교체 알고리즘은 주로 이론상 성능을 평가하기 위한 목적으로 사용된다.
LRU 페이지 교체 알고리즘
최적 페이지 교체 알고리즘은 구현하기 어려워도 이와 비슷한 알고리즘은 만들 수 있다.
최적 페이지 교체 알고리즘을 조금 변형하여 가장 오랫동아 사용되지 '않을' 페이지가 아닌 가장 오랫동안 사용되지 '않은' 페이지를 교체하는 알고리즘을 구현하는 것이다.
그래서 LRU 페이지 교체 알고리즘은 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체한다.
스레싱
페이지 폴트가 자주 발생하는 이유에는 나쁜 페이지 교체 알고리즘만 있는 것은 아니다.
사실 더 근본적인 이유는 프로세스가 사용할 수 있는 프레임 수가 적기 때문이다. 프레임이 부족하면 CPU는 페이지 폴트가 자주 발생할 수밖에 없고, 결과적으로 CPU의 이용률도 떨어지게 된다. CPU가 쉴새 없이 프로세스를 실행해야 컴퓨터 전체의 생산성도 올라갈 텐데, 페이지 교체에 너무 많은 시간을 쏟으면 당연히 성능에도 큰 악영향이 초래된다. 이처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱이라고 한다.
스래싱을 그래프로 표현하면 아래와 같은데, 세로축인 CPU 이용률이 높으면 CPU는 현재 일을 쉬지 않고 하고 있다는 의미이고, 가로축인 멀티 프로그래밍의 정도는 메모리에 올라와 있는 프로세스의 수를 알 수 있다. 메모리에서 동시 실행되는 프로세스의 수를 멀티프로그래밍의 정도라고 한다.
이 그래프는 동시에 실행되는 프로세스의 수(멀티프로그래밍의 정도)를 늘린다고 해서 CPU 이용률이 그에 비례해서 증가하는 것이 아님을 나타낸다. 동시에 실행되는 프로세스 수가 어느 정도 증가하며 CPU 이용률이 높아지지만, 필요 이상으로 늘리면 각 프로세스들이 사용할 수 있는 프레임 수가 적어져 오히려 CPU의 성능이 저해될 수 있다.
스래싱이 발생하는 근본적인 이유는 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다. 그렇기에 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼 프레임을 할당해 줄 수 있어야 한다.
프레임 할당
우선 가장 단순한 형태의 프레임 할당 방식부터 보자면, 모든 프로세스에 균등하게 프레임을 제공하는 균등 할당 방식이 있다. 하지만 실행되는 프로세스들의 크기는 각기 다르기 때문에 균등 할당 방식은 그렇게 권장할 만한 방법이 아니다.
가령 크기가 큰 프로세스와 상대적으로 크기가 작은 프로세스가 있으면 크기가 큰 프로세스에 더 많은 프레임을 할당하는 것이 더 합리적이다. 이렇게 프로세스의 크기가 크면 프레임을 많이 할당하고 프로세스의 크기가 작으면 프레임을 적게 나눠 주는 방식을 비례 할당이라고 한다.
균등 할당과 비례 할당 방식은 프로세스 실행 과정은 고려하지 않고 단순히 물리 메모리의 크기만을 고려한 방식이라는 점에서 정적 할당 방식이라고 한다.
하지만 비례 할당 또한 완벽한 방식은 아니다. 프로세스의 크기가 클지라도 막상 실행해 보니 많은 프레임을 필요로 하지 않는 경우도 있고, 반대로 프로세스의 크기는 작아도 많은 프레임이 필요로 하는 경우가 있다. 즉, 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지는 결국 실행해 봐야 아는 경우가 많다는 것이다.
프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식에는 크게 작업 집합 모델 방식과 페이지 폴트 빈도 방식이 있다. 이 두 개 방식은 프로세스의 실행을 보고 프레임 수를 결정한다는 점에서 동적 할당 방식이라고도 한다.
스래싱이 발생하는 이유는 빈번한 페이지 교체 때문이다. 그렇기에 작업 집합 모델 기반 프레임 할당 방식은 '프로세스가 일정 기간 동안 참조한 페이지 집합'을 기억하여 빈번한 페이지 교체를 방지한다. 여기서 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 작업 집합이라고 한다.
또, 페이지 폴트 빈도를 기반으로 한 프레임 할당도 알아보자면, 이를 그래프로 표현했을 때 다음과 같이 반비례 관계를 보이는 것을 알 수 있다.
여기서 임의로 페이지 폴트율의 상한선과 하한선을 그려보면 상한선보다 높은 프로세스는 너무 적은 프레임을 갖고 있다는 것을, 하한선보다 더 낮은 프로세스는 너무 많은 프레임을 갖고 있다는 것을 알 수 있다. 그러면 경우에 따라 프레임을 더 할당해주거나 프레임을 회수해주면 된다.
즉, 페이지 폴트 빈도 기반 프레임 할당 방식은 페이지 폴트율에 상한선과 하한건을 정하고, 이 범위 안에서만 프레임을 할당하는 방식이다.
15-1 파일과 디렉터리
파일
파일이란 하드 디스크나 SSD와 같은 보조기억장치에 저장된 관련 정보의 집합을 의미한다.
달리 표현하면 의미 있고 관련 있는 정보를 모은 논리적 단위라고 할 수 있다.
파일을 이루는 정보에는 이름과 파일을 실행하기 위한 정보, 관련된 부가 정보가 있다.
이 부가 정보를 속성 또는 메가데이터라고 하는데, 파일의 속성에는 파일 형식, 위치, 크기 등과 같은 다양한 정보가 나타난다.
파일 속성과 유형
운영체제마다 유지하는 파일 속성은 조금씩 차이가 있지만, 운영체제 내부에 파일 시스템은 파일별로 다음과 같은 속성을 유지하고 관리한다.
| 속성이름 | 의미 |
|---|---|
| 유형 | 운영체제가 인지하는 파일의 종류를 나타낸다. |
| 크기 | 파일의 현재 크기와 허용 가능한 최대 크기를 나타낸다. |
| 보호 | 어떤 사용자가 해당 파일을 읽고, 쓰고, 실행할 수 있는지를 나타낸다. |
| 생성 날짜 | 파일이 생성된 날짜를 나타낸다. |
| 마지막 접근 날짜 | 파일에 마지막으로 접근한 날짜를 나타낸다. |
| 마지막 수정 날짜 | 파일에 마지막으로 수정된 날짜를 나타낸다. |
| 생성자 | 파일을 생성한 사용자를 나타낸다. |
| 소유자 | 파일을 소유한 사용자를 나타낸다. |
| 위치 | 파일의 보조기억장치상의 현재 위치를 나타낸다. |
파일 속성 중 파일 유형은 운영체제가 인식하는 파일 종류를 나타내는데, 같은 이름의 파일일지라도 텍스트 파일, 음악 파일 등 유형이 다르면 실행 양상도 달라지게 된다. 그래서 흔히 파일 유형을 알리기 위해서는 이름 뒤에 확장자를 붙인다. 확장자는 파일 종류가 무엇인지 운영체제에 알려주는 힌트와 같은 역할이다.
| 파일 유형 | 대표적인 확장자 |
|---|---|
| 실행파일 | 없는 경우, exe, com, bin |
| 목적파일 | obj, o |
| 소스 코드 파일 | c, cpp, cc, java, asm, py |
| 워드 프로세서 파일 | xml, rtf, doc, docx |
| 라이브러리 파일 | lib, a, so, dll |
| 멀티미디어 파일 | mpeg, mov, mp3, mp4, avi |
| 백업/보관 파일 | rar, zip, tar |
파일 연산을 위한 시스템 호출
파일을 다루는 모든 작업은 운영체제에 의해 이루어 진다. 어떤 프로그램도 임의로 파일을 조작할 수 없고 운영체제를 통해야 하는데, 이를 위해 운영체제는 다음과 같은 시스템 호출을 제공한다.
- 파일 생성
- 파일 삭제
- 파일 열기
- 파일 닫기
- 파일 읽기
- 파일 쓰기
디렉터리
운영체제는 파일들을 일목요연하게 관리하기 위해 디렉터리를 이용하는데, 윈도우에선 디렉터리를 폴더라고 부른다.
옛날 운영체제에서는 하나의 디렉터리만 존재하여 모든 파일이 하나의 디렉터리 아래에 있었다. 이와 같은 구조를 1단계 디렉터리라고 불렀다. 하지만 컴퓨터 용량이 커지다 보니 저장할 수 있는 파일이 많아지고, 1단계 디렉터리로는 많은 파일을 관리하기 어렵기 때문에 실제로 1단계 디렉터리를 사용하는 컴퓨터는 거의 없었다.
그래서 나오게 된 것이 트리구조 디렉터리인데, 트리 구조 디렉터리는 최상위 디렉터리가 있고 그 아래에 여러 서브 디렉터리(자식 디렉터리)가 있다. 최상위 디렉터리는 흔히 루트 디렉터리라고 부르고 슬래시(/) 표현한다.
그러다 보니 자연스레 생긴 개념이 바로 경로이다. 경로는 디렉터리를 이용해 파일 위치, 나아가 파일 이름을 특정 짓는 정보이다.
절대 경로와 상대 경로
디렉터리 내에는 동일한 이름의 파일이 존재할 수 없지만, 서로 다른 디렉터리에는 동일한
이름의 파일이 존재할 수 있다. 이는 루트 디렉터리부터 파일까지 경로가 다르기 때문인데,
이렇듯 모든 파일은 디렉터리에서 자기 자신까지 이르는 고유한 경로를 가지고 있고, 이러한
경로를 절대 경로라고 한다.
유닉스와 리눅스, macOS 등의 운영체제에서는 절대 경로를 표현할 때 루트 디렉터리를 표시할 뿐만 아니라 디렉터리와 디렉터리 사이의 구분자로도 슬래시(/)를 사용한다. 그래서 예를 들면 /home/minchul/a.sh로 표현할 수 있다.
참고로 윈도우에서는 디렉터리 구분자로 \를 사용한다. 그래서 윈도우에 절대 경로는 \home\minchul\a.sh로 표현된다.
경로를 나타내는 또 다른 방식으로는 상대 경로가 있다. 절대 경로가 루트 디렉터리부터 시작하는 경로라면 상대 경로는 현재 디렉터리부터 시작하는 경로이다. 예를 들어 현재 디렉터리 경로가 /home이라면 a.sh의 상대 경로는 minchul/a.sh가 되는 것이다.
디렉터리 연산을 위한 시스템 호출
운영체제는 파일 연산을 위한 시스템 호출을 제공할 뿐만 아니라 디렉터리 연산을 위한 시스템 호출도 제공하는데, 대표적인 종류는 다음과 같다.
- 디렉터리 생성
- 디렉터리 삭제
- 디렉터리 열기
- 디렉터리 닫기
- 디렉터리 읽기
디렉터리 엔트리
여기서 중요한 점은 디렉터리도 그저 특별한 형태의 '파일'이라는 점이다. 즉, 디렉터리도 단지 포함된 정보가 조금 특별한 뿐이지 파일이다. 파일이 내부에 해당 파일과 관련된 정보를 담고 있다면, 디렉터리는 내부에 해당 디렉터리와 관련된 정보를 담고 있다. 그리고 이 정보는 보통 테이블(표) 형태로 구성되어 디렉터리는 보조기억장치에 테이블 형태의 정보로 저장된다.
각각의 엔트리(행)에 담기는 정보는 파일 시스템마다 차이가 있지만, 파일 시스템을 막론하고 디렉터리 엔트리가 공통으로 포함하는 정보는 디렉터리에 포함된 대상의 이름과 그 대상이 보조기억장치 내에 저장된 위치를 유추할 수 있는 정보가 담긴다.
즉, 운영체제는 이러한 정보를 저장하는 파일을 디렉터리라고 간주하는 것이다.
예를 들어 다음과 같은 구조의 디렉터리와 파일이 있다고 가정해 보겠다.
그렇다면 home 디렉터리 테이블을 다음과 같이 구성된다. 여기서 ..은 상위 디렉터리, .은 현재 디렉터리를 가리킨다.
디렉터리 엔트리를 통해 보조기억장치에 저정된 위치를 알 수 있기 때문에 home 디렉터리에서 minchul 디렉터리가 저장된 곳을 알 수 있고, 마찬가지로 minchul 디렉터리 엔트리에는 디렉터리에 속한 파일들의 이름(a.sh, b.c, c.tar)과 이들의 위치가 있기 때문에 보조기억장치 내에 저장된 위치를 알고 실행할 수 있는 것이다.
15-2 파일 시스템
파티셔닝과 포매팅
보조기억장치를 처음 사용하기 위해서는
파티션을 나누는 작업( 파티셔닝 )과 포맷 작업( 포매팅 )을 거쳐야 한다.
파티셔닝은 저장 장치의 논리적인 영역을 구획하는 작업을 의미하는데, 쉽게 말하면 칸막이로 영역을 나누는 작업이라고 할 수 있다. 그리고 이렇게 파티셔닝 작업을 통해 나누어진 영역 하나하나를 파티션이라고 한다.
포맷하는 작업, 포매팅은 저장 장치를 완전히 삭제하는 작업도 맞지만 더 정확히 말하자면
파일 시스템을 설정하여 어떤 방식으로 파일을 저장하고 관리할 것인지를 결정하고, 새로운 데이터를 쓸 준비를 하는 작업을 의미한다. 바로 이때 어떤 종류의 파일 시스템을 쓸 것인지도 결정난다.
파일 시스템에는 여러 종류가 있고, 파티션마다 다른 파일 시스템을 설정할 수도 있다. 또한 파티셔닝과 포매팅은 동시에 진행되는 경우가 많고, 이미 포매팅까지 완료되어 판매되는 경우도 많다.
파일 할당 방법
운영체제는 파일과 디렉터리를 블록 단위로 읽고 쓴다. 하나의 파일이 보조기억장치에 저장될 때 하나 이상의 블록에 걸쳐 저장된다는 것이다. 하드 디스크의 가장 작은 저장 단위는 섹터이지만, 운영체제는 하나 이상의 섹터를 블록이라는 단위로 묶은 뒤 블록 단위로 파일과 디렉터리를 관리한다. 파일 시스템이 모든 섹터를 관리하기엔 개수도 많고, 크기도 작기 때문이다.
이런 상황에서 파일을 보조기억장치에 할당하는 방법에는 크게 두 가지가 있다.
연속 할당과 불연속 할당이다. 그리고 불연속 할당에는 크게 연결 할당, 색인 할당이 있다.
연속 할당
연속 할당은 가장 단순한 방식이다. 이름 그대로 보조기억장치 내 연속적인 블록에 파일을 할당하는 방식이다. 연속으로 할당된 파일에 접근하기 위해서는 파일의 첫 번째 블록 주소와 블록 단위의 길이만 알면 된다. 그렇기에 연속 할당을 사용하는 디렉터리 엔트리에는 파일 이름과 더불어 첫 번째 주소와 블록 단위의 길이를 명시한다.
연속 할당 방식은 구현이 단순하지만, 외부 단편화를 야기한다는 치명적인 문제가 있다.
연결 할당
연속 할당의 문제를 해결할 수 있는 방식이 연결 할당이다. 연결 할당은 불연속 할당의 일종이기에 파일이 여러 블록에 흩어져 저장되는데, 그래서 각 블록 일부에 다음 블록의 주소를 저장하여 각 블록이 다음 블록을 가리키도록 데이터를 연결 리스트로 관리한다.
여기서 마지막 블록에는 다음 블록이 없다는 특별한 표시자를 기록하는데, 예시에서는 -1을 이용했다.
연결 할당은 외부 단편화 문제를 해결하지만 이 또한 단점이 있다.
1) 반드시 첫 번째 블록부터 하나씩 차례대로 읽어야 한다.
첫 번째 단점은 파일의 중간 부분부터 접근하고 싶어도 반드시 파일의 첫 번째 블록부터 접근하여 하나씩 차례대로 읽어야 한다는 점이다. 다시 말해 파일 내 임의의 위치에 접근하는 속도, 임의 접근 속도가 매우 느리다. 이는 성능 면에서 상당히 비효율적이다.
2) 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근할 수 없다.
두 번째 단점은 하나의 블록 안에 파일 데이터와 다음 블록 주소가 모두 포함되어 있다 보니, 하드웨어 고장이나 오류가 발생하면 그 블록 이후의 블록에 접근할 수 없다.
그래서 오늘날에는 위 내용을 그대로 구현하기보다는 이를 조금 변형하여 사용하는데, 연결 할당을 변형한 대표적인 파일 시스템이 FAT 파일 시스템이다 .
색인 할당
연결 할당은 블록 일부에 다음 블록 주소를 표현하는 방식인 반면, 색인 할당은 파일의 모든 블록 주소를 색인 블록이라는 하나의 블록에 모아 관리하는 방식이다. 파일 A에 순차적으로 접근하고 싶다면 색인 블록에 저장된 주소에 차례대로 접근하면 된다.
또 색인 할당은 연결 할당과 달리 파일 내 임의의 위치에 접근하기 쉽다. 색인 블록 안에 파일을 구성하는 테이블 블록 주소가 있으므로 색인 블록만 알면 해당 파일 데이터에 접근할 수 있는 것이다. 그렇기에 색인 할당을 사용하는 파일 시스템에서는 디렉터리 엔트리에 파일 이름과 더불어 색인 블록 주소를 명시한다.
색인 할당을 기반으로 만든 대표적인 파일 시스템은 유닉스 파일 시스템이다.
FAT 파일 시스템
앞서 말한 것처럼 연결 할당의 단점을 보완한 파일 시스템이 FAT 파일 시스템이다.
연결 할당에 근본적인 원인은 블록 안에 다음 블록의 주소를 저장하였기 때문이었다. 하지만 각 블록에 포함된 다음 블록의 주소들을 한데 모아 테이블 형태로 관리하면 이 문제를 상당 부분 해소 할 수 있는데, 이러한 테이블을 파일 할당 테이블( FAT )이라고 한다.
FAT 파일 시스템은 옛날 마이크로소프트의 운영체제인 MS-DOS에서 사용되었고, 최근까지 USB 메모리, SD 카드와 같은 저용량 저장 장치용 파일 시스템으로 많이 이용되고 있다. 버전에 따라 FAT12, FAT16, FAT32가 있으며, FAT 뒤에 오는 숫자는 블록을 표현하는 비트 수를 의미한다.
FAT 파일 시스템에서 FAT는 파티션에 앞부분에 만들어지는데, 다음 그림은 FAT12 파일 시스템을 사용하는 파티션을 갼략화한 도식도이다.
하드 디스크의 한 파티션을 FAT 파일 시스템으로 포맷하면 해당 파티션이 다음과 같이 구성된다. FAT영역에는 FAT가 저장되고, 뒤이어 루트 디렉터리가 저장되는 영역이 있으며, 그 뒤에 서브 디렉터리와 파일들을 위한 영역이 있다.
FAT는 하드 디스크 파티션의 시작 부분에 있지만, 실행하는 도중 FAT가 메모리에 캐시될 수 있다. 그러면 FAT가 메모리에 적재된 채 실행되어 기존 연결 할당보다 다음 블록을 찾는 속도가 매우 빨라지고, 결과적으로 앞서 설명한 연결 할당 방식보다 임의 접근에도 유리해진다.
이번에는 FAT 파일 시스템의 디렉터리 엔트리를 조금 더 자세히 살펴보겠다. 앞서 말한 것처럼 FAT 파일 시스템의 디렉터리 엔트리에는 파일 이름과 파일의 첫 번째 블록 주소가 명시된다.
또, 이외에도 파일 속성과 관련한 정보들도 담기는데, 다음과 같은 형식으로 블록에 저장된다.
유닉스 파일 시스템
유닉스 파일 시스템은 색인 할당 기반의 파일 시스템이다. 색인 할당은 색인 블록을 기반으로 파일의 데이터 블록을 찾는데, 유닉스 파일 시스템은 이 색인 블록을 i-node라고 부른다.
앞서 FAT 파일 시스템에서 파일 속성 정보가 디렉터리 엔트리에 표현되었다면 유닉스 파일 시스템에서는 파일 속성 정보가 i-node에 표현된다. i-node에는 파일 속성 정보와 열다섯 개의 블록 주소가 저장될 수 있다.
유닉스 파일 시스템에는 파일마다 이러한 i-node가 있고, i-node마다 번호가 부여되어 있다.
i-node들은 다음과 같이 파티션 내 특정 영역에 모여 있고, 데이터 영역에 디렉터리와 파일들이 있다. 
그런데 여기서 문제가 있다. i-node의 크기는 열다섯 개의 블록으로 유한하기 때문에 i-node 하나는 열다섯 개의 블록을 차지하는 파일까지 가리킬 수 있다. 그 이상의 크기를 가지고 있는 파일을 저장해야 하는 경우에는 i-node 하나만으로 파일의 데이터 블록을 가리킬 수 없다.
유닉스 파일 시스템은 이러한 문제를 다음과 같이 해결한다.
1 ) 블록 주소 중 열두 개에는 직접 블록 주소를 저장한다.
i-node가 가리킬 수 있는 열다섯 개의 블록 주소 중 처음 열두 개에는 파일 테이터가 저장된 블록 주소가 직접적으로 명시되는데, 이를 직접 블록이라고 한다. 이것만으로 파일 데이터 블록을 모두 가리킬 수 있다면 여기서 추가적인 작업이 필요하지 않다.
2 ) '첫 째' 내용으로 충분하지 않다면 열세 번째 주소에 단일 간접 블록 주소를 저장한다.
열두 개의 블록 주소로 파일의 모든 블록을 가리킬 수 없다면 열세 번째 블록 주소를 단일 간접 블록의 주소로 저장한다. 단일 간접 블록이란 파일 데이터가 저장된 블록이 아닌 파일 데이터를 저장한 블록 주소가 저장된 블록을 의미한다. 
3 ) '둘 째' 내용으로 충분하지 않다면 열네 번째 주소에 이중 간접 블록 주소를 저장한다.
열세 개의 블록 주소로 파일의 모든 블록을 가리킬 수 없다면 i-node의 열네 번째 블록 주소를 이중 간접 블록 주소로 하여 저장한다. 이중 간접 블록은 단일 간접 블록들의 주소를 저장하는 블록이라고 보면 된다.
4 ) '셋 째' 내용으로 충분하지 않다면 열다섯 번째 주소에 삼중 간접 블록 주소를 저장한다.
열네 개의 블록 주소로 파일의 모든 블록을 가리킬 수 없다면 i-node의 열다섯 번째 블록 주소를 삼중 간접 블록 주소로 하여 저장한다. 삼중 간접 블록은 이중 간접 블록들의 주소를 저장하는 블록이라고 보면 된다.
이렇게 삼중 간접 블록까지 이용하면 웬만한 크기의 파일은 모두 표현할 수 있다.
이로써 i-node만 알면 파일 속성뿐만 아니라 파일 크기가 크더라도 파일 데이터를 모두 가리킬 수 있다. 그래서 유닉스 파일 시스템의 디렉터리 엔트리에는 파일 이름과 i-node 번호로 구성된다.
좋은 글 감사합니다. 자주 방문할게요 :)