[운영체제] CH16 - CH17

CH16 세그멘테이션

베이스와 바운드 레지스터를 사용하는 주소 공간에서는 스택과 힙 사이에 사용되지 않는 큰 공간이 존재한다 

그 공간은 사용되지 않더라도 주소 공간을 물리 메모리에 재배치할 때 물리 메모리를 차지하기 때문에 메모리 낭비가 심하고, 주소 공간이 물리 공간이 물리 메모리보다 큰 경우 실행이 매우 어렵다는 측면에서 유연성이 없다

🐣 주소 공간이 물리 메모리보다 큰 경우 왜 실행이 어려울까 찾아보니, 그러면 모든 주소를 물리 메모리에 매핑할 수 없기 때문에 실행이 어려워지고, 이는 시스템의 유연성을 떨어뜨리는 요인이 된다고 한다 

+ 공간을 어떻게 활용할 것인가 - 공간 관리 기법 

핵심 질문 - 대형 주소 공간을 어떻게 지원하는가
스택과 힙 사이에 빈 영역이 크게 존재하는 주소 공간을 어떻게 지원하는가? 우리의 예는 주소 공간이 작기 때문에 그렇게 낭비가 심각하지 않지만, 크기가 4GB 인 32비트 주소 공간, 통상 프로그램은 단지 수 메가바이트만 사용함에도 불구하고 주소 공간 전체가 메모리에 탑재되어야 한다 

16.1 세그멘테이션 - 베이스/ 바운드 (Base/ Bound) 의 일반화

 

세그멘테이션 Segmentation 은 MMU에 하나의 베이스와 바운드 값이 존재하는 것이 아니라

세그먼트 Segment 마다 베이스와 바운드 값이 존재한다는 개념으로 시작한다 

 

세그먼트는 특정 길이를 가지는 연속적인 주소 공간이고,

우리가 기준으로 삼은 주소 공간에는 코드, 스택, 힙 세 종류의 세그먼트가 있다 

세그멘테이션을 사용하면 운영체제는 각 세그먼트를 물리 메모리의 다른 위치에 배치할 수 있고

사용하지 않는 가상 주소 공간이 물리 메모리를 차지하는 것도 방지할 수 있다

 

그림 16.2에서 64KB의 물리 메모리에 3개의 세그먼트와 운영체제로 예약된 16KB 영역의 경우, 사용 중인 메모리에만 물리 공간이 할당되어 사용되지 않은 영역이 많은 대형 주소 공간*을 수용할 수 있다

(*드문드문 사용되는 주소 공간 Sparse Address Space 라고 부른다)

 

이 그림에서는 3쌍의 베이스와 바운드 레지스터 집합이 필요하고

그림 16.3 에서 각 레지스터의 값을 보여준다,

각 바운드 레지스터는 세그먼트의 크기를 저장한다 

 

세그먼트의 사이즈는 앞서 소개한 바운드 레지스터와 일치하며

이 세그먼트에 몇 바이트가 유효한지 하드웨어에게 알려준다

 

 

그림 16.1 의 주소 공간을 사용하고 가상 주소 100번지를 참조하여 주소 변환을 한다고 할 때 

가상 주소 100번지는 코드 세그먼트에 속한다 (그림의 1~2KB 영역에 속한다)

참조가 일어나면 하드웨어는 베이스 값에 이 세그먼트의 오프셋 100 을 더해 

물리 주소는 100+32KB 또는 32868이 된다 

그 후, 주소가 범위 내에 있는지 검사하고 (100은 2KB보다 작다)

범위 내에 있을 경우 물리 메모리 주소 32868을 읽는다 

 

가상 주소 4200의 경우, 힙의 베이스 34KB에 더하면 물리 주소 39016가 되고, 이 주소는 올바른 물리 주소가 아니다

먼저 힙 안에서의 오프셋, 즉 주소가 참조하는 바이트가 이 세그먼트 시작으로부터 몇번째 바이트인지를 얻어야 한다 

