[CS] 3-3. 운영체제 - 가상 메모리, 파일 시스템

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.

1. 가상 메모리

지난 시간까지 우리는 운영체제에서 어떻게 멀티프로세스나 멀티스레드 환경에서 통신을 관리하고, CPU 자원을 효율적으로 활용하는지에 대해서 알아봤었다. 이번에는 운영체제의 메모리 관리 기법인 가상 메모리가 무엇인지에 대해서 알아보자.

앞의 내용을 본다면 자칫 CPU가 프로세스들이 메모리 속 어디에 저장되어 있는지 이미 알고 있다고 착각할지도 모른다. 하지만 그렇게 되면, 레지스터가 메모리만큼 커야 할 텐데 거기에는 무리가 있다. 또 사용 중이지 않은 프로세스는 메모리에서 해제된다. 그렇다면 어떻게 CPU는 메모리에 적재된 프로세스의 주소를 인식하고 관리할까? 이를 설명하기 위해 물리 주소와 논리 주소에 대해 먼저 이해해 보자.

 

1-1 물리 주소와 논리 주소

CPU와 프로세스는 실제 메모리의 하드웨어상 주소인 물리 주소가 아니라 다른 주소 체계를 사용하는데, 이게 논리 주소이다. 논리 주소란 프로세스마다 부여되는 0번지부터 시작하는 주소 체계를 의미한다.

물리 주소는 실제 하드웨어의 번지수이기 때문에 중복이 없지만, 중복되는 논리 주소는 얼마든지 존재할 수 있다. 하지만 결국 논리 주소더라도 실제 하드웨어 상의 메모리에 접근하려면 물리 주소로 변환하는 작업이 필요하다. 그렇지 않으면 CPU는 논리 주소로, 메모리는 물리 주소로 이야기할 테니 소통에 문제가 생기니 말이다.

이 과정에서 필요한 것이 바로 메모리 관리 장치(MMU, Memory Management Unit)이다. MMU는 CPU와 메모리 사이에 위치하며, CPU가 이해하는 논리 주소를 메모리가 이해하는 물리 주소로 변환하는 역할을 한다. 그렇다면 이런 주소 체계와 변환 체계를 바탕으로 프로세스가 어떻게 구체적으로 메모리에 할당되는지에 대해서 알아보자.

 

1-2 스와핑과 연속 메모리 할당

가장 기본적인 메모리 할당방식은 스와핑과 연속 메모리 할당이다. 차근차근 알아보자.

(1) 스와핑

메모리에 적재된 프로세스 중에 현재 실행 중이지 않은 프로세스를 임시로 스왑 영역(swap space)이라는 보조기억장치의 일부 영역으로 쫓아내고 그리고 생겨난 빈 영역에 다른 프로세스를 적재하여 실행하는 메모리 관리 방식을 스와핑이라고 한다.

현재 실행되지 않는 프로세스를 메모리 -> 스왑 영역으로 옮겨지는 것을 스왑 아웃, 그 반대는 스왑 인이라고 한다. 스왑 아웃되어 스왑 영역에 옮겨졌던 프로세스가 다시 스왑 인이 되면, 그전에 있던 물리 주소와는 다른 주소에 적재될 수 있다.

(2) 연속 메모리 할당과 외부 단편화

프로세스에 연속적인 메모리 공간을 차례차례 할당하는 방식을 연속 메모리 할당이라고 한다.

스와핑이나 연속 메모리 할당 모두 뭔가 당연하다는 생각이 들 수 있지만, 실제로는 외부 단편화로 인해 효율적인 메모리 사용 방식일 수는 없다. 외부 단편화란 프로세스의 실행과 종료를 반복하다 보면, 메모리 사이에 빈 공간이 생기지만 그 공간이 프로세스를 적재하기에 적절하지 못해 그대로 빈 공간으로 남아 메모리 낭비로 이어지는 걸 말한다.

예를 들어 다음과 같은 그림이 있다고 가정해 보자.

위와 같이 프로세스 A와 C 사이에 C나 A 같은 프로세스를 하나 더 실행시키기에는 너무 공간이 좁아 빈 공간이 여전히 남게 되고, 이런 게 쌓이다 보면 메모리 낭비로 이어지게 된다.

 

1-3 페이징을 통한 가상 메모리 관리

앞에서 살펴본 스와핑과 연속 메모리 할당은 2가지 문제가 있다. 하나는 적재와 삭제를 반복하며 프로세스 사이에 빈 공간이 생겨난 외부 단편화이고, 또 하나는 물리 메모리보다 큰 프로세스를 실행할 수 없다는 문제이다. 만약 프로세스를 반드시 연속적으로 할당해야 한다면 4GB 메모리로는 4GB 이상의 프로그램은 실행할 수 없을 것이다.

 

