서론
CPU스케줄링의 결과로 CPU 이용률과 사용자에 제공하는 컴퓨터 응답속도를 모두 향상할 수 있다. 그러나 이러한 성능 향상을 실현하려면 많은 프로세스를 메모리에 유지해야 한다. 즉, 메모리를 공유해야 한다. 메모리를 관리하는 다양한 방법에 대해 알아보자.(대부분의 알고리즘은 하드웨어와 운영체제 메모리 관리를 밀접하게 통합해야 한다.)
주소 바인딩(Address binding)
주소 바인딩이란 프로그램 명령어와 데이터를 물리적 메모리 주소에 연결하는 과정을 말한다. 주소 바인딩은 세 단계에서 발생할 수 있다.
- 컴파일 타임 바인딩(Compile time binding)
- 로드 시간 바인딩(Load time binding)
- 실행 시간 바인딩(Execution time binding)
컴파일 타임 바인딩(Compile time binding)
메모리 위치가 컴파일 타임에 알려지면 절대 주소가 있는 절대 코드가 생성될 수 있다. 시작 위치가 변경되면 코드를 다시 컴파일해야 한다.
로드 시간 바인딩(Load time binding)
컴파일 타임에 메모리 위치를 알 수 없는 경우 상대 주소가 있는 재배치 가능 코드가 생성될 수 있다. 시작 위치가 변경되더라도 새로고침만 하면 된다.
실행 시간 바인딩(Execution time binding)
런타임까지 바인딩이 지연하다 CPU가 주소를 생성할 때마다 바인딩을 확인한다. 주소 매핑을 위해 MMU(Memory Management Unit)와 같은 하드웨어 지원이 필요하다.(대부분의 OS는 이 방법을 사용한다.)
메모리 관리 장치(Memory Management Unit, MMU)
논리 주소(Logical address)란 CPU에 의해 생성되며 가상 주소라고도 한다. 물리적 주소(Physical address)란 메모리 장치가 본 주소이다. 메모리 관리 장치는 논리 주소를 물리 주소에 매핑하는 하드웨어이다. 아주 단순한 MMU 기법은 재배치(relocation) 레지스터의 값을 CPU에서 생성된 모든 주소에 추가하는 방식이다. 사용자프로그램 및 CPU는 논리 주소를 처리하지만 물리 주소는 볼 수 없는 것에 주의해야 한다.
동적 적재(Dynamic Loading)
메모리 동적 적재는 프로그램이 실행될 때 필요한 부분만을 메모리에 적재하는 기법이다. 이는 프로그램의 실행 속도를 향상하고 메모리의 효율성을 높이는 데 도움이 된다. 동적 적재는 필요하지 않은 루틴은 절대 로드되지 않고 실행 중에 필요한 부분만 적재한다. 이는 많은 양의 오류 처리 코드가 필요할 때 유용하다. 그렇다고 로드할 때마다 매번 동일한 주소가 비어 있지 않는다. 어디든지 로드될 수 있기 때문에 동적 연결(dynamic linking)이 필요하다.
동적 연결(Dynamic Linking)
동적 연결(Dynamic Linking)은 프로그램 실행 시에 외부 라이브러리나 모듈을 필요로 할 때 해당 라이브러리를 런타임에 연결(실행 시간까지 연기됨)하는 기법이다. 정적 연결(Static Linking)과는 달리, 실행 파일에 외부 라이브러리의 코드가 포함되지 않으며, 필요할 때에만 동적으로 연결된다. 또한, 라이브러리가 필요한 모든 프로세스에 대해 메모리에 하나의 복사본이면 충분하다.
스와핑(Swapping)
스와핑(Swapping)은 운영체제에서 메모리 관리를 위해 사용되는 기법으로, 현재 메모리에 적재(load)되어 있는 프로세스나 프로그램의 일부를 일시적으로 메모리에서 보조기억장치(하드 디스크 등)로 이동시키는 것을 말한다. 그런 다음 나중에 메모리로 다시 가져온다.
배킹 스토어(Backing store)는 운영체제에서 스와핑(Swapping)을 지원하기 위해 사용되는 보조기억장치(Secondary Storage)이다. 스와핑은 현재 메모리에 적재된 프로세스나 프로그램의 일부를 보조기억장치로 이동시키는 것을 말하며, 이때 이동된 데이터는 보조기억장치의 일부인 backing store에 저장된다. 그렇기에 모든 이미지를 수용할 수 있을 만큼 충분히 빠르고 크다.(e.g. 디스크)
연속 할당(Contiguous Allocation)
메인 메모리는 일반적으로 두 개의 부분으로 나누어지는 데, 하나는 운영체제를 위한 것이며 다른 하나는 사용자 프로세스를 위한 것이다.
메모리 매핑 및 보호
메모리 매핑 및 보호는 프로세스 간의 메모리 격리 및 보안을 보장하기 위해 운영 체제에서 사용하는 중요한 기술이다. 이러한 기술은 MMU(메모리 관리 장치)와 함께 재배치 레지스터 및 제한 레지스터를 사용하여 달성된다. 재배치 레지스터(Relocation registers) 및 제한 레지스터(Limit register)에 의해 촉진되는 메모리 매핑 및 보호는 프로세스 간의 메모리 격리 및 보안을 보장하기 위해 운영 체제에서 사용하는 기본 기술이다. 이러한 메커니즘을 통해 프로세스는 지정된 영역 외부의 메모리에 대한 무단 액세스를 방지하면서 자체 가상 주소 공간에서 작동할 수 있다. 운영 체제는 이러한 기술을 활용하여 여러 프로세스를 동시에 실행할 수 있는 안전하고 신뢰할 수 있는 환경을 제공할 수 있다.
재배치 레지스터는 논리 주소의 동적 매핑을 활성화하여 사용자 프로세스를 보호하는 수단 역할을 한다. 재배치 레지스터의 목적은 각 논리 주소에 고정 값을 추가하여 메모리에서 해당 물리 주소를 결정하는 오프셋을 제공하는 것이다. 이 동적 매핑을 통해 프로세스는 실제 물리적 메모리 위치와 독립적인 논리 주소로 작동할 수 있다. 재배치 레지스터를 통합함으로써 운영 체제는 메모리 격리를 유지하고 프로세스가 할당된 영역 외부의 메모리에 액세스 하지 못하도록 방지할 수 있다.
재배치 레지스터 외에도 제한 레지스터는 메모리 보호에서 중요한 역할을 한다. 제한 레지스터는 논리 주소 범위를 정의하여 각 논리 주소가 지정된 제한 내에 속하도록 한다. MMU는 주소 변환 중에 이 제한 정보를 활용하여 프로세스가 지정된 주소 경계를 넘어 메모리에 액세스 하지 못하도록 효과적으로 제한한다. 프로세스가 허용 범위를 벗어난 메모리에 액세스 하려고 하면 MMU는 예외를 발생시켜 운영 체제가 개입하여 승인되지 않은 메모리 액세스를 처리하도록 트리거한다.
메모리 할당
메모리 할당에는 컴퓨터 시스템의 프로세스나 프로그램에 대한 메모리 할당이 포함된다. 메모리 할당 프로세스에는 일반적으로 프로세스의 요구 사항을 수용하기 위해 메모리의 적절한 부분을 찾는 작업이 포함된다. 메모리 할당에 대한 일반적인 접근 방식 중 하나는 메모리 공간 전체에 흩어져 있는 사용 가능한 큰 메모리 블록인 홀(Hole)을 사용하는 것이다. 프로세스가 생성되거나 추가 메모리를 요청할 때 운영 체제는 프로세스의 메모리 요구 사항을 수용할 수 있을 만큼 충분히 큰 구멍(여유 파티션)을 검색한다. 운영 체제는 현재 프로세스에 할당된 메모리 부분인 할당된 파티션과 할당되지 않은 메모리 부분인 사용 가능한 파티션 또는 홀에 대한 정보를 유지 관리한다. 전반적으로 홀을 사용한 메모리 할당에는 프로세스의 메모리 요구 사항을 수용할 수 있을 만큼 충분히 큰 가변 파티션(free partitions)을 찾는 작업이 포함된다. 운영 체제는 할당된 파티션과 여유 공간을 효율적으로 관리함으로써 프로세스에 필요한 메모리를 할당하는 동시에 시스템의 메모리 활용도를 최적화한다.
동적 스토리지 할당 문제
외부 단편화(External Fragmentation)
외부 단편화는 메모리 요청을 이행하기에 충분한 총 여유 메모리 공간이 있지만 사용 가능한 공간이 특정 요청을 충족할 만큼 충분히 연속적이지 않은 상황을 말한다. 이 단편화는 사용 가능한 메모리가 더 작은 비연속 블록으로 분할되어 비효율적인 메모리 사용률을 초래할 때 발생한다. 운영 체제가 사용 가능한 모든 여유 메모리를 하나의 큰 블록으로 압축하여 흩어진 홀을 제거하고 연속적인 여유 메모리 공간을 만드는 압축이라는 프로세스를 통해 외부 단편화를 줄일 수 있다.
내부 단편화(Internal Fragmentation)
내부 단편화는 프로세스에 할당된 메모리가 필요한 실제 메모리보다 약간 클 때 발생한다. 할당된 메모리와 요청된 메모리 간의 크기 차이를 내부 단편화라고 한다. 이는 메모리가 일반적으로 고정 크기 블록에 할당되기 때문에 발생하며, 요청된 메모리 크기가 이러한 블록과 완벽하게 일치하지 않으면 할당된 파티션 내에 사용되지 않은 공간이 일부 있을 것이다. 이 미사용 공간은 상대적으로 작지만 여러 할당에 걸쳐 합산되어 비효율적인 메모리 사용을 초래할 수 있다.
페이징(Paging)
페이징(Paging)은 운영체제에서 사용되는 메모리 관리 기법 중 하나로, 메모리를 고정된 크기의 페이지(page)로 나누는 것을 의미한다. 메모리와 이미지(프로그램)를 각각 고정된 크기로 분할한다. 페이지 프레임(page frame)은 메모리의 고정된 크기의 블록을 말하며, 페이지는 프로그램의 고정된 크기의 블록을 말한다. 이때, 페이지와 페이지 프레임의 크기는 512바이트에서 8킬로바이트 사이이며, 2의 거듭제곱으로 설정된다. 프로그램 이미지는 전체적으로 디스크에 저장되어 있으며, 프로그램 시작 시 첫 번째 페이지만 메모리에 로드된다. 나머지 페이지들은 필요할 때 메모리에 요청에 따라 로드된다. 예를 들어, 특정 페이지 X는 이미 메모리의 페이지 프레임 Y에 로드되어 있을 수도 있고, 이전에 로드된 적이 없어 디스크에 있는 상태일 수도 있다. 또한, 페이지는 메모리의 임의의 위치에 배치될 수 있다. CPU가 주소를 제시할 때마다 메모리 관리 장치(MMU)는 페이지 테이블을 조회하여 논리 주소를 물리 주소로 변환하는 역할을 수행한다. 이러한 방식으로 페이징은 프로그램의 실행에 필요한 페이지들을 필요한 때에 로드하고, 가상 주소를 물리 주소로 변환하여 프로그램이 메모리에 올라간 페이지에 접근할 수 있도록 한다. 이를 통해 메모리의 효율적인 사용과 가상 메모리 확장, 메모리 보호 등의 이점을 제공한다.
주소 변환 체계(Address Translation Scheme)
CPU에서 생성되는 논리 주소는 두 부분으로 나뉜다. 예를 들어, 주어진 주소 길이는 32이고 페이지 크기는 4KB일 때, 아래 그림과 같이 페이지 번호(p)와 페이지 오프셋(d)으로 나눌 수 있다. 페이지 번호는 페이지 테이블이 인덱스로 사용되며, 물리적 메모리에 있는 각 페이지 프레임의 기본 주소를 포함한다. 페이지 오프셋은 기본 주소와 결합하여 물리적 메모리 주소를 정의한다.
공유 페이지(Shared pages)는 여러 프로세스 간에 공유되는 페이지를 말한다. 페이징 기법을 사용하는 운영체제에서는 여러 프로세스가 동시에 실행될 수 있으며, 이들 프로세스는 독립적인 가상 주소 공간을 가지게 된다.
페이징은 메모리 보호가 구현되어 있다. 각 프레임에 보호 비트를 연결한다. 비트는 읽기 전용(Read-only), 읽기-쓰기(read-write), 실행 전용 비트(execute-only bit), 유효-무효 비트(Valid-invalid bit)로 나뉜다.
장점(Advantage)
- 물리적 메모리보다 큰 메모리 공간을 제공하다.
- 32비트 프로세서의 경우 4GB의 논리 주소 공간이 가능하다.
- 수요 페이징을 지원한다.
- 메모리 배치 정책이 필요하지 않는다.
- 페이지 공유한다.
- 메모리 공간을 서로 보호
단점(Disadvantage)
- 시간적 오버헤드(Temporal overhead) e.g. TLB(Translation Look-aside Buffer)
- 공간 오버헤드(Spatial overhead) e.g. 다단계 페이지 테이블, 해시 페이지 테이블, 반전 페이지 테이블
페이지 테이블 구현(Implementation of Page Table)
페이지 테이블(Page table)은 메인 메모리에 보관된다. 페이지 테이블 기본 레지스터(Page-table base register, PTBR)는 페이지 테이블을 가리킨다. 모든 데이터/명령 액세스에는 두 개의 메모리 액세스가 필요하다. 하나는 페이지 테이블을 위한 액세스, 다른 하나는 데이터/명령어를 위한 액세스이다. 이러한 두 개의 메모리 액세스 문제는 Translation Look-aside Buffer (TLB)의 사용으로 해결될 수 있다.
추가적인 메모리 공간이 페이지 테이블을 저장하기 위해 필요하다. 예를 들어, 프로그램은 큰 주소 공간을 가지고 있으며, 32비트 주소를 사용한다면 4GB 크기의 프로그램을 가리킬 수 있다. 다른 예로, 페이지 크기가 4KB일 경우, 프로그램은 1백만 개의 페이지 테이블 엔트리를 필요하다. 엔트리 크기가 4바이트라면, 4MB의 페이지 테이블이 필요하다. 즉, 페이지 테이블은 각각의 프로세스마다 별도의 데이터 구조이므로, 프로세스 수가 N일 때 N개의 페이지 테이블을 저장하기 위해 4MB * N의 메모리가 필요하다.
유효 액세스 시간(Effective Access Time
- TLB 조회 시간: ε
- 메모리 액세스 시간: 1
- 적중률: α (TLB에서 발견되는 백분율)
Effective Access Time = (1 + ε) α + (2 + ε)(1 – α) = 2 + ε – α
페이지 테이블의 구조(Structure of the Page Table)
- 계층적 페이지 테이블 (Hierarchical Page Table)
- 2단계 페이지 테이블 체계(Two-level Page Table Scheme)
- 3단계 페이지 테이블 체계(Three-level Page Table Scheme)
- 해시 페이지 테이블(Hashed Page Table)
- 역 페이지 테이블(Inverted Page Table)
계층적 페이지 테이블(Hierarchical Page Table)
2단계 페이지 테이블 체계(Two-level Page Table Scheme)
2단계 페이지 테이블 체계(Two-level Page Table Scheme)는 대규모 주소 공간을 효과적으로 관리하기 위한 페이지 테이블 구조이다. 2단계 페이징 기법으로서 페이지 테이블 자체가 다시 페이징 되게 하는 것이다. 즉, 페이지 테이블 자체도 페이징이 되기에 전체 페이지 테이블을 디스크에 저장하고 요청 시 페이지 테이블의 페이지를 로드하는 방식을 가진다. 이 방식은 단일 페이지 테이블을 사용하는 것보다 메모리 절약을 위해 사용된다.
2단계 페이지 테이블 체계를 사용한 주소 변환
논리 주소(4K 페이지 크기의 32비트)를 분할하여 20비트 페이지 번호와 12비트 페이지 오프셋으로 나눌 수 있다. 심지어 페이지 테이블 자체가 페이징 되므로 페이지 번호를 외부 페이지 테이블의 인덱스용 10비트와 내부 페이지 테이블의 인덱스용 10비트로 분할된다.
3단계 페이지 테이블 체계(Three-level Page Table Scheme)
해시 페이지 테이블(Hashed Page Table)
주소 공간이 32비트보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블을 많이 쓴다. 해시 페이지 테이블은 해시 테이블을 사용하여 논리 페이지 번호를 해싱한다. 해시 테이블은 동일한 위치에 해시된 요소들을 포함하는 체인으로 구성된다. 논리 페이지 번호는 체인 내 항목들의 첫 번째 필드와 일치 여부를 비교한다. 일치하는 항목을 찾으면 해당하는 물리 프레임 번호를 추출한다.
해싱(Hashing)은 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 것을 말한다. 이렇게 변환된 값은 해시 값 또는 해시 코드라고도 한다.
역 페이지 테이블(Inverted Page Table)
역 페이지 테이블은 가상 주소를 물리 주소로 변환하기 위한 페이지 테이블의 대안적인 구조이다. 전통적인 페이지 테이블은 가상 주소 공간의 각 페이지에 대한 매핑 정보를 가지고 있다. 즉, 페이지 번호가 페이지 테이블의 인덱스로 사용되고, 해당 인덱스의 엔트리에는 물리 프레임 번호가 저장된다. 하지만 역 페이지 테이블은 반대로, 물리 프레임을 기준으로 가상 주소의 매핑 정보를 저장한다. 역 페이지 테이블은 물리 프레임 번호를 인덱스로 사용하고, 해당 인덱스의 엔트리에는 해당 프레임을 사용하는 가상 주소의 정보가 저장된다. 즉, 역 페이지 테이블(Inverted Page Table)은 페이지 테이블의 공간 오버헤드를 줄이기 위한 구조이다. 기존의 페이지 테이블은 프로그램 크기에 비례하여 크기가 증가하며, 각 페이지에 대한 테이블 엔트리를 유지해야 한다. 하지만 역 페이지 테이블은 페이지 프레임마다 하나의 테이블 엔트리를 가지고 있으며, 엔트리는 해당 프레임을 사용하는 가상 주소 정보와 프로세스 ID를 포함한다. 이로써 하나의 페이지 테이블만을 유지하면 되며, 프레임의 수만큼의 엔트리가 필요하다. 역 페이지 테이블은 연관 검색(associative search)을 사용하여 전체 테이블을 검색해야 하므로 검색 시간이 증가한다. 이를 해결하기 위해 해시 테이블이나 연관 레지스터를 사용하여 검색 시간을 최소화할 수 있다. 역 페이지 테이블은 메모리 절약을 이루는 동시에 검색 속도를 희생하는 특징을 가지고 있다.
Segmentation
Segmentation은 메모리 관리 기법 중 하나로, 프로그램을 서로 다른 크기의 논리적인 블록인 세그먼트(Segment)로 분할하는 방식이다. 각 세그먼트는 프로그램의 논리적인 단위로써, 예를 들면 코드 세그먼트, 데이터 세그먼트, 스택 세그먼트 등이 있을 수 있다. 세그먼트는 논리적인 의미를 가지며, 프로그램의 모듈성과 유연성을 제공한다. 각 세그먼트는 서로 다른 크기를 가질 수 있으며, 크기는 해당 세그먼트에 필요한 메모리 공간에 따라 결정된다.
프로그램이 실행될 때, 주소 변환 단계에서는 세그먼트 번호와 세그먼트 내 오프셋을 이용하여 논리적 주소를 물리적 주소로 변환한다. 이를 위해 세그먼트 번호는 세그먼트 테이블의 인덱스로 사용되고, 해당 인덱스의 엔트리에서 기준 주소와 한계를 확인하여 물리적 주소를 계산한다.
각 세그먼트는 세그먼트 테이블(Segment Table)에 의해 관리된다. 세그먼트 테이블은 세그먼트의 논리적 주소와 물리적 주소 사이의 매핑 정보를 저장하는 데이터 구조이다. 세그먼트 테이블의 각 엔트리는 세그먼트의 기준(base) 주소와 한계(limit)를 포함하고 있다. 기준 주소는 해당 세그먼트의 시작 위치를 가리키며, 한계는 세그먼트의 크기와 세그먼트 메모리에 상주하는 시작 물리적 주소를 나타낸다. 한계 주소는 세그먼트의 길이를 나타낸다. 세그먼트 테이블 베이스 레지스터(Segment-table base register, STBR)는 메모리에서 세그먼트 테이블의 위치를 가리킨다. 세그먼트 테이블 길이 레지스터(Segment-table length register, STLR)는 프로그램에서 사용하는 세그먼트 수를 나타낸다. 세그먼트 번호 s는 s < STLR인 경우에 유효하다.
각 세그먼트는 논리적인 의미와 보호를 가지며, 세그먼트 테이블에 의해 관리된다. 세그먼트에는 보호 비트가 있어 세그먼트의 유효성, 읽기/쓰기/실행 권한 등을 설정할 수 있다. 또한 세그먼트 수준에서 코드 공유가 가능하며, 세그먼트의 길이가 다양하므로 동적 할당 문제가 발생할 수 있다. 이러한 동적 할당 문제는 first-fit, best-fit, worst-fit과 같은 방식으로 해결될 수 있다.
핵심
- 주소 바인딩은 프로그램 명령과 데이터를 물리적 메모리 주소에 연결하는 프로세스이다.
- 주소 바인딩은 세 단계(컴파일 시간, 로드 시간 및 실행 시간)에서 발생할 수 있다.
- 실행시간 바인딩에서는 실행시간까지 바인딩이 지연된다. 즉, CPU가 주소를 생성할 때마다 바인딩을 확인한다.
- MMU(Memory Management Unit)는 논리 주소를 물리 주소에 매핑하는 하드웨어이다.
- 페이징에서 전체 프로그램 이미지는 디스크에 상주한다.(프로그램이 시작되면 첫 페이지만 로드하고 나머지 페이지는 요청 시 메모리에 로드된다.)
- 페이징은 물리적 메모리보다 큰 프로그램 실행을 가능하게 한다.
- 페이징에서 모든 데이터/명령 액세스에는 두 개의 메모리 액세스가 필요하다. 하나는 페이지 테이블용이고 다른 하나는 데이터/명령용이다.
- 계층적 페이지 테이블 방식에서는 페이지 테이블 자체도 페이징된다.
'컴퓨터공학 > 운영체제' 카테고리의 다른 글
| OS 11. Mass-Storage Structure (0) | 2023.05.18 |
|---|---|
| OS 10. Virtual Memory (0) | 2023.05.18 |
| OS 8. Deadlocks (1) | 2023.05.16 |
| OS 7. 동기화 예제 (0) | 2023.04.06 |
| OS 6. 동기화 도구(Synchronization Tools) (0) | 2023.04.06 |
댓글