[운영체제] 메모리관리

목표

• 논리 주소와 물리 주소의 차이점과 주소를 변환할 때 MMU의 역할을 설명한다
• 메모리를 연속적으로 할당하기 위해 최초, 최적, 및 최악 집합 전략을 적용한다
• 내부 및 외부 단편화의 차이점을 설명한다
• TLB가 포함된 페이징 시스템에서 논리 주소를 물리 주소로 변환시킨다
• 계층적 페이징, 해시 페이징 및 역 페이지 테이블을 설명한다

배경

기본 하드웨어

• 프로그램은 실행되기 위해 디스크로부터 메모리에 프로세스로 저장되어야 한다.
• 메인 메모리와 레지스터들은 CPU가 접근할 수 있는 유일한 저장장치
• 실행되는 모든 명령어는 메모리와 레지스터 안에 있어야 함
• CPU 코어에 내장된 레지스터들은 일반적으로 CPU 클록의 1사이클 내에 접근이 가능
• 메인 메모리에 접근하기 위해서는 많은 CPU 클록 틱 사이클이 소요
• 캐시는 메인 메모리와 CPU 레지스터 사이에 빠른 속도의 메모리를 의미
• 명령을 올바르게 수행하기 위해서는 메모리가 보호 되어야 함
• 각각의 프로세스가 독립된 메모리 공간을 가지도록 보장
• 기준 레지스터와 상한 레지스터를 통해 프로세스 별 주어진 영역의 크기를 지정
• 새롭게 만들어지는 프로세스가 기존 프로세스의 메모리 공간에 접근하면 운영체제는 트랩을 발생

주소의 할당

• 프로그램은 이진 실행 파일 형태로 디스크에 저장
• 이를 실행하기 위해서는 프로그램을 메모리로 가져와서 프로세스 문맥에 배치해야 함
• 프로세스가 실행되면 메모리에서 명령 및 데이터에 접근함
• 프로세스가 종료되면 다른 프로세스를 위해 메모리가 회수
• 운영체제가 프로세스를 물리 메모리에 적재하는 방법은 다음과 같다
• 원시 프로그램에서 주소는 심볼 형태로 표현
• 컴파일러는 심볼 주소를 재배치 가능 주소로 바인딩(첫 번째 바인트부터 열네 번째 바이트 주소)
• 링커와 로더는 재배치 가능 주소를 절대 주소( 74014번지 )로 바인딩
• 명령어와 데이터 바인딩은 다음으로 구분
• 컴파일 시간 바인딩 : 컴파일러가 절대 코드를 생성, 시작 주소가 변경되면 다시 컴파일 해야 함
• 적재 시간 바인딩 : 컴파일러는 이진 코드를 재배치 가능 코드로 만든 후 프로그램이 메모리에 적재될 때 바인딩, 시작 주소가 변경되면 사용자 코드를 다시 적재하면 됨
• 실행 시간 바인딩 : 프로세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세크먼트로 옮겨질 수있음, 특별한 하드웨어가 필요

논리 주소 대 물리 주소

• 논리 주소 : CPU가 생성하는 주소
• 물리 주소 : 메모리가 취급하는 주소( 메모리 주소 레지스터(MAR)에 주어지는 주소 )
• 컴파일 또는 적재 시에 주소를 바인딩하면 논리 주소와 물리 주소가 같음
• 실행 시간 바인딩 기법에서는 논리, 물리 주소가 다르며 논리 주소를 가상 주소라 함
• 가상 주소를 물리 주소로 바꾸기 위해 하드웨어 장치인 메모리 관리 장치(MMU)를 사용
• MMU 안에 들어 있는 재배치 레지스터에 있는 값이 모든 논리 주소에 더해져 물리 주소로 변환
• 사용자 프로그램은 논리 주소를 다루며 물리 주소를 모른다

동적 적재

