8장 주 기억 장치 관리

8.1 배경(Background) 주 기억 장치 전형적인 명령어 실행 과정 각각 주소가 할당된 일련의 워드 또는 바이트들로 구성 CPU는 program counter가 지시하는 대로 기억 장치로부터 다음에 수행할 명령어를 가져 오며, 그 명령어는 필요한 추가적인 데이터를 가져올 수 있다 데이터를 기억 장치로 보낼 수도 있다 전형적인 명령어 실행 과정 ① 기억 장치로부터 명령어를 가져온다 ② 명령어를 해독한다 ③ 기억 장치에서 피연산자(operand)를 가져와 피연산자에 대해 명령어를 실행한다 ④ 실행 결과를 기억 장치에 저장한다

8.1.1 기억장치 보호(Memory Protection) * 목적: 사용자 프로그램에 의해 인터럽트 벡터가 변경되는 것을 방지한다. 운영체제의 인터럽트 서비스 루틴이 변경되는 것을 방지한다.   * 방법 각 프로그램의 기억 공간을 분리하여, 프로그램이 접근할 수 있는 적정 주소의 범위를 결정하여 그 범위 밖의 기억 공간을 보호한다. 기준(base) 레지스터와 한계(limit) 레지스터를 사용한다. ◆ 기준 레지스터: 가장 작은 합법적인 물리 메모리 주소를 저장한다. ◆ 한계 레지스터: 프로그램 영역이 저장되어 있는 범위의 크기를 저장한다.

보호과정 * 보호 과정 CPU 하드웨어가 사용자 모드에서 생성된 모든 주소를 레지스터와 비교함으로써 성취된다. ⇒ 사용자 모드에서 실행되고 있는 프로그램이 모니터 메모리나 다른 사용자 메모리에 접근하려는 모든 시도는 모니터로 트랩을 일으키며, 모니터는 그러한 시도를 치명적인 오류로 취급한다. ⇒ 이 기법은 사용자 프로그램이 운영체제 혹은, 다른 사용자의 코드나 데이터 구조를 변경하는 것을 막아 준다.

8.1.2 주소의 할당 (Address Binding) 프로세스 실행 과정 ① 이진 실행 파일 형태의 프로그램이 디스크에 저장된다 ② 프로그램은 실행되기 위해 주 기억 장치로 이동하여 프로세스가 된다 ③ 사용하는 기억 장치 관리 기법에 따라 프로세스는 디스크와 주 기억 장치 사이를 오가며 실행한다 입력 큐 : 디스크에 있으면서 실행을 위해 메모리로 적재되기를 기다리는 프로세스들의 집합 사용자 프로그램이 실행되기 전의 과정 ①  기호(symbol) 형태의 주소를 갖는 원시(source) 프로그램을 작성한다 ②  컴파일러가 일반적으로 기호 형태의 주소를 재배치 가능한 주소로 변환(binding)한다. ③  연결 편집기(linkage editor)나 적재기(loader)가 재배치 가능 주소를 절대 주소로 변환(binding)한다.

① 컴파일 시간(compile time) 바인딩 주소 바인딩의 종류 ① 컴파일 시간(compile time) 바인딩 프로세스가 적재될 기억 장치 내의 위치를 컴파일 때 미리 알 수 있으면, 컴파일 때 절대 주소가 생성 프로그램의 시작 위치를 변경하고자 한다면 다시 컴파일해야 한다  (예) MS-DOS의 .COM 양식의 프로그램 ② 적재 시간(load time) 바인딩 절대 주소는 적재할 때 결정된다 만일 프로그램의 시작 위치를 변경하고자 한다면 다시 적재(reload)해야 한다 ③ 실행 시간(execution time) 바인딩 절대 주소는 프로그램 실행 중에 결정된다 프로세스는 실행 중에 기억 장치 내에서 이동할 수 있다

8.1.3 논리적∙물리적 주소 공간 (Logical-Versus Physical-Address Space) 논리 주소(상대 주소) : CPU가 생성하는 주소(프로그램 내의 주소) 물리 주소(절대 주소) : 기억 장치가 취급하는 주소, 즉 기억 장치 주소 레지스터(MAR)에 주어지는 주소 컴파일 시간 바인딩과 적재 시간 바인딩 논리 주소 = 물리 주소 실행 시간 바인딩 논리 주소(가상 주소) ≠ 물리 주소    주소 공간(Address Space) 논리 주소 공간 : 프로그램에 의해 생성된 모든 논리 주소 집합 물리 주소 공간 : 논리 주소에 대응하는(corresponding) 모든 물리 주소 집합

