[운영체제] CH07-2. Main Memory - Contiguous Allocation, Fragmentation, Segmentation, Paging

PikminProtectionAssociation·2024년 11월 16일

CS 운영체제

행성 탈출기

목록 보기

19/21

Contiguous Allocation

메인 메모리는 OS와 여러 사용자 프로세스를 수용함
- degree of multiprogramming은 보통 메인 메모리 크기에 의해 제한을 받음
연속 메모리 할당은 초기 OS에서 사용하던 메모리 관리 기법
메인 메모리를 kernel 영역과 사용자 프로세스 영역으로 나눔
- kernel은 메인 메모리에 늘 상주하는 프로그램으로, 보통 낮은 주소 영역대에 자리 잡음
- 보통 interrupt vector(interrupt 발생 시 분기해야 하는 주소들이 담긴 공간)는 0번지부터 시작
  → kernel이 낮은 주소대에 자리 잡음으로써 interrupt vector 영역을 자연스럽게 kernel의 자료구조 일부로 포함
- 사용자 프로세스는 높은 주소 영역대를 사용
- 프로세스가 시작하면 일정 공간을 차지했다가 종료하면 사용 영역을 반납
- 각 프로세스가 메모리에 머무는 동안 하나의 연속된 공간을 사용

Contiguous Allocation (Cont.)

연속 할당에서 만약 프로세스 크기가 1MB일 경우 이를 실행시키기 위해서는 메모리에 1MB의 빈 공간이 있어야 하며, 매번 실행 시마다 빈 공간의 위치가 달라짐
→ relocation register가 필요
relocation register를 사용하면 매번 다른 빈 공간에 할당 가능하며 프로세스가 자신에게 주어진 영역 외에 허용되지 않은 영역을 접근하는 것을 방지할 수 있음
- base register : 물리주소의 가장 작은 값
- limit register : 논리주소 범위
- MMU가 논리주소를 동적으로 mapping
- relocation register를 사용하면 어떤 OS에서는 OS 크기 자체를 실행 중에 줄일 수도 있음
  - 예를 들어 OS가 지원하던 주변 장치가 향후에 더 이상 쓰이지 않게 되면 그 장치와 관련된 코드는 메모리에 있을 필요가 없음
  - transient code : kernel의 일부지만 늘 메모리에 있을 필요가 없는 코드

실행 중인 프로세스의 논리주소가 limit register보다 작은지 검사
- limit register는 보통 프로세스 크기와 동일한 값
relocation register 값에 논리주소를 더해서 물리주소를 만들어 냄
- relocation register 값은 물리주소 상에서 현재 실행 중인 프로세스가 위치하고 있는 시작 주소
limit register와 relocation register에는 현재 실행 중인 프로세스와 관련된 값들이 저장되어 있음
- 프로세스 실행이 전환될 때 register가 복원되는데, 이 과정의 일환으로 두 register의 값도 새 프로세스의 것으로 변환이 됨

Multiple-partition allocation

메모리에 load된 프로세스의 수만큼 빈 메모리를 분할해서 할당
가변 크기의 partition을 사용 (프로세스마다 크기가 다르므로 프로세스가 필요로 하는 만큼 메모리를 할당하기 위해)
Hole : 가용한 메모리로, 메모리에 다양한 크기로 흩어져 있음
새 프로세스가 메모리 할당을 요청하면 해당 프로세스를 수용할 수 있는 크기의 hole 중 하나를 할당
프로세스가 일정 영역을 차지하고 있다 종료하면 사용하고 있던 영역을 kernel에게 반환하고, 반환된 공간에 인접한 hole이 있는 경우 합쳐서 큰 hole을 유지하도록 관리
프로세스가 실행과 종료를 반복하면 여러 개의 hole들이 메모리 공간에 흩어지는 현상 발생
OS는 전체 메모리 중 프로세스에게 할당된 partition과 비어있는 hole 위치 정보를 유지해야 함

Dynamic Storage-Allocation Problem