위와 같은 문제를 해결하기 위해 등장한 메모리 관리 기술이 가상 메모리이다. 가상 메모리(virtual memory)란 실행하고자 하는 프로그램의 일부만 메모리에 적재해 실제 메모리보다 더 큰 프로세스를 실행할 수 있도록 만드는 메모리 관리 기법이다. 보조기억장치의 일부를 메모리처럼 사용하거나, 프로세스의 일부만 적재해 실제 크기보다 메모리르 더 크게 보이게 하는 기술이라고 할 수 있다.

대표적인 가상 메모리 기법에는 페이징과 세그멘테이션이 있는데 페이징이 좀 더 범용적으로 많이 사용되니 페이징 위주로 알아보자.

(1) 페이징

페이징(paging)은 프로세스의 논리 공간을 페이지라는 일정한 단위로 나누고 물리 주소 공간을 페이지와 동일한 크기의 프레임이라는 일정한 단위로 나눈 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.

위와 같이 메모리를 할당하게 되면, 외부 단편화가 발생할 수 없다. 빈 공간의 크기에 맞게 불연속적으로 할당할 수 있다면 빈 공간은 효율적으로 사용할 수 있다. 

 

페이징 기법에서도 스와핑이 사용될 수 있다. 다만 프로세스 전체가 메모리에서 스왑 아웃/인 되는 것이 아니라 필요에 따라서 페이지 단위로 스왑 아웃/인 된다. 페이징 기법에서의 스왑 아웃/인은 페이지 아웃/인이라고 부른다. 

다만 페이징 기법에도 문제가 있는데, 물리 메모리 내에 페이지가 불연속적으로 중구난방 배치되어 있다면, CPU가 하나를 실행하고 다른 페이지를 실행할 때 탐색 시간이 오래 걸릴 수 있다. 이를 해결하기 위해 페이지 테이블을 활용한다.

페이지 테이블은 페이지 번호와 실제 적재된 프레임 번호가 대응된 형태로 적혀있다. CPU는 프로세스마다 고유의 페이지 테이블을 확인해 다음 페이지에 더 용이하게 접근할 수 있게 된다. 또한 페이지 테이블에는 페이지, 프레임 번호 이외에도 다른 중요한 번호가 있는데, 페이지 테이블에서 각각 구성하는 행들을 페이지 엔트리라고 불리며 다음과 같은 형태를 띄운다.

페이지 번호	프레임 번호	유효 비트	수정 비트	참조 비트	보호 비트(r, w, x)

각각 간략하게 설명하면 다음과 같다.

• 페이지 번호, 프레임 번호 : 앞에서 설명했듯 각각의 페이지와 프레임 번호가 적재
• 유효 비트 : 해당 페이지에 접근 가능한 지 여부를 알려주는 비트. 페이지가 메모리에 적재되어 있으면 1, 아니면 0
  • 만약 메모리에 적재되어 있지 않은(유효 비트가 0인) 페이지에 접근하면 page fault라는 exception 발생. 
  • 처리 과정 : 기존 작업 백업 ➡ 폴트 처리 루틴 실행(페이지를 메모리에 적재 후 유효 비트 1로 변경) ➡ 페이지 실행
• 보호 비트 : 페이지 보호 기능을 위해 존재하는 비트. 각각 읽기, 쓰기, 실행을 나타냄(read, write, execute)
• 참조 비트 : CPU가 해당 페이지에 접근한 적 있는지를 나타내는 비트.
• 수정 비트 : 해당 페이지에 데이터를 쓴 적이 있는지 여부를 알려주는 비트로 dirty bit라고도 부른다.
  • 만약 수정했다면, 메모리에서 해제할 때 보조 기억장치에도 수정된 내용을 반영해야 한다.

이처럼 페이지는 페이지테이블을 통해 다양한 기능들을 제공받고 효율적으로 메모리를 관리하지만, 앞에서 설명한 문제와 다른 내부 단편화(internal fragmentation) 문제가 발생할 수 있다. 내부 단편화는 말 그대로 페이지 크기보다 작은 크기로 발생하게 되는 메모리 낭비이다. 예를 들어 페이지가 10KB인데, 프로세스가 107KB이라면, 마지막 페이지는 3KB 정도가 남는다.(10KB - 7KB) 즉 페이지 하나보다 작은 크기로 인해 발생하는 메모리 낭비 문제이다.

내부 단편화와 별개로 또 한 가지 생각해봐야 할 문제가 하나 더 있다. 어떤 프로세스를 실행하려면 결국 페이지와 프레임의 정보가 담긴 페이지 테이블이 어디에 적재되는지도 알아야 하는데, 실행하고자 하는 모든 프로세스의 페이지 테이블을 메모리에 적재하고 있을까? 