힙은 가상 주소 4KB, 4096에서 시작하기 때문에 오프셋 4200은 실제로 4200 - 4096 = 104가 된다, 이 오프셋 104를 베이스 레지스터의 물리 주소 34KB에 더해 원하는 결과 34920을 얻게 된다 

 

만일 힙의 마지막을 벗어난 (가상 주소로 7KB보다 더 먼) 주소를 접근하려고 한다면, 그 주소가 범위를 벗어났다는 것을 하드웨어가 감지하고 운영체제에 트랩을 발생시켜서 운영체제가 문제의 프로세스를 종료시킬 가능성이 크다

+ 트랩은 컴퓨터 시스템 CH08 예외 처리 종류에 나온다 

세그먼트 폴트 Segment Fault 
세그먼트 사용 시스템에서 불법적인 주소 접근 시 발생한다 
세그먼트를 지원하지 않는 컴퓨터에서도 사용되지만
이 경우에는 코드의 오류 원인을 알 수도 없다 

 

 

16.2 세그먼트 종류의 파악 

하드웨어는 변환을 위해 세그먼트 레지스터를 사용하며, 일반적으로 가상 주소의 최상위 비트 몇 개로 세그먼트 종류를 나타낸다 

VAX/ VMS 시스템에서는 3개의 세그먼트가 있고, 그 3종류를 나타내기 위해 가상 주소의 2비트를 활용한다 

 

최상위 비트가 00일 때, 가상 주소가 코드 세그먼트를 가리킨다는 것을 하드웨어가 알고, 코드 세그먼트의 베이스와 바운드 쌍을 사용하여 정확한 물리 메모리에 재배치한다

또한, 최상위 비트가 01일 때는 하드웨어가 코드 세그먼트는 힙 세그먼트라는 것을 인지한다, 힙에 해당하는 가상 주소 4200를 이진수로 변환하면 0000 0110 1000 (또는 16진수 0x068) 이고 오른쪽처럼 나타낼 수 있다

 

정리하자면, 하드웨어는 세그먼트 레지스터의 최상위 비트 2개로 세그먼트의 종류를 파악하고, 세그먼트 오프셋으로 다음 12비트를 취한다 

오프셋에 베이스 레지스터 값을 더하면 최종 물리 주소가 계산되므로 바운드 검사도 쉽게 할 수 있다 (오프셋 < 바운드 여부 검사)

베이스와 바운드 값들을 배열로 저장한다면 (세그먼트별로 값이 존재) 물리 주소는 아래와 같이 계산할 수 있다 

코드 설명은 생략

세 개의 세그먼트를 나타내려고 세그먼트의 최상위 2비트를 사용하는 것은, 전체 주소 공간의 1/4을 낭비하는 것과 같다 

또한 상위 비트를 사용하여 세그먼트를 선택하는 방식은, 각 세그먼트의 최대 크기가 정해져 있기 때문에 가상 주소 공간의 활용도를 제한한다 

+ 10 스택, 11 커널이라 커널은 사용자 모드에서 접근할 수 없어서 낭비라고 얘기함 

+ 묵시적은 레지스터 값 없이 알아서 찾기 

16.3 스택

 

 

스택은 다른 세그먼트와 다르게 반대 방향으로 확장된다 (낮은 주소 방향으로 확장) + 오프셋은 음수로 만들어야 한다 

그렇기 때문에 간단한 하드웨어가 추가로 필요하다, 베이스와 바운드 값 뿐 아니라 세그먼트가 어느 방향으로 확장하는지도 하드웨어가 알아야 한다, 이 사실을 반영하여 하드웨어가 관리해야 하는 정보를 그림 16.4 에 나타낸다 

자세한 계산은 책 참고 

16.4 공유 지원

메모리를 절약하기 위해 때로는 주소 공간들 간에 특정 메모리 세그먼트를 공유하는 것이 유용하다

특히, 코드 공유가 일반적이다, 공유를 지원하기 위해 세그먼트마다 Protection Bit 를 추가하여 세그먼트를 읽거나 쓸 수 있는지, 코드를 실행시킬 수 있는지를 나타낸다 

 