• 각 루틴은 호출 되기 전까지 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에 대기
• 루틴이 다른 루틴을 호출하면 호출된 루틴이 메모리에 적재됐는지를 조사한 후 적재되어 있지 않으면 재배치 가능 연결 적재기를 불러 요구된 루틴을 메모리로 가져오고 이를 테이블에 기록
• 동적 적재의 장점은 루틴이 필요한 경우에만 적재 되는 것

연속 메모리 할당

• 메모리는 운영체제를 위한 것과 사용자 프로세스를 위한 것으로 나뉨
• 연속 메모리 할당은 각 프로세스가 다음 프로세스가 적재된 영역과 인접한 하나의 메모리 영역에 적재
• 프로세스가 자신이 소유하지 않은 메모리를 접근 할 수 없도록 메모리 보호 문제를 고려
• 재배치 레지스터는 가장 작은 물리 주소 값을 저장하고 상한 레지스터는 논리 주소의 범위 값을 지정

메모리 할당

• 프로세스를 메모리의 가변 크기 파티션에 할당
• 파티션에는 하나의 프로세스만 적재 가능
• 가변 파티션 기법에서는 운영체제는 사용 가능한 메모리 부분과 사용 중인 부분을 나타내는 테이블 유지
• Hole : 사용가능 메모리 블록
• Hole은 다양한 크기로 메모리에 여기저기 퍼져있음
• 프로세스가 도착하면 메모리를 할당할 수 있는 홀에서 적절한 것을 찾아 할당하고 나머지는 Hole 집합으로 돌아감
• 여러가지 Hole에서 어떤 블록을 할당할 것인가는 다음과 같은 3가지 기법이 존재
• 최초 적합 : 첫번째 사용 가능한 공간을 할당
• 최적 집합 : 사용 가능한 공간 중 가장 작은 것을 선택, 전 리스트를 검색해야하며 적은 가용 공간을 만듬
• 최악 적합 : 가장 큰 가용 공간을 택함, 전 리스트를 검색해야 하며 많은 가용 공간을 남김
• 최초 적합과 최적 적합이 시간과 메모리 이용 효율 측면에서 더 좋음
• 최초 적합이 일반적으로 속도가 더 빠름

단편화

• 프로세스들이 메모리에 적재되고 제거되는 일이 반복되면 가용 공간이 너무 작은 공간이 됨
• 외부 단편화 : 메모리가 너무 많은 수의 매우 작은 조각들로 단편화 되어 있어 실제로 메모리 안에 공간이 충분하더라도 단편화되어 있어 새로운 프로세스를 할당 못하는 경우
• 50%의 규칙 : 통계적으로 N개의 블록이 할당되면 0.5N개의 블록이 단편화 때문에 손실 됨
• 내부 단편화 : 할당된 메모리가 요구되는 메모리보다 더 많은 경우 발생하며 할당된 크기와 요구된 크기 사이의 남는 부분을 뜻 함
  

• 외부 단편화의 문제점을 해결하기 위해 압축 기법 사용 가능
• 메모리 모든 내용을 한군데로 몰고 모든 가용 공간을 다른 한군데로 몰아 큰 블록을 만드는 것
• 프로세스들의 재배치가 실행 시간에 동적으로 이뤄지는 경우에만 가능

페이징

기본 방법

• 페이징은 메모리의 물리 주소 공간이 연속되지 않아도 됨
• 물리 메모리는 프레임이라 불리는 같은 크기 블록으로 나뉨
• 논리 메모리는 페이지라 불리는 같은 크기의 블록으로 나뉨
• n 페이지의 사이즈를 지닌 프로그램을 실행시키기 위해 n개의 가용 가능한 프레임이 필요
• 페이지 테이블을 통해 논리 주소와 물리 주소를 매핑
• 내부 단편화는 발생하나 외부 단편화가 발생하지 않음

• 논리 주소는 페이지 번호(p)와 오프셋(d)로 나뉨

• 페이지 번호는 페이지 테이블을 액세스할 때 사용

• 오프셋은 참조되는 프레임 안에서의 위치