메모리에 적재된 페이지 테이블의 위치를 가리키는 레지스터를 페이지 테이블 베이스 레지스터(PTBR)이라고 한다.

 

정답은 "그럴 수도 있지만 운영체제는 지양한다"이다. 모든 페이지 테이블을 메모리에 적재하는 것은 다음과 같은 문제가 있다.

• 메모리 접근 횟수 : CPU는 최소 메모리에 2번 접근해야 한다.(페이지, 페이지 테이블) 그렇게 되면 접근 시간이 2배로 늘어나는 문제가 있는데 이를 해결하기 위해 TLB(translation Look-aside Buffer)라는 페이지 테이블의 캐시 메모리를 사용한다.
  • 참조 지역성의 원리에 근거해 자주 사용할 법한 페이지 위주로 테이블의 일부 내용을 저장한다.
  • 만약 TLB에 CPU가 접근할 페이지 정보가 있다면, TLB는 CPU에게 알려준다(TLB 히트)
  • 만약 없다면, 다시 한번 페이지 메모리에 접근할 수밖에 없다.(TLB 미스)
• 메모리 용량 : 페이지 테이블은 생각보다 크다. 따라서 모든 페이지 테이블을 메모리에 두는 것은 용량의 낭비이다. 이를 해결하기 위해 등장한 방법 중 하나가 계층적 페이징 기법이다. 이는 페이지 테이블 자체를 페이징 하는 기법으로 여러 단계의 페이지를 둔다는 점에서 다단계 페이지 테이블이라고 부르기도 한다.

페이징 시스템의 논리 주소는 페이지 번호, 변위(시작 번지로부터 얼마나 떨어져 있는지)의 형태로 이루어져 있다.

세그멘테이션은 간략하게만 알아보자.
세그멘테이션(segmentation)은 프로세스를 고정된 크기의 페이지가 아니라 가변적인 크기의 세그먼트 단위로 분할하는 방식이다. 다만 세그먼트의 크기가 일정하지 않아 외부 단편화가 발생할 수도 있다.

 

1-4 페이지 교체 알고리즘 

앞에서 페이지 전체가 모두 메모리에 적재될 필요는 없다고 1차적으로 언급했었다. 이처럼 메모리에 필요한 페이지만을 적재하는 기법을 요구 페이징(demand paging)이라고 한다. 아래와 같은 양상을 띤다.

• CPU가 페이지에 접근하는 명령어 실행 ➡ 유효 비트가 1이면 프레임에 접근 ➡ 유효 비트가 0이면 페이지 폴트 ➡ 폴트 발생 시 메모리 적재 후 유효 비트 1로 변경 ➡다시 맨 처음부터 과정을 반복

참고로 아무것도 메모리에 적재하지 않고 일단 실행부터 하는 걸 순수 요구 페이징이라고 하는데, 의도적으로 처음부터 페이지 폴트를 발생시키고, 어느 정도 적재되고 나면 빈도는 줄어들게 된다.

어쨌든 요구 페이징을 통해서 점차 적재하다 보면 메모리가 가득 차게 될 것이고, 그 상황에서 메모리에 적재된 페이지 일부를 페이지 아웃해야 한다. 이때 페이지를 선택하는 효율적인 방법을 페이지 교체 알고리즘이라고 부른다. 대표적인 것은 다음과 같다.

• FIFO 페이지 교체 알고리즘 : 가자 먼저 적재된 순부터 스왑 아웃. 잘 쓰고 있는 페이지도 스왑 아웃할 위험 있음.
• 최적 페이지 교체 알고리즘 : 사용 빈도가 가장 낮은 페이지를 교체. 다만 미래 예측이 어려워 실제 구현이 힘듦.
• LRU 페이지 교체 알고리즘 : 가장 적게 사용한 페이지를 교체. 가장 보편적으로 현재 사용되는 알고리즘들의 원형

---

2. 파일 시스템

이제 마지막으로 어떻게 운영체제가 보조기억장치를 효율적으로 관리하는지 알아보자. 파일시스템은 보조기억장치의 정보를 파일과 디렉터리의 형태로 저장하고 관리할 수 있도록 하는 운영체제 내부 프로그램이다. 한 운영체제 내에서도 여러 파일 시스템을 사용할 수 있고, 파일 시스템이 달라지면 보조기억장치의 정보를 다루는 방법도 달라지게 된다.

 

2-1 파일과 디렉터리

파일 시스템 이전에 파일 시스템을 이루는 파일과 디렉터리가 뭔지 이해해보자.

(1) 파일