코드 세그먼트를 읽기 전용으로 설정하면 주소 공간의 독립성을 유지하면서도,  여러 프로세스가 주소 공간의 일부를 공유할 수 있다 

사용자 프로세스가 읽기 전용 페이지에 쓰기를 시도하는 경우 또는 실행 불가 페이지에서 실행하려고 하면 

하드웨어는 예외를 발생시켜서 운영체제가 위반 프로세스를 처리할 수 있게 해야한다 

16.5 소단위 대 대단위 세그멘테이션

지금까지의 소수의 세그먼트 (코드, 스택, 힙) 만을 지원하는 시스템 예시는 대단위 Coarse-grained 라고 볼 수 있고 

일부 초기 시스템은 주소 공간을 작은 크기의 공간으로 잘게 나누는 것이 허용되었기 때문에 

 

소단위 Fine-grained 세그멘테이션이라고 부를 수 있다 

세그먼트 테이블을 이용하면 매우 많은 세그먼트를 손쉽게 생성하고 융통성 있게 세그먼트를 사용할 수 있다 

16.6 운영체제의 지원

시스템이 각 주소 공간 (세그먼트) 단위로 가상 주소 공간을 물리 메모리에 재배치하면서

스택과 힙 사이의 사용하지 않는 공간에 물리 메모리를 할당할 필요가 없기 때문에

전체 주소 공간이 베이스-바운드 값 하나를 가지는 방식에 비해 물리 메모리를 절약할 수 있다 

 

세그멘테이션의 도입을 위해 운영체제가 해결해야 할 몇가지 문제가 있다

1) 문맥 교환

세그멘테이션을 사용할 경우 운영체제는 문맥 교환 시 세그먼트 레지스터를 저장하고 복원해야 한다

프로세스를 바꿀 때 세그먼트 레지스터에 저장된 정보를 저장하고, 새로운 프로세스에 맞게 이 레지스터를 다시 설정한다 

2) 세그먼트 크기의 변경

어떤 프로그램이 malloc()을 호출하여 객체를 할당했을 때 빈 공간이 없으면 힙 세그먼트의 크기를 증가시켜야 한다

메모리 관리 라이브러리가 힙을 확장하기 위하여 시스템 콜을 호출하고, 운영체제는 공간을 할당한다 

세그먼트 크기 레지스터를 좀 더 큰 (새로운) 크기로 갱신하고, 라이브러리에게 성공을 알리면

라이브러리가 새로운 객체에 공간을 할당하고, 할당된 공간에 대한 포인터를 호출한 프로그램에게 반환하게 된다 

3) 미사용 중인 물리 메모리 공간의 관리 

운영체제는 새로운 주소 공간이 생성되면 이 공간의 세그먼트를 위한, 비어있는 물리 메모리 영역을 찾을 수 있어야 한다 

프로세스는 많은 세그먼트를 가질 수 있고, 각 세그먼트는 크기가 다를 수 있기 때문에

물리 메모리가 작은 크기의 빈 공간들로 채워져서, 새로 생겨나는 세그먼트에 할당하기 힘든 상황을

외부 단편화 External Fragmentation 라고 부른다 

 

이 문제의 해결책 중 한 가지는 기존의 세그먼트를 정리하여 물리 메모리를 압축 Compact 하는 것이다 

운영체제가 현재 실행 중인 프로세스를 중단하고, 데이터를 하나의 연속된 공간에 복사하여 

세그먼트 레지스터가 새로운 물리 메모리 위치를 가리키면, 작업할 큰 빈 공간을 확보할 수 있다 

하지만 세그먼트 복사는 메모리에 부하가 큰 연산이고 많은 프로세서 시간을 사용하기 때문에 비용이 많이 든다 

할당 가능한 메모리 영역들을 리스트 형태로 유지하는 알고리즘을 사용하면, 빈 공간을 간단하게 관리할 수 있다 

고전 알고리즘 - 최적 적합 Best-fit, 최악 적합 Worst-fit, 최초 적합 First-fit, 버디 알고리즘 Buddy Algorithm 

16.7 요약 

