Operating System Concepts -
Contiguous Memory Allocation

8.3.1 Memory Protection

Memory mapping과 Memory protection은 Relocated register와 Limit register에 의해 제공된다.

Relocated register는 가장 작은 물리주소의 값을 저장하며 Limit register는 논리 주소의 범위 값을 저장한다.

CPU Scheduler가 다음으로 실행할 프로세스를 선택할 때 Dispatcher는 문맥 교환의 일환으로 Relocated register와 Limit register에 정확한 값을 적재한다.
CPU에 의해 생성되는 모든 주소는 이 레지스터의 값을 참조하므로 OS와 다른 프로그램을 현재 실행중인 프로세스로부터 보호할 수 있다. (메모리 접근 방지의 의미)

8.3.2 Memory Allocation

가장 간단한 공간 할당 방법은 고정된 크기로 분할하는 것이지만 효율성 측면에서 크게 떨어진다.
때문에 가변 분할 기법을 사용하게 되는데, 메모리의 상태를 파악할 수 있는 테이블을 유지해야 한다.

동적 메모리 할당

1. First-fit: 필요한 메모리를 만족시키는 큰 첫 번째 가용 공간을 할당한다.
   검색은 시작 지점부터 수행하거나 이전 검색 지점부터 시작될 수 있다.
2. Best-fit: 필요한 메모리 크기를 만족시키는 충분히 큰 공간들 중 가장 작은 것을 택한다.
   리스트가 크기 순으로 정렬되어있지 않으면 리스트 전체를 검색해야 하며 이 방법은 아주 작은 잔여 공간을 발생시킨다.
3. Worst-fit: 가장 큰 가용 공간을 택한다. 할당해주고 남게 되는 자유 공간은 다른 프로세스들이 유용하게 사용할 수 있다. 하지만 자유 공간이 크기 순으로 정렬되어있지 않다면 리스트 전체를 다시 검색해야한다.

8.3.3 Fragmentation

외부 단편화(External fragmentation)

앞에서 기술한 알고리즘에서는 외부 단편화가 발생한다.
프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면 자유 공간들이 너무 작은 조각이 되어버리는데, 외부 단편화는 수 많은 작은 조각들이 여러 곳에 분산되어 있을 때 발생한다.
외부 단편화를 해결하는 한 가지 방법은 압축(compaction)이다.
이 방법은 메모리의 모든 내용들을 한 군데로 몰고 모든 자유 공간들을 다른 한 군데로 몰아서 큰 블록을 만드는 것이다. (많은 비용 발생)
외부 단편화를 해결하는 다른 방법은 한 프로세스의 논리 주소 공간을 여러 개의 비 연속적인 공간으로 나누어 각각 할당하는 방법이다. (페이징, 세그먼테이션)

내부 단편화(Internal fragmentation)

할당된 크기와 요구 공간과의 차이에서 발생하는 잉여 공간.

Operating System Concepts -
Swapping

Swapping

프로세스가 실행되기 위해서는 메모리에 존재해야 하지만 필요에 따라 실행 도중 임시로 보조 메모리로 교체되어 나갔다가 되돌아올 수 있다.
이를 Swapping이라고 하며 Swapping의 변형을 roll-in, roll-out이라고도 부른다.
Swapping은 단순히 스케줄링에 의해 프로세스의 time quantum이 다 되었을 때 다른 프로세스를 준비시킬 때 사용할 수도 있지만 우선순위를 고려하여 실행될 수도 있다. (roll in, out)

Swapping을 구현하기 위해선 보조 메모리가 필요한데, 보통 Disk를 사용한다.
시스템은 실행 준비된 프로세스를 ready queue에 보관하며 이들은 스케줄러에 의해 관리된다.

Dispatcher

CPU 스케줄러는 다음 프로세스를 선택할 때 dispatcher를 호출하는데, Dispatcher는 ready queue에 있는 다음 프로세스가 메모리에 올라가있는지 확인하고 만약 없다면 메모리로 올려야 한다.