MMU(Memory Management Unit) 프로그램 실행 중에 가상 주소를 물리 주소로 변환하는 하드웨어 동작 방법: 논리 주소가 기억 장치로 보내질 때마다 기준(재배치) 레지스터에 저장되어 있는 값과 더해져서 물리 주소를 생성한다

8.1.4 동적 적재 (Dynamic Loading) 효율적인 기억 장치 공간 활용 지원 동작 과정: ① 각 루틴은 실제로 호출되기 전까지는 기억 장치에 적재되지 않고 재배치 가능한 적재 형태로 디스크에 저장 ② 먼저 main 프로그램이 기억 장치에 적재되어 실행 ③ 이 루틴이 다른 루틴을 호출할 경우 호출된 루틴이 이미 기억 장치에 적재되어 있는 지 조사 ④ 만약 적재되어 있지 않다면 재배치 가능 연결 적재기가 요구된 루틴을 기억 장치로 적재하고 이러한 변화를 테이블에 기록 ⑤ CPU 제어는 중단되었던 루틴으로 이동 동적 적재의 장점 사용되지 않는 루틴은 결코 미리 적재되지 않는다 ⇒ 특히 커다란 프로그램이 드물게 사용되는 경우에 유용하다(예: 오류 처리 루틴은 오류가 발생할 때만 실행)

8.1.5 동적 연결 및 공유 라이브러리(Dynamic Linking & Shared Libraries) stub가 각 라이브러리 루틴의 참조를 위해 프로그램 코드에 포함된다 stub : 라이브러리를 어떻게 찾을 것인가를 알려주는 작은 코드 조각. 이 라이브러리는 경우에 따라 이미 메모리에 적재되어 있을 것이고, 어떤 경우에는 디스크로부터 가져와야 한다.

중첩(Overlays) 중첩 동기: 한 프로세스의 크기는 그 프로세스에게 할당된 기억 장치보다 더 클 수 있다 ⇒ 프로세스의 실행이 불가능 해결 방법: 중첩을 사용한다 ① 어느 주어진 시간에 꼭 그 당시에 필요한 부분만을 기억 장치에 적재하여 실행한다 ② 다른 부분들이 필요해지면 먼저 기억 장치에 적재되어 있던 정보 중 더 이상 필요가 없거나 덜 중요한 정보들의 자리에 새로운 정보를 적재하여 실행을 계속한다

 사례 : 2 패스 어셈블러 패스 1: 70K, 패스 2: 80K, 가용 메모리 공간: 90K

8.2 스와핑(Swapping) 스와핑 사용 동기: 스와핑을 통한 프로세스 실행과정 프로세스가 실행되기 위해서는 기억 장치에 있어야 하지만 필요한 경우 실행 도중 잠시 보조 기억 장치로 이동한 후, 다시 기억 장치로 적재되어 실행을 계속할 수 있다 스와핑을 통한 프로세스 실행과정 ① CPU 스케줄러는 실행할 프로세스를 결정한다 ② CPU 스케줄러는 디스패처를 호출한다 ③ 디스패처는 큐에서 다음에 실행할 프로세스가 기억 장치에 존재하는 지 검사한다. ④ 만일 프로세스가 적재되어 있지 않고, 또한 가용 기억 장치 공간도 없으면, 디스패처는 현재 메모리에 있는 프로세스들 중에서 선택하여 원하는 프로세스와 스왑한다 ⑤ 스왑되어 나갔던(roll-out) 프로세스는 후에 가용 공간에 발생하면 다시 스왑되어(roll-in) 기억 장치에 적재되어 실행된다. roll-in될 때 이전에 적재되었던 장소로 다시 적재된다(컴파일 시간 바인딩이나 적재 시간 바인딩인 경우 ) roll-in될 때 빈 공간으로 적재된다(실행 시간 바인딩인 경우)