세그멘테이션의 장점

* 메모리 가상화를 효과적으로 실현할 수 있다

* 주소 공간 상 논리 세그먼트 사이의 큰 공간에 대한 낭비를 피할 수 있다 

* 세그멘테이션에 필요한 산술 연산이 쉽고, 하드웨어 구현에 적합하여 속도가 빠르다

* 변환 오버헤드 최소 

* 코드 공유의 장점 발생 

세그멘테이션의 단점

* 세그먼트의 크기가 일정하지 않기 때문에 외부 단편화 발생 

* 드문드문 사용되는 주소 공간을 지원할 만큼 충분히 유연하지 못 함

 

CH17 빈 공간 관리 

외부 단편화를 어떻게 해결할 수 있을까? 

핵심 질문 - 빈 공간을 어떻게 관리하는가 
가변 크기의 요구를 충족시켜야 할 때, 빈 공간은 어떻게 관리되어야 하는가? 단편화를 최소화하기 위해 어떤 전략을 사용할 수 있는가? 여러 대안들의 시간과 공간에 오버헤드는 어떻게 되는가?

사용자 수준 메모리 할당 라이브러리가 관리하는 공간은 힙 Heap 이라고 불리며, 힙의 빈 공간은 일반적으로 링크드리스트 Linked-list 가 사용된다 (링크드리스트는 영역 내의 모든 빈 청크에 대한 주소를 갖고 있다)

17.2 저수준 기법들

분할 Splitting 과 병합 Coalescing 

30바이트의 힙이 있다고 가정할 때, 이 힙의 빈 공간 리스트에는 2개의 원소가 있다 

하나는 첫번째 10바이트의 빈 세그먼트 (바이트 0-9)를 설명하고 다른 하나는 나머지 빈 세그먼트 (바이트 20-29)를 표현한다 

 

10바이트를 초과하는 모든 요청은 요청한 크기에 해당하는 메모리 청크가 없기 때문에, 실패하여 NULL을 반환한다

10바이트보다 적은 요청에 대해서 할당기는 분할 Splitting 로 알려진 작업을 수행한다, 요청을 만족시킬 수 있는 빈 청크를 찾아 둘로 분할하고 첫번째 청크는 호출자에게 반환되고 두번째 청크는 리스트에 남게 된다 (헤드 -> (주소0, 길이10) -> 주소(21, 길이9) -> NULL)

 

응용 프로그램이 free(10)을 호출하여 힙의 중간에 존재하는 공간을 반환되면, 힙에는 10바이트 길이의 청크 3개로 나누어진 빈 공간이 존재하지만, 이 상태에서 20바이트를 요청하면 실패를 반환한다

이 문제는 메모리 청크가 반환될 때 빈 공간들을 병합함으로써 해결 가능하다, 메모리 청크가 반환될 때 해제되는 청크의 주소와 바로 인접한 빈 청크의 주소를 검사해서 빈 공간이 인접해 있다면 그들을 하나의 더 큰 빈 공간으로 병합하여 연속된 메모리 공간을 생성할 수 있다 

할당된 공간의 크기 파악

대부분의 할당기는 추가 정보를 헤더 Header 블록에 저장하고, 헤더 블록은 보통 해제된 청크 바로 직전에 위치한다 

헤더에 할당 영역의 크기와 매직 넘버를 저장한다, 매직 넘버로 안정성 검사 Sanity Check 를 진행할 수 있다 

빈 공간 리스트 내장 

빈 공간을 연결하기 위해 구조체를 생성한다 

힙의 확장 

힙 공간이 부족한 경우 가장 쉬운 방법은 실패를 반환하는 것이다 

대부분의 전통적인 할당기는 적은 크기의 힙으로 시작하여 모두 소진하면 운영체제에게 더 많은 메모리를 요청한다 (unix - sbrk 호출) 그런 후 확장된 영역에서 새로운 청크를 할당한다, 운영체제는 sbrk 요청을 수행하기 위해 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간에 매핑하고 새로운 힙의 마지막 주소를 반환한다 

17.3 기본 전략 

