제 8장 기억장치 관리 (Memory Management) 8.1 배경 8.1.1 주소 바인딩 (Address Binding) 바인딩: 한 주소 공간에서 다른 주소 공간으로의 사상 컴파일 시간, 적재 시간, 실행 시간 (그림 8.1) 8.1.2 동적 적재 (Dynamic Loading) 루틴이 실제로 호출될 때 까지는 디스크에 존재 예) 오류 처리 루틴 (매우 가끔 발생, 많은 양의 코드) OS 지원 없이 프로그래머가 구현 가능

8.1.3 동적 연결 (Dynamic Linking) 동적 연결 : 실행 시까지 메모리 상주 라이브러리 연결을 보류 정적 연결 : 이미지 내에 포함된 라이브러리의 복사본에 의한 자원 낭비가 문제 스터브(stub) : 이미지 당 하나, 라이브러리를 찾거나 적재 => 공유 라이브러리 8.1.4 중첩 (Overlay) 한 프로그램 내에서의 기억 장치 공유 (그림 8.2) 예) 중첩 A: 심볼 테이블(70K), 공통 루틴(30K), 패스 1(70K) 중첩 B: 심볼 테이블(70K), 공통 루틴(30K), 패스 2(80K) 중첩 구동기(overlay driver)가 추가로 필요(분기에 의해 실행) 적재는 빠르지만 실행은 늦어진다(중첩을 위한 입출력) 프로그래머의 부담이 크다

8.2 논리적/물리적 주소 공간 8.3 스웨핑 (Swapping) 논리적 주소(CPU 주소) vs. 물리적 주소(실제 주소) 실행시간 바인딩(동적 재배치) 기법: 두 주소가 달라짐 이 때의 논리 주소를 가상 주소(virtual address)라 한다 가상 주소에서 물리 주소로 사상하는 예 -> 기억장치 관리기(MMU) (H/W) (그림 8.3) 8.3 스웨핑 (Swapping) 주기억 장치와 보조 기억장치간 프로세스 이동 예) 방금 끝났거나 우선순위가 낮은 P를 swap(roll)-out CPU스케쥴러 <-> 기억장치 관리자(S/W) (그림 8.4)

바인딩에 따라 swap(roll)-in 주소가 달라짐 실행 시간 바인딩 => 이전 위치와 다른 위치로 swap-in 디스패쳐는 다음 P가 MM에 없고 빈 공간도 없으면, P를 하나 내보내고 해당 P를 불러온다 문맥 교환 시간 증가: 스웹시간(전송 시간 + 지연 시간) 주의: 입출력 계류 중인 P 수정된 스웨핑 UNIX: 평소에는 안하다가 P가 많아지면 스웹 시작 Windows: 새 P를 위한 공간이 없으면 스웹 사용자가 시기 결정

8.4.1 단일 분할 할당 (Single-Partition Allocation) 8.4 연속 할당 8.4.1 단일 분할 할당 (Single-Partition Allocation) 디스패쳐가 두 ‘레지스터’(재배치/기준, 한계) 설정 프로세스를 보호 MMU가 동적으로 논리 주소를 사상 (그림 8.6) OS의 크기가 가변적(매우 가끔 쓰는 루틴 포함)이거나 프로세스가 하나일 때 유용 8.4.2 다중 분할 할당 (Multiple-Partition Allocation) 여러 P를 MM으로 적재할 필요가 있다 가장 간단한 방법: 고정 크기 분할, 분할 당 1 개의 프로세스

충분한 크기의 블록이 여럿일 때 선택하는 방법 가변 크기 분할 (그림 8.7, 8.8) OS가 가용 구간 ‘테이블’(이용 가능한 블록 크기 목록) 유지 기준 레지스터(base register)도 필요 입력 큐(MM 차지를 위한) 유지 => 스케쥴로 순서 배치 충분한 공간이 없으면 => 대기 혹은 입력 큐 조사 P가 선택되면 충분한 크기의 블록을 찾아 할당 여분 공간은 남겨둠 중간 중간에 블록 분리/결합 충분한 크기의 블록이 여럿일 때 선택하는 방법 최초 적합(First-fit), 최상 적합(Best-fit), 최악 적합(Worst-fit)

8.4.3 외부 및 내부 단편화 외부 단편화(external fragmentation) 전체 가용 공간이 충분하지만 연속적이지 않은 현상 해결책: 압축(compaction) (그림 8.10) 압축은 재배치가 동적인 경우에만 가능 압축 시 코드 절약 방법: P 이동이 필요하면 일단 swap-out 내부 단편화: 블록 크기와 요구량이 미세한 차이(분리할 경우 비용이 더 듬) => 내부 조각을 버려둠 (그림 8.9)

8.5 페이징 (Paging) 8.5.1 기본 방법 외부 단편화의 또 다른 해결 방법 고정된 크기의 블록 (2~4Kbyte) (논리적) 페이지(page) -> 프레임(frame) (물리적) 논리 주소 -> -> 주소 변환 하드웨어 + 해당 P의 PT -> 물리 주소 (그림 8.12, 8.13, 8.14) 페이지 번호 페이지 오프셋 p d m - n n 페이지 테이블(Page Table)

