Operating system concepts
-Paging

Paging

가상 메모리를 모두 같은 크기의 블록으로 편성해 운용하는 기법.
논리 주소 공간이 한 연속적인 공간에 다 모여 있어야 한다는 제약을 없애고, 외부 단편화를 방지하며 압축 작업이 필요하지 않게 만들 수 있다.

페이지는 하드웨어 의존적이다.

Basic method

물리 메모리는 Frame이라 부르는 고정 크기의 블록으로 나누어져 있고, 논리 메모리는 Page라 불리는 프레임과 같은 크기의 블록으로 나누어진다.

CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 변위(d:offset)으로 나누어진다.
페이지 번호는 페이지 테이블(page table)을 액세스 할 때 사용되며, 페이지 테이블은 주 메모리에 존재하는 페이지의 기준 주소를 가지고 있다. (페이지의 주소에 페이지 변위를 더하면 메모리 장치로 전송될 물리 주소가 된다)

논리 주소의 형태

디스크의 입장에서는 페이지의 크기가 클수록 효율적이지만, 내부 단편화를 방지하기 위해선 페이지의 크기가 작을수록 효율적이다.

Hardware support

대부분의 컴퓨터는 페이지 테이블을 주 메모리에 저장하고 페이지 테이블 기준 레지스터(PTBR, Page-Table Base Register)로 페이지 테이블을 가리키도록 한다.

이 방식의 문제점은 메모리 접근 시간이다.
페이지 테이블 자체가 메모리에 올려져 있기 때문에, 특정 주소로 접근하기를 원한다면 먼저 페이지 테이블을 액세스해야 한다.

이 문제를 해결하는 표준 방법은 TLB(Translation Look-aside Buffers)라는 소형 하드웨어 캐시를 사용하는 것이다.

TLB는 매우 빠른 연관 메모리로 구성되며, TLB 내의 각 항목은 key와 value의 두 부분으로 구성된다.
TLB에 페이지를 찾아달라고 요청이 들어오면, 찾고자 하는 페이지를 동시에 여러 개의 내부 키와 비교하여 같은 것이 발견되면 그에 대응하는 프레임 번호를 알려준다.

만약 페이지 번호가 연관 레지스터 TLB에서 찾아지지 않으면 주 메모리의 페이지 테이블에서 찾아야 한다. 이렇게 해서 프레임 번호가 얻어지면 페이지 번호와 프레임 번호가 TLB에 추가되어 다음 참조 시 매우 빨리 처리할 수 있게 된다.

TLB가 가득 찼다면 OS는 새 항목을 넣기 위해 교체 작업을 해야 하는데, LRU부터 무작위 교체까지 다양한 정책이 사용된다.

Effective memory access time

페이지 번호가 TLB에서 발견되는 비율을 hit ratio라고 부른다.

Hit ratio가 80%, TLB 탐색시간이 20ns, 메모리 접근 시간이 100ns일 때
유효 메모리 접근 시간(effective memory access time)은 다음과 같이 구한다.

0.80 * 120 + 0.20 * 220 = 140 ns

Hit ratio가 98%일 때는 122ns

Protection

페이지화된 환경에서 메모리의 보호는 각 프레임과 연관되어있는 Protection bit에 의해 구현된다.
Protection bit는 보통 페이지 테이블에 속해있으며 페이지의 읽기/쓰기 속성을 정의할 수 있다.

읽기 전용 페이지에 쓰기를 시도하면 OS에게 하드웨어 트랩이 전달된다.

페이지 테이블의 각 엔트리에는 유효/무효(valid/invalid)라는 하나의 비트개 더 있는데,
이 비트가 유효일 경우 관련 페이지가 프로세스의 합법적인 페이지임을 의미하고 무효인 경우 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.

Shared page

페이징의 또 다른 장점은 공통 코드를 공유할 수 있는 것이다.

각 프로세스들은 레지스터들의 복사 값과 프로세스가 실행되는 동안 필요한 데이터들을 저장하는 공간을 따로 가지고 있기 때문에 공통 코드를 실행하는데 문제가 없다.

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은 라이브러리 루틴을 알아내거나 적재하고 나서 자신을 그 루틴의 주소로 대체하고 루틴을 실행한다.
다음 번 동일한 루틴이 호출되면 동적 연결을 할 필요 없이 직접 그곳의 라이브러리 루틴을 실행한다.
즉 여러 프로그램에서 동일한 함수를 사용하면 메모리 내의 한 곳에 루틴을 올려놓고 사용하게 된다.