일련의 빈 공간(hole)이 여러 개 있는 상황에서 크기가 n인 프로세스의 메모리 할당 요청이 들어왔을 때 이를 어떻게 만족시킬 것인가?
First-fit
- 요구하는 사이즈보다 큰 hole 중에서 무조건 첫 번째 hole을 할당
- 빈 공간 검색이 오래 걸리지 않는 장점이 있음
- 첫 번째 hole을 찾는 과정에서 직전에 검색한 지점 이후부터 검색을 시작할 때는 'Next-fit'이라는 용어롤 사용하기도 함
Best-fit
- 크기 n의 요청에 대해서 이를 수용할 수 있는 가장 작은 크기의 hole을 선택
- 전체 빈 공간을 다 검색해야 함
Worst-fit
- 크기 n의 요청에 대해서 이를 수용할 수 있는 가장 큰 크기의 hole을 선택
여러 측면을 고려해봤을 때 First-fit이나 Best-fit이 Worst-fit보다 나은 것으로 알려져있음

Fragmentation

dynamic storage allocation을 사용하면 단편화 현상이 발생함
External Fragmentation (외부 단편화)
- 현재 남은 hole들의 합을 따져보면 주어진 메모리 요청을 수용할 수 있는 크기이지만 hole들이 전체 메모리 공간에 흩어져 있어 요청을 만족할 수 없는 상황
Internal Fragmentation (내부 단편화)
- 메모리 요청보다 조금 큰 hole을 할당하는 과정에서 할당 이후 자투리 공간이 남는 현상
연구에 따르면 First-fit을 사용하는 경우 할당된 블럭이 n개일 때 그 중 50%는 단편화에 의해서 사용할 수 없는 상태가 됨
- 50-percent rule : 전체 메모리의 1/3은 쓸 수 없는 상황이 되는 것
단편화는 메모리 할당 뿐만 아니라 디스크 공간 할당에서도 발생함
- 저장 장치의 문제가 아닌 저장 단위(할당 단위)의 문제
- 할당 단위가 가변 크기인 경우 어느 저장 장치에서나 단편화 문제가 발생
Compaction
- 사용 중인 메모리 블럭을 어느 한 시점에 한쪽으로 다 몰아서 반대편에 커다란 빈 공간을 만드는 기법
- 외부 단편화는 compaction을 통해 해소 가능
- 시스템이 동작 중에 프로세스들이 차지하는 공간을 이동하는 셈이므로, relocation이 동적으로 이뤄져야 함
  → runtime binding 시스템만이 compaction 수행 가능
- 입출력을 하고 있는 프로세스는 주의해야 함
  - 모든 입출력에는 buffer가 필요한데, 입출력 도중이라면 buffer의 메모리 주소를 해당 입출력 장치에게 이미 알려준 상황일 가능성이 많으므로 compaction이 이루어지면 문제가 생김
  - 입출력 중인 프로세스는 compaction 대상에 포함시키지 않거나 입출력 시 buffer를 OS 내에서만 갖게 하는 방법

Segmentation

사용자가 보는 메모리 관점에서 메인 메모리를 관리하는 기법
메모리 할당 단위가 segment 단위로 이루어짐
- 보통 하나의 프로그램은 일련의 논리적인 단위인 segment로 이루어져 있다고 생각함
연속 메모리 할당과 다른 점
- 프로그램 전체를 물리주소 공간에 연속적으로 할당하는 것이 아닌 segment라는 단위로 쪼개서 segment별로 물리 메모리에 할당함
- segment도 여전히 가변 크기이므로 dynamic storage allocation과 유사한 문제 발생 가능

Segmentation Architecture

segmentation에서는 프로세스가 만들어내는 논리주소가 숫자 하나가 아닌 segment 번호와 offset의 2개의 숫자로 이루어짐
- <segment-number, offset>
- 프로그램 내에서 특정 위치를 지정하기 위해서는 내가 지정하고자 하는 곳이 속한 segment가 몇 번인지 확인
- segment가 특정이 되면 시작점으로부터 가르키고자 하는 곳이 떨어진 거리를 offset으로 표현
Segment table
- 각 프로세스 segment마다 segment table이라는 자료구조가 필요
- 각 segment별로 해당 segment의 물리주소 상에서의 시작 주소(base)와 segment 크기(limit)에 대한 정보를 모아놓음
segmentation을 하려면 CPU 내의 MMU가 segmentation을 지원해야 함
Segment-table base register (STBR)
- 현재 실행 중인 프로세스의 물리 메모리 상의 segment table 위치를 가리킴
Segment-table length register (STLR)
- 현재 실행 중인 프로세스의 segment 개수
Protection
- segment 단위로 protection이 이루어지며, segment마다 protection bit가 있음
- valid bit : 이 프로세스에게 속한 segment이면 1, 그렇지 않으면 0
- read/write/execute : segment별로 접근 권한 표시 가능