8.3 연속 메모리 할당 (Contiguous Memory Allocation) 기억 장치의 할당 메모리에 상주하는 운영체제를 위한 부분: 인터럽트 벡터는 보통 0번지에 위치하기 때문에 운영체제는 하위 기억 장치에 위치하는 것이 보통이다 사용자 프로세스를 위한 부분

8.3.1 메모리 보호 (Memory Protection) 이유:  ① 운영체제를 사용자 프로세스로부터 보호 ② 사용자 프로세스들 간의 보호 방법:  ◆ 재배치 레지스터 사용 : 프로세스가 적재되기 시작하는 주소값을 저장 ◆ 상한(limit) 레지스터 사용 : 프로세스의 논리 주소의 범위(range)값을 저장한다 물리 주소 = 논리 주소 + 재배치 레지스터의 내용

8.3.2 메모리 할당 (Memory Allocation) 메모리 할당 방법 고정 크기 분할 MVT (1) 고정 크기 분할 ① 특징:  기억 장치 공간을 고정된 크기로 분할한다(가장 간단하다) 각 분할마다 오직 한 개의 프로세스만 적재된다 분할의 개수는 다중 프로그래밍 정도의 의해 결정된다 ② 프로세스 실행 과정: 한 분할이 비게 되면 한 프로세스가 입력 큐에서 선택되어 빈 분할에 들어온다 프로세스가 끝나면 그 분할은 다른 프로세스를 위해 사용될 수 있다

(2) MVT(General fixed-partition) 특징: ◆ 일괄처리 환경에서 사용된다 ◆ 운영체제는 기억 장치의 어떤 부분이 사용되고 있고, 어떤 부분이 사용되지 않고 있는가를 테이블에 기록 과정 : ① 초기에 모든 기억 장치 공간을 한 개의 큰 사용 가능한 블록으로 설정 ② 새 프로세스가 생성되고 기억 장소를 요구하면 운영체제는 가용 공간을 찾아 이 프로세스에게 충분한 크기의 공간을 할당 ③ 할당하고 남은 부분은 미래의 요청에 대비하여 가용 부분으로 유지한다

 (사례) FCFS(First-Come First-Served) job scheduling

동적 기억 장치 할당(dynamic storage allocation) 종류: ① 최초 적합: 사용 가능한 공간들 중에서 첫 번째 가용 공간(hole)을 할당 ② 최적 적합: 사용 가능한 공간들 중에서 가장 작은 공간을 할당 ③ 최악 적합: 사용 가능한 공간들 중에서 가장 큰 공간을 할당 외부 단편화 프로세스들이 기억 장치에 적재되고 제거되는 일이 반복되면서 작은 공간 조각들이 분산되어 생기는 현상. 분산된 작은 유휴 공간들을 모두 합치면 충분한 공간이 되지만 그것들이 작은 조각들로 여러 곳에 분산되어 있어서 새로운 프로세스를 위한 가용 공간으로 사용이 불가능하다. 50-percent rule: 최초 적합의 방법을 사용하여 N 개의 블록이 할당되었을 때 0.5N 개의 블록이 단편화로 인한 손실이 될 수 있다

8.3.3 단편화(Fragmentation) 내부 단편화(Internal Fragmentation) 요구된 공간보다 조금 더 큰 공간을 할당하는 경우에 발생 내부 단편: 요구된 공간과 실제 할당된 공간의 차이 외부 단편화 문제 해결 방법 압축(Compaction) : 외부 단편의 감소 페이징(Paging) : 외부 단편 제거 세그먼테이션(Segmentation): 외부 단편 감소 압축 기억 장치의 모든 내용들을 한 장소로 몰고 모든 자유 공간을 다른 부분으로 몰아서 큰 블록을 형성 압축과 결합된 스와핑도 가능하다 단점: 압축이 항상 가능한 것을 아니다 ⇒ 재배치가 가능하고 실행 시간 바인딩이 가능해야 한다.

8.4 페이징(Paging) 페이징 목적: 외부 단편을 제거한다 방법 : 논리 주소 공간이 서로 이웃하지 않는 것을 허용한다

