제 9 장 가상기억장치 (Virtual Memory) 프로세스가 기억장치에 없어도 실행이 가능한 기법 장점: 사용자 프로그램이 실제 기억장치보다 클 수 있다 단점: 구현이 어렵고 성능이 저하될 우려가 있다 9.1 배경 (Background) 프로그램 전체가 한꺼번에 요구되지는 않는다 오류 처리 코드: 매우 가끔 필요 배열, 테이블: 실제 필요량보다 크게 선언 프로그램 선택사항(option): 사용되지 않는 기능이 많음

부분 저장(기억장치에) 실행의 장점 물리 기억장치와 논리 기억장치를 분리 기억 공간의 크기 제약이 없어진다 같은 시간에 더 많은 수의 프로그램을 수행가능 적재(load)/스웹(swap)을 위한 I/O 시간 감소 물리 기억장치와 논리 기억장치를 분리 프로그래머는 기억장치 크기와 중첩(overlay)등을 고민하지 않음 (그림 9.1)

9.2 요구 페이징 (Demand Paging) 요구 페이징 순수 요구 페이징 필요한 페이지만 주기억 장치에 적재 (cf. 스웨핑-그림 9.2 ) 유효 무효 비트가 무효(invalid)면, 타당하지 않거나(주소 공간에 포함되지 않은 페이지), 타당하지만 현재 ‘디스크’에 있음을 의미 무효 페이지를 접근하려 하면, 페이지 부재(page fault) 트랩(trap) 발생 (그림 9.4) 순수 요구 페이징 최초 실행 시 매번 페이지 부재에 의해 페이지를 적재 요구될 때까지 결코 페이지를 기억장치에 들이지 않는다 H/W에 의해

9.3 요구 페이징의 성능 유효 접근 시간 = (1-p)  ma + p  페이지 부재 시간 페이지 부재 시간의 주 구성 요소 1. 페이지 부재 인터럽트의 처리 2. 페이지를 디스크로부터 판독 3. 프로세스 재시작 페이지 부재 횟수는 성능을 심각히 저하시킬 수 있다 예) 접근 시간 증가를 10% 미만으로 유지하려면... ma: 100nsec, 페이지 부재 시간: 25msec 110 > 100 + 25,000,000  p, p < 0.0000004 => 2백5십만번 중 한번 이하로 부재가 발생해야... 그러나 전체 P를 다 읽고 시작하는 것보단 나을 수 있다 페이지 부재 확률

9.4 페이지 교체 (Page Replacement) 새 페이지를 위한 가용 공간이 없으면 페이지 교체 필요 페이지 교체 과정 1. 디스크에서 페이지 위치 확인 2. 가용 프레임 찾기 a. 가용 프레임이 있으면 사용 b. 없으면 희생 프레임 선정(페이지 교체 알고리즘) c. 희생 페이지를 디스크에 기록하고, PT/FT 수정 3. 가용 프레임으로 페이지 판독, PT/FT 수정 4. 사용자 프로세스 재시작 수정(dirty) 비트: 페이지가 변화(기록)되었는지의 여부 수정되지 않았다면 디스크로 기록할 필요 없음

9.5 페이지 교체 알고리즘 (Page Replacement Algorithm) 가장 낮은 페이지 부재율 달성이 목표 참조열(reference string): 평가의 기준 예) 참조주소 페이지당 100바이트 참조열 이후의 평가 기준 프레임 수: 3개 참조열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 0100, 0432, 0101, 0612, 1012, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

9.5.2 최적 페이지 교체 알고리즘 (Optimal Algorithm, OPT)    9.5.1 선입선출 (FIFO) 알고리즘    가장 오래된 페이지를 교체 (그림 9.8) 프로그램하기 쉽다 Belady의 이상 현상(abnomaly): 프레임 수가 증가함에 따라 오히려 페이지 부재가 증가 (그림 9.9) => FIFO의 문제 9.5.2 최적 페이지 교체 알고리즘 (Optimal Algorithm, OPT)    가장 낮은 부재율, 이상 현상 없음 "앞으로 가장 오래 사용되지 않을 페이지를 교체하라” (그림 9.10) 구현 힘듬: 미래의 지식 요구 => 비교 기준으로 사용 (cf. SJF)