Segmentation Hardware

logical address
- 논리주소가 32bit 크기의 숫자라고 가정할 때, 앞부분 12bit는 segment 번호이고 나머지 20bit는 offset
- segment 1개의 크기는 최대 1MB(2^20)로 최대 2^12개까지 가능
segment 번호를 가지고 segment table을 검색하여 entry를 찾음
segment의 limit 값과 offset 크기를 비교한 뒤, 시작 주소 base를 더해서 최종 물리주소를 만들어냄
- d > limit 이면 논리주소가 valid 하지 않으므로 trap 발생 (segment 크기를 초과하는 메모리 접근 시도)
CPU 명령이 1개 실행될 때마다 메모리 접근 횟수
- 명령을 메모리로부터 가져오는 동작이 있으므로 최소 1번
- 가져온 명령이 해야 하는 동작 중에는 CPU 내에서만 이루어지는 간단한 명령도 있지만 명령 실행 도중 메모리를 1번 더 접근할 수도 있음
  - 예를 들어 더해야 하는 숫자가 메모리에 있는 경우
  - 최소 1번이나 2번의 메모리 접근이 필요
- 그림에 의한 주소 변환은 명령 하나마다 최소 명령을 가져올 때 1번 이루어지고, 명령이 실행되는 과정에서 추가 주소 변환이 있을 수 있음

Paging

전체 물리 메모리를 고정된 크기의 frame으로 나눠서 물리 메모리를 frame 단위로 할당하는 메모리 관리 기법
- 2의 거듭제곱 크기로 나눔
- 보통 최소 512byte에서 16MB까지
page : 프로세스의 논리주소 공간 또한 frame과 동일한 크기로 나누는데, 이 조각 하나를 page라고 부름
kernel은 늘 어느 frame이 사용 중인지 관리해야 함
n개의 page를 메모리에 load한 결과, 프로세스는 물리 메모리 상에서 n개의 조각이 비연속적으로 위치할 수 있음
- 메모리 할당 단위가 미리 정해진 page 크기에 따라서 고정된 크기를 최소 단위로 하므로 외부 단편화 현상이 없어짐
page table
- 한 프로세스를 구성하는 page가 어느 frame에 load 되어 있는지를 기록
- 프로세스가 실행하는 동안 프로세스의 논리주소를 물리주소로 변환할 때도 사용
프로세스는 디스크에 머물 때도 page 단위로 저장
내부 단편화는 여전히 남아 있음
- page 크기가 1KB이고 프로그램 크기가 10KB+1B일 때 전체 11개의 page가 나오게 됨
- 마지막 page는 실제로 1byte만 사용되므로 나머지는 낭비되는 내부 단편화 발생

Paging Model of Logical and Physical Memory

page table은 프로세스마다 1개씩 존재하며, 어느 page가 어느 frame에 load 되어 있는지 기록

Address Translation Scheme

논리주소가 m비트
- page 크기는 2의 거듭제곱 형태이므로 page 크기는 2^n
- 예를 들어 4KB(2^12) 크기의 page를 사용하면 n의 값은 12
Page number (p)
- 전체 m비트 중 윗부분 m-n비트의 값은 현재 보고 있는 논리주소가 page p번에 해당함을 의미
- 이 주소를 변환하려면 page table에서 p번째 entry를 참조해서 해당 page의 물리주소 상 위치를 알아내야 함
Page offset (d)
- 아랫부분 n개의 비트 값 d는 주어진 논리주소가 p번 page에서 d번째 byte에 해당함을 의미
보통 논리주소 자릿수가 m비트이면 프로세스가 가질 수 있는 논리주소 공간은 2^m byte이고 page 크기는 2^n