8.4.1 기본 방법(Basic Method) 방법: ① 물리 주소를 프레임이라 불리우는 고정된 크기의 블록으로 나눈다 ② 논리 주소를 페이지라 불리우는 프레임과 같은 크기의 블록으로 나눈다 ③ 한 프로세스가 실행될 때 그 프로세스의 페이지는 보조 기억 장치로부터 주 기억 장치의 프레임으로 적재된다 ④ 프로세스의 페이지가 실행될 때 CPU에서 나오는 모든 논리 주소는 페이지 번호(p)와 페이지 변위(d)로 이루어진다(논리 주소 = 페이지 번호 + 페이지 변위) ⑤ 논리 주소의 페이지 번호는 페이지 테이블을 통해 해당 프레임 번호(f)로 사상된다 ⑥ 물리 주소의 프레임 번호(f)와 변위(d)를 결합하여 원하는 정보에 접근한다(물리 주소 = 프레임 번호(f) + 변위(d) )

페이징 하드웨어 p: 페이지 번호 d: 페이지 변위(offset) f: 물리 메모리에 저장되어 있는 각 페이지의 기준(시작) 주소

페이지 크기 하드웨어에 의해 정의된다 컴퓨터 구조에 따라 페이지 당 512(29) 바이트에서 16M bytes(216) 바이트 사이이며 2의 제곱의 형태를 취한다 (예) 논리 주소 크기: 2m, 페이지 크기: 2n 일 때 ⇒ (m­n) 비트는 페이지 번호를 나타내고, n 비트는 페이지의 변위를 나타낸다 m p d m-n n

구체적 사례 1

구체적 사례 2

페이징 기법의 특징 페이지 크기 및 경향 large page size  small page sizes 외부 단편이 없다 내부 단편 발생 : 평균적으로 프로세스 당 한 페이지 크기의 반 정도 페이지 크기 및 경향 현재 경향은 page의 크기가 커짐 (2k or 4k) large page size ◆ 장점  ① 페이지 테이블의 크기가 작아짐 ② 디스크 입출력이 효율적이다 ◆ 단점 : increased internal fragmentation  small page sizes   ◆ 장점 : 내부 단편이 감소한다 ◆ 단점 : 페이지 테이블이 커진다

프레임 테이블 운영체제가 유지해야 하는 테이블 운영체제가 물리 메모리의 할당에 대한 세부 정보를 유지하는 수단 ⇒ 할당된 프레임, 가용 프레임, 총 프레임의 수 등에 대한 정보를 유지 운영체제가 유지해야 하는 테이블 ① 페이지 테이블 ⇒ 하드웨어 지원 필요 ② frame 테이블 물리 주소의 할당에 대한 세부 사항을 기록 테이블의 각 entry는 해당 물리 프레임에 대한 정보를 기록한다  ⇒ each frame is free or allocated, if it is allocated, to which page of which process(es)

8.4.2 하드웨어 지원 (Hardware Support) 페이지 테이블 구조 ① 전용의 레지스터들로 구현 ② 메모리에 페이지 테이블 보관 ③ TLB 사용 (1) 전용의 레지스터들로 구현된 페이지 테이블 구성: 전용의 레지스터들로 구현된다 장점: 빠르다 단점: 페이지 테이블이 클 때 비싸다. (2) 메모리에 페이지 테이블을 구성하는 방법 구성: page table base register(PTBR)를 사용하여 메모리에 페이지 테이블을 구성 장점 : 페이지 테이블의 크기가 커도 된다. 단점 : 느리다 ⇒ 한 개의 바이트(정보)를 접근하는 데 두 번의 메모리 접근 필요(메모리에 있는 페이지 테이블 접근 + 실제 데이터 접근)

구성: 방법: 장점 : 빠르다 단점 : 고비용이다 히트율: (3) TLB를 사용하여 페이지 테이블을 구성하는 방법 구성:  ◆ Translation look-aside buffers(TLB)라 불리우는 특수한 소형 하드웨어 캐시를 사용하여 페이지 테이블 구성 ⇒ 매우 빠른 연관(associative) 메모리 ◆ TLB 내의 각 entry는 키(key)와 값(value)으로 구성 방법:  ① TLB에 페이지를 찾아달라는 요청이 들어오면 찾고자 하는 페이지를 동시에 여러 개의 내부 키와 비교한다 ② 페이지 번호가 같은 것이 발견되면 그에 대응하는 프레임 번호를 알려준다 장점 : 빠르다 단점 : 고비용이다 히트율:  ◆ 원하는 페이지 번호를 TLB에서 발견할 확률 ◆  연관 메모리 내의 레지스터의 수와 관련이 있다