파일은 크게 파일의 이름, 파일을 실행하기 위한 정보, 관련된 부가 정보로 이루어져 있다. 여기서 부가 정보는 다른 이름으로 속성(attribute) 혹은 메타데이터(metadata)로 불리는데, 파일의 형식, 위치, 크기 같은 정보들이 이에 해당한다. 파일을 수정하고 조작하는 행위는 운영체제가 담당하기 때문에 응용 프로그램이 접근할 수 없고 시스템 콜을 사용해 운영체제를 통해 조작해야 한다.

예를 들어 프로세스가 시스템 콜을 통해 10개의 파일을 할당받았다면, 현재 사용 중인 파일을 프로세스는 구분할 줄 알아야 한다. 이를 위해 프로세스는 파일 디스크럽터(file descriptor, 윈도우는 file handle) 라는 정보를 사용한다. 

 

(2) 디렉터리

파일들을 효율적으로 관리하게 사용하는데, 윈도우에서는 폴더라고 부르기도 한다. 오늘날의 디렉터리는 트리 형태의 계층적 구조를 띄고 있다.

트리 구조 디렉터리는 최상위의 루트 디렉터리와 그 하위의 서브 디렉터리의 계층적 구조로 구성되고, 우리가 일반적으로 pc에서 사용하는 경로느 디렉터리 정보를 활용해 파일 위치를 특정하는 정보를 의미한다.

사실 파일과 디렉터리를 구분하는 것처럼 설명하고 있지만, 운영체제에서는 디렉터리를 디렉터리에 속한 요소의 관련 정보가 포함된 특별한 파일 정도로 간주한다. 디렉터리의 속한 요소의 관련 정보는 테이블의 형태로 디렉터리 엔트리가 행 별로 작성되어 있다.

실제로 운영체제에서 사용하는 디렉터리 엔트리는 다음과 같은 형태로 구성되어 있다.

struct dirent {
    // 파일의 inode 번호. inode는 파일이나 디렉터리에 대한 메타데이터를 담고 있는 고유한 식별자
    ino_t d_ino;
    
    // 디렉터리 파일에서의 오프셋(위치). 이 값은 해당 디렉터리 엔트리가 디렉터리 파일 내에서 몇 번째에 위치하는지 나타냄
    off_t d_off;               
    
    // 디렉터리 엔트리의 레코드 길이. 즉, 이 `dirent` 구조체 하나의 크기를 의미
    unsigned short d_reclen;   
    
    // 파일의 타입을 나타내는 값. 파일인지 디렉터리인지, 심볼릭 링크인지 등을 구분할 수 있음.
    unsigned char d_type;      
    
    // 파일이나 디렉터리의 이름. 최대 255자의 이름을 저장할 수 있으며, 널 종료 문자열(`\0`)로 끝남.
    char d_name[256];          
};

 

 

(3) 파일 할당

대략적으로 디렉터리와 파일이 어떻게 구현되어 있는지 이해했다면, 어떻게 보조기억장치에 구체적으로 저장되는지 알아보자. 운영체제는 파일과 디렉터리를 블록(block)이라는 단위로 읽고 쓰는데, 블록은 대략 4096바이트의 크기를 지니고 있다. 파일 시스템에 따라서 블록에 파일 및 디렉터리를 저장하는 방식은 다양할 수 있지만, 대표적으로 2개만 설명하면 다음과 같다.

• 연결 할당 : 각 블록의 일부에 다음 블록의 주소를 저장해 점차 가리키는 형태로 저장.
• 색인 할당 : 파일을 이루는 모든 블록의 주소를 색인 블록이라는 블록에 담고 관리하는 방식

 

2-2 파일 시스템

파일 시스템은 정말 다양하며 운영체제 마다 여러 개의 파일 시스템을 선택해 사용할 수 있다. 어떤 파일 시스템을 사용할지는 보조기억장치를 포매팅, 즉 파일 시스템을 설정하여 어떤 방식으로 파일을 관리할지 결정하고 새로운 데이터를 쓸 준비를 하는 단계에서 결정할 수 있다.

운영체제마다 굉장히 다양한 파일 시스템을 사용하겠지만(NTFS, ReFS, EXT 시리즈, APFS 등) 가장 대표적인 리눅스에서 지원하는 파일 시스템의 경우(EXT1~4, XFS, ZFS) 아이노드라는 색인 블록을 기반으로 파일을 할당한다.

또 추가적으로 USB 메모리 저장장치가 PC에 연결하면 사용할 수 있듯, 마운트를 통해서 서로 다른 파일 시스템끼리 접근하는 것도 가능하다. 마운트란 어떤 저장장치의 파일 시스템에서 다른 저장장치의 파일 시스템으로 접근할 수 있도록 파일 시스템을 편입시키는 과정을 의미한다.

---

참고

페이징(Paging)과 페이지 테이블(Page table)