• 페이지 번호를 p를 추출해 페이지 테이블 인덱스로 사용

• 페이지 테이블에서 해당 프레임 번호 f를 추출하여 논리 주소의 페이지 번호 p를 f로 변환

• 프레임 번화 f 와 오프셋 d를 합쳐 물리 주소를 구성
  

• 논리 주소 공간의 크기가 2^m이고 페이지 크기가 2^n일 때 논리 주소의 상위 m-n 비트는 페이지 번호를 지정하고 n 하위 비트는 페이지 오프셋을 지정

• n = 2, m = 4일 때논리 주소 3(0011)은 페이지 번호 (0) 오프셋 (3) 을 가리킴

• 따라서 실제 주소 23 ((5x4) + 3) 으로 변환

하드웨어 지원

• 페이지 테이블은 메인 메모리에 유지된다
• PTBT(Page-table base regiseter)은 페이지 테이블을 가리킨다
• PTLR(Page-table length register)은 페이지 테이블의 크기를 가리킨다
• 메인 메모리에 페이지 테이블을 저장하면 문맥 교환 속도가 빨라지지만 메모리에 두번 접근해야 하기 때문에 메모리 접근 속도가 느려짐
• TLB(Translation Look-aside Buffer) : 특수한 소형 하드웨어 캐시로 키(페이지 번호)와 값(프레임 번호)를 저장
• TLB 검색은 명령어 파이프라인의 일부로 동작하여 성능을 향상 시킴
• TLB는 각 항목에 ASIDs(address-space identifiers)를 저장시켜 각 TLB 항목이 어느 프로세스에 속한 것인지 알려줌
• TLB에서 가상 주소를 변환할 때 현재 수행 중인 프로세스의 ASID가 TLB 항목에 있는 ASID와 일치하는지 검사
• ASID 지원이 없으면 새로운 페이지 테이블이 선택될 때마다 TLB를 전부 플러시 시켜야 함

• 적중률 : 접근하려는 메모리 페이지 번호가 TLB에서 발견되는 비율
• 실질 메모리 접근 시간을 계산하기 위해 적중률에 따른 가중치를 적용
• 메모리 접근 시간이 10ns이고 적중률이 80%이면 실질 접근 시간은 12ns(0.8 x 10 + 0.2 x 20) 이다

보호

• 페이징 환경에서 메모리 보호는 각 페이지에 붙어 있는 보호 비트에 의해 구현
• 각 비트는 페이지가 읽고 쓰기 또는 읽기 전용인지를 정의
• 주소 변환을 할 때 해당 페이지가 쓰기 가능한 페이지인지 검사하고 읽기 전용 페이지에 쓰기를 시도하면 트랩 발생
• 페이지 테이블의 각 엔트리에는 유효/무효 비트가 존재
• 무효 비트는 해당 페이지가 프로세스의 논리 주소에 공간에 속하지 않는다는 것을 나타냄

공유 페이지

• 페이지의 장점은 공통의 코드를 공유할 수 있는 점
• 물리 메모리에 하나의 프레임을 저장하고 각 사용자 프로세스의 페이지 테이블은 동일한 물리적 프레임으로 매핑

페이지 테이블의 구조

계층적 페이징

• 2단계 페이징 기법을 사용해 페이지 자체가 다시 페이지 되도록 설정

• 32비트의 논리 주소를 20 비트의 페이지 주소와 12 비트의 페이지 오프셋으로 분할
• 20 비트의 페이지 주소를 10 페이지씩 나누어 첫번째 페이지 넘버와 두번째 페이지 넘버를 나타냄

• 64비트 구조에서는 각 논리 주소를 사상하기 위해 너무 많은 메모리 접근이 필요하기 때문에 부적합

해시 페이지 테이블