실제 기억 장치 접근 시간(effective memory access time) 전용의 레지스터로 구성된 페이지 테이블 effective access time = 1 memory access time 메모리에 구성된 페이지 테이블 effective access time = 2 memory access time TLB로 구성된 페이지 테이블                            ≤ effective time ≤ * effective memory access time의 예(페이지 329)   1 memory access time    + TLB search time   2 memory access time    + TLB search time

8.4.3. 보호(Protection 보호 목적 ① 잘못된 실행 명령으로부터 보호 ⇒ 보호 비트 사용 ② illegal한 address로부터 보호 ◆ valid-invalid bit 사용 ◆ PTLR 사용(Page Table Length Register)

② 3 비트인 경우 : '1' → read, '2' → write, '3' → execute-only로 지정 (1) 보호 비트에 의한 보호 메모리 보호는 페이지 테이블에 저장되어 있는 보호 비트에 의해 이루어진다 (예)  ① 보호 비트가 1 비트인 경우 read and write(0) or read-only(1) : 만일 'write' 동작을 명령하면 운영체제에 하드웨어 trap이 발생한다 ② 3 비트인 경우 : '1' → read, '2' → write, '3' → execute-only로 지정 (2) 유효-무효 비트에 의한 보호 페이지 테이블의 각 entry에 ‘유효/무효’라는 하나의 비트 첨가 ① 비트값이 유효이면 관련된 페이지가 프로세스의 합법적인 페이지임을 표시 ② 무효이면 해당 페이지는 프로세스의 논리 주소 공간에 속하지 않음을 표시 운영체제는 이 비트를 이용해서 그 페이지에 대한 접근을 허용하든지 또는 허용하지 않든지 할 수 있다 ⇒ 비합법적인 주소는 유효/무효 비트를 사용하여 운영체제에게 트랩을 걸 수 있다

Page table length register(PTLR)에 의한 보호 페이지 테이블의 크기를 표시한다 발생한 논리 주소가 그 프로세스의 유효한 주소 범위에 있는 것인지를 확인하기 위해 PTLR의 값이 검사된다

8.4.4 공유 페이지 페이징 기법에서의 코드 공유 코드를 쉽게 공유할 수 있다 ⇒ 시분할 시스템에서 중요하다 공유가 필요한 중요한 프로그램들; 컴파일러, 윈도우 시스템, 데이터베이스 시스템 등 역 페이지 테이블은 공유 메모리 기법에서 사용되기 어렵다 ⇒ (이유) 메모리의 특정 프레임에 match되는 페이지의 번호가 프로세스들마다 서로 다른 수 있다

8.5 페이지 테이블의 구조 (Structure of the Page Table) 8.5.1 계층적 페이징(Hierarchical Paging) 계층적 페이징의 필요성 만일 논리 주소 공간이 매우 크다면, 페이지 테이블 자체도 대단히 클 수가 있다 (예) 4K 비트 크기의 페이지를 갖는 32 비트의 논리 주소 공간 각 프로세스에 대해서 220(1 million)개의 페이지 테이블 entry가 생성된다. 즉 220 × 4 bytes = 222 bytes(4Mbytes) 크기의 페이지 테이블이 필요하다

해결책 방법: 페이지 테이블을 작은 조각들로 나눈다 ⇒ 다단계 페이지 테이블 구성 종류: ① 2 단계 페이징 기법: 페이지 테이블 자체를 페이징한다 예) VAX

(예) SPARC architecture(with 32-bit addressing) ① 3 단계 페이징 기법 (예) SPARC architecture(with 32-bit addressing) ② 4단계 페이징 기법 ◆ 32-bit Motorola 68030 architecture ◆ converting a logical address to physical one ⇒ four memory accesses 다단계 페이징 기법에서 실제 접근 시간의 예 가정: 98% hit ratio를 가진 cache를 썼을 때 : 실제 접근 시간 = 0.98 × 120 + 0.02 × 520  = 128 nanoseconds. ⇒ 28% slow down