9.5.3 LRU (Least Recently Used) 알고리즘    가까운 미래의 근사치 대신 가장 최근의 과거 정보 활용 오랫동안 사용되지 않은 페이지를 교체 과거에 대한 OPT FIFO보다 낫지만 구현이 문제: 최후 사용 시간의 순서 결정 계수기(counter) : 페이지 테이블 항목에 참조 시간 기록 필드 유지 비용, 클럭 비용 스택(stack) (페이지 번호의) : 페이지가 참조될 때마다 스택의 Top으로 이동 이중 연결 리스트로 구현 (그림 9.12) Belady이상 현상 없음 하드웨어 지원 필요 (없으면 인터럽트가 너무 많음)

9.5.4.1 참조 비트(reference bits)가 추가된알고리즘 9.5.4 LRU 근접 알고리즘 페이지의 참조 비트(reference bit) (h/w에 기반)를 활용 9.5.4.1 참조 비트(reference bits)가 추가된알고리즘 일정 간격으로 참조 비트를 기록(예: 11010010) 타이머 인터럽트 -> 최상위 비트 교체 & shift-right 9.5.4.2 2차 기회(Second Chance) 페이지 교체 알고리즘 참조 비트가 오직 하나, circular 큐 (clock알고리즘) (그림 9.13) 참조 비트가 1인 경우만 한 번 기회를 더 줌 1이면 0으로 바꾸고 한 바퀴 돌고 나서도 0이면 쫒아냄 모든 비트 1이면 선입선출(FIFO) 처리

9.5.4.3 2차 기회 개선 (Enhanced Second Chance) 알고리즘 앞과 유사(순환)하지만 “참조 비트와 수정 비트 쌍” 사용 (0,0), (0,1), (1,0), (1,1)의 4등급으로 구분 참조비트가 1:최근 사용, 수정비트가 1:디스크 기록 필요 최저 등급 중 처음 만난 페이지를 교체 9.5.5 계수 알고리즘 (Counting Algorithm) 각 페이지를 참조한 숫자에 대한 계수기 유지 LFU 알고리즘: 최소 빈도 페이지를 교체 문제:초기에만 집중 사용 해결:시간에 따라 지수적으로 계수 감소 MFU 알고리즘: 최대 빈도 페이지를 교체(최신이므로) 둘다 어렵고 성능도 OPT에 접근 못함

9.5.6 페이지 버퍼 알고리즘 (Page Buffering Algorithm) 페이지를 내보내는 시간을 줄이자! 1. 희생될 프레임을 디스크로 보내기 전에 저장소(pool)에 저장: 페이지가 나가기 전에 프로그램을 빨리 재시작 가능 2. “변경”된 페이지의 리스트 유지 페이지 장치가 쉴 때마다 변경된 페이지를 디스크에 기록하고 변경 비트를 0으로 reset 3. 저장소의 각 프레임에 어떤 페이지가 있는지를 기억 디스크까지 가지 않고 저장소에서 직접 다시 사용 => FIFO 보완 방법

9.6 프레임의 할당 9.6.1 최소 프레임 수 여러 프로세스를 한정된 기억장치에 어떻게 배분? 하나의 명령어가 참조할 수 있는 모든 페이지를 수용해야 (페이지 부재 시 명령어를 처음부터 다시 시작하지 않게) 최소 프레임 수는 명령어 집합 구조(컴퓨터 구조)에 의해 정의 간접 참조가 문제 (예: move의 경우 6프레임 필요) 무한적 간접 참조 가능: 횟수 제한(계수기)