최적 적합 Best Fit 

요청한 크기와 같거나 더 큰 메모리 청크를 갖는다, 그 후 가장 작은 크기의 청크를 반환한다 

최악 적합 Worst Fit 

가장 큰 빈 청크를 찾아 요청한 크기만큼만 반환하고 남는 부분은 빈 공간 리스트에 계속 유지한다 

🐣 데이터 특성 상 확장이 계속 일어나는 구조인 경우 사용할 수 있지 않을까? 
🐣 그래서 외부 단편화를 막을 수 있고, 외부 단편화를 막는 것에 대해 장점은 반환할 때 편하다 

최초 적합 First Fit 

요청보다 큰 첫번째 블럭을 찾아서 요청만큼 반환한다 

🐣 앞에 작은 블록들이 모여 있을 수 있음 -> 그걸 해결하는 방법이 주소-기반 정렬 Addess-Base Ordering 

다음 적합 Next Fit 

마지막으로 찾았던 원소 이후부터 탐색한다

🐣 리스트를 균등하게 검색할 수 있다 

17.4 다른 접근법

개별 리스트(segregated list)

특정 프로그램이 자주 요청하는 크기가 있다면, 그 크기의 공간을 관리하기위한 별도 리스트를 유지하는 것이다.

장점은 별도 리스트를 유지함으로써 단편화를 많이 줄일 수 있다. 요청된 크기의 공간을 리스트에 있으니 신속하게 할당 및 해제가 가능하다.

하지만 문제가 있는데, 지정된 크기의 메모리 풀과 일반적인 풀에 얼마만큼의 메모리를 할당해야 할까? 특수목적 할당기인 **슬랩 할당기(slab allocator)**가 이를 해결해준다.

슬랩 할당기(slab allocator) 원리

• 커널 부팅 시 커널 객체를 위한 객체 캐시를 할당한다.
• 객체 캐시란, 락, 파일 시스템 등 자주 요청되는 자료구조를 말함
• 객체 캐시는 지정된 크기 객체로 구성된 빈 공간 리스트고 메모리 할당 및 해제를 빠르게 하기위해 사용된다.
• 캐시 공간이 부족하면 상위 메모리 할당기에서 추가 슬랩을 요청한다.
• 만약 사용하지 않은 캐시의 경우, 상위 메모리 할당기는 이를 회수해간다.
• 슬랩 할당 방식은 빈 객체들을 초기화된 상태로 유지한다는 점에서 개별 리스트 방식보다 우수하다. </aside>

개별 리스트와 슬랩 할당 방식의 차이점

슬랩 할당 방식은 객체를 반환할 때 초기화된 상태로 유지하여 메모리 재사용시 초기화 작업을 줄여준다.

개별 리스트 방식은 할당 해제된 메모리가 초기화되지 않은 상태로 남기에 성능과 안전성이 좋지 않다.

특징 슬랩 할당 방식 개별 리스트 방식(Free List)

메모리 초기화	객체 반환 시 초기화된 상태로 유지됨	객체 반환 후 초기화되지 않은 상태로 유지됨
재사용 시 초기화 필요성	초기화 불필요 (즉시 재사용 가능)	재사용 시 초기화 필요
초기화 오버헤드	없음 (한 번 초기화 후, 재사용)	있음 (메모리 재사용 시, 매번 초기화해야 함)
성능	높음 (초기화 작업이 없으므로 할당/해제 성능 향상)	낮음 (초기화 과정으로 인해 추가적인 작업 발생)
안정성	높음 (초기화된 상태 유지로 초기화되지 않은 메모리 접근 방지)	낮음 (초기화되지 않은 메모리에 접근할 수 있어 위험)
보안성	높음 (초기화되지 않은 데이터 노출 가능성 적음)	낮음 (초기화되지 않은 메모리 사용 시 보안 취약점 발생 가능)
사용 용도	주로 커널이나 동일한 크기의 객체를 반복적으로 사용하는 경우 적합	일반적인 메모리 관리에 사용되지만, 성능이 중요한 경우 적합하지 않음