8.5.2 해시된 페이지 테이블 해시 테이블(hashed page table) 해시 테이블을 이용한 주소 변환 과정 가상 주소를 hash로 사용하는 hashed page table을 사용한다(주소 공간이 32비트 보다 큰 경우에 많이 사용) 해시 페이지 테이블의 각 원소는 연결 리스트를 가지고 있으며 충돌을 일으켜서 모두 이 곳으로 hash되는 element들로 구성된다 각 원소는 세 개의 field를 가진다; (a) 가상 페이지 번호, (b) 사상되는 페이지 프레임 번호, (c) linked list 상의 다음 element를 가리키는 포인터 해시 테이블을 이용한 주소 변환 과정 ① 가상 주소 공간으로부터 페이지 번호가 오면 그것을 hashing한다 ② hashing 결과 해시 테이블에서 linked list를 따라가며 첫 번째 element와 virtual page number를 비교해본다 ③ 다음의 두 가지 중 한 가지를 실행한다 ◆ match되면 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다 ◆ match가 안되면 linked list의 다음 element로 가서 동일한 일을 반복한다

페이지 테이블 기법 단점: 각 페이지 테이블은 수백만의 entry를 가질 수 있다 ⇒ 물리 메모리를 불필요하게 소비할 수 있다  페이지 테이블 기법 단점: 각 페이지 테이블은 수백만의 entry를 가질 수 있다 ⇒ 물리 메모리를 불필요하게 소비할 수 있다 해결방법 : 역 페이지 테이블을 이용한다

8.5.3 역 페이지 테이블 (Inverted Page Table) inverted page table의 entry 수=frame 수

역 페이지 테이블의 구성 : 각 entry는 페이지를 소유하고 있는 프로세스의 정보와 함께 실제 물리 메모리에 저장되어 있는 페이지의 논리(가상) 주소로 구성된다 단지 한 시스템에 한 개의 페이지 테이블이 존재한다 물리 메모리에 저장되어 있는 각 페이지에 대해 한 개의 entry만이 존재한다 logical address의 구성 ⇒ <process-id, page-number, offset>

8.6 세그먼테이션 8.6.1 기본 방법 사용자가 메모리를 보는 관점 가변 길이를 갖는 세그먼트들의 집합 세그먼트들 사이의 순서는 무시 (예) 프로그램의 사용자 관점

세그먼테이션 기억 장치에 대한 사용자의 관점을 지원하는 메모리 관리 기법 논리 주소 공간은 세그멘트들의 집합이며 각 세그멘트는 이름과 크기(길이)를 가지고 있다 논리 주소는 세그먼트 번호(이름)와 세그먼트 내의 변위로 표시된다 logical address 구성 ⇒ <segment-number, offset>

8.6.2 하드웨어 세그먼트 테이블 과정: 필요성: 2 차원의 사용자 정의 주소를 1 차원의 물리 주소로 사상시켜야 한다 구성: 각 세그먼트 테이블의 entry는 세그먼트 기준(base)과 세그먼트 한계(limit)로 구성된다 과정:  ① 논리 주소는 세그먼트 번호(s)와 그 세그먼트 내에서의 변위(d)로 구성된다 ② 세그먼트 번호(s)는 세그먼트 테이블에 대한 색인(index)으로 사용된다 ③ 다음의 동작 중 하나를 실행한다 ◆ 변위 d가 0과 세그먼트 한계(limit) 사이의 범위에 있으면 해당 세그먼트 번호가 가리키는 세그먼트 테이블의 entry의 기준값과 변위가 더해져서 실제 물리 주소가 생성된다 ◆ 변위(d)가 범위 밖의 값이면 트랩(trap)이 발생된다

세그멘트 테이블의 구현 ① 전용의 레지스터를 사용하여 테이블 구성 ⇒ 접근이 빠르다 ② 메모리에 테이블 구성 ◆ STBR(segment table base register) : 세그먼트 테이블의 시작 주소를 저장 ◆ STLR(segment table length register) : 세그먼트 테이블의 길이를 저장 ◆ 한 개의 논리 주소마다 두 번의 메모리 접근 필요 ⇒ 2 배의 속도 저하 ◆ [해결책] 최근에 사용된 세그먼트 테이블의 entry들을 저장하는 연관 레지스터 set을 사용한다 ③ 연관 레지스터를 사용하여 상대적으로 작은 레지스터 집합으로 구성