• 32비트보다 큰 가상 주소를 사용하면 해시 페이지 테이블을 사용
• 가상 페이지 번호는 해시되어 페이지 테이블에 저장
• 해시 페이지 테이블의 각 항목은 연결리스트를 가지고 있음
• 각 항목은 가상 페이지 번호, 사상되는 페이지 프레임 번호, 연결리스트의 다음 포인터를 지님
• 가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱해 해당 인덱스에 있는 연결리스트의 첫번째 원소부터 페이지 번호를 비교하여 대응되는 물리 주소를 얻음

역 페이지 테이블 - Inverted Page Table

• 프로세스는 각자 하나씩 페이지 테이블을 지니고 페이지 테이블은 프로세스가 해당하는 가상주소마다 테이블의 한 슬롯을 지닌다
• 이 때문에 페이지 테이블의 크기가 너무 커진다는 단점이 발생
• 메모리 프레임 마다 하나의 페이지 테이블 항목을 할당하여 프로세스 증가와 관계없이 크기가 고정된 페이지 테이블에 프로세스를 맵핑하여 할당하는 메모리 관리 기법
• 시스템에 하나의 페이지 테이블만 존재, 테이블 내 항목은 메모리 한 프레임씩 맵핑
• 각 항목은 그프레임에 올라와 있는 페이지 주소, 페이지를 소유한 프로세스 ID를 표시
• 페이지 공유가 안되기 때문에 실제로 사용하지는 않음

세그먼테이션

세그먼테이션

• 세그먼테이션 : 프로세스를 논리적 내용을 기반으로 나눠서 메모리에 배치
• 페이징: 고정 분할 분산 할당, 내부 단편화 O, 외부 단편화 X
• 세그먼테이션: 가변 분할 분산 할당, 내부 단편화 X, 외부 단편화 O
• 세그먼테이션 역시 평균 세그먼트 크기가 작을수록 외부 단편화 작음
• 메모리 압축 기법이나 동적 대치 알고리즘을 활용하여 외부 단편화 최소화 가능프로그램을 구성하는 서브루틴, 프로시저, 함수, 모듈 등으로 세그먼트를 구성 -> 각 세그먼트는 연관된 기능을 수행하는 하나의 모듈 프로그램으로 다룸보호 정책이나 관리에 필요한 사항은 페이징과 비슷함분할 영역이 가변적이기 때문에 스와핑은 힘들 수가 있음

세그먼테이션 테이블

• STBR(세그먼트 테이블 기준 레지스터)와 STLR(세그먼트 테이블 경계 레지스터)를 사용
• STBR: 세그먼트 시작 영역(논리적 주소),
• STLR: 세그먼트 크기(물리적 주소)프로세스를 dispatch 할 때 논리적 주소를 검사하는 역할
• 페이징: Page Table Base Register(PTBR) 사용
• 세그먼트 테이블은 각 세그먼트의 경계(segment limit)와 세그먼트 기준(segment base)를 가지고 세그먼트 메모리 주소의 시작과 끝을 나타냄
• 논리 주소의 세그먼트 번호(s)는 세그먼트 테이블의 인덱스로 사용됨오프셋(d)은 0과 세그먼트 경곗값 사이어야 함(아니면 trap 발생)

보호와 공유

• 페이징보다 세그먼테이션에서의 보호와 공유는 더 효율적
• 보호에서는 세그먼테이션은 r,w,x 비트를 추가하고 세그먼테이션은 프로세스를 논리적으로 나누기 때문에 해당 비트를 설정하기 매우 간단하고 안전하며 공유하기도 쉬움
• 페이징은 코드 영역을 나눈다해도 code+data+stack 영역이 섞일 위험이 존재

페이징

• 세그먼트만 단독으로 사용하면 세그먼트의 크기가 다양하기 때문에 다양한 크기의 hole 발생
• 세그먼테이션은 보호와 공유에서 효율적이나 외부 단편화 문제를 해결하기 어려움
• 이 두개를 합쳐 세그먼트를 페이징 기법으로 나누는 방법 존재
• 하지만 세그먼트와 페이지가 동시에 존재하기 때문에 주소 변환을 두번 해야 함