14-1 연속 메모리 할당
연속 메모리 할당: 프로세스들을 메모리에 배치할 때 연속적으로 이어서 배치하는 것
스와핑
스와핑(swapping): 메모리에 적재된 프로세스들 중 현재 실행되지 않는 프로세스들을 임시로 보조기억장치 스왑 영역으로 보내는 것
스왑 영역(swap space): 메모리에서 쫓겨나온 프로세스들이 보조기억장치에서 존재하는 곳
- 스왑 아웃(swap-out): 메모리 → 스왑 영역
- 스왑 인(swap-in): 스왑 영역 → 메모리
메모리 할당
메모리 내 빈 공간이 여러 개일 경우 프로세스를 배치하는 방식
최초 적합
- 최초 적합(first fit): 운영체제가 메모리 내 빈 공간을 검색하다가 발견하면 곧바로 저장
- 최소한의 검색으로 빠르게 할당
최적 적합
- 최적 적합(best fit): 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간
- 장점: 공간의 효율적 사용
- 단점: 남는 공간이 다른 프로세스가 사용하기 힘든 아주 작은 공간이라 외부 단편화가 발생하게 됨
최악 적합
- 최악 적합(worst fit): 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간
- 장점: 가장 큰 빈 공간을 골라 프로세스를 배치하기 때문에, 할당하고 남은 공간도 꽤 커서 다음에 들어올 다른 프로세스가 이 남은 공간을 다시 활용할 확률이 비교적 높음
외부 단편화
- 외부 단편화(external fragmentation): 메모리의 빈 공간에 프로세스가 할당되면서 생기는 메모리 사이 사이에 빈 공간
- 빈 공간의 총합은 크지만, 사이사이에 작게 쪼개져있어 더 이상 프로세스를 적재하기 어려워진 상황
- 압축(compaction)
- 흩어져있는 빈 공간들을 재배치를 통해 하나의 큰 공간으로 만드는 작업
- 재배치로 인해 작업의 중지, 무엇을 어디로 옮길지에 대한 판단으로 인한 어려움
14-2 페이징을 통한 가상 메모리
가상 메모리(virtual memory)
- 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
- 페이징, 세그멘테이션
페이징이란
페이징(paging)
- 프로세스의 논리 주소 공간을 **페이지(page)**라는 일정한 단위로 자름
- 메모리 물리 주소 공간을 **프레임(frame)**이라는 페이지와 동일한 크기의 일정한 단위로 자름
- 페이지를 프레임에 할당
페이지 아웃(page out): 메모리에 적재될 필요가 없는 페이지들을 보조기억장치로 스왑 아웃
페이지 인(page in): 실행에 필요한 페이지들을 메모리로 스왑 인
페이지 테이블
- 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서 이를 순차적으로 실행하기 힘듬
- 페이지 테이블(page table)
- 현재 어떤 페이지가 어떤 프레임에 할당되어있는지를 알려주는 테이블
- 페이지 번호와 프레임 번호 등이 담겨있음
- 프로세스의 어떤 페이지가 메모리 내 어떤 프레임에 들어가 있다는 뜻
- CPU는 페이지 테이블을 통해 프로세스의 물리 주소가 불연속적이더라도 CPU가 바라보는 주소인 논리 주소는 연속적으로 배치되도록 함
- 각 프로세스의 페이지 테이블 정보는 PCB에 기록됨
- CPU는 메모리에 2번 접근해야함
- 메모리의 페이지 테이블에서 필요한 페이지의 주소를 알아냄
- 1에서 알아낸 주소를 이용해 메모리 내 페이지에 접근
내부 단편화
- 내부 단편화(internal fragmentation): 페이지 내부에 남은 크기로 인해 발생하는 메모리 낭비
- 프로세스의 크기는 모두 달라 특정 페이지에는 공간이 조금 남을 수 있음
- 1 페이지가 10K일 때, 프로세스가 108KB라면?
- 페이지 크기가 작아지면 내부 단편화 크기도 작아지지만, 반대로 페이지 테이블이 커지는 문제가 있음
- 이에 대한 조절이 중요
- 대형 페이지(huge page): 기본적으로 허용된 페이지 크기보다 큰 페이지로 메모리에 유지되는 것
- 페이지 테이블 베이스 레지스터(PTBR, Page Table Base Register)
- CPU 내에 있는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키는 곳
- 현재 실행중인 프로세스의 페이지 테이블의 주소를 가리킴
- TLB(Translation Lookaside Buffer)
- CPU 옆에 있는 페이지 테이블의 캐시 메모리
- 최근에 사용된 페이지 테이블의 일부 내용 저장
- TLB에 원하는 페이지의 주소가 있을 경우 메모리에 1회만 접근하게 됨
- TLB Hit: CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있는 경우
- TLB Miss: 페이지 번호가 TLB에 없는 경우
- 이때는 메모리 내의 페이지 테이블에 접근
페이징에서의 주소 변환
페이징 시스템 내의 모든 논리 주소는 2가지로 이루어짐
- 페이지 번호(page number): 접근하려는 페이지 or 프레임
- 변위(offset): 접근하려는 주소가 그 페이지 or 프레임 내에서 어느 위치인지
- 5, 2: 5번 페이지에서 2번째 위치
- 5번 페이지가 15~25 위치를 가진다면 16을 의미하게 됨
페이지 테이블 엔트리
페이지 테이블 엔트리(PTE, Page Table Entry)
- 페이지 테이블의 각각의 행들
- 페이지 번호, 프레임 번호 외 유효 비트와 보호 비트 등이 있음
- 유효 비트(valid bit)
- 해당 페이지에 접근 가능한지 여부
- 페이징도 스와핑으로 인해 항상 메모리에 있진 않음
- 메모리에 있다면 1, 없다면 0
- 페이지 폴트(page fault): 유효 비트가 0인 페이지에 접근시 발생하는 예외(Exception)
- 발생시 처리 과정
- CPU가 기존 작업 내역을 백업
- 페이지 폴트 처리 루틴 실행
- 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경
- CPU가 다시 해당 페이지에 접근
- 발생시 처리 과정
- 보호 비트(protection bit)
- 해당 페이지가 읽고 쓰기가 모두 가능한지
- 프로세스를 이루는 요소 중 코드 영역은 읽기 전용
- 운영체제가 읽기 전용 영역에 쓰기가 시도되는 것을 막아줌
- 단순 0,1이 아닌 r, w, x를 관리하여 읽기/쓰기/실행 의 가능 여부를 관리하기도 함
- 참조 비트(reference bit)
- CPU가 이 페이지에 접근한 적이 있는지 여부
- 적재 이후 접근한 적이 있으면 1
- 수정 비트(modified bit)
- 해당 페이지에 데이터를 쓴 적이 있다면 1
- 수정된 적이 없는 페이지는 페이지 아웃할 때 보조기억장치에 쓰기 작업을 할 필요가 없음
- 이미 있던 것과 동일
- 페이징 인 이후에도 보조기억장치(스왑 영역)에 있는 페이지는 그대로 남아있다.
페이징의 이점 - 쓰기 시 복사
- 일반적으로 프로세스 두 개가 복제되면 코드 및 데이터 영역을 비롯한 모든 자원이 복제되어 메모리에 적재됨
- 기본적으로 프로세스 간에는 자원을 공유하지 않으므로
- 복제시 자식 프로세스가 부모 프로세스와 동일한 페이지 테이블을 통해 동일한 프레임을 가리키면 절약 가능
- 쓰기 시 복사: 부모 혹은 자식 프로세스 중 페이지에 쓰기 작업이 발생하면 그때 별도의 고유한 페이지가 프레임에 할당됨
계층적 페이징
계층적 페이징(hierarchical paging)
- 다단계 페이지 테이블(multilevel page table) 기법
- 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식
- 전체 페이지 테이블을 메모리에 항상 두는 비효율을 방지
- 바깥쪽에 하나의 페이지 테이블을 하나 더 두어 잘린 페이지 테이블의 페이지들을 가리킴
- 외부 페이지 테이블 → 페이지 테이블 → 해당 페이지 의 순서로 CPU가 찾아감
- 외부 페이지 테이블은 항상 메모리에 유지
- 계층적 페이징을 사용하지 않는 논리주소: 페이지 번호 + 변위
- 계층적 페이징을 사용하는 환경의 논리주소: 바깥 페이지 번호 + 안 페이이지 번호 + 변위
- 2개 이상의 계층이 존재할 수 있으나 너무 많으면 페이지 폴트 발생시 메모리 참조 횟수가 증가함
14-3 페이지 교체와 프레임 할당
요구 페이징
요구 페이징(demand paging)
- 프로세스를 메모리에 적재할 때 필요한 페이지만을 메모리에 적재
- 페이지 교체와 프레임 할당이 중요
순수 요구 페이징(pure demand paging)
- 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행.
- 페이지 폴트가 바로 발생하나, 점차 실행에 필요한 페이지가 적재되며 페이지 폴트 발생 빈도가 떨어짐
페이지 교체 알고리즘
- 메모리에 적재된 페이지 중 누구를 보조기억장치로 스왑 아웃 할지 결정하는 알고리즘
- 일반적으로 페이지 폴트를 가장 적게 발생시키는 알고리즘이 좋은 알고리즘
- 페이지 참조열(page reference string)
- CPU가 참조하는 페이지들 중 연속된 페이지를 생략하는 페이지열
- ex) 2 2 2 3 5 5 5 3 3 7 순서로 접근하다면 2 3 5 3 7 이 페이지 참조열
- 중복된 페이지를 참조할 땐 페이지 폴트가 발생하지 않기 때문
- 페이지 참조열을 통해 페이지 폴트 횟수를 알 수 있음
FIFO 페이지 교체 알고리즘
- FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacement Algorithm)
- 가장 먼저 올라온 페이지부터 스왑아웃
- 어떤 페이지는 실행 내내 사용될 수도 있으므로 최선은 아님
2차 기회 페이지 교체 알고리즘
- 2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm)
- 가장 오래된 페이지의 참조 비트가 1이라면 0으로 변경
- 가장 오래된 페이지의 참조 비트가 0이라면 스왑아웃
최적 페이지 교체 알고리즘
- 최적 페이지 교체 알고리즘(optimal page replacement algorithm)
- 앞으로 가장 오랫동안 사용하지 않을 페이지를 스왑아웃
- 이론적으로는 가장 적은 페이지 폴트 발생
- 하지만 프로세스가 앞으로 메모리 어느 부분을 어떻게 참조할지 모르므로 현실적으로 불가능
- 페이지 교체 알고리즘의 평가용으로 사용
LRU 페이지 교체 알고리즘
- LRU 페이지 교체 알고리즘(LRU, Least Recently Used Page Replacement Algorithm)
- 가장 오랫동안 사용하지 않은 페이지를 스왑아웃
스래싱과 프레임 할당
- 스래싱(thrashing)
- 메모리에 프레임이 부족하여 실제 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요
- 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아짐
- 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않아 발생
- 멀티프로그래밍의 정도(degree of multiprogramming)
- 메모리에서 동시 실행되는 프로세스의 수
- 어느정도 증가하면 CPU 이용률이 높아진다.
- 지나치면 스래싱으로 인해 오히려 CPU 이용률이 낮아짐
- 프레임 할당 방식
프로세스들에 프레임을 할당 하는 방식
정적 할당 방식
- 균등 할당(equal allocation)
- 모든 프로세스에 동일한 프레임 개수를 할당
- 프로세스들의 크기는 모두 제각각이므로 비효율
- 비례 할당(proportional allocation)
- 프로세스의 크기에 따라 할당
- 프로세스의 크기와 실행시 필요한 프레임의 수가 항상 비례하진 않음
- 균등 할당(equal allocation)
동적 할당 방식
- 작업 집합 모델(working set model) 사용 방식
- 작업 집합(working set): 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
- 작업집합의 크기만큼 메모리를 할당
- CPU는 메모리를 참조할 때 참조 지역성의 원리에 의거해 주로 비슷한 구역을 집중적으로 참조
참조 지역성의 원리
- 캐시 메모리가 메모리로부터 가져올 데이터를 결정하는 원칙
- CPU는 최근에 접근했던 메모리 공간에 다시 접근하려는 경향이 있다.
- CPU는 접근한 메모리 공간 근처를 접근하려는 경향이 있다.
- 페이지 폴트 빈도(PFF, Page-Fault Frequency) 사용 방식
- 페이지 폴트율이 너무 높으면 그 프로세스는 프레임이 부족한 것
- 페이지 폴트율이 너무 낮으면 그 프로세스는 프레임이 남는 것
- 상한선과 하한선을 기준으로 프로세스에 프레임을 할당하거나 회수하는 것
- 작업 집합 모델(working set model) 사용 방식
댓글