8.1.1 기본 하드웨어

- 기계 명령어들은 메모리 주소만을 인수로 취하며, 디스크의 주소는 인수로 취하지 않는다.

- 모든 실행되는 명령어와 데이터는 주 메모리와 레지스터에 있어야 한다.

- 레지스터들은 일반적으로 CPU clock의 1cycle 내에 접근이 가능하다.

- 주 메모리의 접근을 완료하기 위해서는 많은 CPU clock tick cycle이 소요되며, 이 경우 명령어를 실행하지 못하고 지연되는 현상이 발생한다.
이를 해결하기 위하여 Cache를 사용한다.

- 접근 속도의 차이에 대한 고려 외에User program으로부터 운영체제 영역을 보호하고 프로그램의 충돌을 방지하는 작업을 수행해야 한다. (하드웨어 지원)

1. 각각의 프로세스는 독립된 메모리 공간을 가진다.
2. 이를 위해 특정 프로세스만 접근할 수 있는 legal 영역을 설정하고 프로세스가 이 영역만을 접근하도록 하는 것이 필요하다.
3. Base와 Limit 레지스터를 사용하여 이러한 보호 기법을 구현한다.

Figure1. Base Limit Registers

Base Register: 가장 작은 legal 주소 값을 저장한다.
Limit Register: 주어진 영역의 크기를 저장한다.

4. 메모리 공간의 보호는 CPU 하드웨어가 User mode에서 만들어진 모든 주소와 레지스터를 비교함으로써 이루어진다.
User mode에서 실행되는 프로그램이 자신의 메모리 영역이 아닌 다른 메모리 영역을 침범하면 운영체제는 치명적인 에러로 간주하고 trap을 발생시킨다.

5. Kernel mode에서 실행되는 프로세스는 메모리 접근에 어떠한 제약도 받지 않는다. (운영체제는 Kernel에서 실행된다.)
운영체제는 User program을 User memory 영역에 적재하고, 에러가 발생한 경우 그 프로그램을 dump out시키고 system call의 parameter 값을 변경하는 것과 같은 일들을 할 수 있다.

8.1.2 주소의 할당 (Address Binding)

프로그램이 실행되기 위해서는 프로세스가 되어야 한다.
사용하는 메모리 관리 기법에 따라 프로세스는 실행하는 동안 디스크와 주 메모리 사이를 왔다 갔다 할 수 있으며 input queue를 형성한다.

대부분의 시스템은 사용자 프로세스가 메모리 내 어느 부분으로도 올라올 수 있도록 지원하고 있다.
즉 사용자 프로세스는 상대적 주소를 가질 수 있다. (각 프로세스마다 논리적 0번지를 가질 수 있다.)

원시 프로그램에서 주소는 숫자가 아닌 심벌로 표현되며 컴파일러는 이 심벌 주소를 재배치 가능 주소로 바인딩 시키고, 추후에 Linkage editor나 loader가 재배치 가능 주소를 절대 주소로 바인딩 시킨다.

각각의 바인딩 과정은 한 주소 공간에서 다른 주소 공간으로 맵핑하는 것.

Compile time binding

프로세스가 메모리 내의 특정 위치를 사용하는 것을 컴파일 할 때 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있다.
ex) MS-DOS의 .COM양식 프로그램

Load time binding

컴파일 시점에 프로세스가 메모리 내 위치를 알지 못하면 컴파일러는 이진 코드를 재배치 가능 코드로 만들고,
프로그램이 주 메모리로 실제로 적재될 때 심볼 주소와 절대 주소가 바인딩된다.

Execution binding

프로세스가 실행 중 메모리 내에서 옮겨질 수 있다면 바인딩이 실행 시간까지 허용되었다고 말할 수 있다.
(특별한 하드웨어를 이용해야 한다.)

8.1.3 Logical-Versus Physical-Address Space

Logical address: CPU가 생성하는 주소

Physical address: MAR에 주어지는 주소로서 메모리가 취급하는 주소

• Compile time binding의 경우 Logical address == Physical address
• Load time binding은 Logical address와 Physical address가 같으며 이 경우 Logical address를 Virtual address라 한다.

Logical address space: 프로그램에 의해 생성된 모든 논리 주소 집합

Physical address space: Logical address space에 상응하는 모든 물리 주소 집합

프로그램 실행 중에는 Virtual address와 Physical address를 Mapping해주는 작업이 필요한데, 하드웨어 장치인 Memory Management Unit에 의해 구현된다.