9.6.3 전역 대 지역 할당 (Global Versus Local Allocation) 9.6.2 할당 알고리즘 균등 할당, 비례 할당 (ai = si/S X m) 9.6.3 전역 대 지역 할당 (Global Versus Local Allocation) 지역 교체: 각 P가 자신에 할당된 프레임 중에서만 선택 가능 전역 교체: 자신의 페이지 부재율 조정 불가 (다른 P의 영향) 그러나 더 좋은 성능, 더 일반적

9.7 스레싱 (Thrashing)    한 P의 페이지 부재-> 다른 P의 페이지 부재 -> CPU 이용률 저하-> 새 P 시작(다중 프로그래밍 정도(degree) 증가)-> 더 심각한 이용률 저하 ->스레싱 (그림 9.14) 완화 방안: 지역/우선순위 교환 알고리즘 사용 여전히 개별 P의 스레싱은 가능->유효 접근 시간 증가 방지 방안: 작업 집합 (working set) 실행의 지역성 모델 (locality model) 지역: 실제로 함께 사용되는 페이지의 집합 프로그램은 여러 지역으로 구성(예: 서브루틴) 지역은 겹칠 수 있다 현재의 지역보다 많은 수의 프레임을 할당해야...

9.7.2 작업 집합 (Working Set) 모델 9.7.3 페이지 부재 (Page-Fault) 빈도 작업 집합: 최근  번의 참조에 포함된 페이지의 집합 : 작업 집합 창 (그림 9.16) “지역”의 근사값 “D > 유효 프레임의 수” 이면 스레싱 발생 D = WSSi (WSSi=작업 집합의 크기) 중지할 P를 선택하고 다른 P에 프레임 분배 스레싱을 방지하면서 다중 프로그래밍 정도를 높임 어려운 점: 작업 집합의 추적=>스레싱의 직접 조절은 힘듬 9.7.3 페이지 부재 (Page-Fault) 빈도 페이지 부재율의 상/하한을 정하여 직접적으로 페이지 부재율을 조절

9.8 기타 고려사항 9.8.1 프리페이징 (Prepaging) 9.8.2 페이지 크기 프로세스 시작 시 참조가 예상되는 페이지들(예: 작업 집합)을 한꺼번에 가져옴 프로세스 초기의 페이지 부재 집중 현상을 완화 9.8.2 페이지 크기 “페이지 테이블, 전송률, 페이지 부재”의 관점에서는 페이지가 클수록 좋다 “내부 단편화, 지역성”의 관점에서는 작을수록 좋다 최근 추세는 페이지가 커지는 방향 고용량, 고속화=>단편화 등은 별로 문제되지 않음 9.8.3 역 페이지 테이블 (8.5.4 참조)

9.8.5 입출력 상호 잠금 (Input/Output Interlock) 9.8.4 프로그램 구조 자료 구조/프로그래밍 구조를 조정=>지역성 증가 예) 배열, 적재기(서로 자주 호출하는 모듈들을 같은 페이지에) LISP는 포인터가 많아 (PASCAL보다) 참조 지역성이 낮다 9.8.5 입출력 상호 잠금 (Input/Output Interlock) 문제 상황: 어떤 P가 I/O 큐에 있는 동안 I/O버퍼에 해당되는 페이지가 다른 P에 의해 교체됨 (그림 9.18) 해결안: 1.사용자 기억장치에 대해서는 I/O를 수행하지 않음 사용자 기억장치-> 시스템 기억장치(복사)-> I/O 장치 오버헤드가 너무 크다 2.잠금 비트(lock-bit): I/O 관련 페이지는 교체 않함

9.8.6 실시간 처리 (Real-Time Processing) 또 다른 문제 상황 예: 낮은 우선순위 P가 쓰려고 방금 가져온 페이지를 높은 우선순위 P가 교체하는 현상=>한번도 사용되지 않은 새 페이지는 교체하지 않음 9.8.6 실시간 처리 (Real-Time Processing) 가상 메모리는 실시간 처리에 부적합 결합 예: Solaris 2=> 실시간 P에 페이지 잠금 허용 9.9 요구 세그먼테이션 (Demand Segmentation) 페이지 대신 세그먼트 단위로 메모리를 교체: OS/2

