간단 요약
연속 할당 : 메모리에 ‘연속적으로’ 공간을 할당하는 것
- 고정분할 : 메모리를 미리 나누어 관리. 내부단편화
- 가변분할 : 매시점 프로그램에 맞춰 동적으로.외부단편화
불연속 할당 : 메모리를 연속적으로 할당하지 않는 기법
- 페이징(paging) : 동일한 크기(보통 4kb)의 페이지 단위로 나누어 메모리의 서로 다른 위치에 프로세스를 할당합니다. 홀의 크기가 균일하지 않은 문제가 없어지지만 주소 변환이 복잡해짐.
- 세그멘테이션 : 페이지 단위가 아닌 의미 단위인 세그먼트(segment)로 나누는 방식입니다. 프로세스는 코드, 데이터, 스택, 힙 등으로 이루어지는데, 코드와 데이터 등 이를 기반으로 나눌 수도 있으며 함수 단위로 나눌 수도 있음을 의미합니다. 공유와 보안 측면에서 좋으며 홀 크기가 균일하지 않은 문제가 발생됨
- 페이지드 세그멘테이션 : 공유나 보안을 의미 단위의 세그먼트로 나누고, 물리적 메모리는
페이지로 나누는 것을 말함.
메모리 연속할당 기법
메모리에 ‘연속적으로’ 공간을 할당하는 것
연속할당 기법은 프로세스를 메모리에 올릴 때 주소 공간을 메모리의 한 곳에 연속적으로 적재하는 방식입니다. 연속 할당 방식에서는 물리적 메모리를 다수의 분할로 나누어 하나의 분할에 하나의 프로세스가 적재되도록 합니다.
연속할당 기법은 크게 고정분할 방식과 가변분할 방식으로 나뉩니다.
고정분할 방식
메모리를 미리 나누어 관리
고정분할 방식은 물리적 메모리를 정해진 개수만큼의 영구적인 분할로 나누어두고 각 분할에 하나의 프로세스를 적재하는 방식입니다. 분할의 크기는 모두 동일할 수도 있고 서로 다를 수도 있습니다.
고정분할 방식은 동시에 메모리에 올릴 수 있는 프로그램의 수가 고정되어 있으며 수행 가능한 프로그램의 최대 크기 또한 제한된다는 점에서 가변분할 방식에 비해 융통성이 떨어집니다.
또한 고정분할 방식에는 외부조각과 내부조각 문제가 발생할 수 있습니다.
가변분할 방식
매시점 프로그램에 맞춰 동적으로
가변분할 방식은 메모리에 적재되는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식이다. 따라서 가변분할 방식은 프로그램의 크기를 고려해서 메모리를 할당하고 이를 기술적으로 관리할 수 있는 기법이 필요하다.
가변분할 방식은 프로세스에 딱 맞게 메모리 공간을 사용하기에 내부조각 문제는 발생하지 않는다. 그러나 사용중인 프로세스가 종료되어 메모리에 새로운 프로세스를 올릴 메모리 공간이 충분하지 않을 경우 외부 조각 문제가 발생한다.
가변분할 방식은 어디 메모리 공간에 프로세스를 올려야 할지 결정해야하는 문제가 있다. 이를 해결하기 위한 기술적 방법으로 다음과 같이 3가지가 있다.
- 최초적합: 가장 먼저 나오는 가용 가능한 메모리 공간에 프로세스를 올리는 방법이다.
- 최초적합: 가장 딱 맞는 메모리 공간을 찾아 프로세스를 올리는 방법이다.
- 최초적합: 가장 큰 메모리 공간에 프로세스를 올리는 방법이다.
가변분할 방식에서 발생하는 외부조각 문제를 해결하기 위한 방법으로 컴팩션(compaction: 압축)방법이 있다. 물리적 메모리 중에서 사용중인 메모리 공간을 한쪽으로 몰고 가용 공간을 확보하는 방법이다. 메모리를 효율적으로 사용할 수 있는 측면에서는 좋은 선택이지만 수행중인 프로세스의 메모리 주소 공간을 이동시켜야 하므로 비용이 매우 많이 든다.
메모리 불연속할당 기법
불연속할당 기법은 하나의 프로세스가 물리적 메모리의 여러 위치에 분산되어 올라갈 수 있는 메모리 할당 기법을 말합니다.
페이징 기법
동일한 크기(보통 4kb)의 페이지 단위로 나누어 메모리의 서로 다른 위치에 프로세스를 할당합니다. 홀의 크기가 균일하지 않은 문제가 없어지지만 주소 변환이 복잡해짐.
페이징 기법은 프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식을 말한다. 페이징 기법에서는 각 프로세스의 주소 공간 일부는 백킹스토어에, 일부는 물리적 메모리에 혼재시키는 것이 가능하다.
페이징 기법에서는 물리적 메모리를 페이지와 동일한 크기의 프레임으로 미리 나누어 둔다.
메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로, 메모리를 같은 크기로 미리 분할해 두더라도 빈 프레임이 있으면 어떤 위치이든 사용될 수 있기 때문이다.
따라서 페이징 기법은 동적 메모리 할당 문제(메모리 주소 공간 결정 문제)가 발생하지 않는다는 강점을 가진다. 빈 페이지가 보이면 메모리를 올리기만 하면 된다.
페이징 기법에서는 프로세스의 주소 공간과 물리적 메모리가 모두 같은 크기의 페이지 단위로 나누어지기 때문에 빈 공간은 어느 곳이든 활용 할 수 있다. 따라서 메모리상의 가용 공간의 크기가 작아서 빈 공간임에도 활용되지 못하는 외부조각 문제가 발생하지 않는다. 그러나 프로그램의 크기가 항상 페이지 크기의 배수가 된다는 보장이 없기 때문에 프로세스의 주소 공간 중 제일 마지막에 위치한 페이지에서는 내부조각이 발생할 가능성이 있다.
주소 변환 기법
페이징 기법에서는 주소 변환 절차가 연속할당 방식에 비해 다소 복잡하다. 이는 하나의 프로세스라 하더라도 페이지 단위로 물리적 메모리에 올리는 위치가 상이 하므로, 논리적 주소를 물리적 주소로 변환하는 작업이 페이지 단위로 이루어져야 하기 때문이다. 즉, 특정 프로세스의 몇 번째 페이지가 물리적 메모리의 몇 번째 프레임에 들어 있다는 페이지별 주소 변환 정보를 유지하고 있어야 한다. 따라서 페이징 기법에서는 모든 프로세스가 각각의 주소 변환을 위한 페이지 테이블(page table)을 가지며, 이 테이블은 프로세스가 가질 수 있는 페이지의 개수만큼 주소 변환 엔트리를 가지고 있게 된다.
페이징 기법에서는 CPU가 사용하는 논리적 주소를 페이지 번호(p)와 페이지 오프셋(d)로 나누어 주소변환을 사용한다.
1. 페이지 테이블에서 페이지 번호(p)를 확인하여 물리적 메모리 상의 기준 주소(base address)를 확인한다.
2. 물리적 주소에서 오프셋(d)만큼 떨어진 곳이 실제 물리적 메모리 주소이다.
페이지 테이블
페이지 테이블에 접근하기 위해 운영체제는 2개의 레지스터를 사용한다. 이들은 각각
- 페이지 테이블 기준 레지스터(page table base register) : 페이지 테이블의 시작 위치
- 페이지 테이블 길이 레지스터(page table length register) : 페이지 테이블의 크기
기능을 갖고 있다.
그렇다면 페이지 테이블은 어디에 있을까❓
페이지 테이블은 메모리에 존재한다. 즉, 실제 물리적 메모리의 주소를 알기 위해서
1. 페이지 테이블 정보를 확인하기 위해 메모리 접근
2. 물리적 메모리를 얻기 위해 메모리 접근
총 2번의 메모리 접근을 하게되는 오버헤드가 발생한다. 이와 같은 문제를 해결하기 위해 TLB(Translation Look-aside Buffer)라고 불리는 고속의 주소 변환용 하드웨어 캐시를 사용한다.
TLB 하드웨어는 가격이 비싸서 용량이 적다. 따라서 TLB에서 모든 페이지 테이블 정보를 확인 할 수는 없다. 또 원하는 페이지를 찾기 위해 모든 페이지를 뒤져야하게 되는데 페이지 테이블 개수가 n개 라면 O(n)의 시간 복잡도가 걸리게 된다. 이를 극복하기 위해 병렬탐색이 가능한 연관 레지스터를 사용하여 모든 페이지 테이블 정보를 한꺼번에 찾는다.
TLB를 확인해도 원하는 페이지 정보를 확인 할 수 없다면 페이지 테이블을 방문하여 물리적 메모리 주소를 확인한다.
계층적 페이징
현대의 컴퓨터는 32bit 혹은 64bit 주소 체계를 사용한다. 32bit 컴퓨터에서는 2^32byte(4GB)의 주소 공간을 갖는 프로그램을 지원할 수 있다. 이러한 컴퓨팅 환경에서 페이지 크기가 4KB라면 4GB/4KB = 1M(2^20)개의 페이지 테이블이 필요하게 된다. 각 페이지 테이블 항목이 4byte씩 필요로 한다면 한 프로세스당 필요한 페이지 수는 4MB의 공간을 필요로 하게 된다.
32bit 운영체제는 2^32byte의 주소공간 즉, 4GB의 주소공간을 갖는 프로그램을 지원한다.
프로세스 주소공간 4GB
페이지 크기 4KB
페이지 테이블 항목당 필요한 용량 4byte
4GB/4KBx4byte = 4MB
사용하는 프로세스가 증가할수록 페이지 테이블을 위한 많은 메모리 공간이 사용된다. 이러한 메모리 낭비를 줄이기 위해 2단계 페이징 기법을 사용한다. 2단계 페이징 기법은 외부 페이지 테이블과 내부 페이지 테이블을 사용한다. 사용되지 않는 주소 공간에 대해서는 외부 페이지 테이블의 항목을 NULL로 설정하여 대응되는 내부 페이지 테이블을 생성하지 않는 방법이다.
계층적 페이징 기법은 메모리 공간을 줄여 공간적인 이득을 볼 수 있지만 주소 변환을 위해 페이지 단계수가 3단계, 4단계로 증가할 수록 메모리에 접근하는 횟수도 증가하여 오버헤드가 증가하는 손해가 뒤따르게 된다.
그러므로 TLB와 계층적 페이징 기법을 적절히 사용하여 메모리 공간 효율과 시간 효율을 높여야 한다.
역페이지 테이블
역페이지 테이블 기법은 물리적 메모리의 페이지 프레임 하나당 페이지 테이블에 하나씩 항목을 두는 방식이다. 다시 말하면 논리적 주소에 대해 페이지 테이블을 만드는 것이 아니라, 물리적 주소에 대해 페이지 테이블을 만드는 것이다.
역페이지 테이블❓
논리적 주소에 대한 페이지 테이블 ❌
물리적 주소에 대한 페이지 테이블 ✔️
즉, 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체에 페이지 테이블을 하나만 두는 방법이다.
페이지 테이블의 각 항목은 프로세스 번호(pid)와 프로세스 내의 논리적 페이지 번호(P)를 담고 있게 된다.
역페이지 테이블을 사용하기 위해 모든 페이지를 탐색해야 하므로 시간적으로 손해를 보게 된다. 이를 해결하기위해 역페이지 테이블은 병렬 탐색을 가능하게 하는 연관 레지스터를 사용하여 시간적 효율성을 높이게 된다.
공유 페이지
공유 페이지란 공유 코드를 담고 있는 페이지를 말한다. 공유 페이지는 여러 프로세스에 의해 공유되는 페이지이므로 물리적 메모리에 하나만 적재되어 메모리를 좀 더 효율적으로 사용할 수 있게 한다.
메모리 보호
페이지 테이블에는 주소 변환을 위한 정보 뿐만 아니라 메모리 보호를 위한 보호비트(protection bit)와 유효 무효 비트(valid-invalid bit)를 두고 있다.
보호비트(protection bit)는 각 페이지에 대한 접근 권한의 내용을 담고 있다. 각 페이지에 대한 접근을 허용하는지의 정보가 보호비트에 저장된다. 다시 말해 각 페이지에 대한 읽기/쓰기 등의 접근 권한을 설정하는 데에 사용된다.
유효 무효 비트(valid-invalid bit)는 해당 페이지의 내용이 유효한지에 대한 내용을 담고 있다. '유효'로 설정되어 있으면 메모리에 해당 페이지가 존재함을 뜻하며, '무효'일 경우 프로세스가 주소 부분을 사용하지 않거나, 해당 페이지가 백킹스토어에 존재하여 접근 권한이 없다는 의미로 사용된다.
세그먼테이션
페이지 단위가 아닌 의미 단위인 세그먼트(segment)로 나누는 방식입니다.
프로세스는 코드, 데이터, 스택, 힙 등으로 이루어지는데, 코드와 데이터 등 이를 기반으로 나눌 수도 있으며 함수 단위로 나눌 수도 있음을 의미합니다. 공유와 보안 측면에서 좋으며 홀 크기가 균일하지 않은 문제가 발생됨
세그먼테이션은 프로세스의 주소공간을 의미 단위의 세그먼트(segment)로 나누어 물리적 메모리에 올리는 방법이다.
프로세스의 주소 공간은 일반적으로 코드, 데이터, 스택 등의 의미 있는 단위들로 구성이 된다. 세그먼트는 이와 같은 주소 공간 전체를 크게는 하나의 세그먼트로 보기도 한다. 일반적으로 코드, 데이터, 스택 등의 기능 단위로 세그먼트를 정의하며, 프로그램을 구성하는 함수 하나하나를 각각 세그먼트라고 정의할 수도 있다. 주의할 점은 논리적 단위로 나눈 것이기 때문에 세그먼트의 크기가 균일하지 않다는 점이다.
세그먼트 테이블
세그먼테이션 기법에서는 주소 변환을 위해 세그먼트 테이블을 사용한다. 세그먼트 테이블의 각 항목은 기준점(base)과 한계점(limit)을 가지고 있다.
- 기준점(base) : 물리적 메모리에서 세그먼트의 시작 위치
- 한계점(limit) : 세그먼트의 길이
세그먼테이션 기법에서는 세그먼트 길이가 균일하지 않으므로 세그먼트의 시작 위치 정보뿐 아니라 길이 정보도 함께 보관하고 있는 것이다.
페이징 기법에서는 주소 변환을 위해 기준 레지스터(PTBR)와 테이블 길이 레지스터(PTLR)를 사용했듯이 세그먼테이션 기법에서도 세그먼트 테이블 기준 레지스터(STBR)과 세그먼트 테이블 길이 레지스터(STLR)를 사용하게 된다.
- 세그먼트 테이블 기준 레지스터(STBR) : 프로세스의 세그먼트 테이블 메모리 위치(시작 주소)
- 세그먼트 테이블 길이 레지스터(STLR) : 프로세스 세그먼트의 총 개수
세그먼트 테이블 주소 변환
세그먼테이션 기법에서는 논리적 주소를 물리적 주소로 변환하기 전에 두 가지 항목을 체크합니다.
1. 요청된 세그먼트의 번호가 STLR 미만의 값인지 확인합니다. 만약 그렇지 않다면 존재하지 않는 세그먼트에 대한 접근으로 예외상황을 발생시켜 메모리에 접근 봉쇄합니다.
2. 논리적 주소의 오프셋 값이 그 세그먼트의 길이보다 작은 값인지 확인합니다. 만약 그렇지 않다면 세그먼트 테이블의 길이를 넘어서는 오프셋 위치에 대한 접근으로 예외상황을 발생시켜 메모리에 접근 봉쇄합니다.
장단점
세그먼트는 의미 단위로 나누어져 있기 때문에 공유와 보안의 측면에서 페이징 기법에 비해 효과적이다. 주소 공간의 일부를 공유하거나 특정 주소 공간에 접근 제어를 할경우 크기가 아니라 의미 단위로 공유되기 떄문이다.
세그먼테이션은 프로세스를 의미 단위로 나누어 메모리에 적재하기 때문에 세그먼트의 길이가 균일하지 않다. 따라서 물리적 메모리 관리에서 외부조각이 발생하게 되며, 세그먼트를 어느 가용 공간에 할당할 것이지 결정하는 문제가 발생한다.
페이지드 세그먼테이션
공유나 보안을 의미 단위의 세그먼트로 나누고, 물리적 메모리는 페이지로 나누는 것을 말함.
각각의 장단점을 갖고 있음을 알 수 있다. 페이지드 세그먼테이션은 페이징 기법과 세그먼테이션 기법의 장점을 취하는 주소 변환 기법이다.
세그먼테이션과 마찬가지로 프로세스를 의미 단위의 세그먼트로 분할한다. 단, 세그먼테이션 처럼 불규칙한 길이가 아니라 동일한 크기의 페이지들의 집합으로 구성하는 것이다.
페이지드 세그먼테이션 테이블
하나의 세그먼트를 여러개의 페이지로 구성되므로 페이지드 세그먼테이션은 2개의 테이블을 사용한다.
- 외부의 세그먼트 테이블
- 내부의 페이지 테이블
페이징 기법의 2단계 페이지 테이블과 유사한 구조를 사용한다.
페이지드 세그먼테이션 테이블을 활용하여 주소변환 하는 과정은 다음과 같다.
1. 논리적 주소의 상위 비트인 세그먼트 번호를 통해 세그먼트 테이블의 해당 항목을 확인한다.
2. 해당 항목에는 세그먼트의 길이와 세그먼트의 페이지 테이블 시작 주소가 있다.
3. 세그먼트 길이를 넘어선 메모리 접근인지 체크한다. 유효하지 않다면 트랩을 발생시킨다.
4. 오프셋 값을 상위/하위 비트로 나누어 상위비트는 세그먼트 내의 페이지 번호로 사용하고, 하위 비트는 페이지 내에서의 변위로 사용한다.
출처 : 면접을 위한 CS 전공지식 노트
https://zangzangs.tistory.com/141?category=458016
[OS] 메모리 불연속할당 - (3) 페이지드 세그먼테이션
[OS] 메모리 불연속할당 - (3) 페이지드 세그먼테이션 안녕하세요? 장장스입니다. 실제 물리적 메모리는 크게 연속할당 방식과 불연속할당 방식으로 나뉩니다. 오늘은 메모리 불연속할당 방
zangzangs.tistory.com
'CS > 운영체제' 카테고리의 다른 글
| 운영체제 면접 질문 (0) | 2022.09.28 |
|---|---|
| 페이지교체 알고리즘 : FIFO, LRU, NUR, LFU (0) | 2022.07.26 |
| 캐시, 캐시히트, 캐시미스 (0) | 2022.07.26 |
| CPU 스케줄링 알고리즘(비선점형, 선점형) (0) | 2022.07.26 |
| 세마포어, 뮤텍스, 모니터의 차이 그리고 교착상태(deadlock) (0) | 2022.07.26 |