그런데 이 때 메모리에 충분한 공간이 없다면 공간을 만들기 위해 메모리에 올라가 있는 다른 프로세스를 Swap out하고 실행할 프로세스를 올린다. (Swap in)

Context-switch time

이런 Swapping system에서는 문맥 교환 시간(Context-switch time)이 상당히 오래 걸리게 된다.

Context-switch time이란?
사용자 프로세스의 크기 100MB, Disk는 초당 50MB의 전송률을 가진다.
100MB/50MB = 2초
평균 8ms의 회전 지연 시간을 가정했을 때 Swap시간은 2008ms가 된다. (디스크 헤더 탐색 시간은 고려하지 않았다)
그런데 우리는 Swap out을 실행하고 Swap in을 실행해야 하므로 총 Swap 시간은 4016ms가 된다.

Swap 시간을 줄이기 위해서는 실제로 사용하는 부분만을 스왑하는 것인데, 이를 위해선 메모리 요구사항의 변화가 있을 때 마다 시스템에게 이를 알려주어야 한다.
(request memory, release memory와 같은 system call)

실제로 사용되는 수정된 Swapping

표준 Swapping 방식은 거의 사용되지 않는다.
너무 많은 시간을 필요로 하고, 실행 시간이 너무 작아지기 때문이다.
수정된 Swapping은 많은 UNIX 버전에서 사용되며 보통 때는 Swap을 하지 않지만, 많은 프로세스가 실행되고 메모리 부족이 일어나면 Swapping이 시작된다.

Operating System Concepts

8.1.4~8.1.5 Dynamic Loading,
Dynamic Linking & Shared Libraries

Dynamic loading (Dynamic linking)은 메모리로 라이브러리 또는 다른 프로그램을 적재/링크 하는 방식으로, CPU의 메모리 사용량을 줄이기 위해 일부 라이브러리 코드의 적재/링크를 미루어둔다.

미뤄진 라이브러리 또는 코드는 생성된 실행 파일에 포함되어있지 않으며 dll에 저장된다.
이는 프로그램 실행 도중 필요할 때 CPU의 호출에 의해 적재/링크 된다.

Dynamic Loading에서 각 루틴은 실제 호출 전 까지 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에 대기하고 있다.
main프로그램이 메모리에서 실행되고 있을 때 이 루틴이 다른 루틴을 호출하게 되면 호출된 루틴이 메모리에 적재되어있는지 조사하고, 만약 적재되어 있지 않다면 Relocatable linking loader가 요구된 루틴을 메모리에 올리고 변경 사항을 프로그램의 주소 테이블에 기록한다.
이 적재 과정이 종료되면 CPU는 중단되었던 루틴으로 다시 보내지고 실행을 계속한다.

동적 적재의 장점

• 사용되지 않는 루틴들은 적재되지 않기 때문에 메모리를 절약하는데 아주 유용하다.
• 동적 적재는 운영체제로부터 특별한 자원을 요구하지 않는다. (그러나 운영체제는 동적 적재를 구현하는 라이브러리 루틴을 제공한다.)

Stub

동적 연결에서 라이브러리를 호출하는 곳 마다 Stub이 생긴다.
Stub은 작은 코드 조각으로 메모리에 존재하는 메모리를 찾는 방법 또는 메모리에 없을 경우 라이브러리를 적재하는 방법을 제공한다.

Stub이 실행될 때 필요한 라이브러리 루틴이 이미 메모리에 존재하는지 검사하며 없으면 루틴을 메모리로 적재한다. 그리고 Stub은 라이브러리 루틴을 알아내거나 적재하고 나서 자신을 그 루틴의 주소로 대체하고 루틴을 실행한다.
다음 번 동일한 루틴이 호출되면 동적 연결을 할 필요 없이 직접 그곳의 라이브러리 루틴을 실행한다.
즉 여러 프로그램에서 동일한 함수를 사용하면 메모리 내의 한 곳에 루틴을 올려놓고 사용하게 된다.