제 10 장 파일 시스템 인터페이스 10.1 파일 개념 10.1.1 파일 속성 10.1.2 파일 조작 파일 시스템 = 파일 집합체 + 디렉토리(분할) 구조 10.1 파일 개념 파일: 보조기억장치에 기록된 연관된 정보의 집합체 보조기억장치의 가장 작은 논리적 할당 요소 프로그램 + 자료(data) 10.1.1 파일 속성 이름, 형태, 위치, 크기, 보호, 시간/날짜/사용자 식별 10.1.2 파일 조작 생성: 공간 찾기, “디렉토리”에 파일 항목 생성 파일이 존재하는 장치와 위치에 대한 포인터 파일의 이름과 위치 기록

개방(open) : 개방 파일 테이블(open-file table)   기록: 시스템 호출 (예: write(fname, info) ) 판독 재설정(reposition): seek 삭제(공간 회수, 디렉토리 항목 제거) , 절단(길이만 0) 개방(open) : 개방 파일 테이블(open-file table)   반복적인 디렉토리 탐색을 피함 개방 시 디렉토리 항목을 open-file table로 복사 현재 파일 포인터/파일 개방 카운트/디스크 위치 기억장치 사상(memory mapped) 파일   (그림 10.1) 현재 파일 위치 포인터(current file position pointer) 사용

10.1.3 파일 형태 10.1.4 파일 구조 대개, 파일 이름으로 파일의 형태를 구분 효율적으로 파일을 다룸 (그림 10.2) 10.1.4 파일 구조 파일의 구조를 구분할 필요 (예: .hwp <-> .dat) .hwp의 앞 부분에 자동 프로그램 연결을 위한 정보 포함 UNIX의 경우에는 구조 구분을 하지 않음 구조 구분이 적으면 프로그래밍이 번거롭고, 많으면 운영체제의 크기가 증가

10.1.5 내부 파일 구조 파일(논리 레코드의 집합) -> “블록(block)” -> 디스크 10.2 접근 방법 10.2.1 순차 접근 테이프 모델 (그림 10.3) 10.2.2 직접 접근 디스크 모델 블록 13 판독->블록 7기록->… 항로편 713의 여분 좌석수를 713번 블록에 저장: hash 사람 이름 DB에서 (사람 이름 to 블록번호) 조합(pack)/분해(unpack)

10.2.3 기타 접근 방법 10.3 디렉토리 구조 색인(index): 필요한 블록에 대한 포인터 (그림 10.5) 2차 색인: IBM의 ISAM(Indexed Sequential Access Method) 10.3 디렉토리 구조 분할요소(partition): 디렉토리 구성의 논리적 단위 (그림 10.6) 디렉토리상 동작 파일의 탐색/생성/삭제/재명명/traverse(훑기), 리스트(dir) 디렉토리의 논리적 구조 1단계/2단계/트리/비순환 그래프/일반 그래프 (그림 10.7~10.11)

10.4 보호 (가장 일반적이고 쉬운 방법은 “복사”) 10.4.1 접근의 형태 10.4 보호 (가장 일반적이고 쉬운 방법은 “복사”) 10.4.1 접근의 형태 다른 사용자의 파일 접근 형태를 제한 판독/기록/실행/추가(append)/삭제/리스트 10.4.2 접근 리스트와 그룹 접근 리스트: 파일별로 접근 가능한 사용자들 기록 (비효율적) 대안1:소유자(owner)/그룹/모든 사람(others)으로 구분 대안2: 암호 => 파일별/디렉토리별? all or nothing/다중암호? 10.5 일관성 의미 구조 (다수 사용자가 공유 파일 동시 접근) UNIX: 한 사용자가 개방된 파일에 기록하면 동시에 다른 사용자가 볼 수 있음 (단일 영상) <-> Andrew(세션 의미 구조) cf. HWP