새 P -> 프레임 할당 -> PT 갱신 (그림 8.15) 페이징 자체가 동적 재배치 외부 단편화 없고, 내부 단편화 있다 새 P -> 프레임 할당 -> PT 갱신 (그림 8.15) 할당시 프레임 테이블 사용 사용자 관점에서는 ‘연속된 기억장치를 혼자 사용’ 문맥 교환 시 디스패쳐가 PCB에 기록되어 있는 pointer를 사용하여 해당 프로세스의 PT로 교체 문맥 교환 시간 증가

8.5.2 페이지 테이블의 구조 8.5.2.1 하드웨어 지원  전용 레지스터 집합: 페이지 개수 만큼 페이지 테이블 기준 레지스터 (PTBR:page-table base register) PT를 주기억장치에 저장 (항목 수가 너무 많으므로) 문맥 교환시 이 레지스터(1개)만 변화시킴 문제점 : 한 word 접근을 위해 기억장치 2번 접근 보완책 연관 레지스터(associative register) / 보조 예비 기억장치(translation look-aside buffers(TLB)) 고속, 각 레지스터는 ‘키 : 값’ (그림 8.16) 적중률(hit ratio) : 연관 레지스터에서 발견되는 비율 

8.5.3 다단계 페이징 (Multilevel Paging) 8.5.2.2 보호 (Protection) 유효-무효(valid-invalid) 비트 (그림 8.17) 페이지 테이블 길이 레지스터(PTLR)를 사용하기도 함: 안 쓰는 페이지가 많은데 비트를 모두 기록하는 것은 낭비 8.5.3 다단계 페이징 (Multilevel Paging) 현대 컴퓨터: 매우 큰 논리 주소 공간(232~264) 예) 논리 주소 공간=32bit, 페이지 크기=4K ( 212 ) PT 항목수 = 100만 ( 220 ) PT 각 항목의 크기 = 4byte, PT 전체 크기 = 4Mbyte => 너무크다  32 - 12

2단계 페이징 기법(two-level paging scheme) (그림 8.18) PT를 쪼개어 각각을 페이지에 저장(PT로만 채워진 페이지) 64비트의 경우 3단계 페이징  페이지 번호 페이지 변위 p1 p2 d 10 10 12  바깥 페이지 안쪽 페이지 페이지 변위 p1 p2 d 42 10 12 2번째 바깥 페이지 바깥 페이지 안쪽 페이지 변위 p1 p2 p3 d 32 10 10 12

8.5.4 역 페이지 테이블 (Inverted Page Table) 실제 페이지(프레임) 하나에 하나의 테이블 항목 시스템에는 단지 하나의 PT만 존재 (그림 8.20) 테이블 저장량 감소, 테이블 탐색 시간은 증가 페이지 부재 (스웨핑 등으로) 시 문제 발생 외부 PT (P당 하나씩) 사용 => swap 8.5.5 공유 페이지 (Shared Pages) 재진입 코드(pure code) : 실행 도중 결코 변하지 않음 그림 8.21 (데이터는 각자 보유) <-> Thread (데이터까지 공유)

8.6 세그먼테이션 (Segmentation) 8.6.1 기본 방법  사용자의 입장(개념)에 더욱 가까운 주소 방식 프로그램은 가변 크기 세그먼트의 모임, 순서 무의미 위치의 기준은 해당 세그먼트의 시작 위치 Sqrt 명령의 5번째 명령문 논리공간 = 세그먼트(이름 + 길이)의 집합 (그림 8.22) 주소 = 세그먼트의 이름(번호) + 변위 페이징에서는 구분 없음(하나의 주소) 하드웨어가 처리, 사용자(컴파일러)는 모름 8.6.2 하드웨어 (그림 8.23, 8.24)

8.6.4 보호(Protection)와 공유(Sharing) 8.6.3 세그먼트 테이블의 구현 레지스터 집합 STBR, STLR : 연관 레지스터로 보완 (PTBR, PTLR처럼) 8.6.4 보호(Protection)와 공유(Sharing) 보호 비트(읽기/쓰기/실행 전용 표현), 배열 관리 세그먼트의 특별한 장점 세그먼트는 스스로 수정하지 않는다 공유 세그먼트 수준에서 공유 (그림 8.25) 편집기 코드(공유) + 각자의 독립 세그먼트(지역 변수) 함수 Sqrt 공유

s1 s2 d1 d2 8 10 6 10 8.6.5 단편화 (Fragmentation) 8.7 페이지화된 세그먼테이션 외부 단편화 => 압축 필요(가변 크기 분할 기법에서처럼) 8.7 페이지화된 세그먼테이션 세그먼트 테이블 오버헤드 / 외부 단편화오버헤드를 줄이기 위한 대안 예) 그림 8.26, 그림 8.27 세그먼트 번호 변위 s1 s2 d1 d2 8 10 6 10 세그먼트 테이블 오버헤드 감소 외부 단편화 감소