유성이의 공부일지(14) - 혼자공부하는 컴퓨터 구조 + 운영체제 14장
14-1. 연속 메모리 할당
스와핑
- 메모리에 적재된 프로세스들 중에서는 현재 실행되지 않는 프로세스가 있을 수 있음
- 스와핑은 프로세서들을 임시로 보조기억장치 일부 영역으로 쫓아내고 메모리 상의 빈 공간에 또 다른 프로세스를 넣어 실행하는 방식
- 스왑 영역은 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
- 스왑 아웃은 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
- 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것을 스왑 인이라고 함
- 스왑 아웃 되었던 프로세스가 다시 스왑 인될 때는 스왑 아웃되기 전의 물리 주소와는 다른 주소에 적재될 수 있음
- 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스 동시 실행 가능o
메모리 할당
- 20MB 크기의 프로세스를 적재하고 싶다고 가정
- 메모리의 사용자 영역을 총 200MB 라고 했을때, 프로세스를 적재 할 수 있는 빈 공간은 빈 공간A, 빈 공간B, 빈 공간C
최초 적합
- 최초 적합은 운영체제가 메모리의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
- 즉 운영체제가 빈 공간A -> 빈 공간B -> 빈 공간C 순으로 빈 공간을 검색했다면 프로세스는 빈 공간 A에 적재
- 최초 적합은 프로세스가 적재될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식 -> 검색 최소화, 빠른 할당 가능o
최적 적합
- 최적 적합은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식
- 앞선 예시에서 프로세스가 적재될 수 있는 빈 공간 중 가장 작은 공간은 빈공간 C
- 최적 적합 방식으로 메모리를 할당하면 프로세스는 빈공간 C에 할당
최악 적합
- 최악 적합은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식
- 예시로 프로세스가 적재될 수 있는 빈 공간 중 가장 큰 공간은 빈 공간 B
- 최악 접합 방식으로 메모리를 할당하면 프로세스는 빈 공간 B에 할당됨
외부 단편화
- 사용자 영역의 크기가 200MB 라고 가정
-> 크기가 50MB인 프로세스 A, 크기가 30MB인 프로세스 B, 크기가 100MB인 프로세스 C, 크기가 20MB인 프로세스 D
- 현재 메모리에 남아 있는 빈 공간의 총합? -> 50MB
- 위와 같은 그림의 상황에서 50MB 크기의 프로세스를 적재할 수 있는가?
-> 불가능하다 | 빈 공간이 50MB 정도 되어도 프로세스가 적재를 못함 x
- 프로세스들이 메모리에 연속적으로 할당되는 환경에서는 우와 같이 프로세스들이 실행되고 종료되길 반복함
- 메모리 사이사이에 빈 공간이 생김
- 프로세스 바깥에 생기는 이러한 빈 공간이지만 그 큰 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래 -> 메모리 낭미
-> 이러한 현상을 외부 단편화 라고 함
- 외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리를 압축하는 방법이 있음
- 여기저기 흩어져 있는 빈 공간을 하나로 모으는 방식
- 메모리 내에 저장된 프로세스를 적당히 재배치시켜 여기저기 흩어져 있는 작은 빈 공간들을 하나의 큰 빈공간으로 만듬
- 단점으로는 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중재시켜야 함
- 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기시킴
- 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어려움...
14-2. 페이징을 통한 가상 메모리 관리
프로세스를 메모리에 연속적으로 할당하는 방식은 두 가지 문제를 내포함
- 외부 단편화
- 물리 메모리보다 큰 프로세스를 실행할 수 없다는 점
페이징이란
- 페이징은 메모리의 물리 주소 공간을 프레임 단위로 자름
- 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당 하는 메모리 관리 기법
- 페이징에서도 스와핑 사용 가능o
- 프로세스 전체가 스왑 아웃/스왑 인이 안되는 것이 아닌 페이지 단위로 됨
- 메모리에 적재될 필요가 없는 페이지 들은 보조기억장치로 스왑 아웃
- 실행에 필요한 페이지들은 메모리로 스왑 인
- 페이징 시스템에서의 스왑 아웃 -> 페이지 아웃, 스왑 인 -> 페이지 인
- 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 x
- 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재
- 당장에 필요하지 않는 페이지들은 보조기억장치에 남겨둘 수 있음
페이지 테이블
- 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서 이를 순차적으로 실행 x
- 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU가 모두 알고 있기란 어려움
해결하기 위해!!
- 페이징 시스템은 프로세스가 비록 물리 주소에 불연속적으로 배치됨
- 논리 주소에는 연속적으로 배치되도록 페이지 테이블을 이용함
- 페이지 테이블은 페이지 번호와 프레임 번호를 찍어주는 일종의 이정표
- CPU로 하여금 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있게 함
- 물리 주소상에서는 프로세스들이 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리주소는 연속적으로 보임
- 즉 프로세서들이 메모리에 분산되어 저장되어 있더라도 CPU는 논리 주소를 순차적으로 실행하면 됨
페이지 테이블 베이스 레지스터(PTBR)
- 프로세스마다 각자의 프로세스 테이블을 가지고 있고 각 프로세스의 페이지 테이블들은 메모리에 적재되어 있음
- PTBR은 각 프로세스의 페이지 테이블이 적재된 주소를 가리킴
- 프로세스 A가 실행될때 PTBR은 프로세스 A의 페이지 테이블을 가리킴
- CPU는 프로세스 A의 페이지 테이블을 통해 프로세스 A의 페이지가 적재된 프레임을 알 수 있음
- B도 이와 마찬가지!!
- TLB(Translation Lookaside Buffer)는 CPU 근처에 있는 페이지 테이블의 캐시 메모리
- 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장함
- TLB 히트는 CPU가 발생한 논리 주소에 대한 페이지번호에 TBL가 있을 경우 발생함
- 이 경우는 페이지에 적재된 프레임을 알기 위해서 메모리 접근 필요 x -> 메모리 접근을 한번만 하면 됨
- 하지만 페이지 번호가 TLB에 없는 경우 -> 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근 할 수 밖에 없음
-> 이를 TLB 미스라고 함
페이징에서 주소 변환
- 하나의 페이지 혹은 프레임은 여러 주소를 포괄하기에 특정 주소에 접근하려면 두 가지 정보가 필요
- 어떤 페이지 혹은 프레임에 접근하고 싶은지
- 접근하려는 페이지 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지
- 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호와 변위 이루어져 있음
- 가령 CPU가 32비트 주소를 보냈다면 이 중 N비트는 페이지 번호, 32-N 비트는 변위 이런식으로 이루어져 있음
- 페이지 번호는 말 그대로 접근하고자 하는 페이지
- 페이지 테이블에서 해당 페이지 번호를 찾으면 페이지가 어떤 프레임에 할당되었는지 알 수 있음
- 변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼마나 떨어져 있는지 알기 위한 정보
- 논리 주소 <페이지 번호, 변위>는 페이지 테이블를 통해 -> <프레임 번호, 변위>로 변환됨
- CPU가 5번 페이지, 변위 2라는 논리 주소(<5,2>)에 접근하고 싶다고 가정
- CPU가 접근하게 될 물리 주소는 어디?
-> 5번 페이지는 현재 1번 프레임에 있음
- 그렇다면 CPU는 1번 프레임, 변위 2에 접근하게 됨
- 1번 프레임은 8번지 부터 시작 -> 즉 CPU는 10번지에 접근하게 됨
페이지 테이블 엔트리
- 페이지 테이블의 각 엔트리, 페이지 테이블의 각각의 행들을 페이지 테이블 엔트리 라고 함
유효 비트
- 현재 해당 페이지에 접근 가능한지 여부를 알려줌
- 페이지 테이블 엔트리에서 프레임 번호 다음으로 중요한 정보!!
- 프로세스를 이루는 모든 페이지가 메모리에 있지 x
- 일부 페이지는 보조기억장치(스왑 영역)에 있는 경우가 많음
- 현재 페이지가 메모리에 적재되어 있는지 아니면 보조기억장치에 있는지 알려주는 비트
- 즉 페이지가 메모리에 적재되어 있다 -> 유효 비트 1
- 페이지가 메모리에 적재되어 있지 않다 -> 0
페이지 폴트
- CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하고자 하면 페이지 폴드라는 예외가 생김
- CPU가 페이지 폴드를 처리하는 과정은 다음과 같음
- CPU는 기존의 작업 내역을 백업합니다
- 페이지 폴트 처리 루틴을 실행합니다
- 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경해 줍니다
- 페이지 폴트를 처리했다면 이제 CPU는 해당 페이지에 접근할 수 있게 됨
보호 비트
- 페이지 보호 기능을 위해 존재하는 비트
- 보호 비트를 통해 해당 페이지가 읽고 쓰기가 모두 가능한 페이지인지, 혹은 읽기만 가능한 페이지인지를 나타낼 수 있음
- 가령 바트가 0 -> 이 페이지는 읽기만 가능한 페이지
- 1 -> 읽고 쓰기가 모두 가능한 페이지
- 보호 비트는 세 개의 비트로 조금 더 복잡하게 구현할 수 있음
- 읽기를 나타내는 r, 쓰기를 나타내는 w, 실행(eXecute)을 나타내는 x의 조합으로 권한의 조합을 나타낼 수 있음
- 보호 비트가 100으로 설정된 페이지의 경우 r은 1
- w와 x는 0이므로 이 페이지는 읽기만 가능
- 보호 비트가 110으로 설정됨 -> 이 페이지는 읽고 쓰기만 가능하고 실행은 불가능
- 111로 설정된 페이지는 읽기, 쓰기, 실행이 모두 가능
참조 비트
- CPU가 이 페이지에 접근한 적 있는지 여부를 나타냄
- 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1, 한 번도 읽거나 쓴적이 없으면 0
수정 비트
- 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려줌, 더티 비트라고도 부름
- 이 비트가 1이면 변경된 적이 있는 페이지, 0이면 변경된 적이 없는 페이지임
수정 비트가 존재하는 이유?
- 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지 판단하지 위해 존재
- CPU는 메모리를 읽기도 하지만 쓰기도 함
- CPU가 한 번도 접근하지 않았거나 읽기만 한 페이지의 경우 보조기억장치에 저장된 해당 페이지의 내용과 메모리에 저장된 페이지 내용은 서로 같은 값을 가지고 있음
- 수정된 적이 있는 페이지가 스왑 아웃일 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 함
14-3. 페이지 교체와 프레임 할당
요구 페이징
- 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하기 않고 필요한 페이지만을 적재하는 기법
- 요구 페이지의 기본적인 양상
- CPU가 특정 페이지에 접근하는 명령어를 실행한다
- 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다
- 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생한다
- 페이지 폴트 처리 루틴은 해당 페이지로 적재하고 유효 비트를 1로 설정한다
- 다시 1번을 수행한다
- 순수 요구 페이징은 프로세스의 첫 명령어를 실행하는 순간에 페이지 폴트가 계속 발생하게 되고, 실행에 필요한 페이지가 어느 정도 적재된 이후 부터는 페이지 폴트 발생 빈도가 떨어지는 것
- 요구 페이징 시스템이 안정적으로 작동하려면 필연적으로 페이지 교체와 프레임 할당을 해결해야 함
페이지 교체 알고리즘
- 페이지 폴드를 가장 적게 일으키는 알고리즘은 좋은 알고리즘으로 평가함
- 페이지 폴드가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 느려짐...
- 페이지 교체 알고리즘을 제대로 이해하려면 페이지 폴드 횟수를 알 수 있어야 함
- 페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있음
- 페이지 참조 열은 CPU가 참조하는 페이지들 중에서 연속된 페이지를 생각한 페이지 열을 의미
- 연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문
FIFO 페이지 교체 알고리즘
- 메모리에 가장 먼저 올라온 페이지 부터 내쫓는 방식 -> '오래 머물렀다면 나가라'의 의미임
- 프로그램 실행 초기에 적재된 페이지 속에는 프로그램 실행 초기에 잠깐 실행되다가 이후에 사용되지 않을 페이지도 있음
- 하지만 프로그램 실행 내내 사용될 내용을 포함하고 있을 수도 있음
최적 페이지 교체 알고리즘
- CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
- 보조기억장치로 내보내야 할 페이지는 앞으로 사용 빈도가 가장 낮은 페이지
- 앞으로의 사용 빈도가 가장 낮은 페이지를 교체 하는 알고리즘을 페이지 교체 알고리즘으로 삼는 것이 가장 합리적임
LRU 페이지 교체 알고리즘
- 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘을 구현 가능한 것
- 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체함
스래싱과 프레임 할당
- 스래싱은 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
- 메모리에서 동시에 실행되는 프로세스의 수를 멀티프로그래밍의 정도라고 함
- 멀티프로그래밍의 정도가 높다면 현재 메모리에는 많은 프로세스가 동시에 실행중
- 낮다면 현재 메모리에는 적은 프로세스가 동시에 실행 중이라고 이해하면 됨
- 균등 할당은 모든 프로세스에 동일한 프레임을 배분하는 방식
- 비례 할당은 프로세세의 크기에 따라 프레임을 배분하는 방식
프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식
- 작업 집합 모델
- 페이지 폴드 빈도
- 작업 집합은 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
- 작업 집합 모델 기반 프레임 할당은 작업 집합의 크기만큼 프레임을 할당하는 방식
- 페이지 폴트율 기반 프레임 할당은 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 안에서만 프레임을 할당하는 방식