18. 분산 조정(Distributed Coordination) ▶ 이 장의 목표 - 중앙 집중 동기화 방법을 분산 환경으로 확장하는 방법 - 분산 시스템에서의 교착 상태 취급 방법 18.1 사건 순서화(Event Ordering) ▶ 분산 시스템: 공유기억장치나 클록 없음 → 사건의 순서 예측 어려움 * 사건 발생전 관계(happened-before relation): 분산 시스템에서 사건의 부분적인 순서를 나타냄 → 전체 사건의 순서를 결정하는 분산 알고리즘 소개 18.1.1 사건 발생 전후 관계(Happened-Before Relation) ▶ 사건 발생 전후 관계의 정의 - 프로세스내의 모든 사건들은 순차적임 - 인과 관계 법칙에 의해 메시지는 송신되어야 수신될 수 있음 * “→”: 사건 발생 전후 관계 표시 - 비반사적 부분 순서(irreflexive partial ordering) ex) A→B→A 허용 안함 ① A와 B가 동일 프로세스내의 사건이고, A가 B보다 먼저 수행된다면 A→B이다. ② A가 한 프로세스에 의해 메시지를 송신하는 사건이고, B가 다른 프로세스에 의해 그 메시지를 수신하는 사건이라면 A→B이다. ③ A→B이고 B→C이면, A→C이다. * 두 사건 A와 B가 → 관계가 없는 경우, 병행적으로 수행되었다고 말할 수 있음 ▶ 병행성과 사건 발생 전후 관계의 표현: “시공간 다이어그램(space-time diagram)” [그림 18.1] 세 개의 병행 프로세스들에 대한 상대적인 시간 - 수평 방향: 공간, 즉 서로 다른 프로세스 혹은 프로세서들 - 수직 방향: 시간의 흐름 * A에서 B로 또는 B에서 A로의 경로가 없으면 사건 A와 B는 병행성이 있음 (→ 관계의 예) (병행 관계의 예) , , , (∵, ) , 18.1.2 구현(Implementation) ▶ 전역 순서화(global ordering) 정의: 각 시스템 사건을 타임스탬프(time stamp)에 연관시키는 방법 → 임의의 쌍 A와 B에 대해 A→B이면 사건 A의 타임스탬프는 사건 B의 타임스탬프보다 작다. ▶ 시간 표식 순서화 기법 ① 각 프로세스 마다 논리적 클록 를 정의: 프로세스내의 사건마다 증가하는 계수기로 구현 → 동일 프로세스내의 임의의 두 사건에 대해 전역 순서화 요구를 만족시킬 수 있음 ex) 내의 사건 A가 사건 B보다 먼저 발생: ② 그러나, 프로세스간에는 전역 순서화 요구를 만족한다고 보장 못함 ex) (사건 A) 이 에게 메시지 보냄: (사건 B) 가 그 메시지를 받음: → 의 논리적 클록이 보다 느릴 수 있기 때문: A→B 만족 못함 ③ 이를 해결하기 위해, 프로세스의 논리적 클록의 현재 값보다 큰 타임스탬프를 갖는 메시지를 받게 되면, 논리적 클록을 증가시키는 것이 필요함 → (사건 B) 프로세스 가 타임스탬프 인 메시지를 받았을 때: ex) ④ 타임스탬프 순서화 기법으로 두 사건 A, B의 타임스탬프가 같으면, 병행성 있음을 의미함 → 전역 순서화를 위해, 프로세스 식별 번호를 사용할 수 있음 18.2 상호 배제(Mutual Exclusion) ▶ 분산 환경에서의 상호배제 구현 (가정) 각각 서로 다른 프로세서에 상주하는 n개의 프로세스로 구성되는 시스템 18.2.1 중앙 집중형 접근(Centralized Approach) ▶ 개념: 시스템 내의 프로세스 중 하나가 임계구역의 출입구를 관리하는 조정자 역할을 수행 “조정자(coordinator)” ① 요청 메시지 프로세스 Pi 임의의 스케줄링 알고리즘 사용가능 ④ if 해제시 선택 ③ if 사용중 대기시킴 ⑤ 응답 메시지 ② 검사(사용중 or 유휴중) ⑦ 해제 메시지 요청큐 임계구역 ⑥ 사용 ▶ 특성 - 상호 배제 보장 - 조정자의 스케줄링 알고리즘이 공정(FCFS)하면 기아 상태도 발생하지 않음 - 조정 프로세스의 고장 시 새로운 프로세스가 대신하게 됨 → 18.6절 참조 18.2.2 완전 분산형 접근(Fully Distributed Approach) ▶ 사건 순서화 정책에 기반을 둔 알고리즘: 임계 구역에 대한 모든 요청을 전역 순서화하고 FCFS 순서로 프로세스를 처리하는 방법 아직 응답을 안한 요청 메시지 리스트 ④ 임계구역에서 나온 후 요청 리스트에 있는 모든 프로세스에 응답 ③ 모든 프로세스로부터 응답 받으면 사용 ① 임계 구역 요청 시, - 시간 표식 TS를 생성하고 - 요청 메시지 를 자신을 포함한 모든 프로세스에게 전송 프로세서 다른 모든 프로세스들 임계구역 요청 리스트 ② 검사 (사용안함/사용중/대기중) ↙ ↓ ↘ 즉시응답 응답보류 타임스탬프 ↓ 참조 사용 후 응답 ▶ 요청 메시지의 회신/보류 결정 요령: ②에 해당 ⑴ 프로세스 가 임계 구역 내에 있으면, 회신 보류 → 사용 후 회신 ⑵ 가 임계 구역에 들어가길 원치 않으면, 즉시 응답 ⑶ 가 임계 구역에 들어가기 위해 대기중인 경우, → 상대 프로세스 의 요청의 타임스탬프와 자신의 타임스탬프를 비교: - 상대의 타임 스탬프가 작으면, 상대가 먼저 요청한 것이므로 즉시 응답 - 그렇지 않으면, 회신을 보류하고 요청 큐에 추가 ▶ 특성 - 상호 배제 보장 - 교착 상태 미발생 보장 - 타임스탬프 순서로 스케줄되므로(FCFS 방식), 기아 상태 미발생 보장 - 임계 구역 출입을 위한 메시지 수: 2×(n-1) ← “최소 메시지 수” ▶ (예) 프로세스 , , 로 구성된 시스템 1) 과 의 요청 발생: 각자 다른 모든 프로세스에게 요청 전송 → , 2) 는 즉시 회신 3) 은 요청의 타임스탬프(4)가 요청의 타임스탬프(10)보다 작으므로 즉시 회신 은 요청의 타임스탬프(10)가 요청의 타임스탬프(4)보다 크므로 회신 보류 4) 는 과 로부터 회신을 받았으므로 임계 구역에 들어감 5) 는 임계 구역에서 나오면 에게 회신을 보내 임계 구역에 들어 갈 수 있게 함 ▶ 모든 프로세스가 참여하는 방식에서 비롯되는 단점 (1) 각 프로세스는 다른 모든 프로세스를 구별해야 함 → 새로운 프로세스의 가담 시, - 그룹내의 모든 다른 프로세스의 이름을 알아야 함 - 자신의 새로운 프로세스 이름을 모두에게 알려야 함 (2) 임의 프로세스의 고장(응답 못함)은 전체 과정을 파괴시킴 → 체제 내의 모든 프로세스의 상태를 계속 조사해야 함 - 고장 발견시 - 해당 프로세스에 요청 메시지를 보내지 않음 - 회복 발견시 - 해당 프로세스에 대한 재 가담 프로시저를 호출함 18.2.3 토큰 패싱 접근(Token-Passing Approach) ▶ 개념: 시스템내의 프로세스들간에 토큰을 순환시키고, 유일하게 존재하는 토큰을 소유한 프로세스만이 임계 구역에 들어가게 하는 방법 → 토큰(token): 시스템에서 전달되는 일종의 특정한 메시지 형태 - 임의의 프로세스가 토큰을 받으면, 그 토큰을 보유하고 해당 임계 영역에 진입할 수 있음 - 그 프로세스가 임계 구역을 나오면, 토큰을 다시 전송함 - 토큰을 받은 프로세스가 임계 구역에 진입하는 것을 원치 않으면, 그 토큰을 단지 이웃에 전송함 ▶ 링 구조 시스템의 경우 1) 특성 - 논리적으로 구현 가능: 물리적인 통신 네트워크는 링 구조일 필요 없음 - 상호 배제 성립: 토큰이 유일하므로 - 기아 상태 미발생: 단방향 링의 경우 - 임계 구역의 상호 배제를 위한 메시지 수는 변동이 심함 → 경쟁이 심한 경우, 각 출입마다 하나의 토큰 메시지 필요 경쟁이 거의 없는 경우, 각 출입마다 다수의 토큰 메시지 필요 2) 두 가지 고장의 경우 - 토큰이 분실되면, 한 프로세스를 선택하여 새로운 토큰을 생성시킴 → 선택 알고리즘(18.6절) - 임의의 프로세스가 고장나면, 새로운 논리적 링을 재구성해야 함 18.3 원자성(Atomicity) ▶ 트랜잭션 조정자(transaction coordinator): 분산 시스템에서 트랜잭션 수행의 원자성을 보장하는 기능 담당 → 지역 트랜잭션 조정자: 해당 사이트에서 시작된 모든 트랜잭션의 실행을 조정하고 각 지역 사이트의 복구를 위해 로그(log)를 유지함 - 트랜잭션의 수행을 시작 - 트랜잭션을 서브 트랜잭션들로 나누어 여러 사이트에 분배 - 트랜잭션의 종료를 조정 - 모든 사이트에서 승인(commit)되지 않으면, 거부(abort)됨 18.3.1 2 단계 승인 프로토콜(The Two-Phase Commit Protocol) ▶ 2 단계 승인(Two-Phase Commit; 2PC) 프로토콜: 트랜잭션 를 수행하는 모든 사이트가 실행의 최종 결과에 동의하게 함으로써, 원자성을 보장하는 한 방법 (가정) 트랜잭션 는 사이트 에서 시작되고, 는 의 트랜잭션 조정자라고 하자. 가 실행을 완료할 때 - 즉, 를 수행한 모든 사이트가 에게 가 완료되었음을 알리면 - 는 다음의 2PC 프로토콜을 시작함 ① 단계 1: - 는 레코드 를 로그에 추가하고, 레코드를 보조기억장치에 저장 - 를 수행한 모든 사이트에 prepare 메시지를 전송 - 그 메시지를 받은 해당 사이트의 트랜잭션 관리자는 의 부분에 대해 승인 여부를 결정 1) 미승인시: 를 로그에 추가하고, abort 메시지를 에 전송 2) 승인시: 를 로그에 추가하고, 에 관계된 모든 레코드를 보조기억장치에 저장하고, ready 메시지를 에 전송 ② 단계 2: - 는 모든 응답을 받거나 일정 시간이 지난 후 의 승인 또는 거부를 결정 1) 관련된 모든 사이트로부터 ready 를 받은 경우: 승인(commit) 2) 그렇지 않은 경우: 거부(abort) - 결정에 따라 레코드 또는 를 로그에 추가하고 보조기억장치에 저장 - 조정자는 commit 또는 abort 메시지를 모든 관련 사이트에 전송하고, 각 사이트는 그 메시지를 받은 후 로그에 기록함 18.3.2 2PC에서 결함 처리(Failure Handling in 2PC) 18.3.2.1 관련 사이트 결함(Failure of a Participating Site) ▶ 관련 사이트 가 결함으로부터 복구될 때, 임의의 트랜잭션 에 대한 처리 ① 로그에 레코드를 유지하는 경우: redo() 수행 ② 로그에 레코드를 유지하는 경우: undo() 수행 ③ 로그에 레코드를 유지하는 경우: 에 문의 1) 가 정상인 경우: commit 또는 abort를 에게 알려줌 - redo() 또는 undo() 수행 2) 가 결함인 경우: - query-status 메시지를 모든 사이트에 보냄 - 메시지를 받은 사이트는 가 수행되었는지 로그를 살펴보고, 만일 수행된 경우 commit 또는 abort를 알림 - 만일 아무런 응답이 없으면 의 운면에 대한 결정은 미뤄지고, 주기적으로 query-status 메시지를 재전송함 ④ 로그에 에 대한 어떠한 메시지도 없는 경우: 로부터의 prepare 메시지를 응답하기 전에 결함이 발생했음을 의미 → 필연적으로 가 를 abort하게 되고, 따라서 는 undo() 수행하게 됨 18.3.2.2 조정자 결함(Failure of Coordinator) ▶ 조정자가 트랜잭션 에 대한 commit 프로토콜 수행 중에 고장이 발생하면, 관련 사이트들은 다음과 같이 의 운명을 결정함 ① 활성 사이트가 자신의 로그에 레코드를 포함하는 경우: 는 commit됨 ② 활성 사이트가 자신의 로그에 레코드를 포함하는 경우: 는 abort됨 ③ 활성 사이트가 자신의 로그에 레코드를 포함하지 않는 경우: 이 사이트는 ready 메시지를 에 보내지 않았으며 따라서 는 를 abort 시켰을 것이므로, 의 복구를 기다릴 필요 없이 를 abort시킴 ④ 활성 사이트가 자신의 로그에 레코드를 포함하는 경우: 의 복구를 기다림. 이때 는 활성 사이트에 있는 자료에 대해 잠금 기능을 수행하게 되고, 그로 인해 다른 트랜잭션들도 를 기다리게 됨 → 블록킹(blocking) 문제 18.3.2.3 네트워크 결함(Failure of Network) ▶ 링크의 결함이 발생하면, 이를 사용하는 사이트는 상대 사이트에 결함이 발생한 것으로 간주하게되고, 앞의 처리 과정이 잘 수행됨 → 네트워크 분할이 발생할 수 있음 - 조정자와 관련 사이트들이 동일 영역에 속하는 경우: commit 프로토콜에 영향을 미치지 않음 - 그렇지 않은 경우: 메시지 분실 발생 18.4 동시성 제어(Concurrency Control) ▶ 분산 데이터베이스 시스템의 트랜잭션 관리자: 지역 사이트에 저장된 자료를 접근하는 트랜잭션들의 수행을 관리 - 지역 트랜잭션: 자신의 사이트에서만 수행되는 트랜잭션 - 전역 트랜잭션: 여러 사이트에서 수행되는 트랜잭션 → 관리자는 트랜잭션 복구를 위해 로그를 유지해야 하고, 적절한 병행성 제어 방법을 채택해야 함 18.4.1 잠금 프로토콜(Locking Protocols) ▶ 6장의 2단계 잠금 프로토콜은 분산 환경에서도 적용 가능함 → 단, 잠금 관리자(lock manager) 구현 필요 18.4.1.1 비중복 방법(Nonreplicated Schemes) ▶ 시스템에 중복 자료가 없는 경우, - 각 사이트에 저장되어 있는 자료 항목에 대해 잠금과 해제 요청을 관리하는 기능의 지역 잠금 관리자(local lock manager)를 둠 - 트랜잭션이 사이트 에 있는 자료 항목 의 잠금을 원하는 경우, 사이트 에 있는 잠금 관리자에게 특정 잠금 모드로 메시지를 전송함 1) 수용할 수 없는 경우: 지연 2) 수용할 수 있는 경우: 승인 메시지를 반환 (장점) 구현이 간단: 잠금 요청 - 2개의 메시지, 해제 요청 - 1개의 메시지 (단점) 교착 상태 취급이 복잡 18.4.1.2 단일 조정자 접근(Single Coordinator Approach) ▶ 특정 사이트 에 있는 단일 잠금 관리자가 모든 잠금과 풀림 요청을 처리하게 하는 방법 - 읽기: 해당 자료 항목의 복사본이 있는 하나의 사이트로부터 읽음 - 기록: 해당 자료 항목의 복사본이 있는 모든 사이트에 기록 (장점) 1) 단순한 구현: 잠금 요청 - 2개의 메시지, 해제 요청 - 1개의 메시지 2) 단순한 교착 상태 취급: 한 사이트에서 모든 잠금과 해제가 수행되므로 7장의 교착 상태 취급 알고리즘을 직접 분산 환경에 사용할 수 있음 (단점) 1) 병목 현상(bottleneck): 사이트 에서 모든 요청을 처리해야 하기 때문 2) 취약성(vulnerability): 사이트 의 고장은 처리 중단이 초래되거나 복구 방법이 요구됨 18.4.1.3 다수결 프로토콜(Majority Protocol) ▶ 각 사이트에 잠금 관리자를 유지하여 그 사이트의 모든 자료나 복사본에 대해 잠금을 관리하게 하는 방법 → 트랜잭션은 자료 항목 의 대다수 복사본들에 대해 잠금을 요청해야 함: n/2 +1 이상 (장점) 분산형 (단점) 1) 복잡한 구현: 잠금 요청 - 2(n/2+1) 메시지 요구, 풀림 요청 - (n/2+1) 메시지 요구 2) 복잡한 교착 상태 취급 - 18.5절 참조 18.4.1.4 편의 프로토콜(Biased Protocol) ▶ 각 사이트마다 해당 관리자가 잠금과 해제를 관리하되, 공유 잠금과 배타 잠금을 구분하여 취급하는 방법 - 공유 잠금: 의 복사본을 가진 한 사이트의 잠금 관리자에게 잠금을 요청 → 읽기: 적은 부담 - 배타 잠금: 의 복사본을 가진 모든 사이트의 잠금 관리자에게 잠금을 요청 → 기록: 추가 부담 18.4.1.5 주 복사본(Primary Copy) ▶ 자료 항목 의 주 복사본을 유일한 주 사이트에 저장하고, 잠금을 주 사이트에게 하는 방법 (장점) 복사본이 없는 경우와 동일한 병행성 제어 가능 (단점) 주 사이트의 고장시 의 다른 복사본을 이용할 수 없음 18.4.2 타임스탬핑(Timestamping) ▶ 중앙 집중형의 타임스탬핑 방법을 그대로 사용하려면, 단일 타임스탬프를 생성하는 방안 필요함 18.4.2.1 단일 타임스탬프 생성(Generation of Unique Timestamps) ▶ 단일 타임스탬프를 생성하는 두 방법 1) 집중형 방법: 단일 사이트가 타임스탬프를 분배하기 위해 선정되는 방법 → 논리적 카운터 또는 지역 클록으로 구현 2) 분산형 방법: - 지역 단일 타임스탬프: 각 사이트마다 논리적 카운터나 지역 클록으로 구현 - 전역 단일 스탬프: 지역 단일 타임스탬프 + 사이트 식별자로 구현 [그림 18.2] 단일 타임스탬프 생성 → 다수의 지역 클록이 동기화되는 것을 보장하기 위한 방법: 타임스탬프 를 가진 트랜잭션 가 사이트 는 방문했을 때, 만일 가 의 현재 값보다 크면 는 를 로 증가시킴 18.4.2.2 타임스탬프 순서화 방법(Timestamp Ordering S초듣) ▶ 6.9절의 기본 타임스탬프 기법은 분산 시스템에 바로 확장될 수 있음 (단점) 트랜잭션들 사이의 충돌이 발생할 경우 대기 방법보다 롤백 방법을 통해 해결함 → 해결을 위한 핵심 1) 의 은 의 이 존재하고 이면 지연됨 2) 의 은 또는 를 수행하는 가 존재하고 이면 지연됨 18.5 교착 상태 처리(Deadlock Handling) ▶ 분산 환경을 위한 교착 상태의 방지(prevention), 회피(avoidance), 탐지(detection) 알고리즘 → 기존 방법(7장)과 거의 유사하게 사용할 수 있음 1) 교착 상태 방지: 자원 순서화에 의한 교착 상태 방지 기법 - 시스템의 모든 자원을 전역 순서화 함: 자원마다 유일한 번호를 부여함 - 프로세스는 자원 를 요청하기 위해서는 이 보다 큰 번호의 자원을 소유하지 않아야 함 → 구현 간단, 자원의 전역 순서화 필요 2) 교착 상태 회피: 은행가 알고리즘 - 시스템내의 한 프로세스를 은행가 알고리즘에 필요한 정보를 관리하는 은행가로 사용하면 됨 - 모든 자원의 요청은 은행가를 통해서 이루어짐 → 구현 간단, 은행가로의 병목 현상 심각 18.5.1 교착 상태 방지(Deadlock Prevention) ▶ 타임스탬프 순서화에 기반을 둔 교착 상태 방지 기법 1) wait-die 기법: 비선점 방식 → 가 의 보유중인 자원을 요구할 때, 가 보다 적은 타임스탬프(더 오래 기다림)를 가지고 있으면 기다릴 수 있고(wait), 그렇지 않으면 는 복귀함(die) ex) 요구 요구 → ← ⇒ 은 기다리고, 복귀함 (5) (10) (15) 2) wound-wait 기법: 선점 방식 → 가 의 보유중인 자원을 요구할 때, 가 보다 적은 타임스탬프를 가지고 있으면 는 의 자원을 선점하고(wound) 는 복귀한다. 그렇지 않으면 는 기다릴 수 있다(wait). ex) 요구 요구 → ← ⇒ 은 자원을 선점하고 는 복귀하며, 는 자원을 기다림 (5) (10) (15) ▶ 차이점 wait-die 기법 wound-wait 기법 오래된 프로세스가 기다림(선점 안함) 오래된 프로세스는 기다리지 않음(선점함) 는 로부터 필요한 자원을 획득하기 위해 여러 번 복귀될 수 있음 (다수의 roll back 발생) 가 에 의해 복귀된 후에는 가 보유중인 자원을 요청하고 기다리게 됨 (소수의 roll back 발생) ▶ 공통점 - 각 프로세스에 우선 순위를 부여: 타임 스탬프를 우선 순위로 사용 - 교착 상태 방지를 보장: 대기 그래프(wait-for graph)의 임의의 간선 에 대해 항상 가 보다 우선 순위가 높거나 항상 낮게 함으로써 사이클이 발생하지 않게 함 - 기아 상태(starvation) 가능: 낮은 우선 순위의 프로세스가 계속해서 복귀될 수 있음 → 복귀되는 프로세스의 타임스탬프를 갱신하지 않음으로써 기아 상태 방지 가능 - 두 기법 모두 교착상태가 아닌 경우의 불필요한 복귀 발생 → 교착 상태 탐지 기법 필요 18.5.2 교착 상태 탐지(Deadlock Detection) ▶ 지역 대기 그래프(local wait-for graph): 각 사이트에서의 대기 그래프 - 노드: 그 사이트의 자원을 점유하거나 요청하는 지역적 또는 비지역적 프로세스 - 아크: 자원 요청 ex) [그림18.3] 두 개의 지역 대기 그래프 ▶ 지역 대기 그래프의 구성: 동일 프로세스가 서로 다른 사이트에 존재할 수 있음 → 사이트 A의 프로세스 가 사이트 B의 프로세스 에 의해 점유된 자원을 필요로 하면, 요청 메시지가 에서 로 보내지고, 간선 가 사이트 B의 지역 대기 그래프에 포함됨 ▶ 교착 상태 점검 (가정) 자원 유형별로 하나의 자원이 존재 - 지역 대기 그래프에 사이클 존재 ○: 교착 상태 발생 의미 - 자원 대기 그래프에 사이클 존재 ×: 교착 상태 아니라고 장담 못함 → 교착 상태가 아님을 증명하려면, 모든 지역 그래프의 합집합(union)인 전역 대기 그래프에서 사이클이 없음을 보여야 함 ex) [그림 18.4] 전역 대기 그래프 ▶ 분산 시스템에서 대기 그래프를 구성하는 방법: 18.5.2.1-18.5.2.2 18.5.2.1 중앙 집중형 접근(Centralized Approach) ▶ 교착 상태 탐지 조정자(deadlock-detection coordinator): 모든 지역 그래프의 합으로 구성되는 전체 대기 그래프를 관리하는 프로세스 - 실제 그래프(real graph): 특정 시간에 존재하는 그래프 - 구성 그래프(constructed-graph): 통신 지연으로 조정자에 의해 생성된 실제 그래프의 근사치 ▶ 대기 그래프의 구성 시점 - 새로운 간선의 삽입 혹은 제거 시마다 - 주기적으로 대기 그래프에서 많은 변화가 일어났을 때마다 - 조정자가 사이클 탐지 알고리즘을 수행할 필요가 있을 때마다 → 교착 상태 탐지알고리즘으로 사이클이 발견되면, 조정자는 희생자를 선택하고 모든 사이트에게 특정 프로세스가 희생자로 선택되었다는 사실을 알려주어야 함 ▶ 불필요한 복귀의 발생 원인 1) 거짓 사이클(false cycle)이 전역 대기 그래프에 존재하는 경우 ex) [그림 18.5] 지역 및 전역 대기 그래프 ① 사이트 A의 가 점유하고 있는 자원을 해제: A의 간선 제거 ② 가 사이트 B의 가 점유하고 있는 자원을 요청: B에 간선 삽입 ③ 만일 조정자에게 제거 메시지보다 삽입 메시지가 먼저 도착하면, 전역 대기 그래프에 거짓 사이클 발생 → 교착 상태 회복 작업 시작 2) 실제 교착 상태가 발생하여 희생자가 선택될 때, 불필요한 복귀나 취소가 발생할 수 있음 ex) [그림 18.3] 참조 ① 사이트 A가 를 취소시키기로 결정하고, ② 동시에 조정자가 사이클 발견하여 를 희생자로 선택하면, → 와 가 복귀됨(실제로는 만 복귀되면 됨) ▶ 대기 그래프의 구성: 다른 사이트로부터의 요청에 유일한 식별자인 타임스탬프를 붙임 1) 사이트간 자원 요청시: 사이트 A의 가 사이트 B의 의 자원을 요청하는 경우 ① 사이트 A의 로컬 대기 그래프에 타임스탬프가 부착된 간선 을 추가 ② 가 즉시 자원을 줄 수 없는 경우에만 사이트 B의 로컬 대기 그래프에 그 요청 간선을 추가 2) 사이트내의 자원 요청시: 동일 사이트에 있는 가 의 자원을 요청하는 경우 → 해당 사이트에 타임스탬프가 없는 간선 을 즉시 추가 ▶ 중앙 집중형 교착 상태 탐지 알고리즘 → 모든 교착 상태를 탐지하면서 거짓 교착 상태는 탐지하지 않는 방법 1) 조정자는 시스템의 각 사이트에 초기화 메시지를 전송 2) 이 메시지를 받은 각 사이트는 자신의 지역 대기 그래프를 조정자에게 보냄 3) 각 사이트의 지역 대기 그래프를 받은 조정자는 전역 그래프를 구성 - 정점: 시스템내의 모든 프로세스에 대한 정점을 포함 - 간선: 다음 조건을 만족하는 간선 를 포함 ① 하나의 대기 그래프에 간선 가 존재하는 경우이거나, ② 둘 이상의 대기 그래프에 타임스탬프를 가진 간선 가 존재하는 경우 4) 사이클이 존재하면 교착 상태이고, 그렇지 않으면 교착 상태가 아님 18.5.2.2 완전 분산형 접근(Fully Distributed Approach) ▶ 기본 개념 - 각 사이트가 전체 그래프의 일부를 나타내는 확장된 지역 대기 그래프를 구성하고, - 교착 상태가 존재하면 적어도 하나의 부분 그래프에서 사이클이 나타나게 하는 방법 ▶ 확장된 지역 대기 그래프: 기존의 지역 대기 그래프의 확장 → 외부 그래프를 로 표현 - 추가: 가 다른 사이트의 임의의 프로세스가 점유하고 있는 자원을 요청한 경우 - 추가: 가 점유하고 있는 자원을 다른 사이트의 임의의 프로세스가 요청한 경우 ex) [그림 18.6] 확장된 지역 대기 그래프 ← [그림 18.3] → 확장된 지역 대기 그래프에 사이클 존재할 때 ① 를 포함하지 않는 경우: 교착 상태임 ② 를 포함하는 경우: 교착 상태일 가능성이 있음 → “교착 상태 탐지 알고리즘” 수행 ▶ 완전 분산형 교착 상태 탐지 알고리즘 1) 사이트 에서 를 포함하는 사이클 발견 2) 이 사이클을 파악하기 위해, 는 에 대응하는 에게 사이클 정보를 담고 있는 교착 상태 탐지(dead-lock detection) 메시지를 보냄 3) 는 이 메시지 정보를 이용하여 지역 대기 그래프를 갱신하고, 사이클이 존재하는지 검사함 - 사이클이 존재하지 않는 경우: 교착 상태 아님 - 를 포함하지 않고 사이클이 존재하는 경우: 교착 상태임 - 를 포함하는 사이클이 존재하는 경우: 마찬가지로, 에 대응하는 사이트 에 교착 상태 탐지 메시지를 보냄 ex) [그림 18.6] → [그림 18.7] 확장된 지역 대기 그래프 ① 이 를 포함하는 사이클 발견: [그림 18.6] ② 이 교착 상태 탐지 메시지를 에 전송함 ③ 는 지역 대기 그래프를 갱신함: [그림 18.7] ④ 는 를 포함하지 않는 사이클 발견: 교착 상태 → 복구 수행 * 이때, 과 가 동시에 교착 상태 탐지 알고리즘을 전송할 수 있음: 불필요한 중복 처리 ▶ 메시지 전달 횟수를 감소시키기 위한 방안 1) 각 트랜잭션 에 식별자를 붙임: 2) 사이트 가 사이클 를 발견하면, 일 경우에만 교착 상태 탐지 메시지를 전송함 ex) [그림 18.6] 참조 (가정) , 두 사이트가 동시에 사이클 발견 - : 사이클 발견 → : 교착 상태 탐지 메시지를 전송 안함 - : 사이클 발견 → : 교착 상태 탐지 메시지를 전송함 18.6 선출 알고리즘(Election Algorithms) ▶ 조정자 프로세스(coordinator process)의 역할 - 상호 배제 보장 - 교착 상태 탐지를 위한 전역 대기 그래프의 유지 - 시스템내의 입출력 장치의 조정 → 사이트의 결함으로 조정자 프로세스의 수행이 불가능해지면, 다른 사이트에 조정자 기능을 새로이 복사하여 시스템을 계속 동작시킬 수 있음 ▶ 선출 알고리즘: 조정자의 새로운 복사를 어느 곳에 하는가를 결정하는 알고리즘 - 프로세스 가 유일한 우선 순위 를 가지고 있고, 프로세스와 사이트는 1:1 대응관계이고, 조정자는 항상 가장 큰 우선 순위를 가진 프로세스라고 가정하면, 가장 큰 우선 순위를 가진 프로세스를 선택함 - 이 숫자는 체제내의 모든 활동하는 프로세스에 보내져야 하고, 고장으로부터 회복된 프로세스가 현재의 조정자를 구별할 수 있어야 함 ▶ 종류 ① Bully 알고리즘: 프로세스가 다른 모든 프로세스에 메시지를 보낼 수 있는 시스템에 적용 ② 링 알고리즘: 논리적 또는 물리적으로 구성된 링 구조의 시스템에 적용 → 두 알고리즘 모두 체제 내의 프로세스의 수가 이라면 선택에 메시지가 필요함 18.6.1 Bully 알고리즘(Bully Algorithm) ▶ 알고리즘 1) 프로세스 가 조정자에게 메시지를 보낸 후 시간 간격 이내에 응답을 받지 못함 → 조정자의 고장이라 간주 2) 프로세스 는 자신보다 높은 우선 순위를 가진 모든 프로세스에게 선택 메시지를 보내고, 그 프로세스들로부터의 응답을 시간 동안 기다림 3) 시간 내에 아무런 응답이 없으면, 보다 큰 우선 순위의 프로세스가 없다고 가정해서 자신이 조정자로 선택되고, 는 보다 낮은 우선 순위를 지닌 모든 활동하는 프로세스에게 가 새로운 조정자라는 메시지를 보냄 4) 만일 응답을 받게 되면, 는 높은 우선 순위를 지닌 프로세스가 선출되었다고 하는 메시지를 새로운 시간 동안 기다림. 만일 이내에 메시지가 도달하지 않으면 높은 우선 순위 프로세스가 고장이라 가정하여 알고리즘을 다시 수행함 ▶ 수행 중 조정자가 아닌 프로세스 는 로부터 다음의 두 메시지 중 하나를 받을 수 있음 ① 가 새로운 조정자이다(): 프로세스 는 이 정보를 기록 ② 가 선출 과정을 시작한다(): 는 에게 응답을 보내고, 아직 자신의 선출 과정을 시작하지 않았으면 시작함 → 자신의 선출 과정을 완료하면 낮은 우선 순위의 모든 프로세스에 자신의 우선 순위를 보냄 ▶ 고장난 프로세스가 회복된 경우에도 같은 알고리즘을 수행함 → 자신보다 높은 순위의 프로세스가 없으면 현재 낮은 순위의 조정자가 있더라도 자신이 조정자 프로세스가 된다는 사실을 알려 주어야 함 ▶ 프로세스 , , , 로 구성된 시스템의 예(가정: 첨자가 클수록 우선순위 높음) ① 모든 프로세스가 활동하며, 가 조정자 프로세스임 ② 과 가 고장이고, 는 시간 이내에 로부터 응답을 받지 못하므로, 에게 메시지를 보내 자신의 선출 알고리즘을 시작함 ③ 는 에게 응답을 하고, 에게 메시지를 보내 자신의 선출 알고리즘을 시작함 ④ 는 로부터 메시지를 받고 시간 동안 기다림 ⑤ 는 시간 이내에 로부터의 응답이 없으므로 자신을 새로운 조정자로 선택하여 과 에게 순위 3을 보냄. 단 은 고장이므로 받지 못함 ⑥ 얼마 후에 회복된 은 , , 에게 선출 요청을 보냄 ⑦ 와 가 에 응답하고 자신의 선출 알고리즘을 시작하고, 위와 같은 방법으로 가 다시 선출됨 ⑧ 끝으로 회복된 는 가장 높은 순위를 가진 프로세스이므로 선출 요청을 하지 않고 자신이 현재의 조정자라는 메시지를 , , 에게 전달함 18.6.2 링 알고리즘(Ring Algorithm) ▶ 기본 사항 - 링크는 단방향이고, 프로세스는 자신의 오른쪽 이웃에게만 메시지를 보냄 - 활동 리스트(active list): 알고리즘이 끝날 때 시스템 내의 모든 활동적인 프로세스의 우선 순위를 보유하는 자료 구조 → 각 프로세스마다 활동 리스트 유지 ▶ 알고리즘 1) 프로세스 가 조정자의 고장을 탐지하면, 새로운 빈 활동 리스트를 작성한 후, 우측 프로세스에 메시지를 보내고 활동 리스트에 를 추가함 2) 프로세스 가 좌측 프로세스로부터 메시지를 받으면 다음의 세 가지 중 하나의 형태로 응답함 ① 만일 이것이 첫 번째 메시지라면, 는 와 를 지닌 새로운 활동 리스트를 만들고, 를 보내고 를 보냄 ② 만일 이면, 는 를 활동 리스트에 더하고 우측 이웃에 메시지를 전달함 ③ 만일 이면, 의 활동 리스트에 시스템 내의 모든 활동하는 프로세스의 순위를 포함함 → 는 활동 리스트에서 가장 큰 순위의 프로세스를 새로운 조정자 프로세스로 선출함 ▶ 회복한 프로세스는 질문 메시지를 보내, 현재의 조정자로부터 그의 우선 순위 메시지를 받음 18.7 의견의 일치(Reaching Agreement) ▶ 시스템이 신뢰성을 갖기 위해서는 프로세스 집합이 어떤 공통 값에 일치하도록 하는 장치가 필요 → 불일치 원인: ① 통신 매체가 고장이 나서 메시지를 잃어버리거나 잘못 전달하는 경우 ② 프로세스에 고장이 나서 예측할 수 없는 프로세스 행동을 유발하는 경우 ex) 비잔틴 장군 문제: 적진을 포위한 모든 장군의 의견일치 필요 - 연락병에 의한 통신 - 연락병이 적군에 잡혀 메시지를 전달 못함 → 신뢰성 없는 통신 - 한 장군이 배반하여 교란함 → 고장난(오작동) 프로세스 18.7.1 신뢰성 없는 통신(Unreliable Communications) ▶ 가정: 프로세스의 잘못은 명백히 판별되지만, 통신 매체는 신뢰할 수 없음 1) 사이트 A의 프로세스 가 사이트 B의 프로세스 에게 메시지를 보낸 후 메시지의 전달 여부에 따라 수행해야 할 연산이 다른 경우(ex: 전달된 경우 함수 S를 연산; 미 전달된 경우 함수 F를 연산)에는 접수 메시지를 기다려야 함 → 시간 제한(time-out) 기법에 의해 기다리는 시간 간격을 정의하여 메시지를 보내고, 규정 시간이 초과되면 메시지를 재전송하고 다시 기다리는 과정을 접수 메시지를 받거나 고장 사실을 알게 될 때까지 반복함 2) 도 가 응답 메시지를 받았는지를 알 필요가 있는 경우(ex: 도 가 응답 메시지를 받은 경우에만 S를 연산)에는 마찬가지로 상대의 접수 메시지를 기다려야 함 → 즉, 와 는 상호 접수가 되어야 S를 연산할 수 있는데, 고장이 있는 경우에는 이 작업이 수행될 수 없음 * 일반적으로, 분산 환경에서는 와 가 각각의 상태에 완전히 일치할 수 없음 18.7.2 고장난 프로세스(Faulty Processes) ▶ 가정: 통신 매체는 신뢰할 수 있지만, 프로세스는 예측할 수 없는 방법으로 고장날 수 있음 ▶ 알고리즘: 전체 개의 프로세스 중 개 이하가 고장나 있고, 각 프로세스 가 개인 값 를 가진 시스템에서, 고장나지 않은 프로세스 가 다음을 만족하는 를 구성하는 알고리즘 ① 가 고장나지 않은 프로세스이면 ② 와 가 모두 고장나지 않은 프로세스이면 ▶ 알고리즘의 특성 ① 인 경우에만 알고리즘이 고안될 수 있음 ② 일치점 도달에 대한 최악의 지연 시간은 메시지 전달 지연에 비례 ③ 일치점 도달에 필요한 메시지 수는 모든 프로세스의 정보를 모아야 하므로 매우 많음 ▶ , 인 경우의 알고리즘 1) 두 단계의 정보 교환 ① 각 프로세스는 자신의 개인 값을 다른 모든 프로세스에게 보냄 ② 각 프로세스는 첫 번째 단계에서 얻었던 정보를 다른 모든 프로세스에게 보냄 → 이때, 고장난 프로세스는 값을 보내지 않거나 변조된 값을 보낼 수 있음 만일, 고장난 프로세스의 값이 도착하지 않으면 각 프로세스가 임의로 결정한 후 보냄 2) 고장나지 않은 프로세스 는 다음을 만족하는 를 구성 ① ② : 에 대해 보고된 세 값 중 적어도 두 개가 일치하면 그 다수 값을 사용하고, 그렇지 않으면 내정 값 NIL을 사용

17. 분산 파일 시스템(Distributed File Systems; DFS) ▶ 분산 파일 시스템의 목적: 분산 시스템에서 물리적으로 여러 사이트들간에 퍼져 있는 파일들에 대해 동일한 방식의 파일 공유를 지원하는 것 17.1 배경(Background) ▶ 용어 - 서비스(service): 여러 기계에서 수행되는 소프트웨어 항목 → 클라이언트들에게 특정 기능을 제공 - 서버(server): 단일 기계에서 수행중인 서비스 소프트웨어 - 클라이언트(client): 자신의 클라이언트 인터페이스를 형성하는 연산 집합으로 서비스를 유발하는 프로세스 → 기본적인 파일 동작들의 집합으로 구성: 파일 생성, 파일 삭제, 파일 판독, 파일 기록 등 ▶ 분산 파일 시스템의 특징 - 자치성(autonomy): 시스템 내의 클라이언트와 서버는 각각 자치성(autonomy)을 가짐 - 투명성(transparency): 시스템이 클라이언트에게 중앙집중형 파일 시스템처럼 보여짐 - 이동성(mobility): 사용자는 임의의 사이트에서 로그인 가능 ▶ 분산 파일 시스템의 환경과 구현에는 그 종류가 매우 다양함 → 주요 성능 측정: 다양한 서비스들을 만족시키기 위해서 요구되는 시간 17.2 네이밍(Naming)과 투명성(Transparency) ▶ 네이밍: 논리적인 객체들과 물리적인 객체들간의 사상 - 사용자: 파일의 이름에 의해서 표현되는 논리적인 자료 객체를 사용 - 시스템: 디스크에 저장되어 있는 물리적인 자료 블록을 조작 → 파일의 추상화: 디스크내의 저장 방식이나 위치를 숨김 ▶ 분산 파일 시스템의 투명성: 네트워크 내에서의 저장 위치까지 숨기는 추상화 기능 첨가 → 파일 중복: 하나의 파일 이름이 주어지면 해당 중복 파일들의 위치 집합을 반환 (즉, 다중 복사본들과 그 위치를 숨김) 17.2.1 네이밍 구조(Naming Structure) ▶ 네이밍 사상에 관한 두 가지 중요 개념 - 위치 투명성(location transparency): 파일의 이름에 그 파일의 물리적 기억장소에 대한 정보를 나타내지 않음 → 파일 위치가 고정됨 ex) 대부분의 시스템 - 위치 독립성(location independency): 파일의 물리적 기억장치의 위치가 변경되어도 파일 이름을 변경할 필요 없음 → 파일 위치의 자동 변경 가능(보다 강력한 속성) ex) Andrew 등 일부 ▶ 위치 독립성의 특성 - 위치 독립성에 의한 이름과 위치의 분리는 더 좋은 추상화를 제공 - 위치 독립성은 기억 장소 공유를 증진시킴: 즉, 시스템 전체의 디스크 이용률을 균등화할 수 있음 - 위치 독립성은 네이밍 계층을 저장장치 계층이나 컴퓨터 내부 구조로부터 분리할 수 있음 17.2.2 네이밍 기법(Naming Schemes) ▶ 세 가지 접근 방법 ① 파일의 이름을 호스트 이름(host name)과 지역 이름(local name)의 조합으로 구성하는 방법 - 가장 간단한 방법 - 시스템 전역에 걸쳐 유일한 이름을 보장 - 위치 투명성과 위치 독립성 없음 - 동일한 파일 동작으로 지역 또는 원격 파일 모두에 적용 가능 ② 원격 디렉토리들을 지역 디렉토리에 붙일 수 있게 하는 방법 - Sun의 네트워크 파일 시스템(NFS)에서 사용 - 수동 마운팅 ↔ 자동 마운팅: 마운트 포인트와 파일 구조 이름의 테이블을 기반으로 요구 시에 마운트됨 - 투명성 있는 공유를 지원하는 방식이지만 제한적임 ③ 구성 파일 시스템들을 전체적으로 통합하는 방법 - 이상적으로, 구성된 파일 시스템 구조는 전통적인 파일 시스템 구조와 동일한 형태임 - 실제로는 이러한 목표를 어렵게 하는 여러 특별한 파일이 존재함 ex) 장치 파일, 이진 디렉토리 등 ▶ 네이밍 구조의 평가: 관리의 복잡성 → NFS 구조(②)가 가장 복잡하고 어려움: 임의의 원격 디렉토리가 지역 디렉토리에 부착될 수 있기 때문에, 전체 계층은 비구조적일 수 있음 17.2.3 구현 기법(Implementation Techniques) ▶ 투명한 네이밍 기법의 구현: 파일 이름을 연관된 위치로 사상하는 작업 필요 - 파일을 구성단위로 모으는 기법 - 저수준이면서 위치 독립적인 파일 식별자 사용 → 구조적 이름 사용 1) 파일이 속해있는 구성 단위를 식별 2) 단위내의 특별한 파일을 식별 17.3 원격 파일 접근(Remote File Access) ▶ 원격 파일 접근: ‘원격 서비스 기법’ 사용 - 접근을 위한 요구들은 서버에 전달되고, - 서버 기계는 접근을 수행하고, - 그 결과를 사용자에게 돌려줌 ex) 원격 프로시저 호출(RPC) → 성능 보장을 위해 캐싱(cashing) 사용: 네트워크의 교통량과 디스크 입출력을 감소시킴 17.3.1 기본 캐싱 기법(Basic Caching Scheme) ▶ 캐싱의 개념 - 만일 어떤 접근 요구를 만족하는 자료가 캐시되어 있지 않으면 이 자료의 복사본을 서버로부터 클라이언트 시스템으로 이동시키고, 접근은 캐시된 복사본 상에서 행해짐 - 동일한 정보에 대한 반복된 접근은 부가적인 네트워크 접근 없이 지역적으로 처리될 수 있음 - 요구 페이지 가상 기억장치와 유사 → “캐시 일관성 문제” 발생(17.3.4절 참조) ▶ 캐싱의 단위가 증가할수록, - 적중률(hit-ratio) 증가 - 실제적인 자료 전송시간이 지연 - 일관성 문제 증가 17.3.2 캐시 위치(Cache Location) ▶ 캐시된 자료의 저장 위치 ① 디스크 캐시: 비휘발성이므로 기억장치의 오류 발생시에도 자료가 지역에 보관됨 ② 주기억장치 캐시 - 디스크가 없어도 됨 - 접근 속도가 빠름 - 급격한 성능 향상 추세 - 서버와 사용자를 위한 단일 캐싱 기법의 설계 가능 17.3.3 캐시 갱신 전략(Cache Update Policy) ▶ 수정된 자료 블록을 서버의 마스터 복사본에 갱신하기 위한 전략 ① 즉시 기록(write-through): 수정직후 즉시 기록하는 방법 → 다른 기록 접근을 지연시킴 ② 교체 기록(alternate write)/지연 기록(delayed-write): 수정은 캐시에서 이루어지고, 마스터 복사본의 수정을 지연하는 방법 - 장점: 기록 접근이 신속하고, 마스터 복사본에 다시 기록되기 전에도 자료 갱신 가능 - 단점: 신뢰성 문제 초래 - 사용자 기계 손상시 기록되지 않은 자료의 분실 가능 ▶ 지연 기록 기법의 종류 ① 클라이언트의 캐시에서 블록이 나오기 직전에 반영하는 방법 → 장시간 캐시에 상주 가능 ② 정규 기간마다 캐시를 조사하여 지난 조사 이후 갱신된 블록을 반영하는 방법 → 교체 기록과 즉시 기록 전략의 절충안 ③ 파일이 폐쇄될 때 반영하는 방법: “폐쇄시 기록(write-on-close)” → 짧은 시간 열리거나 또는 가끔 변경되는 파일의 경우 비효율적이고, 프로세스 닫기가 지연됨 17.3.4 일관성(Consistency) ▶ 클라이언트 기계는 캐시된 자료와 마스터 복사본이 일치하는지를 결정해야 함 → 불일치하면 캐시자료를 더 이상 접근하지 않아야 하고, 가장 최신의 복사본이 캐시되어야 함 ▶ 캐시의 타당성 검증 방법 ① 클라이언트 시작 접근 방법(client initiated approach) - 클라이언트가 서버와의 접촉을 통해서 타당성 검사를 시작 - 타당성 검사의 빈도가 중요 → 모든 접근 전의 검사에서 파일의 첫 접근(파일 열기) 검사에 이르기까지 다양하고, 타당성 검사와 중복되는 모든 접근은 지연됨 ② 서버 시작 접근 방법(server initiated approach) - 서버가 불일치 가능성을 발견하면, 캐시된 일부 또는 전체 파일을 기록 - 불일치 가능성은 파일이 서로 다른 두 클라이언트에 의해 충돌 상태로 캐시될 때 발생함 17.3.5 캐싱(Caching)과 원격 서비스(Remote Service)의 비교 ▶ 캐싱과 원격 서비스의 비교 - 원격 접근은 캐싱이 사용되면 효율적으로 처리될 수 있는 반면, 원격 서비스만으로 처리하면 네트워크 통신량, 서버 부하, 성능면에서 저하됨 - 캐싱에서의 대량 자료의 전송이 원격 서비스에서의 특정 요청에 대한 연속된 응답 전송보다 네트워크 부하가 적음 - 캐시 일관성 문제는 캐싱의 가장 큰 단점임 - 캐싱의 장점을 살리기 위해서는 실행을 지역 디스크나 기억장치를 가지는 클라이언트로 이동시키는 것이 바람직함 - 캐싱의 경우에 저수준의 기계간 인터페이스와 고수준의 사용자 인터페이스가 매우 다른 반면, 원격 서비스의 경우에는 기계간 인터페이스가 지역 사용자 파일 시스템 인터페이스를 그대로 확장한 것이라 할 수 있음 17.4 상태 정보를 가진 서비스(Stateful Service)와 상태 정보가 없는 서비스(Stateless Service) 유형 내용 상태 정보를 가진 서비스 상태 정보가 없는 서비스 서버의 역할 - 클라이언트에 의해 접근되는 파일을 계속 추적 - 클라이언트가 요구하는 블록을 단순히 제공 처리 속도 - 파일이 주기억장치에 캐시되고, 연결 식별자(inode)를 통해 쉽게 접근되므로 디스크 접근 횟수를 줄일 수 있음 - 파일의 순차적인 접근을 파악하여 다음 블록을 미리 판독할 수 있음 - 클라이언트의 목적을 서버가 알 수 없으므로, 클라이언트의 요구 메시지가 길고 요구에 대한 처리 속도가 느림 서비스 도중의 시스템 손상 - 서버 손상: 손실된 서버의 휘발성 정보를 복구하기 위해 클라이언트와 대화하는 프로토콜을 사용하여 손상 발생 전의 상태로 복구함 - 클라이언트 고장: “고아 탐지 및 제거(orphan detection and elimination)” 손상된 클라이언트의 프로세스 상태를 기록하고 있으므로 추후 복구 가능 - 서버 손상: 자신의 재구성 쉬움 단, 클라이언트는 서버가 느려졌다고 판단함 - 클라이언트 고장: 파일 동작을 클라이언트 스스로 수행하므로 불가능 추가 제한 요소 - 일정하고 전체적이고 저수준의 네이밍 기법이 요구됨 - 연속된 파일 동작 요구에 대해 여러 단계의 처리가 필요함 17.5 파일 중복(File Replication) ▶ 파일 중복의 특성 - 파일 중복은 가용성을 증가시킴 → 다중 기계 중복의 경우, 접근 요구에 대해 최단 서비스 시간이 소요되는 복사본 선택 - 파일 중복은 결함 독립 기계에서의 복사라야 함 → 복사본의 유용성은 나머지 복사본의 유용성과 무관 - 파일 중복을 사용자에게 숨기는 것이 바람직 → 중복된 파일 이름을 특정 복사본에 사상시키는 네이밍 필요 → 중복 제어: 중복의 수준을 결정하고 복사본의 위치를 결정하는 제어 행위 ▶ 문제점: 복사본의 갱신 → 사용자의 관점에서 복사본들은 동일한 논리적인 존재이므로, 임의 복사본에 대한 갱신은 다른 모든 복사본에게 반영되어야 함(일관성) - 일관성 유지 방법: 일관성 유지를 위해 프로세스의 무한정 대기 상태를 초래할 수 있는 방법 - 일관성 무시 방법: 프로세스 수행을 보장하기 위해 일관성 파괴로 인한 오류를 감수하는 방법 ex) Locus 시스템 ▶ 사례: Ibis의 중복 기법 - 주 복사 방법의 변형 - 이름 사상 영역: <주 복사본 식별자, 지역 복사본 식별자>으로 구성 - 요구 중복(demand replication): 존재하지 않는 복사본을 지역적으로 캐시하여 읽는 방법 - 갱신은 주 복사본에서만 실행되고, 적절한 메시지를 보내 다른 중복들을 무효화시킴 → 단위적이고 순차적인 무효화가 보장되지 않기 때문에 훼손된 복사본이 유효하다고 여겨질 수 있음 17.6 시스템 예제 ▶ 분산 파일 시스템의 5 가지 예: UNIX United, Sun NFS, Andrew, Sprite, Locus → 17.6.1-17.6.5

16. 분산 시스템 구조(Distributed System Structures) 16.1 네트워크 운영체제(Network Operating Systems) ▶ 다수의 시스템들에 대해 알고 있는 사용자에게 원격 자원을 접근할 수 있게 하는 환경을 제공 → 원격 로그인, 원격 파일 전송 16.1.1 원격 로그인(Remote Login) ▶ 인터넷의 telnet 기능 제공 ex) 원격 시스템 kcs.kongju.ac.kr에서의 연산 - 먼저, 원격 시스템에 계정을 가지고 있어야 함 - telnet kcs.kongju.ac.kr - 원격 시스템의 프로세스(데몬)가 사용자에게 로그인 이름과 패스워드를 요청 - 원격 로그인이 성공되면, 원격 시스템에서의 연산 가능 16.1.2 원격 파일 전송(Remote File Transfer) ▶ 인터넷의 파일 전송 프로토콜(file transfer protocol: FTP)프로그램 기능 제공 ex) kcs.kongju.ac.kr의 사용자가 cs.utexas.edu에 있는 파일 paper.txt를 my-paper.txt로 복사 - 먼저, 원격 시스템에 계정을 가지고 있어야 하고, 파일의 위치를 알고 있어야 함 - FTP 프로그램 호출: ftp cs.utexas.edu - 원격 시스템의 프로세스(데몬)가 사용자에게 로그인 이름과 패스워드를 요청 - 원격 로그인이 성공되면, 파일 paper.txt이 있는 부디렉토리로 연결: cd 부디렉토리 - 파일 복사: get paper.tex my-paper.tex (파일 공유 아님) ▶ 익명의 FTP(anonymous ftp) - 원격 시스템에 계정을 가지지 않아도 되지만, 원하는 파일 paper.txt는 공용 보호 설정으로 지정된 특정 부디렉토리 ftp에 위치해야 함 - FTP 프로그램 호출: ftp cs.utexas.edu - 원격 시스템의 프로세스(데몬)가 사용자에게 로그인 이름과 패스워드를 요청하면, 이름 “anonymous”와 임의의 패스워드(ex: email 주소)를 입력함 - 파일 복사: get paper.tex my-paper.tex (파일 공유 아님) ▶ FTP는 telnet과 유사하게 구현됨 - 원격 시스템에는 FTP 포트에 연결을 원하는 요청을 감시하는 데몬(demon)이 존재함 - 로그인 인증이 성취되면, 사용자는 원격적으로 명령을 실행할 수 있음 1) telnet 데몬: 모든 명령의 실행을 허용 2) FTP 데몬: 일반 운영체제 명령과는 다른 파일에 관련된 특별한 명령어 집합의 실행을 허용 → get, put, ls/dir, cd, 기타 전송모드나 연결 상태를 결정하는 명령 등 (p.543 참조) 16.2 분산 운영체제(Distributed Operating System) ▶ 분산 운영체제에서는 사용자들이 지역 자원에서와 동일한 방법으로 원격 자원에 접근 가능 16.2.1 자료 이주(Data Migration) ▶ 사이트 A에 있는 사용자가 사이트 B에 있는 파일 등의 자료에 접근하려 할 때, 시스템이 자료를 이동하는 두 가지 기본적인 방법 → 이때, 파일에 대한 모든 접근은 ‘로컬 방식’임 ① 파일 전체를 이동하는 방식 ex) Andrew 파일 시스템(17장) → 비효율적 file(자료) A B 접근요청 전체이동 반환 ② 실제 필요한 파일 일부를 이동하는 방식: 요구 페이징과 유사 ex) SUN Microsystem의 네트워크 파일 시스템(NFS) 프로토콜(17장) → 효율적 file(자료) A B 접근요청 일부이동 반환 ▶ 자료 이주 시, 다른 문자 코드를 사용한다면 번역이 필요할 수도 있음 16.2.2 연산 이주(Computation Migration) ▶ 대용량 파일의 접근이나 분석의 경우, 자료가 아닌 연산을 이동하는 것이 효율적임 → 파일이 위치하는 사이트에 접근하여 연산 후 결과를 반환 받는 것이 바람직 ① 원격 프로시저 호출(remote procedure call; RPC) - 프로세스 P가 원격 사이트 A에 프로시저를 통지하고, - 이 프로시저는 실행 후 결과를 반환 화일 결과 반환 프로세스 P 사이트 A 원격 프로시저 호출 ② 메시지 전송 - 프로세스 P가 원격 사이트 A에 작업에 대한 메시지를 보내면, - 원격 사이트에서는 해당 업무를 위한 프로세스 Q를 생성하고, 결과를 메시지 시스템으로 반환 화일 결과 반환 프로세스 P 사이트 A 메시지 전송 16.2.3 프로세스 이주(Process Migration) ▶ 프로세스의 전체 혹은 일부를 다른 사이트에서 수행 가능 → 연산 이주의 논리적 확장 ▶ 사용 이유 ① 부하 균등화(load balancing): 부하를 균등하게 하기 위해 프로세스를 분산함 ② 연산 속도 향상(computation speedup): 프로세스가 동시에 다른 사이트에서 수행될 수 있는 부분 프로세스들로 분리될 수 있다면, 전체 반환 시간(turnaround time)이 축소됨 ③ 하드웨어 선호성(hardware preference): 특정 프로세스는 특정 프로세서에 의해 수행되는 것이 적합할 수 있음 ④ 소프트웨어 선호성(software preference): 특정 프로세스는 특정 사이트의 소프트웨어에 의해 수행하는 것이 적합할 수 있음 ⑤ 데이터 접근(data access): 데이터의 양이 많은 경우 데이터의 이주보다 프로세스의 이주가 바람직함 ▶ 프로세스 이주를 위한 두 가지 상호보완적인 기법 ① 시스템은 프로세스가 이동되었다는 사실을 사용자로부터 숨김 즉, 사용자가 이주 명령을 명시할 필요 없음 → 주로 부하 균형, 연산 속도 향상 목적 ② 사용자가 프로세스의 이주를 명시하는 경우 → 특정 하드웨어나 소프트웨어의 선호성 목적 16.3 원격 서비스(Remote Services) ▶ 원격 서비스 방식: 접근 요청이 원격 서버에 전해지면, 서버는 접근을 수행하고 그 결과를 사용자에게 반환 16.3.1 원격 프로시저 호출(Remote Procedure Calls; RPC) ▶ 원격 프로시저 호출 - 메시지 기반 통신 기법 사용 - 원격 시스템으로 전송되는 메시지들은 해당 포트(port)에 반응하는 RPC 데몬으로의 주소가 지정되어 있으며, 함수의 식별자와 매개변수를 보유함 - 포트 번호는 메시지 패킷의 첫 부분에 부착됨 - 해당 함수가 수행되고 결과가 요청자에게 반환됨 ▶ RPC 동작에 관한 문제 1) 호출의 의미(semantics): 통상적인 네트워크 에러로 인해 RPC는 실패(fail)나 중복(duplicated)될 수 있음 → 메시지에 타임 스탬프를 부착하여 전송하고, 서버가 수령한 메시지의 모든 타임 스탬프 이력을 보관하고 중복되는 메시지를 무시함으로써 해결 가능 2) 서버와 클라이언트간의 통신에 관한 문제: 클라이언트가 서버의 포트 번호를 파악하는 방법 ① 바인딩 정보가 고정 포트 주소 형태로 사전에 결정되게 하는 방법 → 컴파일시에 RPC 호출은 관련된 고정 포트 번호로 고정됨 ② 바인딩이 랑데부 기법에 의해 동적으로 실행되게 하는 방법 - 운영체제는 특정 RPC 포트에 랑데부 데몬(부합기(matchmaker))을 둠 - 클라이언트는 부합기에 RPC의 이름을 메시지로 보내 해당 RPC의 포트 주소를 요청함 - 포트 번호가 반환되고, RPC 호출이 해당 포트로 전송됨 → 추가적인 부하가 요구되지만, 보다 융통성이 있음 [그림 16.1] 원격 프로시저 호출의 실행 16.3.2 스레드(Threads) ▶ 스레드: 태스크 내부에서 다른 연산들이 비동기적으로 계속 작동되고 있는 동안에 메시지를 보내거나 받기 위해 사용됨 * 팝업 스레드(pop-up-thread): 새로운 RPC에 응답하기 위해 “필요할 때” 만들어지는 스레드 ▶ 동일 기계에서 실행되는 다른 프로세스들에 있는 스레드 간에 공유 기억장치를 통해 매우 효율적인 통신이 가능하다면 RPC는 보다 경량화될 수 있음 * 서버 스레드(Server Threads; ST) ↔ 클라이언트 스레드(Client Thread; CT) ▶ OSF의 DCE(Distributed Computing Environment) → UNIX 및 Microsoft Windows/NT에서 사용 * 호출: p.550의 내용 16.4 견고성(Robustness) ▶ 분산 체제에서 발생 가능한 결함: 링크의 결함, 사이트의 결함, 메시지 분실 등 → 견고한 시스템을 위해, - 결함을 탐지하고, - 시스템을 재구성하여 연산을 계속하고, - 사이트나 링크가 회복되면 복구되어야 함 16.4.1 결함 탐지(Failure Detection) ▶ 일반적으로 링크 결함, 사이트 결함, 메시지 분실을 탐지할 수는 있지만 이를 구별하기는 거의 불가능함 ▶ 핸드 쉐이킹 프로시저(hand shaking procedure): 링크와 사이트의 결함 탐지용 ① 사이트 A와 B가 직접적인 물리적 링크로 연결되어 있다면, 고정된 시간 간격마다 양 사이트는 서로 I-am-up이라는 메시지를 보냄 ② 만일 A가 정해진 시간동안에 이 메시지를 받지 못하면, - 사이트 B가 결함이거나, - A와 B 사이의 링크가 결함이거나, - B로부터의 메시지 분실이라고 가정함 ③ 또 다시 일정 시간동안 B로부터의 I-am-up 메시지를 기다리거나, 혹은 B에게 Are-you-up? 메시지를 보내고 응답을 기다림 → 이 과정을 몇 차례 반복한 후에도 응답이 없으면, 링크나 사이트의 결함으로 단정함 ④ 사이트 A는 Are-you-up? 메시지를 가능한 다른 경로를 통해(존재할 경우) B에게 보내어 링크 결함과 사이트 결함을 구별할 수 있음 → “시간 제한(time-out) 기법” 사용 - 제한 시간내에 응답이 있는 경우, 링크 결함을 단정함 - 제한 시간내에 응답이 없는 경우, 다음 중 어떤 것이 실제로 발생했는지 판단할 수 없음 1) 사이트 B가 다운되었거나, 2) A에서 B로의 (유일한) 직접 경로가 다운되었거나, 3) A에서 B로의 대체 경로도 다운되었거나, 4) 메시지가 분실되었음 16.4.2 재구성(Reconfiguration) ▶ 결함을 탐지한 사이트 A는 시스템을 재구성하고 정상적인 작동을 위한 프로시저를 시작함 ① A에서 B로의 링크 결함인 경우: 체제 내의 다른 모든 사이트에 알려, → 라우팅 테이블을 수정하게 함 ② 사이트의 결함인 경우: 체제 내의 다른 모든 프로세스에 알려, - 고장난 사이트를 이용하지 않게 하고, - 특히, 중앙 조정자의 결함인 경우 새로운 조정자 선출이 요구되고, - 결함이 논리적인 링 부분인 경우 논리적인 링을 재구성함 - 만일, 고장이 아닌 도달될 수 없는 상태라면 네트워크 분할을 의미함 → 이 경우 두 사이트가 조정자 역할을 수행함으로써 두 사이트가 동시에 임계구역에 들어가게 되는 현상 등이 발생할 수 있음 16.4.3 결함 복구(Recovery from Failure) ▶ 결함인 링크나 사이트가 수리되면, 무리 없이 시스템에 통합되어야 함 ① A와 B 사이의 링크 결함이 수리되면, 이 사실을 양 사이트가 인지해야 함 → 계속된 핸드 쉐이킹 프로시저에 의해 해결될 수 있음 ② 사이트 B의 결함이 복구되었을 때, 이 사실을 다른 모든 사이트에 알리고 다른 사이트들로부터 정보를 얻어 지역 테이블을 갱신함 ex) 라우팅 테이블, 다운된 사이트들의 목록, 도달되지 않은 메시지나 메일 등의 정보 16.5 설계시 고려 사항 ▶ 분산 시스템의 설계를 위한 주요 특성 - 투명성(transparency): 사용자들에게 중앙 집중식 시스템으로 보이게 함 → 사용자 이동성(user mobility): 어떤 시스템에서도 로그인 할 수 있음 - 결함 허용(fault tolerance): 어느 정도의 결함으로 기능 저하가 수반되더라도 계속 수행 가능 → 결함 허용 시스템 - 확장성(scalability): 증가하는 서비스 부하에 적응하는 능력 ▶ 대규모 분산 시스템 설계의 문제점 ① 부하 요구가 시스템 크기에 비례하는 서비스 기법은 확장성을 제한함 ② 중앙 집중식 제어 기법과 집중식 자원은 결함 허용 시스템의 구축에 사용될 수 없음 ③ 서버의 프로세스 구조: 경량 프로세스 혹은 스레드가 바람직

제 5 부 분산 시스템(Distributed Systems)

15. 네트워크 구조(Network Structures)

▶ 여러 개의 물리적 프로세서(physical processor)들 사이에 연산을 분산시키는 방법

① 강 결합(tightly coupled) 시스템

- 프로세서들은 기억장치(memory)와 클록(clock)을 공유

- 통신은 주로 공유된 기억장치를 통하여 일어남

② 약 결합(loosely coupled) 시스템

- 프로세서들은 각자 고유의 국소 기억장치와 클록을 지님

- 통신은 고속의 버스나 전화선과 같은 통신 라인을 통하여 일어남

15.1 배경(Background)

▶ 분산 시스템: 통신 네트워크를 통하여 서로 약 결합된 프로세서들의 집합

- 지역(local) 자원: 그 프로세서가 가지고 있는 자원

- 원격(remote) 자원: 다른 프로세서들 및 그들이 가지고 있는 자원

▶ 분산 시스템의 프로세서: 사이트(site), 노드(node), 컴퓨터(computer), 기계(machine)

→ 마이크로 컴퓨터, 워크스테이션, 미니 컴퓨터, 메인 프레임 컴퓨터, 슈퍼컴퓨터 등

- 서버(server): 자원을 가지고 있는 사이트

- 클라이언트(client): 그 자원을 사용하는 사이트

[그림 15.1] 분산 시스템

▶ 자원 접근 기법

① 네트워크 운영체제: 사용자는 시스템의 다양성을 알고 있어야 함

  → 해당 원격 시스템에 로그인하든지, 또는 원격 시스템으로부터 자료를 전달받음

② 분산 운영체제: 사용자는 시스템의 다양성을 이해할 필요 없음

  → 지역 자원들을 접근하는 방법과 동일한 방법으로 원격 자원들을 접근

15.2 동기(Motivation)

▶ 분산 시스템의 목적: 자원 공유, 연산 속도 향상, 신뢰성, 통신

15.2.1 자원 공유(Resource Sharing)

   연결

사이트 A     사이트 B

 파일  레이저 프린터

▶ 분산 시스템에서의 자원 공유 방식

- 파일의 공유

- 분산 데이터베이스에서의 정보 처리

- 원격 사이트에서의 파일 인쇄

- 원격 특수 목적의 하드웨어 사용

15.2.2 연산 속도 향상(Computation Speed-up)

▶ 특정 연산이 동시 수행 가능한 다수의 부 연산(sub-computation)으로 분할될 수 있는 경우

→ 여러 사이트에 연산을 분산시켜 유용성(availability)을 높임

▶ 특정 사이트가 현재 너무 많은 작업으로 과부하(overload) 상태인 경우

→ 일부 작업을 덜 부하가 걸린 사이트로 이동시켜 부하 공유(load sharing)를 함

15.2.3 신뢰성(Reliability)

▶ 분산 시스템의 구성

- 자치 시설들(autonomous installations)로 구성된 경우: ex) 범용 컴퓨터

→ 하나의 고장을 극복할 수 있음

- 각 기능을 책임지는 작은 기계들로 구성된 경우: ex) 터미널 문자 입출력, 파일 시스템 등

→ 하나의 고장이 전체 시스템의 고장임

▶ 일반적으로 시스템 내에 같은 종류의 하드웨어와 자료를 여러 개 중복시킨다면, 사이트들의 일부가 고장난다 할지라도 시스템은 계속 동작될 수 있음

- 사이트의 고장을 시스템에 의해 감지될 수 있어야 함

- 시스템은 고장난 사이트에 대한 서비스를 더 이상 사용해서는 안됨

- 고장난 사이트를 대행하는 사이트에 기능이 올바르게 이동되었는지 확인하여야 함

- 회복 또는 수리된 사이트가 체제 내에 무리 없이 포함될 수 있는 기법이 있어야 함

15.2.4 통신(Communication)

▶ 여러 사이트들이 통신 네트워크를 통해 연결되어 있으면, 다른 사이트에 있는 사용자들은 정보를 교환할 수 있음

→ 시스템간의 메시지 전송은 단일 컴퓨터 내에서의 메시지 전송과 유사함

ex) 파일 전송, 로그인, 메일, 원격 프로시저 호출 등

▶ 분산 시스템의 장점들은 다운사이징(downsizing)이라는 산업화 경향을 탄생시킴

→ 메인 프레임을 워크스테이션이나 개인용 컴퓨터로 구성된 네트워크로 구성

(장점) 비용 감소, 자원 관리의 유용성과 확장성, 우수한 사용자 인터페이스, 손쉬운 유지 보수

▶ 메시지 전송 방식의 운영체제는 분산 시스템으로 쉽게 확장될 수 있음

15.3 위상(Topology)

▶ 시스템 내의 사이트들이 연결되는 물리적 방법의 비교 기준

① 기본 비용: 시스템 내의 여러 사이트들을 연결하는데 드는 비용

② 통신 비용: 사이트간에 메시지를 전달하는데 드는 비용

③ 신뢰성: 시스템 내의 링크나 사이트가 고장날 경우, 나머지 사이트들 간의 통신 가능 여부

▶ 위상의 표현: 그래프

- 노드(node): 사이트(site)

- 간선(edge): 사이트간의 직접 통신 경로

15.3.1 완전 연결 네트워크(Fully Connected Networks)

▶ 개념: 각 사이트가 시스템 내의 다른 모든 사이트와 직접 연결되는 형태

  [그림 15.2] 완전 연결 네트워크

- 기본 비용: 모든 두 사이트간의 연결로 매우 비쌈 ∝ (사이트 수)2 

- 통신 비용: 임의의 두 사이트간의 메시지 전달이 단 한번의 링크 사용으로 처리되므로 매우 신속 

- 신뢰성: 많은 수의 링크가 고장나야 시스템이 분할되기 때문에 신뢰성이 매우 높음

15.3.2 부분 연결 네트워크(Partially Connected Networks)

▶ 개념: 일부 사이트 사이에만 직접 연결이 존재하는 형태

[그림 15.3] 부분 연결 네트워크

- 기본 비용: 완전 연결 네트워크보다 저렴

- 통신 비용: 완전 연결 네트워크보다 느림  

ex) A→D vs A→B→C→D

- 신뢰성: 완전 연결 네트워크보다 떨어짐 

→ 네트워크의 분할 가능성이 높음

ex) 의 고장 → 분해: A,B,E ↔ C,D

→ 분할 가능성을 낮추기 위해, 각 사이트가 적어도 두 개의 다른 사이트와 연결되게 하는 방법

ex)  링크의 첨부

15.3.3 계층 네트워크(Hierarchical Networks)

▶ 개념: 트리 구조의 연결 형태

[그림 15.4] 트리 구조 네트워크

- 기본 비용: 일반적으로 부분 연결 기법보다 낮음

- 통신 비용: 일반적으로 부분 연결 기법보다 느림 → 공통의 조상 노드를 통해 메시지를 전달

- 신뢰성: 낮음 → 단말 노드를 제외한 노드의 고장은 분할을 초래

ex) 회사의 컴퓨터 네트워크

15.3.4 성형 네트워크(Star Networks)

▶ 개념: 특정의 한 사이트만이 다른 모든 사이트와 직접 연결이 존재하고, 그 외 사이트들은 서로 연결되지 않은 형태

[그림 15.5] 성형 네트워크

- 기본 비용: 사이트 수에 비례

- 통신 비용: 최대 2개의 링크 이동만 소요, 그러나 중심 사이트에서의 병목 현상으로 속도 저하됨

→ 이동 회수 감소, 이동 시간 증가

- 신뢰도: 중앙 사이트에 고장이 발생하면 네트워크는 완전히 분할됨

15.3.5 링 네트워크(Ring Networks)

▶ 개념: 각 사이트가 정확히 다른 두 사이트와 물리적으로 연결되는 형태

→ 정보 전달의 방향: 단방향(unidirectional) 또는 양방향(bidirectional)

[그림 15.6] (a)

- 기본 비용: 사이트 수에 비례

- 통신 비용: 매우 높음

1) 단방향의 경우: 최대 n-1번의 메시지 전송 소요

2) 양방향의 경우: 최대 n/2번의 메시지 전송 소요

- 신뢰도: 낮음

1) 단방향의 경우: 한 사이트 고장 → 분할

2) 양방향의 경우: 두 사이트 고장 → 분할

▶ 신뢰도 향상을 위한 이중 연결 링 구조: [그림 15.6] (b)

 

15.3.6 다중 접근 버스 네트워크(Multiaccess Bus Networks)

▶ 개념: 모든 사이트가 공유하는 버스(bus)라는 하나의 링크를 두는 형태

ex) 직선 버스, 링 버스

[그림 15.7] 버스 네트워크

- 기본 비용: 사이트 수에 비례

- 통신 비용: 매우 낮음, 그러나 버스에 대한 병목 현상이 발생할 수 있음

- 신뢰도: 낮음

→ 한 사이트의 고장은 통신에 영향을 주지 않으나, 링크의 고장은 완전한 분할을 초래함

* 메시지 교환 전용 중심 사이트를 지닌 성형 네트워크의 위상과 유사함

* 이더넷(Ethernet) 네트워크는 다중 접근 버스 모델을 기반으로 함

15.3.7 혼성 네트워크(Hybrid Networks)

▶ 개념: 서로 다른 유형의 네트워크들이 상호 연결되어 있는 형태

ex) 한 사이트 내에서는 이더넷과 같은 다중 접근 버스가 사용되고, 사이트들 간에는 계층 네트워크가 사용되는 형태

→ 통신은, 상호간에 다중 프로토콜을 번역해야 하고 자료에 대한 경로 배정이 복잡하기 때문에 다소 어려움이 있음

15.4 네트워크 형태(Network Types)

▶ 지역적으로 분산되는 방식에 따른 분류

- 근거리 통신망(Local-Area Network; LAN): 좁은 지역 ex) 빌딩 내, 인접한 빌딩 등

- 원거리 통신망(Wide-Area Network; WAN): 넓은 지역 ex) 미 대륙

15.4.1 근거리 통신망(Local-Area Network; LAN)

▶ 동기: 1970년대 메인 프레임 컴퓨터 시스템의 대용으로 탄생

- 하나의 큰 메인 프레임대신 다수의 작은 컴퓨터를 이용함으로써 보다 경제적임

- 자원이나 자료의 공유 위한 네트워크 연결 필요

▶ 통신 네트워크

- 특성: 모든 사이트가 서로 근접해 있기 때문에, 일반적인 컴퓨터 네트워크보다 속도가 높고 오류 발생률이 낮음

- 종류: 트위스트 페어(twisted pair), 기저대역 동축케이블(baseband coaxial cable), 광섬유(fiber optics) 등

- 형태: 다중 접근 버스, 링, 성형 네트워크 등

- 속도: 1Mbyte/sec - 1Gbyte/sec (일반적으로 10Mbyte/sec 정도)

- 구성: [그림 15.8] 근거리 통신망(LAN)

ex) 다수의 이종 소형 컴퓨터, 공유 주변 장치, 게이트웨이(gateway) 등

                                      ↙             ↘

                 (레이저 프린터, 자기 테이프 등)   (다른 네트워크 접근을 위한 특정 프로세서)

→ 주로 이더넷 방법 사용: 다중 접근 버스를 사용하기 때문에 중앙 제어기가 따로 필요 없으므로 새로운 호스트를 네트워크에 쉽게 추가 할 수 있음

15.4.2 원거리 통신망(Wide-Area Network; WAN)

▶ 동기

- 1960년대 말경, 사이트간의 효율적인 통신 제공을 위해 시작하였으며, 광범위 사용자 모임에 의해 하드웨어와 소프트웨어를 공유하였음

- “Arpanet”이 시조

▶ 통신 네트워크

- 특성: 지역적으로 광범위하게 사이트들이 분산되어 있기 때문에, 통신 링크는 비교적 느리고 신뢰성이 낮음

- 종류: 전화선, 마이크로웨이브 링크, 통신 위성 채널 등

→ 보통 표준 전화선 사용: 모뎀(modem) - 디지털 신호 ↔ 아날로그 신호

- 속도: LAN보다 느림

1) 전화 시스템 서비스 T1의 경우, 1.544Mbyte/sec

2) 28개의 T1이 병렬로 구성된 T3의 경우, 45Mbyte/sec

- 구성: [그림 15.9] 원거리 통신망에서의 통신용 프로세서

→ 특정 통신 프로세서(CP)에 의해 조정됨

15.5 통신(Communication)

▶ 통신 네트워크 내부동작을 위해 설계자가 고려해야 할 기본 문제

① 네이밍(naming)과 이름 변환(name resolution): 상호 통신하는 두 프로세스의 배치에 관한 기법

② 라우팅 전략(routing strategies): 메시지의 전송 경로 배정에 관한 기법

③ 패킷 전략(packet strategies): 패킷의 개별적 혹은 연속적 전송에 관한 기법

④ 연결 기법(connection strategies): 두 프로세스간의 메시지 전송에 관한 기법

⑤ 경쟁(contention): 네트워크 사용 요구의 충돌 해결에 관한 기법

15.5.1 네이밍(Naming)과 이름 변환(Name Resolution)

▶ 프로세스의 명칭: <호스트 이름, 식별자>

- 호스트 이름: 네트워크 상의 고유 이름 host-id ex) kcs

- 식별자: 사이트 내에서의 프로세스 고유번호 process-id

▶ 호스트 명칭을 명시하는 두 가지 방법

1) 모든 호스트가 네트워크를 통해 접근할 수 있는 다른 호스트의 이름과 주소를 포함하는 자료 파일을 가지는 방법(컴파일 시의 바인딩과 유사)

→ 호스트의 추가 혹은 제거할 때마다 모든 호스트의 자료 파일을 갱신해야 함

즉, 특정 사이트에 모든 파일의 정보가 유지되도록 각 사이트가 정기적으로 갱신

2) 네트워크 상의 시스템들 사이에 정보를 분산시키는 방법(실행 시의 바인딩과 유사)

→ “영역 이름 서비스(Domain Name Service; DNS)”

즉, 각 이름 서버 사이트가 해당 영역에 대한 호스트 정보를 자동 조사에 의해 갱신함

- 이름 서버(name server): 이름의 요소를 역순으로 받아들여 host-id를 반환하는 프로세스

  ex) kcs.kongju.ac.kr → 210.106.81.35

- 시스템 A에 있는 프로세스가 “bob.cs.brown.edu”와 통신하기 위한 절차

① A의 커널은 “edu”에 대한 이름 서버에게 “brown.edu”에 대한 이름 서버의 주소를 질의

→ “edu”의 이름 서버는 “brown.edu” 명칭 서버가 상주하는 호스트의 주소를 반환

② A의 커널은 그 주소의 이름 서버에 “cs.brown.edu”에 대해 질의

→ 해당 주소가 반환됨 

③ A의 커널은 그 주소에 “bob.cs.brown.edu”에 대해 질의

→ 해당 호스트의 인터넷 주소인 host-id(ex: 128.148.31.100)를 반환

- 각 영역은 자치적인 부 영역들을 둘 수 있음

- <호스트 이름, 식별자>를 지닌 메시지를 수령한 목적지 호스트의 커널은 식별자에 나타난 프로세스에 메시지를 전달

15.5.2 라우팅 전략(Routing Strategies)

▶ 물리적 경로의 수

- 유일: 스타 구조 네트워크, 계층 구조 네트워크

- 다수: 나머지의 일반적인 구조

▶ 라우팅 테이블(routing table): 각 사이트마다 다른 사이트로 메시지를 보내는 경로를 저장

→ 각 통신 경로의 속도 및 비용 등의 정보를 기록

▶ 라우팅 전략

① 고정 라우팅(fixed routing): 유일한 경로 사용

- 하드웨어 고장이 일어나지 않는 한 변경되지 않음

- 일반적으로 통신비용을 최소화하기 위해 최단거리 경로를 선정

→ 링크의 고장이나 부하 변화에 적응 못함, 메시지 전송순서대로 도착됨

② 가상 회선(virtual circuit): 일정 기간(session) 동안 고정되는 경로 사용

ex) 파일 전송(단시간), 원격 등록(장시간) 등

→ 부하 변화에 부분적으로 적응 가능, 메시지 전송순서대로 도착됨

③ 동적 라우팅(dynamic routing): 메시지 보낼 때마다 결정되는 경로 사용

- 일반적으로 사이트는 특정 순간에 가장 적게 사용되는 링크를 통하여 메시지를 전송함

→ 부하 변화에 적응적임, 단 메시지 도착순서가 바뀔 수 있음(메시지 번호로 해결 가능)

※ 정적 라우팅과 동적 라우팅을 혼용하는 방법: “게이트웨이(gateway)”

- 정적 라우팅: 각 호스트에서 게이트웨이로의 경로

- 동적 라우팅: 게이트웨이에서 다른 네트워크 상의 사이트로의 경로

▶ 라우터(router): 메시지를 라우팅하기 위해 컴퓨터 시스템에 있는 한 부분

15.5.3 패킷 전략(Packet Strategies)

▶ 패킷(packet), 프레임(frame), 데이터그램(datagram): 일반적으로 가변 길이인 메시지를 고정 길이로 전송하는 기본 단위

▶ 미연결(connectionless) 메시지: 패킷의 도착을 회신하지 않는 방식의 메시지, 신뢰성 낮음

→ 신뢰도를 높이기 위해 연결(connection) 필요

15.5.4 연결 전략(Connection Strategies)

▶ 네트워크를 통하여 통신하고자 하는 프로세스 쌍을 연결하는 방법

① 회로 교환(circuit switching): 통신기간 동안에 두 프로세스 사이에 물리적 연결이 설정되고, 그 동안에는 다른 프로세스가 이 링크를 사용 못함

ex) 전화 체제와 유사: 통화중에는 제 3자가 통화할 수 없음

→ 초기 설정 시간 필요, 각 메시지별 오버헤드 적음

② 메시지 교환(message switching): 각 메시지의 이동 기간마다 두 프로세스간에 물리적인 링크가 동적으로 짧은 시간동안 설정됨

* 메시지: 자료 블록(가변 길이)

  - 시스템 정보: 출발지, 목적지, 오류 수정 코드 등

  - 실제 자료

ex) 우편 체제와 유사: 다른 사용자들로부터의 여러 메시지들이 같은 링크를 통해 전송됨

→ 초기 설정 시간 적지만, 각 메시지별 오버헤드 큼

③ 패킷 교환(packet switching): 메시지를 고정 길이의 패킷으로 나누어 패킷별로 전송하고, 도착한 패킷들을 재결합함

→ 초기 설정 시간 적지만, 각 메시지별 오버헤드 매우 큼(패킷마다 오버헤드가 부착되기 때문)

15.5.5 경쟁(Contention)

▶ 여러 사이트가 동시에 하나의 링크를 통해 정보를 보내고자 하는 상황

- 주로 링이나 다중 접근 버스 네트워크의 경우에 발생

- 충돌된 정보는 폐기되고 재전송해야 함

▶ 충돌 회피를 위한 기법

① CSMA/CD

- CSMA(carrier sense with multiple access): 메시지를 전송하기 전에 링크가 사용 가능할 때까지 계속해서 확인

- CD(collision detection): 충돌 탐지

  두 사이트가 정확히 동시에 전송을 시작하면 충돌이 발생될 수 있으므로, 각 사이트는 다른 사이트가 보내는 메시지와 충돌이 있는지 항상 감시해야 하고, 만일 충돌이 탐지되면 전송을 중단하고 재시도해야 함

→ 부하가 많을수록 충돌이 빈번해짐

ex) 이더넷(ethernet) 시스템에 성공적으로 사용중

② 토큰 전달(token passing)

- 보통 링 구조에서 토큰이라는 메시지가 순환하고 있고, 정보를 전송하려는 사이트는 토큰이 도착하면 토큰을 링에서 제거 후 메시지를 전송하고 메시지 전송이 완료되면 토큰을 재전송하는 방법

- 시스템은 토큰의 분실을 탐지해야 하고, 선출 알고리즘(18.6절)에 의해 사이트를 선택하면 그 사이트가 토큰을 생성함

→ 처리 능력이 일정함

ex) IBM과 Apollo 시스템에서 채용

③ 메시지 슬롯(message slot)

- 보통 링 구조에서 다수의 고정 길이 메시지 슬롯이 순환중이고, 사이트는 빈 슬롯이 도착해야 메시지와 제어 정보(출발지, 목적지, 슬롯의 할당여부 등)를 슬롯에 넣어 전송함

- 각 사이트는 슬롯의 제어 정보를 조사하여 자기 것이 아니면 슬롯을 재전송하고, 자기 것이면 슬롯의 메시지를 꺼내고 슬롯이 비었음을 나타내도록 제어 정보를 재설정함

ex) 캠브리지 디지털 통신링(Cambridge Digital Communication Ring)에 시험용으로 채택

15.6 설계 전략(Design Strategies)

▶ 통신 네트워크의 설계: [그림 15.10] ISO 네트워크 모델을 통한 두 컴퓨터간 통신

→ 느리고 오류가 많은 환경에서 비동기적인 동작들을 조정하는 문제를 고려해야 함

- 구현을 위한 문제를 계층적으로 분할하여 간략화 함

- 한 시스템의 각 계층은 다른 시스템의 동일한 계층과 통신함

- 각 계층은 고유의 프로토콜을 가지며, 프로토콜은 하드웨어 또는 소프트웨어로 구현됨

▶ 국제 표준 기구(International Standard Organization; ISO)의 계층 구조

[그림 15.11] ISO 프로토콜 계층 요약

① 물리적 계층(physical layer): 비트 스트림을 물리적으로 전송하는 기계적, 전기적 사항들을 담당

→ 하드웨어 네트워크 장치로 구현

② 자료 연결 계층(data-link layer): 프레임이나 고정 길이 패킷의 처리를 담당

→ 물리 계층에서 발생하는 오류 탐지와 회복까지 담당

③ 네트워크 계층(network layer): 통신망에서 연결 제공과 패킷의 경로 배정을 담당

→ 라우터 수행: 나가는 패킷의 주소 제어, 들어오는 패킷의 주소 해독, 부하 변화에 따른 경로 배정 정보 유지 등

④ 트랜스포트 계층(transport layer): 네트워크에 대한 하위 수준의 접근 및 클라이언트간의 메시지 전달 담당

→ 메시지를 패킷으로 분할, 패킷의 순서 유지, 흐름 제어, 물리적 주소의 생성 등

⑤ 세션 계층(session layer): 세션 즉, 프로세스와 프로세스간의 프로토콜 구현 담당

→ 원격 로그인, 파일 및 메일 전송 등을 위한 실제 전송

⑥ 표현 계층(presentation layer): 사이트간의 형식적 차이를 해결

→ 문자 변환, 문자 에코잉(반 듀플렉스(half duplex)-전 듀플렉스(full duplex) 모드) 등

⑦ 응용 계층(application layer): 사용자간의 직접적인 상호 교신을 허용

→ 파일 전송, 원격 로그인 프로토콜, 전자우편, 분산 데이터베이스 등

▶ 물리적으로 하나의 메시지는 상위 계층에서 하위 계층으로 전달되어 최종적으로 패킷으로 전송되고, 수신측에서는 메시지가 하위 계층에서 상위 계층으로 상승하면서 분석되고 헤드가 제거됨

[그림 15.12] ISO 네트워크 메시지

→ 실제로는 ISO 모델을 사용하지 않고 보다 적은 계층으로 구성된 TCP/IP 모델을 주로 사용함

▶ TCP/IP(Transmission Control Protocol/Internet Protocol)

[그림 15.13] TCP/IP 프로토콜 계층

* IP 프로토콜: 정보의 기본 단위인 IP 데이터그램의 인터넷을 통한 전송 담당

① TCP/IP: 연결(connection) 전송 프로토콜 - 응답 있음

→ TCP 프로토콜이 IP를 사용하여 두 프로세스간에 정보 스트림을 신뢰성 있게 전송

② UDP/IP: 무연결(connectionless) 전송 프로토콜 - 응답 없음

→ UDP 프로토콜이 IP를 사용하여 두 프로세스간에 정보 스트림을 신뢰성 없게 전송

15.7 네트워킹의 예: [그림 15.14] 이더넷 패킷

14. 제3의 저장장치 구조(Tertiary Storage Structure)

14.1 제3의 저장장치(Tertiary-Storage Devices)

▶ 제3의 저장장치의 특성

- 저렴

- 제거 가능

ex) 플로피 디스크, CD-ROM 등

14.1.1 제거 가능한 디스크(Removable Disks)

▶ 판독기록 디스크: 반복된 쓰기, 읽기 가능

① 제거 가능한 자기 디스크

ex) 플로피 디스크

- 플라스틱 케이스로 보호

- 용량: 1Mbyte - 1Gbyte 이상

- 하드디스크만큼 빠르게 동작

- 표면의 긁힘에 의한 손상 가능

② 자기 광 디스크

- 자기 광 헤드는 자기 디스크 헤드보다 디스크 표면으로부터 멀리 떨어짐

- 플라스틱이나 유리에 의한 자기 물질 보호

- 헤드에 의한 손상으로부터 보다 안전

- 레이저빔이 주사된 좁은 지점(비트)은 가열되어 자기장을 받아들일 수 있는 샵(shop)을 형성

- 레이저 빛의 Kerr효과에 의한 한 비트를 판독

→ 레이저빔이 자기 지점에서 반사될 때 자기장의 방향에 따라 시계방향 또는 반 시계방향으로 회전하는 현상을 이용

③ 광 디스크

→ 자기장을 사용하지 않고 레이저 빛에 의해 상대적으로 밝거나 어두운 점으로 변경하는 기술

1) 단계 변화(phase-change) 디스크

- 레이저 빛의 강도를 조절하여 결정체나 비결정체로 상태를 변화시킴

- 두 상태는 레이저 빛을 서로 다른 강도로 반사함

2) 염료 중합체(dye-polymer) 디스크

- 디스크는 레이저 빛을 흡수하는 염료를 포함한 플라스틱으로 입혀짐

- 레이저는 작은 점을 가열하여 융기(bump)를 만들어냄

- 레이저 빛의 강도를 조절하여 부드러운 상태나 원래의 상태로 변화시킴

▶ WORM 디스크: 단 한번만 쓰고 여러 번 판독

ex) CD-ROM, DVD

- 두 장의 유리나 플라스틱 판 사이에 알루미늄 필름을 넣음

- 레이저 빛으로 알루미늄 필름을 통과시켜 작은 구멍을 냄

- 영구적이고 신뢰성이 높음

14.1.2 테이프(Tapes)

▶ 특성

- 저렴하고 방대한 자료 저장 가능

- 전송 속도는 디스크와 유사하나, 임의 접근 속도는 훨씬 느림

→ 빨리 감기나 되감기의 속도가 느리기 때문

- 디스크 자료의 백업 복사용으로 많이 사용됨

▶ 로보틱 테이프 교환기: 테이프 구동기와 테이프 저장고의 저장 슬롯 사이에 테이프를 옮김

- 스태커(stacker): 소수의 테이프를 가지고 있는 저장고

- 사일로(silo): 많은 수의 테이프를 가지고 있는 저장고

→ 니어라인(near-line) 저장장치로도 불림

14.1.3 향후 기술

▶ 예: 입체 사진의 저장 - 현재는 비용이 많이 들어 사용되지 않고 있음

14.2 운영체제 작업(Operating-System Jobs)

14.2.1 응용 인터페이스(Application Interface)

▶ 제거 가능한 디스크: 고정된 디스크와 거의 동일한 방식으로 관리

→ 새로운 카트리지가 구동기에 들어오면, 포맷된 후 공백의 파일 시스템이 만들어짐

▶ 테이프: 하드디스크와 다르게 관리

- 운영체제는 테이프를 가공하지 않은 저장 매체로서 표현함

- 응용은 테이프에 있는 파일을 개방하는 것이 아니라, 전체 테이프 구동기를 개방함

- 독점적으로 사용되기 때문에, 여러 응용에서 인터리빙(interleaving)될 경우 스레딩 발생 가능

- 운영체제의 도움 없이, 응용이 블록의 배열을 어떻게 사용할지를 결정함

→ 테이프는 해당 응용에 의해서만 사용될 수 있음

- 테이프 구동기의 기본 명령: read, write, locate(디스크의 seek 대신 사용)

- 테이프 구동기는 다양한 블록 크기를 가질 수 있고, 각 블록의 크기는 블록이 저장될 때 결정됨

- read position 명령: 테이프 헤드가 위치한 논리적 블록 숫자를 반환

- space 명령: ex) space-2: 두 개의 논리적 블록 뒤에 위치시킴

- 테이프 구동기는 추가 전용 장치임: 기록된 블록 뒤에 테이프 끝(EOT; end-of-tape) 표시를 함

→ 테이프의 중간에서 블록을 변경시키면 그 블록 뒤의 모든 것을 지움

14.2.2 파일 네이밍(File Naming)

▶ 일반적으로 오늘날의 운영체제는 제거 가능한 매체에 대한 이름 공간 문제를 해결하지 않은 채 남겨 놓고 있으며, 자료에 접근하고 해석하는 문제는 응용과 사용자에게 남겨 놓고 있음

ex) 표준화된 예: CD

14.2.3 계층적 저장장치 관리(Hierarchical Storage Management)

▶ 주크박스(jukebox): 제3의 저장장치의 카트리지를 자동적으로 교체하는 장치

▶ 계층적 저장장치 시스템: 주기억장치, 보조기억장치, 제3의 저장장치

→ 파일 시스템의 확장: 원하는 파일이 보조기억장치에 없으면 제3의 저장장치로부터 보조기억장치로 가져올 때까지 open() 시스템 호출이 자동적으로 연기됨

14.3 성능 문제(Performance Issue)

14.3.1 속도(Speed)

▶ 대역폭(bandwidth): 초당 전송되는 바이트 수

- 지속 대역폭(sustained bandwidth): 전송 시간 동안의 전송률 ← 통상적으로 이를 언급

- 유효 대역폭(effective bandwidth): 전체 I/O 시간 동안의 전송률

  → seek나 locate 명령 실행 시간, 쥬크박스의 카트리지 교환 시간 등을 포함

▶ 접근 지연(access latency): 테이프가 디스크에 비해 훨씬 느림

→ 주크박스를 사용하는 경우에는 더욱 느림

14.3.2 신뢰성(Reliability)

▶ 고정 디스크에 대한 상대적 비교

- 제거 가능한 디스크: 카트리지가 먼지, 온도, 습기, 휨 등에 노출되어 신뢰도가 낮음

- 광 디스크: 투명한 플라스틱이나 유리 층 사이에 보호되므로 신뢰도가 높음

- 자기 테이프: 헤드가 테이프와 접하기 때문에 마찰에 의해 헤드의 마모가 심해 신뢰도가 낮음

14.3.3 비용(Cost)

▶ 메가바이트당 비용의 추세

- DRAM 메모리: [그림 14.1]

- 자기 하드디스크: [그림 14.2]

- 테이프 구동기: [그림 14.3]

▶ 결론

- 주기억장치는 디스크 저장장치보다 훨씬 비쌈

- 하드디스크의 가격이 급속히 떨어져서 테이프 구동기와 경쟁이 가능함

- 가장 저렴한 테이프 구동기와 디스크 구동기는 해당 년도에 동일한 용량을 가짐

  → 테이프가 디스크의 백업용으로 사용되기 때문

- 기록 가능한 광 디스크는 하드디스크보다 훨씬 비쌈

13. 보조저장장치 구조(Secondary Storage Structures)

13.1 디스크 구조(Disk Structure)

▶ 디스크 구동기는 논리적 블록(통상 512bytes)의 일차원 배열로 주소 지정

- 구식: 논리적 블록 번호 → 디스크 주소(실린더 번호, 트랙 번호, 섹터 번호)

→ 변환이 어려움

① 손상 섹터를 다른 곳의 여유분 섹터로 대치

② 트랙당 섹터의 수가 바깥쪽으로 갈수록 증가

- 현대식: 실린더를 섹터 수가 일정한 지역(zone)으로 구분

13.2 디스크 스케줄링(Disk Scheduling)

▶ 효율적인 디스크 사용의 평가 기준

- 접근 시간(access time)

① 탐색 시간(seek time): 디스크 암이 요구되는 섹터를 포함하는 실린더로 헤드를 움직이는 시간

② 회전 지연(rotational latency): 디스크 헤드에 요구하는 섹터가 회전하기까지 기다리는 시간

- 대역폭(bandwidth): 전송되는 총 바이트를 첫 번째 요구에 대한 서비스에서 마지막 전송까지의 총 시간으로 나눈 값

▶ 디스크에 대한 입출력을 위한 시스템 호출의 정보

① 입력/출력

② 디스크 주소(구동기 번호, 실린더, 표면, 섹터)

③ 주기억장치 주소

④ 전송 정보의 길이(바이트/단어 수)

→ 만일 디스크 구동기와 제어기가 바쁘면, 큐에서 대기해야 함: 스케줄링 필요

13.2.1 선입선처리(First-Come-First-Served; FCFS) 스케줄링

▶ 개념: 먼저 요청한 것을 먼저 처리

- 알고리즘 간단, 공평

[그림 13.1] 선입선처리 디스크 스케줄링(652 실린더 이동)

→ 최적 탐색 아님

13.2.2 최소 탐색 우선(Shortest-Seek-Time-First; SSTF) 스케줄링

▶ 개념: 현재 헤드의 위치에 가장 가까운 요청부터 처리

- 전반적인 탐색 시간 감소

- SJF(Shortest-Job-First) 알고리즘 형태: 기아 상태(starvation) 발생

[그림 13.2] 최소 탐색 우선 디스크 스케줄링(236 실린더 이동)

→ 최적 탐색 아님

13.2.3 SCAN 스케줄링

▶ 개념: 헤드가 한 쪽 끝에서 다른 쪽 끝으로 왕복 이동하면서 현재의 이동 방향에서 가장 가까운 요청부터 처리하는 방법

[그림 13.3] SCAN 디스크 스케줄링(236 실린더 이동)

→ 양 끝 부분에서는 방금 처리한 부분에 대해 바로 재처리하게 되므로 대기 시간이 균등하지 않음  

13.2.4 순환 SCAN(Circular-SCAN; C-SCAN) 스케줄링

▶ 개념: 헤드가 이동하는 양쪽 끝이 원형으로 맞닿아 있다고 가정하고 순환적으로 일정한 방향으로 처리하는 방법

- 실린더 횡단은 매우 신속하게 이동함

[그림 13.4] 순환 SCAN 디스크 스케줄링(183 실린더 이동)

→ 대기 시간이 균등함

13.2.5 LOOK/C-LOOK 스케줄링

▶ LOOK 개념: 실제로는 요청이 없는 양쪽 끝까지는 도달할 필요가 없으므로, 각 방향의 마지막 요청까지만 이동한 후 바로 반대 방향으로 이동하는 방식

▶ C-LOOK 개념: 실제로는 요청이 없는 양쪽 끝까지는 도달할 필요가 없으므로, 각 방향의 마지막 요청까지만 이동한 후 바로 정해진 방향의 첫 요청위치로 이동하는 방식

  [그림 13.5] C-LOOK 디스크 스케줄링(153 실린더 이동)

13.2.6 디스크 스케줄링 알고리즘의 선택

▶ 최소 탐색 우선(SSTF)과 LOOK이 합리적인 선택임

▶ 최적 알고리즘은 가능하지만 필요한 계산량 때문에 효율적이라고 할 수 없음

▶ 디스크 서비스의 성능에 영향을 끼치는 요인

① 파일 할당 방법

- 연속 할당된 파일: 헤드의 이동이 효율적, 디스크 이용률은 저조

- 링크 파일, 색인 파일: 헤드의 이동이 비효율적, 디스크 이용률은 높음

② 디렉토리나 색인 블록의 위치

→ 파일에 접근할 때마다 참조해야 하므로 디스크의 양끝보다는 중간에 위치시키는 것이 효율적

13.3 디스크 관리(Disk Management)

13.3.1 디스크 포맷팅(Disk Formatting)

▶ 저급 포맷팅(low-level formatting): 자기 원판을 특정의 자료구조를 갖는 섹터로 구분하는 것

- 헤더(header): 섹터 수

- 자료 구역(data area): 보통 512 바이트

- 테일러(tailer): 오류 수정 코드(Error Correction Code; ECC) - 섹터의 손상 여부를 판별

→ 대부분의 하드디스크는 제조 공장에서 저급 포맷팅 됨

▶ 단편(partition) 분할: 실린더의 부분 집합으로 구분

→ 별개의 디스크로 간주

ex) 운영체제 코드 부분, 사용자 파일 부분

▶ 논리적 포맷팅(logical formatting): 파일 시스템을 만드는 것

→ 초기 파일 시스템의 구조를 디스크 속에 저장

- 가용 및 할당 공간의 맵(map): FAT 또는 inode

- 초기의 빈 디렉토리

13.3.2 부트 블록(Boot Block)

▶ 부트스트랩(bootstrap) 프로그램: 시작 프로그램, 초기 프로그램

- 운영체제의 커널을 찾고,

- 이를 주기억장치 내에 적재하고,

- 초기 주소로 점프함

▶ 부트스트랩 프로그램의 위치

- 약간의 부트스트랩 프로그램을 ROM에 저장하고(수정 불가),

- 나머지는 디스크의 고정 위치인 시스템 디스크 또는 부트 디스크에 저장(수정 가능)

[그림 13.6] MS-DOS 디스크 구조

13.3.3 손상 블록(Bad Blocks)

▶ IDE 제어기 디스크의 경우: 손상 블록을 수동으로 처리

→ MS-DOS의 format 명령어(논리적 포맷 및 디스크 검사): 손상된 블록이 발견되면, 사용하지 못하도록 FAT 항목에 특별한 값을 부여함(데이터는 손실됨)

▶ SCSI 제어기 디스크의 경우: 손상 블록을 자동으로 처리

→ 섹터 전진(forwarding) 또는 섹터 옮기기(slipping): 제어기는 손상 블록의 리스트를 유지하고, 손상 섹터를 여분의 섹터로 대체할 수 있음(데이터는 손실됨)

  ex) p.479의 내용

13.4 교체 공간 관리(Swap-Space Management)

▶ 교체 공간: 가상 기억장치를 위한 디스크 상의 일부 공간

13.4.1 교체 공간 사용(Swap-Space Use)

▶ 교체 공간의 사용 방법: 운영체제에 따라 다양

- 프로세스 전체를 유지하는 공간

- 페이지를 위한 공간

- 다중 교체 공간: 서로 다른 디스크에 존재하면서 입출력 장치의 부하를 분산시킴 - ex) UNIX

▶ 교체 공간의 크기: 실제 기억장치의 크기, 가상 기억장치의 크기, 가상 기억장치의 사용 방법 등에 따라 결정됨

- 과소 평가의 경우: 프로세스의 중단 혹은 고장 초래

- 과대 평가의 경우: 공간의 낭비 초래 ← 보다 안전

13.4.2 교체 공간 위치(Swap-Space Location)

▶ 파일 시스템 내에 큰 파일로 존재하는 경우

(장점)

- 통상의 파일 시스템 루틴으로 교체 공간을 생성하고, 이름짓고, 공간 할당을 할 수 있음

- 다른 교체 공간의 추가도 쉬움

(단점)

- 디렉토리 구조와 디스크 할당 자료구조를 추적하기 위한 시간과 별도의 디스크 접근이 소요됨

- 외부 단편화는 교체 시간을 크게 증가시킴

- 블록 할당 정보를 캐시에 둘 수 있으나, 여전히 캐시의 자료 구조 조사를 위한 시간 소요됨

▶ 별도의 디스크 분할(partition)로 존재하는 경우: 보다 일반적

(장점)

- 파일 시스템이나 디렉토리 구조가 이 공간에 위치하지 않음

- 교체 공간 관리자가 블록을 할당하고 해제함

(단점)

- 공간보다 시간을 중시함으로써 내부 단편화 발생

  → 교체 공간은 다른 파일에 비해 훨씬 짧게 존재하면서 빈번히 접근되기 때문에 참을만함

- 교체 공간이 고정된 크기이기 때문에, 재분할(repartitioning)이나 추가에 의해서만 확장 가능

  → 재분할의 경우, 기존 파일 시스템의 이동 필요함

▶ 두 방식을 모두 제공하는 경우: ex) Solaris 2

- 정책과 구현이 분리됨

- 기계 관리자(machine's administrator)에 의해 방식이 결정됨

13.4.3 교체 공간 관리(Swap-Space Management)

▶ UNIX에서의 교체 기법과 페이징 기법의 발전 과정

- 초기에는 전체 프로세스를 연속된 디스크 공간과 기억장치 사이에 복사하는 방식을 사용

- 하드웨어 페이징이 가능해지면서 페이징과 교체를 결합한 방식을 사용

1) 4.3BSD

- 프로세스가 시작될 때 교체 공간이 할당됨

① 텍스트 페이지/텍스트 세그먼트: 프로그램

② 자료 세그먼트: 데이타

- 프로세스당 두 교체 맵이 사용됨

① [그림 13.7] 4.3BSD 텍스트 세그먼트 교체 맵

  → 512K 단위로 할당됨

② [그림 13.8] 4.3BSD 자료 세그먼트 교체 맵

  → 블록 가  크기: 해당 블록 크기를 넘게 되면, 두 배 큰 다음 블록을 할당

2) Solaris 1(SunOS 4)

- 프로세스가 시작되면 텍스트 세그먼트 페이지들을 일단 주기억장치로 불러들여 접근하고, 페이지 아웃되도록 선정되면 미리 생성되어 있는 교체 공간으로 내보내는 방식 채택

  → 효율성 향상

3) Solaris 2

- 교체 공간을 미리 생성되는 것이 아니라 실제 기억장치로부터 방출될 때 교체 공간을 할당하는 방식 채택

→ 주기억장치의 용량이 큰 현대 컴퓨터 시스템에 적합

13.5 디스크 신뢰성(Disk Reliability)

▶ 디스크: 시스템에서 가장 신뢰도가 낮은 요소

→ 높은 고장률

▶ 디스크 스트리핑(striping)/인터리빙(interleaving): 하나의 저장 단위로 디스크들의 그룹을 사용하는 방법

→ 각 블록을 여러 부분 블록으로 나누고 디스크마다 병렬로 전송함으로써 전송 시간을 향상시킴

▶ 중복 배열 디스크(Redundant Array of Independent Disks; RAID): 디스크 스트리핑으로 중복된 자료를 복사함으로써 신뢰도를 향상시키는 조직

① 미러링(mirroring)/새도우잉(shadowing): 이중 디스크를 사용하는 방법

- 쓰기: 이중으로 복사해야 하기 때문에 두 배로 느림

- 읽기: 각 디스크에서 동시에 보내기 때문에 두 배로 빠름

② 블록 인터리브된 패리티(block interleaved parity): 9개의 디스크 중 마지막 하나를 패리티 비트의 블록으로 사용하는 방법

- 한 디스크의 고장시 복구 가능

- 자료 블록의 매 변경마다 패리티 블록을 갱신해야 함

13.6 안정된 저장장치 구현(Stable-Storage Implementation)

▶ 독립된 고장 모드의 다중 저장 장치의 사용: 정보의 무손실 가능

→ 갱신 중의 고장에도 복사본에 의한 복구 가능

▶ 디스크 기록의 결과

- 성공적인 완료: 자료가 디스크 상에 정확하게 기록됨

- 부분적 고장: 전송도중 에러가 발생하여 해당 섹터의 데이터가 손상됨

- 완전 고장: 디스크 기록이 시작되기 전에 고장이 일어나서, 기존 데이터가 그대로 남아있음

▶ 고장 발생시 회복 알고리즘을 가동하기 위해서는, 각 논리적 블록에 두 개의 물리적 블록을 유지하면 됨

12. 입출력 시스템(I/O Systems)

12.1 개요(Overview)

▶ 입출력 부시스템(I/O subsystem): 다양한 입출력 장치들의 다양한 제어를 위한 시스템

ex) 하드디스크, 마우스, CD-ROM 쥬크 박스 등

▶ 입출력 장치 기술의 경향

- 입출력 장치의 다양화

- 소프트웨어와 하드웨어간 인터페이스의 표준화

→ 장치 구동기(device driver): 일관된 장치 접근 인터페이스를 제공

12.2 입출력 하드웨어(I/O Hardware)

▶ 장치의 종류

- 저장장치: 디스크, 테이프

- 전송장치: 네트워크 카드, 모뎀

- 사용자 인터페이스 장치: 스크린, 키보드, 마우스

▶ 장치와 컴퓨터 시스템간의 통신

- 포트(port): 연결점

- 버스(bus): 여러 장치들이 공용하는 와이어 집합

  ex) 데이지 체인(daisy chain): 장치 A - 장치 B - 장치 C

▶ 버스: [그림 12.1] 전형적인 PC 버스 구조

- PCI 버스: 프로세서-메모리 부시스템과 고속 장치의 연결

- 확장 버스: 저속 장치의 연결 ex) 키보드, 병렬포트, 직렬포트

- SCSI 버스: 고속 디스크들의 연결

▶ 제어기(controller): 포트, 버스, 장치의 작동

- 단일 칩(chip)으로 구현: ex) 직렬 포트 제어기

- 회로 기판으로 구현: ex) SCSI 제어기

- 장치에 내장된 제어기: ex) 디스크 구동기에 부착된 기판

▶ 프로세서와 제어기의 통신

- 제어기마다 레지스터 집합을 사용

- 입출력 명령어에 의한 수행

① 버스 선의 트리거링에 의한 통신 장치 선택

② 메모리 대응 입출력(memory-mapped I/O)에 의한 통신

  → 장치 제어 레지스터들이 프로세서의 주소 공간으로 대응

ex) 그래픽 제어기: 스크린의 내용을 저장하기 위한 그래픽 메모리 사용

  (장점) 신속한 입출력

  (단점) 프로그래밍 오류에 의한 훼손 가능 - 보호된 메모리 방식으로 해결

- 입출력 포트: [그림 12.2] 호환성 PC에서 장치 입출력 포트의 위치

→ 4개의 레지스터로 구성

① status 레지스터: 장치의 상태

  ex) 판독 가능 여부, 에러 유발 여부 등

② control 레지스터: 장치 모드의 변경

  ex) 전이중(full-duplex) 혹은 반이중(half-duplex) 통신의 선택, 패리티 검사, 워드 길이 선택, 

      전송 속도 선택 등

③ data-in 레지스터: 입력용 자료 레지스터

④ data-out 레지스터: 출력용 자료 레지스터

12.2.1 폴링(Polling)

▶ 핸드셰이킹(handshaking): 호스트와 제어기 사이의 교류를 위한 프로토콜

- 제어기는 status 레지스터의 busy 비트를 통해 상태를 지정함

① 명령을 수행중인 상태: busy=1

② 명령 수행을 완료하고 다음 명령을 기다리는 상태: busy=0

- 호스트는 command 레지스터의 command-ready 비트를 사용

① 제어기에게 명령을 한 상태: command-ready=1

② 제어기가 명령 수행을 완료한 상태: command-ready=0

(예) 출력: 

① 호스트는 클리어 될 때까지 busy 비트를 반복적으로 판독

② 호스트는 command 레지스터의 write 비트를 설정하고 data-out 레지스터에 한 바이트를 씀 

③ 호스트는 command-ready 비트를 설정

④ 제어기가 command-ready 비트가 설정되었음을 알아차리면 busy 비트를 설정

⑤ 제어기는 command 레지스터를 판독하여 명령이 write임을 파악하고, data-out 레지스터를 판독하여 해당 바이트를 가져와 장치에 출력함

⑥ 제어기는 command-ready 비트를 클리어하고, 입출력 성공을 알리기 위해서는 status 레지스터의 error 비트를 클리어하며, busy 비트를 클리어함

▶ 폴링(polling)/사용중 대기(busy-waiting): 위 과정 ①에서 발생

→ 중앙처리장치의 비효율성 초래: 제어기가 중앙처리장치에 통보하는 인터럽트 방식이 효과적

12.2.2 인터럽트(Interrupts)

▶ 인터럽트 방식의 입출력: [그림 12.3] 인터럽트 구동 입출력 사이클

- 중앙처리장치는 매 명령어 수행 직후에 인터럽트 요청 라인(interrupt request line)을 검사하여 제어기에 의해 보내져온 인터럽트가 있는지 검사

- 중앙처리장치가 인터럽트 신호를 감지하면 현재 상태를 저장하고 인터럽트 핸들러 루틴(interrupt handler routine)으로 이동

- 인터럽트 핸들러는 인터럽트를 분석하고 해당 처리를 수행한 후, return from interrupt 명령을 수행하여 인터럽트 전의 상태로 복귀

▶ 세련된 인터럽트 핸들링 방법

- 중요한 처리 중에는 인터럽트 처리를 미룰 수 있는 방법 필요

- 모든 장치를 폴링하지 않고 인터럽트를 일으킨 장치를 인터럽트 핸들러에게 통지하는 방법 필요

- 인터럽트의 우선 순위에 따라 긴급성을 조절하는 다계층 인터럽트 필요

▶ 두 인터럽트 라인의 경우

- 마스크 불가 인터럽트 라인(nonmaskable interrupt line): 긴급한 에러 발생시

- 마스크 가능 인터럽트 라인(maskable interrupt line): 일반적인 인터럽트 발생시

  → 단, 인터럽트 걸려서는 안 되는 명령어 수행 시, 중앙처리장치에 의해 해제될 수 있음

▶ 특정 인터럽트 핸들러의 선택

- 인터럽트 번호: 인터럽트 벡터(interrupt vector)의 변위로 사용

→ 인터럽트 핸들러 주소를 파악

- 인터럽트 체이닝(chaining): 인터럽트 벡터의 용량보다 장치 수가 많은 경우에 사용하는 기법

→ 인터럽트 벡터의 각 원소들이 인터럽트 핸들러 리스트의 헤드를 가리키게 하고, 해당 리스트를 탐색하게 하는 방법

▶ (예) [그림 12.4] 인텔 펜티엄 프로세서의 인터럽트 벡터 테이블

- 0-31: 마스크 불가 → 다양한 에러용

- 32-255: 마스크 가능 → 장치 생성 인터럽트용

▶ 인터럽트 우선 순위 단계(interrupt priority levels)

→ 높은 우선 순위의 인터럽트가 낮은 우선 순위의 인터럽트 수행을 선점

▶ 다양한 인터럽트 메커니즘

- 일반적인 용도

① 부팅 시: 하드웨어 버스를 조사하여 존재하는 장치를 파악하고 인터럽트 벡터 내에 적절한 인터럽트 핸들러를 설치함

② 입출력 시: 출력 완료, 입력 자료의 유효 또는 오류

③ 예외 발생 시: ex) 0으로 나누기, 부적절한 주소 접근, 사용자 모드에서의 부적절한 명령 시도

- 하드웨어 메커니즘의 적절한 사용: ex) 페이지 부재 인터럽트

- 시스템 호출의 수행: 응용 프로그램이 커널 서비스를 호출하기 위한 함수 호출

- 커널 안에서의 제어 흐름 관리: ex) 디스크 판독

- 스레드 커널 구조: 백그라운드 처리에 대한 인터럽트 핸들링

12.2.3 직접 메모리 접근(Direct Memory Access)

▶ 프로그램된 입출력(Programmed I/O; PIO): 상태 비트를 감시하고 한번에 1 워드(바이트)씩 제어기 레지스터에 옮기는 것

→ 디스크와 같이 많은 전송을 하는 경우, 범용의 중앙처리장치가 담당하는 것은 비효율적이고, 직접 메모리 접근 제어기라 불리는 별도의 처리기가 담당하는 것이 바람직

▶ 직접 메모리 접근(Direct Memory Access; DMA)

- DMA 전송을 초기화하기 위해, 호스트는 DMA 명령 블록을 기억장치에 씀

                 (전송 소스의 포인터, 전송 목적지의 포인터, 전송 바이트 수의 카운터를 포함)

- CPU는 이 명령 블록의 주소를 DMA 제어기에 기록하고 다른 작업을 계속함

- DMA 제어기는 직접 메모리 버스를 운영하여 한 워드씩 전송함

▶ DMA 제어기와 장치 제어기간의 핸드셰이킹

→ DMA-request와 DMA-acknowledge의 두 와이어를 통해 수행

- 장치 제어기는 한 워드의 자료가 메모리로 전송 가능할 때 DMA-request에 신호를 보냄

- DMA 제어기는 이 신호를 받으면, 메모리 버스를 점유하고 메모리 주소 와이어에 원하는 주소를 위치시키며 DMA-acknowledge에 신호를 보냄

- 이 신호를 받은 장치 제어기는 한 워드 자료를 메모리로 전송하고 DMA-request 신호를 해제함

- 전송이 완료되면, DMA 제어기는 CPU에 인터럽트를 검

[그림 12.5] 직접 메모리 접근 전송의 단계

▶ 직접 가상 메모리 접근(Direct Virtual Memory Access; DVMA)

→ 중앙처리장치의 간섭과 주기억장치 사용 없이 두개의 메모리 대응 장치(memory-mapped device) 사이에서의 전송이 가능

12.3 응용 입출력 인터페이스(Application I/O Interface)

▶ 개념: 다양한 입출력 장치를 규격화되고 일관된 방식으로 취급하기 위한 기법과 인터페이스를 구성하는 방법

▶ 접근 방법: 추상화, 캡슐화, 계층화

- 입출력 장치들을 일반적인 종류로 추상화

- 일반적인 종류 각각은 인터페이스라는 규격화된 함수 집합으로 접근

→ 차이점은 장치 구동기로 캡슐화됨

- 소프트웨어 계층화: [그림 12.6] 커널의 입출력 구조

→ 입출력 부시스템을 하드웨어와 독립적으로 만들 수 있음

  (장점) 

  ① 운영체제 개발자: 개발 작업이 단순화 됨

  ② 하드웨어 제조업자: 범용 운영체제 맞는 장치 제어기를 만듦으로써 즉시 사용가능 함

▶ 장치의 다양성: [그림 12.7] 입출력 장치의 특성

→ p.444-445 참조

▶ escape 또는 back-door 시스템 호출: 임의의 명령어를 응용에서 장치 구동기로 투명하게 전달하는 방법

ex) UNIX의 ioctl 시스템 호출: 3 인수

- 파일 디스크립터(descriptor)

- 명령어 선택을 위한 정수

- 임의의 자료구조를 가리키는 포인터

12.3.1 블록과 문자 장치(Block and Character Device)

▶ 블록 장치 인터페이스를 통한 장치 접근: ex) 디스크 구동기

→ read, write, seek 명령

▶ 메모리 대응(memory mapped) 파일 접근: 블록 장치 구동기의 최상위 계층에 해당

→ 주기억장치 상의 바이트 배열을 통해 저장장소로의 접근을 제공

▶ 문자 스트림 인터페이스를 통한 장치 접근: ex) 키보드, 마우스, 모뎀

- 한 문자의 입출력 가능

- 버퍼링과 편집 서비스에 의한 동시의 라인 접근(line-at-a-time access) 제공 가능

12.3.2 네트워크 장치(Network Devices)

▶ 네트워크 입출력 인터페이스: ‘네트워크 소켓(socket) 인터페이스’

ex) UNIX 또는 Windows NT

→ 소켓 인터페이스에서의 시스템 호출은,

- 응용이 소켓을 생성하게 하고,

- 지역 소켓을 원격 주소에 연결하고,

- 어떤 원격 응용이 지역 소켓으로 플러그되는지 알아보고,

- 연결을 통해 패킷을 주고받도록 함

* select 호출: 어느 소켓이 수신될 패킷을 기다리고 있는지, 어느 소켓이 전송될 패킷을 저장할 공간을 가지고 있는지를 리턴 받음

12.3.3 클록과 타이머(Clocks and Timers)

▶ 세 가지 함수 제공

- 현재 시간 제공

- 경과 시간 제공

- T시간에 X 트리거 동작을 발생하는 타이머 지정

→ 시스템 호출이 표준화되어 있지 않음

12.3.4 블로킹과 논블로킹 입출력(Blocking and Nonblocking I/O)

▶ 블로킹 시스템 호출: 응용의 실행이 지연됨

- 시스템 호출 시, 응용은 실행(준비) 큐에서 대기 큐로 이동

- 시스템 호출의 수행 후 응용은 다시 실행 큐로 이동

▶ 논블로킹 시스템 호출: 응용의 실행이 계속됨

ex) 처리중이거나 스크린에 자료를 표시하는 중에 키보드나 마우스의 입력을 받는 인터페이스

    디스크를 판독하면서 동시에 압축을 풀고 디스플레이하는 비디오 응용

→ 구현: 1) 다중 스레드 응용, 2) 비동기적 시스템 호출

12.4 커널 입출력 부시스템(Kernel I/O Subsystem)

12.4.1 스케줄링(Scheduling)

▶ 입출력 스케줄링: 장치 큐의 스케줄링에 의한 요청 재배치 → 13.2절 참조

(목적) 

- 전반적인 시스템 성능 향상

- 프로세스간의 장비 접근을 공평하게 공유

- 입출력 완료까지의 평균 대기 시간 감소

ex) 디스크 헤드가 시작부분에 위치하는 경우, 

  (장치 큐) 응용 1-끝 부분 블록 요청, 응용 2-시작 부분 블록 요청, 응용 3-중간 부분 블록 요청

    → 재배치: 응용 2, 응용 3, 응용 1 

12.4.2 버퍼링(Buffering)

▶ 버퍼: 두 장치 사이 혹은 응용과 장치 사이에 자료 전송을 위한 임시 저장 공간

▶ 버퍼링의 필요성

- 생산자와 소비자 사이의 자료 흐름 속도의 불일치에 대처하기 위함

ex) 파일 전송: 하드디스크 ↔ 모뎀

→ 이중 버퍼링(double buffering)에 의한 비간섭화(decoupling): 

   모뎀이 한 버퍼를 채우는 동안 이미 채워진 버퍼를 디스크에 기록하는 방법

[그림 12.8] Sun Enterprise 6000 장치 전송률

- 서로 다른 자료 전송 크기를 가지고 있는 장치들을 적응시키기 위함

ex) 메시지의 분할(fragmentation)과 재결합(reassembly)에 의한 네트워크 전송

→ 송신측에서 메시지를 패킷(packet) 단위로 분할하여 전송하고 수신측에서 재결합 함

- 응용의 입출력을 위한 “복사 의미론(copy semantics)”을 지원하기 위함

ex) 응용이 버퍼에 대한 포인터와 출력할 바이트 수를 가지고 write 시스템 호출을 한 시점과 동일한 버전의 자료를 디스크에서 보장하는 것

→ write 시스템 호출 시, 응용 버퍼에서 커널 버퍼로 자료를 복사하고 실제 출력은 커널 버퍼로부터 이루어짐

12.4.3 캐싱(Caching)

▶ 캐시(cache): 자료의 복사본을 가지고 있는 빠른 메모리 영역 → 접근 속도가 효율적

▶ 버퍼와 캐시의 차이점

- 버퍼: 현재 복사본을 저장

- 캐시: 다른 곳에 저장된 자료의 복사본을 보다 빠른 기억장소에 저장

→ 동일한 기억장치 영역이 버퍼와 캐시 모두를 위해 사용 가능

12.4.4 스풀링(Spooling) 및 장치 예약(Device Reservation)

▶ 스풀(spool): 중첩되는 자료 스트림을 수용할 수 없는 장치를 위한 출력 버퍼 ex) 프린터

→ 스풀링 시스템이 프린터로 가는 모든 출력을 가로채어 디스크에 파일로 보관하고 하나씩 출력

▶ 배타적인 장치 접근으로 스풀링을 대신할 수 있음

→ 유휴 장치의 할당(allocate) 및 사용 후 해제(deallocate)

12.4.5 에러 처리(Error Handling)

▶ 보호 메모리(protected memory): 하드웨어 및 응용의 에러에 의한 접근에 대처 가능

→ 미미한 에러에 의해 전반적인 시스템 고장이 유발되는 것을 방지

▶ 일시적인 고장에 대한 대처 방안: 

ex) 디스크 read 실패시 read를 재시도, 망의 send 에러시 resend 시도

12.4.6 커널 자료 구조(Kernel Data Structure)

▶ 커널은 입출력 구성 요소의 사용에 대한 상태 정보를 유지해야 함: ex) 개방 파일 테이블

- UNIX: 사용자 파일, 장치 자체, 프로세스의 주소 공간 등의 다양한 객체에 대한 파일 시스템 접근을 제공 → 단일 구조체 내에 은닉함: [그림 12.9] UNIX 입출력 커널 구조

- Windows NT: 입출력을 위한 메시지 전달 방법을 사용

  → 메시지의 출력이나 입력을 위한 버퍼를 가짐

▶ 입출력 부시스템의 서비스: p.455-456의 내용

12.5 입출력 요청의 하드웨어 작업 변환(Transforming I/O Requests to Hardware Operations)

▶ 블록킹 판독 요청의 일반적인 모습: [그림 12.10] 입출력 요청의 전 사이클 → p.458-459의 1-10

12.6 성능(Performance)

▶ 원거리에 있는 컴퓨터간의 로그인의 예: [그림 12.11] 컴퓨터간 통신과 비용

▶ 입출력의 효율성 증대를 위한 원칙: p.461-462의 내용

▶ 입출력 기능 구현의 위치: p.462-463의 내용 → 응용, 커널, 하드웨어

▶ 파일 시스템: 자료와 프로그램의 온라인 저장과 접근에 대한 관리 기법을 제공

→ 보조기억장치에 상주: “디스크”

11.1 파일 시스템 구조(File-System Structure)

▶ 디스크: 보조기억장치의 유지 → 기억장치와 디스크간의 입출력은 블록 단위로 실행

- 재기록 가능

- 직접 접근 가능

→ 디스크 구조: 13장

11.1.1 파일 시스템 조직(File-System Organization)

▶ 파일 시스템 설계의 고려 사항

1) 사용자를 위한 파일 시스템의 표현

① 파일의 정의와 속성

② 파일 구성을 위한 디렉토리 구조

③ 파일에 대한 조작

2) 물리적 보조기억장치와 논리적 파일 시스템을 사상하는 알고리즘과 자료 구조

[그림 11.1] 계층적 파일 시스템

① 논리적 파일 시스템(logical file system): 파일명으로 디렉토리를 참조하여 파일 구성 모듈에게 파일 속성 제공

→ 보호 문제(10장), 보안 문제(19장) 담당

② 파일 구성 모듈(file-organization module): 파일과 디스크 블록에 대한 정보 유지

→ 특정 블록의 주소 산출 담당: ex) 구동기 1, 실린더 73, 표면 2, 섹터 10

③ 기본적 파일 시스템(basic file system): 디스크에 있는 물리적 블록을 읽거나 쓰는 기본 명령어를 발생

④ 입출력 제어(I/O control): 장치 구동기와 정보 전송을 위한 인터럽트 처리기로 구성

→ 12장 참조

▶ 개방 파일 테이블: 디렉토리 구조 참조의 비효율성을 해결

[그림 11.2] 전형적인 개방 파일 테이블

① 파일의 열기(open)시 디렉토리의 해당 항목을 개방 파일 테이블의 항목으로 복사하고 그 항목의 색인(index)을 사용자 프로그램에 넘김

② 이후 파일의 참조 및 속성 수정은 인덱스에 의한 개방 파일 테이블을 통해 효율적으로 이루어짐

③ 파일의 폐쇄(close)시 변경된 내용이 디렉토리에 복사됨

* 색인(index)의 명칭: 

- UNIX의 파일 기술자(file descriptor)

- Windows NT의 파일 처리기(file handler)

- 파일 제어 블록(file control block)

11.1.2 파일 시스템 마운팅(File-System Mounting)

▶ 시스템 상에서 파일처리를 가능하게 하기 위해서 파일 시스템은 마운트되어야 함 

① 운영체제는 해당 파일 시스템에 대한 장치명과 부착시킬 파일구조내의 위치인 마운트 포인터(mount pointer)를 넘겨받음

ex) /home에 파일 시스템 이름 jane을 마운트 → /home/jane으로 참조

② 운영체제는 장치가 타당한 파일 시스템을 포함하는지를 점검

→ 장치 구동기에게 장치 디렉토리를 판독하게 하여 디렉토리가 기대한 형식을 갖는지를 입증함

③ 운영체제는 파일 시스템이 특정한 마운트 포인터에 마운트되어 있음을 디렉토리 구조에 나타냄

▶ 예: Macintosh 운영체제 → 17.6.2절 참조

- 시스템이 처음으로 디스크를 접하면(하드디스크: 부팅시, 플로피 디스크: 구동기에 넣은 순간), 장치에서 파일 시스템을 찾음

- 찾은 파일 시스템을 루트에 마운트하고, 파일 시스템 이름을 홀더 아이콘 형태로 화면에 나타냄

- 사용자는 아이콘을 눌러 사용

11.2 할당 방법(Allocation Methods)

▶ 목적: 디스크 공간의 효율적 사용 및 신속한 파일 접근

▶ 방법

- 연속 할당(contiguous allocation)

- 연결 할당(linked allocation)

- 색인 할당(indexed allocation)

11.2.1 연속 할당(Contiguous Allocation)

▶ 정의: 각 파일에 디스크의 연속적인 주소들의 집합을 할당하는 방법

▶ 디렉토리의 파일 항목: ‘시작 블록의 주소’(b) + ‘파일 길이(블록수)’(n)

→ 파일: 블록 로 구성

[그림 11.3] 디스크 공간에서의 연속 할당

▶ 장점: 접근 용이

- 순차 접근 가능: 블록 의 다음 블록 → 블록

- 직접 접근 가능: 블록 에서 시작하는 번째 블록 → 블록

▶ 단점

1) 파일에 할당할 가용 공간의 확보가 복잡

① 최초 적격(first-fit): 요구량보다 큰 첫 번째 가용 영역을 할당

② 최상 적격(best-fit): 요구량보다 큰 영역 중 가장 작은 것을 할당 

③ 최악 적격(worst-fit): 가장 큰 가용 영역을 할당

→ 모의 실험: 기억 공간 이용률 및 처리 시간 측면에서 ①과 ②가 보다 우수

2) 외부 단편화: 전체 가용 공간이 요구량보다 크지만 연속적인 공간이 아닌 경우에 발생

→ 압축(compaction): ①과 ②의 처리 시간이 오래 걸림

해당 디스크

다른 디스크

① 전체 복사

② 재배치

③ 새 파일 할당

3) 출력되는 파일에 요구되는 기억 장소의 크기 결정 문제

- 오류 메시지와 함께 생성 작업이 중단되면 사용자가 보다 큰 공간을 할당하고 재수행하는 방법

→ 시간 많이 소요, 넉넉하게 공간 할당을 할 경우 공간 낭비

- 생성 작업이 중단되면 파일 시스템이 보다 큰 사용 공간에 복사하고 계속 진행하는 방법

→ 여전히 시간 많이 소요

* 특히 장시간에 걸쳐서 서서히 증가하는 파일의 경우, 총 공간을 미리 할당하는 것은 비효율적

11.2.2 연결 할당(Linked Allocation)

▶ 정의: 파일에 디스크 블록의 연결 리스트(linked list)를 할당하는 방법

→ 각 블록은 다음 블록을 가리키는 포인터를 가져야 함

▶ 디렉토리의 파일 항목: ‘파일의 처음 섹터 포인터’ + ‘파일의 마지막 섹터 포인터’

[그림 11.4] 디스크 공간에서의 연결 할당

▶ 사용법

- 파일 생성: 디렉토리에 새 항목 추가 → 처음 블록 포인터를 로 초기화

- 쓰기: 첫 번째 사용 가능 블록에 쓰고 이전의 마지막 블록에 연결

- 읽기: 처음 블록부터 을 만날 때까지 포인터를 따라가면서 읽음

▶ 장점

- 외부 단편화 현상이 발생하지 않음 → 압축 필요 없음

- 생성되는 파일의 크기를 미리 선언할 필요 없음 → 사용 가능 공간이 존재하는 한 증가 가능

▶ 단점

- 직접 접근이 불가: 파일의 번째 블록 참조를 위해서는 처음부터 포인터를 따라가야 함

- 포인터가 차지하는 공간 소요

ex) 포인터: 4bytes, 블록: 512bytes → 0.78% 소모

- 신뢰성 결여: 운영체제의 결함, 하드웨어의 고장 등으로 포인터 손실시 파일의 상당한 훼손 초래

→ ‘이중 연결 리스트’로 보완 가능: 메모리 소요 증가

▶ 변형: 파일 할당 테이블(FAT) 사용 → MS-DOS, OS/2에서 사용

[그림 11.5] 파일 할당 테이블

- 위치: 각 단편(partition)의 처음 부분(0번 블록)

- 구성: 블록 번호를 인덱스로 하고 각 항목에는 다음 블록 번호를 기록하여 연결 리스트로 사용

(단, (-1): 파일의 끝, 0: 가용블록)

- 단점: 디스크 헤드의 이동이 빈번해짐

→ 요구되는 블록에 접근하기 위해서는 FAT(0번 블록)를 먼저 접근해야하기 때문

- 장점: 직접 접근 시간이 줌

→ FAT(0번 블록)내에서만 탐색하면 됨

11.2.3 색인 할당(Indexed Allocation)

▶ 정의: 각 파일의 색인 블록에 그 파일의 블록들을 가리키는 포인터들을 모아두는 방법

                      → 디스크 블록 주소의 배열

▶ 디렉토리의 파일 항목: ‘각 파일의 색인 블록에 대한 포인터’

[그림 11.6] 디스크 공간에서의 색인 할당

▶ 장점

- 직접 접근 가능: 번째 블록은 색인 블록의 항목에 있는 번째 포인터로 직접 접근

▶ 단점

- 블록수가 적은 파일의 경우: 색인 블록의 기억 장소가 낭비됨

- 블록수가 많은 파일의 경우: 하나의 색인 블록으로 충분한 포인터를 가질 수 없음

(해결 방법)

① 연결 기법(linked scheme): 색인 블록의 마지막까지 이 나오지 않으면 마지막의 주소가 다음 색인 블록의 포인터임

② 다중 수준 색인(multilevel index): 색인 블록의 색인 블록을 운영 - 2단, 3단, ...

→ 주로 매우 큰 파일들이 많은 경우 적합

ex) 1단: 256 포인터

    2단: 256×256=65,536 포인터

③ 결합 기법(combined scheme): BSD UNIX의 경우

[그림 11.7] UNIX의 inode

* 디렉토리의 항목이 inode를 가리킴

11.2.4 성능(Performance)

▶ 기준

- 기억 장소의 효율성

- 자료 블록의 접근 속도

▶ 연속 할당

- 직접 접근/순차 접근: 단 한번의 블록 접근 소요

- 외부 세그먼트 발생함

▶ 연결 할당

- 순차 접근: i번째 섹터에 접근하기 위해서는 디스크를 i번 읽어야 함 → 직접 접근 불가 

- 외부 세그먼트 발생 안함

▶ 연속 할당과 연결 할당의 병용

- 운영체제가 두 가지 방식을 지원해야 하고, 파일 선언시 접근 형태를 선언해야 함  

- 직접 접근 파일과 순차 접근 파일은 복사에 의해 상호 변환 가능

▶ 색인 할당

- 성능은 색인의 구조, 파일의 크기, 블록의 위치에 영향을 받음

▶ 연속 할당과 색인 할당의 병용

- 파일의 크기에 따라, 파일의 유형이 자동 결정 및 자동 변환됨

1) 小(3-4블록 이내): 연속 할당

2) 大: 색인 할당

- 대부분의 파일이 작기 때문에 평균 성능은 우수

11.3 가용 공간 관리(Free Space Management)

▶ 가용 공간 리스트(free space list): 비어 있는 모든 디스크의 블록들을 등록

- 제거: 파일 생성시

- 추가: 파일 삭제시

→ 구현: 11.3.1 - 11.3.4

11.3.1 비트 벡터(Bit Vector)

▶ 비트 ↔ 블록

- 0: 사용 가능

- 1: 사용중

ex) 사용 가능 섹터: 2, 3, 4, ... → 비트 벡터: 00111...

11.3.2 링크드 리스트(Linked List): 연결 할당 개념

▶ 가용 공간 리스트 헤드부터 시작하여 링크에 의해 다음 사용 가능 블록을 연결

[그림 11.8] 디스크 상의 연결된 가용 공간

→ 가용 공간 리스트 검사 시, 모든 가용 블록에 접근해야 함: 비효율적

11.3.3 그룹핑(Grouping): 색인 할당 개념

▶ 처음 가용 블록에 n개의 가용 블록의 주소를 기입하되, 마지막에는 다른 n개의 가용 블록의 주소를 기입하고 있는 블록의 디스크 주소가 위치함

  → 가용 공간 리스트 검사 시, 평균 1/n 블록만을 접근하면 됨: 신속한 검색 가능

11.3.4 계수(Counting): 연속 할당 개념

▶ 가용 공간 리스트의 항목: 연속된 가용 공간마다 첫 번째 블록의 주소와 블록 수를 기록

- 가용 공간 리스트의 축소

- 연속 할당에 유용

11.4 디렉토리 구현(Directory Implementation)

11.4.1 선형 리스트(Linear List)

▶ 선형 리스트(linear list): 선형 탐색

- 실행 시간이 오래 걸림

- 알고리즘 간단

▶ 정렬된 리스트(sorted list): 이진 탐색

- 평균 탐색 시간 감소

- 알고리즘 복잡

11.4.2 해시 테이블(Hash Table)

▶ N 항목의 경우: 파일명(key)     ↔     0 . . N-1

                       ‘해시 함수(hash function)’

(장점) 탐색 시간을 상당히 개선

(단점) 일반적으로 key > N이므로 충돌(collision) 발생 가능

- 다음 빈 공간에 저장: 선형 검색법(linear probing)으로 탐색

- 빈 공간이 없으면 실패: 과잉 상태(overflow) 

  → 고정된 N에서 초래됨: 해시 테이블의 확대 재구성 필요

11.5 효율성(Efficiency)과 성능(Performance)

▶ 시스템의 병목 현상 주원인: 보조기억장치

→ 디스크 공간의 효율성과 파일 시스템의 처리 성능을 향상시키기 위한 기법 논의

11.5.1 효율성(Efficiency)

▶ 디스크 공간의 효율적 사용: 디스크 할당 및 디렉토리 알고리즘과 밀접하게 관련됨

- 분할(partition) 상에 inode를 분배하여 할당: ex) UNIX

→ inode에 인접하여 해당 파일의 데이터를 위치시킴으로써 디스크의 탐색 시간을 줄임

- 파일 크기에 따른 클러스터링 기법: ex) BSD UNIX → 단편화의 최소화

1) 소용량 클러스터: 작은 파일, 파일의 마지막 클러스터

2) 대용량 클러스터: 채워지는 경우 사용

- 디렉토리 구조의 정보 형태

1) 최종 기록 날짜: 파일의 예비 저장(backup) 필요 여부를 결정

2) 최종 판독 날짜: 파일 접근이 빈번한 경우는 비효율적

3) 포인터의 크기: 클수록 파일의 최대 크기가 커지지만 가용 공간 관리를 위한 공간 소모도 커짐

- 파일 시스템의 크기: 고정 크기 ↔ 동적 할당

11.5.2 시스템 성능(Performance)

▶ 디스크 캐시(disk cache): [그림 11.9] 다양한 디스크 캐시 위치

1) 트랙 버퍼(track buffer): 디스크 제어기는 한번에 전체 트랙의 내용을 저장할 수 있는 캐시(on-board cash) 형태의 충분한 지역 기억공간을 가지고 있음

2) 블록 버퍼(block buffer): 사용되지 않는 기억장치 공간을 페이징 시스템과 디스크 블록 시스템에 의해 공유되는 버퍼 풀로 사용

3) 가상/램 디스크(virtual/RAM disk): 기억장치의 특정 부분을 가상/램 디스크로 사용

→ 주로 중간 컴파일된 파일과 같은 임시 파일의 저장에 사용

▶ 디스크 캐싱의 최적화: 파일의 접근 형태에 따라 서로 다른 교체 알고리즘을 사용

ex) 순차적 접근의 경우, LRU 교체는 부적합 → free-behind, read-ahead 기법이 적합

11.6 회복 기법(Recovery)

▶ 시스템 결함으로 인한 자료의 비일관성 또는 자료 손실이 초래되지 않도록 해야 함

11.6.1 일관성 검사(Consistency Checking)

▶ 일관성 검사자(consistency checker)

- 디렉토리 구조에 있는 정보와 디스크에 있는 데이터 블록을 비교하여 발견된 불일치 내용을 수정

- 접근 속도를 높이기 위해 주기억장치에 위치하는 디렉토리 정보의 일부(ex: 개방파일테이블)과 실제 디렉토리와의 불일치를 수정

11.6.2 예비 저장(Backup)과 재저장(Restore)

▶ 재저장: 시스템 프로그램의 저장을 위한 디스크로부터 플로피 디스크, 자기 테이프, 광 디스크와 같은 다른 저장 장치로의 복사

▶ 예비 저장: 개개의 파일 혹은 전체 디스크의 손실로부터 회복하기 위한 재저장 → (예) p.422 내용

10. 파일 시스템 인터페이스(File System Interface)

▶ 파일 시스템: 파일 집합, 디렉토리 구조, 단편(partition)

10.1 파일의 개념(File Concept)

▶ 정보의 저장

- 저장 장치: 다양한 물리적 저장 단위 ex) 자기 디스크, 자기 테이프, 광학 디스크 등

   ↕ 매핑(운영체제)

- 파일: 일관되고 논리적인 저장 단위

① 프로그램: 원시 프로그램, 목적 프로그램

② 데이터: 문자, 숫자, 문숫자 등으로 구성 → 비트, 바이트, 행(line), 레코드들의 연속체

10.1.1 파일 속성(File Attributes)

▶ 모든 파일 정보는 보조기억장치에 상주하는 디렉토리 구조에 유지됨

- 이름: 문자열로 구성 → 그 이름으로 조회

- 형태: 파일의 종류

- 위치: 파일이 존재하는 장치와 위치에 대한 포인터

- 크기: 현재 크기(바이트, 워드, 블록 등), 최대 허용 가능한 크기

- 보호: 접근 제어 정보 → 판독, 기록, 실행의 주체

- 시간, 날짜, 사용자 식별: 생성, 최근 수정, 최근 사용(last use)에 대한 정보 유지

→ 보호, 보안, 사용자 감시에 활용

10.1.2 파일 조작(File Operations)

▶ 운영체제는 파일의 생성, 기록, 판독, 재설정, 삭제, 절단 등을 위한 시스템 호출(system call) 제공

- 파일 생성: ① 공간 할당(11장), ② 디렉토리 항목 생성

- 파일 기록: ① 파일명에 의한 위치 탐색, ② 기록 포인터(write pointer) 유지 및 갱신

- 파일 판독: ① 파일명과 복사 위치에 의한 호출, ② 판독 포인터(read pointer) 유지 및 갱신

  → 기록 포인터+판독 포인터: 현재 파일 위치 포인터(current file position pointer)

- 파일 안에서의 재설정(reposition): 파일 탐색(seek) 조작 명령에 의한 새 위치 찾기

- 파일 삭제: ① 디렉토리에서 해당 항목 찾기, ② 기억공간 해제, ③ 디렉토리 항목 삭제

- 파일 절단: 파일 내용만 지우기 → 파일 길이 속성만을 0으로 설정

▶ 기본 조작 명령은 다른 파일 조작 명령을 실행하기 위해 결합될 수 있음

ex) 파일 복사: 새 파일 생성, 옛 파일 판독, 새 파일 기록

▶ 파일 개방과 폐쇄의 구현

- 묵시적: 첫 번째 참조시 개방하고, 개방한 작업이나 프로그램의 종료시 폐쇄

- 명시적: 시스템 호출에 의한 개방과 폐쇄

▶ 개방 파일 테이블: 프로세스들이 개방한 파일들에 관한 테이블

- 파일 포인터: 현재 파일 위치 포인터 → 각 프로세스마다 생성

- 파일 개방 계수: 계수가 0에 도달할 때, 비로소 항목을 제거

- 파일의 디스크 위치

▶ 파일의 메모리 사상: [그림 10.1] 기억장치 사상 파일

10.1.3 파일 형태(File Types)

▶ 운영체제가 파일 형태를 인식하면, 그 파일을 합리적으로 조작하게 할 수 있음

→ 파일 이름의 한 부분(확장자)에 의한 파일 형태 명시

[그림 10.2] 공통 파일 형태

- 원시 프로그램의 실행 시도 → 최근 수정/생성 시간을 참조한 자동 재컴파일 후 실행

- 파일의 개방 시도(ex: 문서.hwp) → 생성자 프로그램의 자동 호출(ex: HWP 프로그램 실행)

10.1.4 파일 구조(File Structure)

▶ 운영체제와 파일 구조의 관계

1) 운영체제가 다중 파일 구조를 관리하는 경우

(장점) 

- 적절한 처리 가능

(단점) 

- 여러 유형의 파일 처리를 위한 프로그램 탑재로 운영체제가 비대해짐

- 모든 파일은 운영체제가 정의하는 파일 형태 중 하나라야 함

  ex) 암호화된 파일: 수행 불가

2) 운영체제가 어떠한 파일의 형태도 제공하지 않는 경우

ex) UNIX: 단지 바이트들의 연속체로 간주

(장점)

- 사용자에게 최대한의 융통성 부여

(단점)

- 응용 프로그램별로 입력 파일을 적당한 구조로 해석하는 고유 프로그램 필요

  즉, 운영체제로부터 어떠한 도움도 받지 못함

10.1.5 내부 파일 구조(Internal File Structure)

▶ 물리적 레코드 ↔ 논리적 레코드

- 물리적 레코드: 디스크의 경우 고정 블록 - 섹터

   pack↑↓unpack

- 논리적 레코드: UNIX의 경우 1byte

▶ 내부 단편화(internal fragmentation): 파일을 블록 단위로 나누어 유지함으로써 발생하는 마지막 블록의 낭비된 바이트

→ 일반적으로 블록 크기가 클수록 심함

ex) 파일 1949 바이트 → 4블록 2048 바이트: 99 바이트 낭비

             (1블록 = 512 바이트)

10.2 접근 방법(Access Methods)

10.2.1 순차 접근(Sequential Access) ← 테이프 모델 기반

▶ 개념: 순차적으로 읽거나 쓰고 현재 파일 위치 포인터는 자동적으로 증가

[그림 10.3] 순차 접근 파일

- 파일내에서 순차적으로만 판독하거나 기록할 수 있음

- 특정 시스템에서는 n개(통상 1개) 단위의 레코드 앞뒤로 이동 가능

10.2.2 직접 접근(Direct Access) ← 디스크 모델 기반

▶ 개념: 파일을 블록 혹은 레코드의 집합으로 간주하고, 판독이나 기록의 순서에 제약이 없음

→ 대규모 정보 접근에 유용

- 특히 대규모 정보의 경우, 파일명에 대한 해쉬 함수(hash function)를 사용하거나, 주기억장치내의 색인표(in-core index)를 이용하여 파일 탐색

- 파일의 시작부터 매겨지는 상대 블록 번호를 매개 변수로 하는 파일 조작

① 대치 방식: read next → read n; write next → write n

② 추가 방식: position to n + read next; position to n + write next

- 직접 접근에서 순차 접근의 모의 실험

[그림 10.4] 직접 접근 파일에서 순차 접근의 모의 실험

10.2.3 색인 접근(Index Access) ← 직접 접근 기반

▶ 각 파일마다 색인(index)을 두는 방법

- 각 색인에는 여러 블록을 가리키는 포이터들로 구성됨

- 파일 접근 방법: 색인 탐색 후 포인터에 의한 직접 접근

(예) 소매 가격 파일: (품목) Universal Product Code(UPC)(10bytes) + 가격(6bytes)

  → 모든 품목을 UPC 코드로 정렬한 후, 각 블록의 첫 품목에 대한 UPC로 구성된 색인을 사용

▶ 색인 파일에 대한 색인을 만드는 방법: 큰 파일의 경우 색인 파일이 방대해지므로

- 1차 색인 파일: 이진 탐색

- 2차 색인 파일: 이진 탐색

- 데이터 블록: 선형 탐색

(예) IBM의 ISAM(Indexed Sequential Access Methods): 2차 색인의 디스크 블록을 지정하는 작은 마스터 색인을 사용

(예) VMS: [그림 10.5] 색인과 상대적 파일(relative file)의 예

10.3 디렉토리 구조(Directory Structure)

▶ 파일 시스템: 두 부분으로 구성

- 분할(partition)/볼륨(volume)

- 장치 디렉토리(device directory)/볼륨 테이블(volume table)

[그림 10.6] 전형적인 파일 시스템의 구성

▶ 디렉토리에 대한 조작

① 파일 탐색: 파일명에 의해 디렉토리를 탐색

② 파일 생성: 디렉토리에 해당 파일의 항목을 추가

③ 파일 삭제: 디렉토리에서 해당 파일의 항목을 제거

④ 디렉토리 나열: 디렉토리 내의 파일들에 대한 항목 내용을 보여줌

⑤ 파일의 재명명: 파일의 내용이나 사용이 변경될 때마다 파일명 변경 가능

⑥ 파일 시스템 횡단: 일정 기간마다 파일 시스템의 내용과 구조를 테이프나 디스크에 저장

→ 예비 복사(backup copy)

10.3.1 1 단계 디렉토리(Single Level Directory)

▶ 개념 및 특성: [그림 10.7] 1단계 디렉토리

- 모든 파일이 같은 디렉토리에 있어 유지 및 이해가 용이

- 디렉토리내의 모든 파일의 이름이 구별되어야 함

→ 일반적으로, 파일명의 크기에 제한 있음

   ex) MS-DOS: 11자, UNIX: 255자, MS-WINDOWS: 256자

10.3.2 2 단계 디렉토리(Two Level Directory)

▶ 개념 및 특성: [그림 10.8] 2단계 디렉토리 구조

- 각 사용자마다 별도의 사용자 파일 디렉토리(User File Directory; UFD)가 배정됨

- 업무의 시작이나 등록(login)시 마스터 파일 디렉토리(Master File Directory; MFD)를 먼저 탐색

→ “사용자간의 독립”

(장점) 서로 다른 사용자간의 파일명 혼란 해결

  파일의 생성/삭제시 해당 사용자 파일 디렉토리만 탐색하므로 서로 다른 사용자가 동일한 이름의 파일을 사용할 수 있음

(단점) 사용자간의 협력이 어려워짐

다른 사용자의 파일 참조가,

1) 불가한 경우

2) 가능한 경우: 경로(사용자 이름 + 파일명)를 명시해야 함

  ex) USERA의 파일 ‘TEST’

    - USERA의 경우: TEST

    - USERB의 경우: /USERA/TEST

10.3.3 트리 구조 디렉토리(Tree Structured Directory)

▶ 개념 및 특성: [그림 10.9] 트리 구조로 된 디렉토리 구조

- 사용자들이 자신의 종속 디렉토리(subdirectory)를 생성

→ 각 파일은 유일한 경로를 가짐: ex) MS-DOS

- 파일(0)과 종속 디렉토리(1)의 구분: 각 항목에 한 비트 지정

→ 디렉토리의 생성, 삭제, 변경: 시스템 호출

- 경로 이름

1) 완전 경로 이름: 루트 디렉토리(root directory)부터 지정된 파일까지의 경로 명시

2) 상대 경로 이름: 현재 디렉토리(current directory)를 기준으로 지정

- 다른 사용자의 파일 접근이 용이

→ 탐색 경로 지정 가능

  ex) 순위 예: 1) 자신의 지역 디렉토리

2) 시스템 파일 디렉토리

3) 다른 사용자의 디렉토리

10.3.4 비순환 그래프 디렉토리(Acyclic-Graph Directory)

▶ 개념: [그림 10.10] 비순환 그래프 디렉토리 구조

- 디렉토리들이 종속 디렉토리나 파일을 공유할 수 있도록 허용하는 구조

프로그래머1

프로그래머2

공유 파일

공유 디렉토리

공유 파일

▶ 공유 파일/공유 디렉토리 구현 방법

1) 새로운 디렉토리 항목 사용: ‘링크’ - 다른 파일이나 종속 디렉토리를 가리키는 포인터

2) 공유 파일에 관한 모든 정보를 복사하여 필요로 하는 디렉토리에 두는 방법

▶ 문제점

1) 동일한 파일이 서로 다른 경로에 의해 참조되는 중복 참조 문제

2) 삭제된 공유 파일 공간의 재사용 시점 결정 문제

① 파일의 삭제시 링크도 삭제하는 방법: 각 파일에 대한 링크 리스트 필요

② 파일의 삭제시 링크를 그대로 두는 방법: 파일의 존재 유무 파악 필요

③ 파일에 대한 모든 참조가 삭제될 때까지 파일을 보존하는 방법

→ 마지막 참조가 제거되었는지를 결정하는 방법 필요

- 각 파일에 대한 파일 참조 리스트(reference list) 사용: 리스트의 크기가 가변이고 매우 커짐

- 각 파일에 대한 참조 계수(reference count) 사용

10.3.5 일반적인 그래프 디렉토리(General Graph Directory)

▶ 개념: [그림 10.11] 일반적인 그래프 디렉토리

- 순환 가능 구조

▶ 문제점

1) 탐색시: 무한 순환 가능

2) 삭제시: 참조 카운트가 0이 아닌 경우에도 삭제되어야 하는 경우 발생 - 'self-referencing'

(해결) 쓰레기 수집(garbage collection): 접근 가능 파일을 표시한 뒤, 표시 안된 파일들을 사용 가능 기억 장소의 리스트에 추가

  → 처리 시간이 많이 소모됨

10.4 파일 보호(File Protection) → 19장 참조

▶ 물리적인 손상으로부터의 보호[신뢰도]: 복사에 의해 해결 ex) 정기적인 자동 복사

- 하드웨어의 문제: 판독이나 기록상의 오류, 전원 장애, 헤드 파손, 먼지, 온도, 고의적인 파괴행위

- 소프트웨어 문제: 파일 시스템의 버그(bug)

▶ 부적격한 접근으로부터의 보호[보안]: 접근 제어로 해결

10.4.1 접근의 형태(Types of Access)

▶ 제어되는 명령

- 기본 조작의 통제: 판독, 기록, 실행, 추가, 삭제, 리스트

- 상위 조작의 통제: 재명명, 복사, 편집 등

  → 일반적으로 상위 조작은 기본 조작에 의해 통제됨: ex) 판독(기본) → 복사(상위)

10.4.2 접근 리스트와 그룹(Access Lists and Groups)

▶ 사용자의 신원에 따라 접근을 허용하는 방법

→ 접근 리스트(access list): 각 파일과 디렉토리에 대해, 각 사용자의 이름과 접근 유형을 규정

▶ UNIX의 경우

- 세 가지 부류의 사용자(19.4.2절 참조)

① 소유자(u): 파일을 생성한 사용자

② 그룹(g): 파일을 공유하고 유사한 접근을 필요로 하는 사용자들의 집합

③ 다른 사람(o): 시스템에 있는 모든 다른 사람

- 세 가지(3bit) 제어 명령: UNIX의 경우

① r: 판독 접근

② w: 기록 접근

③ x: 실행 제어

→ 접근 리스트는 총 9bit 필요: [10.4.4 참조]

10.4.3 다른 보호 방법(Other Protection Approaches)

▶ 암호(passwords)에 의해 파일/디렉토리 접근을 제어하는 방법

→ 제어 명령(판독, 기록 등)에 따라 구분되는 다중 암호의 사용 가능

▶ 파일의 이름을 알고 있는 경우에만 접근할 수 있게 하는 방법

→ 동일한 파일도 사용된 경로 이름에 따라 다른 접근 유형을 가질 수 있음

10.4.4 예: UNIX

▶ 디렉토리 리스팅: 파일/디렉토리 보호, 소유자명, 그룹명, 파일 크기(byte), 생성 날짜, 파일명

[그림 10.12] 디렉토리 리스팅 예

10.5 일관성 의미 구조(Consistency Semantics)

▶ 일관성 의미 구조: 동시에 공유된 파일에 접근하려고 하는 다수 사용자의 의미 구조를 규정하는 시스템의 특성

  → 파일 공유를 제공하는 파일 시스템 평가의 중요한 기준

▶ 파일 세션(file session): 개방과 폐쇄 사이의 연속된 파일 접근(판독, 기록)

10.5.1 UNIX 의미 구조(UNIX Semantics)

▶ UNIX 파일 시스템의 단일 영상 개념

- 한 사용자의 개방 파일에 대한 기록이 그 파일을 동시에 개방하고 있는 다른 모든 사용자에게 보여짐

- 파일의 현재 위치 포인터 공유로 한 사용자에 의한 포인터 이동이 다른 모든 사용자에게 영향을 끼침

10.5.2 세션 의미 구조(Session Semantics)

▶ Andrew 파일 시스템의 여러 다른 영상 개념

- 한 사용자의 개방 파일에 대한 기록이 그 파일을 동시에 개방하고 있는 다른 모든 사용자에게 즉시 보여지지 않음

- 일단 파일이 폐쇄되면, 그 파일에서 발생한 변경은 그 후에 시작되는 세션에서만 보여지고, 이미 개방된 그 파일의 예들에서는 이러한 변화를 반영하지 않음

10.5.3 불변 공유 파일 의미 구조(Immutable-Shared-Files Semantics)

▶ 특별한 경우

  → 공유 파일은 파일명이 재사용되거나 파일 내용이 변경될 수 없음

9. 가상 기억장치(Virtual Memory)

▶ 목적: 프로세스가 기억장치 내에 전부 존재하지 않아도 수행이 가능하게 하기 위한 기법

→ 요구 페이징 형태의 가상 기억장치에 대해 논의

9.1 배경(Background)

▶ 일반적으로 수행을 위해 프로그램 전체를 요구하지 않고, 전체 프로그램을 요구하는 경우에도 동시에 모두 요구하지 않음

▶ 프로그램의 부분적인 적재 및 수행의 장점

- 실제 기억 공간의 양에 제한을 받지 않음

- 실제 기억 공간을 적게 차지하므로 보다 많은 사용자 프로그램이 수행될 수 있음

- 적재(load)나 교체(swap)를 위한 입출력이 적어지므로 수행이 신속해짐

▶ 가상 기억장치: 물리 기억장치로부터 사용자 논리 기억장치를 분리

→ 매우 큰 가상 기억장치를 제공

[그림 9.1] 물리 기억장치보다 큰 가상 기억장치를 나타내는 도표

▶ 가상 기억장치의 구현

- 요구 페이징(demand paging): 많이 사용

- 요구 세그먼테이션(demand segmentation): 가변 크기의 세그먼트로 인해 복잡

  ex) Burroughs 컴퓨터 시스템, IBM OS/2

9.2 요구 페이징(Demand Paging)

▶ 개념: 스와핑(swapping) 기법을 쓰는 페이징 체제와 유사

[그림 9.2] 연속된 디스크 공간에 페이지화된 기억 장치의 이동

1) 전체 프로그램은 보조 기억장치에 저장하고

2) 게으른 스와퍼(lazy swapper)에 의해 요구된 페이지만 기억 장치에 교체로 저장

- 스와퍼(swapper): 프로세스 전체 교체기

     ↕

- 페이저(pager): 개개의 페이지 교체기 - 보다 적합한 용어

→ 해당 페이지의 위치를 구별하기 위해 페이지 테이블의 유효/무효 비트 기법 사용: 

  기억장치 ↔ 디스크

[그림 9.3] 일부 페이지가 주기억장치에 없을 때의 페이지 테이블

3) 무효 페이지 접근시, 페이지 부재 트랩 발생에 의한 교정: p.316-317의 과정 1-6

[그림 9.4] 페이지 부재를 처리하는 단계

▶ 순수 요구 페이징(pure demand paging): 요구될 때까지 결코 페이지를 기억 장치 속에 들여놓지 않는 방법

→ 기억 장치 속에 어떠한 페이지도 가지지 않고 시작

▶ 요구 페이징을 위한 H/W 및 S/W

- H/W: 페이징과 스와핑을 위한 하드웨어와 동일

1) 페이지 테이블: 유효/무효 비트

2) 보조기억장치: 고속의 디스크 장치 사용 - 스왑 장치

- S/W: 페이지 부재(page fault)를 해결 후 명령어를 다시 시작해야 함

ex) C ← A + B: p.318의 1-5

  → 단계 5에서 페이지 부재가 발생하면, 요구된 페이지를 가져온 후 단계 1부터 재 수행함

9.3 요구 페이징의 성능(Performance of Demand Paging)

▶ 요구 페이지화된 기억 장치에서의 유효 접근 시간

- 기억 장치 접근 시간(memory access time): ma

- 페이지 부재 확률: p

→ 유효 접근 시간 = (1-p) * ma + p * 페이지 부재 시간(page fault time)

                                            (p.320의 1-12 참조)

▶ 페이지 부재 서비스 시간의 세 가지 주요 구성 요소

① 페이지 부재 인터럽트의 처리

② 페이지를 교체하여 읽어들임

③ 프로세스 재시작

ex) 평균 페이지 부재 서비스 시간: 25msec, 기억장치 접근 시간: 100nsec

→ 유효 접근 시간 = (1-p) * 100nsec + p * 25msec

                  = (1-p) * 100nsec + p * 25,000,000nsec

                  = (100 + 24,999,900*p)nsec

- if p = 0.001, 유효 접근 시간 = 25μsec - 250배 감속

- if 10% 미만으로 감속하려면, 110 > 100 + 25,000,000*p, p < 0.0000004

* 페이지 부재율이 매우 낮아야 프로그램 수행 시간을 적당한 수준에서 유지할 수 있음

9.4 페이지 교체(Page Replacement)

▶ 페이지 부재시 빈 프레임이 없는 경우: 과도 할당(over-allocation) 

[그림 9.5] 페이지 교체의 필요성

① 사용자 프로그램을 중단하는 방법

② 프로세스 교체 방법: 다른 프로세스를 내보내 다중 프로그래밍 정도를 낮춰서 프레임을 확보

③ 페이지 교체 방법: 현재 사용되지 않고 있는 프레임을 스왑 공간에 저장하고 그 프레임을 확보

[그림 9.6] 페이지 교체 → p.324-325의 1-4

▶ 페이지 교체 시, 디스크로 나가는 페이지의 복사 시간 절약 방법

→ 수정 비트(modify/dirty bit) 사용: 즉, 페이지가 수정 상태가 아니면 예비기억장치에 복사할 필요 없음

▶ 요구 페이징 구현을 위한 두 알고리즘

- 페이지 교체 알고리즘: 희생될 페이지의 선택

- 프레임 할당 알고리즘: 프로세스마다 할당될 프레임 수 결정

9.5 페이지 교체 알고리즘(Page Replacement Algorithm)

▶ 알고리즘 선택 기준: 페이지 부재율(page fault rate)을 최소로 하는 알고리즘 선택

▶ 기억 장치 참조열(reference string): 난수 발생기에 의한 생성 또는 실제 시스템의 참조 기록

<자료의 양 축소>

- 주소(p+d) 대신 페이지 번호(p)만 고려

- 연속된 참조는 1회 참조로 간주: 연속된 참조시 페이지 부재가 발생하지 않기 때문

ex) 주소 참조열: 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 

                 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105

  → 축소된 페이지 참조열(페이지당 100byte일 때): 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

▶ 프레임 수가 증가할수록 페이지 부재 수는 감소함

ex) 위의 페이지 참조열에 대해,

- 프레임 수 = 3: 3번의 부재 - 최초 참조시에만 발생

- 프레임 수 = 1: 11번의 부재 - 매 참조시 발생

[그림 9.7] 페이지 부재 대 프래임 수의 그래프

▶ (예) 

- 프레임 수: 3

- 페이지 참조열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

9.5.1 선입선출(FIFO; First-In-First-Out) 알고리즘

▶ 원칙: 가장 오래된 페이지를 대치 → 선입선출 큐 활용

  [그림 9.8] 선입선출(FIFO) 페이지 대치 알고리즘 → 총 15번의 페이지 부재 발생

▶ 특성

- 알고리즘 간단

- Belady의 이상 현상 발생 가능

“할당되는 프레임 수가 증가해도 페이지 부재율이 증가하는 현상”

ex) 참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

[그림 9.9] 어떤 참조열에 대하여 FIFO 대치 알고리즘을 적용했을 경우의 페이지 부재 그래프

9.5.2 최적(OPT, MIN; Optimal) 알고리즘

▶ 원칙: 앞으로 가장 오랜 기간 동안 사용되지 않을 페이지를 대치

  [그림 9.10] 최적 페이지 대치 → 총 9번의 페이지 부재 발생

▶ 특징

- 최소의 페이지 부재율을 나타냄

- Belady의 변이가 나타나지 않음

- 참조열의 미래 정보를 요구하므로 비현실적인 알고리즘임

- 다른 알고리즘의 비교 평가를 위한 기준으로 사용

9.5.3 최근 최소 사용(LRU; Least Recently Used) 알고리즘

▶ 원칙: 가장 오랫동안 사용되지 않은 페이지를 대치

[그림 9.11] 최근 최소 사용 페이지 대치 → 총 12번의 페이지 부재 발생

▶ 특징

- 가장 최근의 과거를 가까운 미래의 근사치로 사용

→ 시간적으로 거꾸로 찾는 최적 페이지 알고리즘

- 구현 방법: 하드웨어 지원이 필히 요구됨 

→ 매 기억장치 접근마다 소프트웨어로 정보 유지하는 것은 매우 느리기 때문

① 계수기(counter): 기억 장치 참조시마다 증가하는 계수기를 두고, 페이지를 참조할 때 그 페이지 테이블의 항목에 연관된 사용 시각 레지스터에 계수기의 값을 저장하는 방법

→ 최후 사용 시각이 가장 적은 페이지를 대치

② 스택(stack): 페이지 참조시마다 그 페이지 번호를 스택에서 제거하고 꼭대기(top)에 둠으로써 가장 최근에 사용된 순으로 정렬하는 방법

→ 바닥(bottom)에 있는 페이지를 대치

[그림 9.12] 가장 최근의 페이지 참조를 기록하기 위한 스택의 사용

- Belady의 변이가 발생하지 않음: n개의 프레임을 사용할 때 기억 장치에 있는 페이지 집합은 n+1개의 프레임을 사용할 때 기억 장치에 있는 페이지 집합의 부분 집합이기 때문

9.5.4 LRU 근접(Approximation) 알고리즘

▶ 원칙: LRU를 위한 고급 하드웨어 지원이 없는 시스템의 경우, 참조 비트(reference bit)를 이용하여 부분적인 순서 정보를 추출함으로써 근사 LRU를 구현할 수 있음

→ 페이지 참조시 참조 비트를 세트함으로써 페이지가 사용된 순서는 알 수 없으나 최근의 일정 기간 동안에 사용되었는지 여부를 구별해 낼 수 있음

(1) 참조 비트가 부가된 알고리즘(Additional-Rreference-Bits Algorithm)

- 각 페이지에 대해 참조 비트와 8비트 우측 이동 레지스터(right shift register)를 유지하고, 

- 일정 간격으로 타이머 인터럽트가 발생될 때, 각 페이지의 참조 비트를 해당 이동 레지스터의 상위 비트로 전달하면서 우측으로 이동시키면,

- 레지스터의 무부호 정수 값이 작을수록 최근에 덜 사용된 것이므로, 그 값이 최소인 페이지를 대치함

ex) 00000000: 8번의 기간 동안 사용되지 않은 페이지

    11111111: 각 기간마다 최소한 한번씩 사용된 페이지

    11000100이 01110111보다 최근에 사용된 페이지의 레지스터 값

* 단지 참조 비트만 두고 이동 레지스터를 두지 않으면(0bit), 2차 기회 알고리즘에 해당됨

(2) 2차 기회 알고리즘(Second-Chance Algorithm)

- FIFO 대치 알고리즘을 기본으로 하여 희생자를 선택하는 것을 원칙으로 하되,

- 일정 간격으로 타이머 인터럽트가 발생될 때, 참조 비트가 1인 경우 0으로 변경하여 2차적 기회를 주고, 참조 비트가 0인 경우 대치한다.

- 물론, 페이지의 참조시 해당 참조 비트는 1로 세트된다.

→ 구현: 순환 큐(circular queue) 사용

[그림 9.13] 2차 기회 페이지 대치 알고리즘

(3) 2차 기회 개선 알고리즘(Enhanced Second-Chance Algorithm)

“(참조 비트, 수정 비트)”

- 1등급: (0, 0) - 최근 참조×, 변경×

- 2등급: (0, 1) - 최근 참조×, 변경○

- 3등급: (1, 0) - 최근 참조○, 변경×

- 4등급: (1, 1) - 최근 참조○, 변경○

→ 순환 큐에서 가장 낮은 등급 번호의 페이지를 대치

ex) 매킨토시 가상기억장치에서 사용

9.5.5 계수 알고리즘(Counting Algorithm)

▶ 계수기(counter): 각 페이지에 대해 참조한 숫자를 기록

(1) 최소 사용 빈도수(LFU; Least Frequently Used) 알고리즘

“각 페이지마다 참조 회수 계수기를 유지하고, 최소 값을 갖는(잘 사용되지 않는) 페이지를 대치”

(문제점) 초기 단계에만 빈번히 사용되는 페이지는 오랫동안 남게 됨

→ 지수적으로 감소하는 평균 사용 회수 사용: 일정 시간 간격마다 계수기를 우측 이동시킴

(2) 최대 사용 빈도수(MFU; Most Frequently used) 알고리즘

“각 페이지마다 참조 회수의 계수기를 유지하고, 최대 값을 갖는(이미 많이 사용된) 페이지를 대치”

(문제점) 지속적으로 사용되는 페이지가 있는 경우에는 역효과 발생

→ 페이지가 일정 기간 동안 사용되다가 필요 없어지는 경우에만 적합

▶ LFU와 MFU의 구현은 많은 비용이 소요되고, 최적 알고리즘에 접근하지도 않는 특별 알고리즘임

9.5.6 페이지 버퍼 알고리즘(Page Buffering Algorithm)

▶ 개념: “특정 페이지 대치 알고리즘 + 가용 프레임의 저장소”

→ 희생된 프로세스의 페이지가 보조 기억 장치로 가기 전에 임시로 저장하게 하여 해당 페이지가 곧 다시 필요해지면 신속하게 프로세스를 재개할 수 있게 하는 방법

▶ 추가적인 개선안

① 가용 프레임 저장소에 있는 페이지에 대한 수정 비트 리스트 관리

→ 페이지 기법의 장치가 쉬는 동안에, 가용 프레임 저장소에 있는 페이지의 수정 비트가 1이면 디스크에 기록하고 0으로 리셋함

② 가용 프레임의 저장소에 있는 페이지가 있었던 프레임 번호를 관리

→ 해당 페이지가 곧 다시 필요해지고, 있었던 프레임이 훼손되지 않았다면 프레임 보조기억장치로부터의 입력 없이 재사용 가능

9.6 프레임의 할당(Allocation of Frames)

▶ 개념: 다중 프로그래밍 기법을 사용할 때, 각 프로세스에 할당되는 프레임 수를 결정하는 문제

9.6.1 최소 프레임 수(Minimum Number of Frames)

▶ 명령어 집합 구조에 의해 정의됨

→ 즉, 하나의 명령어가 참조하는 모든 페이지를 수용할 수 있는 충분한 프레임 수

ex) PDP-11: 최소 6 프레임

IBM/370: 최소 8 프레임

Data General사의 Nova3: 최소 17 프레임 - 간접 참조의 영향

▶ 일반적으로 각 프로세스에 할당되는 프레임 수가 줄어들수록 페이지 부재율은 상승하고 수행 속도는 감소한다.

9.6.2 할당 알고리즘

▶ 다중 프로그래밍 정도에 따라 각 프로세스에 할당되는 프레임 수는 가변

▶ 균일 할당(equal allocation): 각 프로세스에 동등하게 할당

- 프레임 수: m

- 프로세스 수: n

→ m/n: 각 프로세스에 할당

   m%n: 가용 프레임 버퍼 저장소(free frame buffer pool)

ex) 프레임 수 = 93, 프로세스 수 = 5

  → 18개씩 할당, 3개는 가용 프레임 버퍼 저장소로 사용

▶ 비례 할당(proportional allocation): 각 프로세스의 크기에 비례하여 할당

- 총 프레임 수: 

- 프로세스 , 가상 기억 장소의 크기 , 할당 프레임 수 

,   (단, 최소 프레임 수 이상, 이하로 조정)

ex) m = 62,  → , 

▶ 우선 순위 적용법: 우선 순위가 높은 프로세스에 많은 기억 장소를 할당하여 수행 속도를 높이는 방법

① 우선 순위와 프로세스 크기를 고려한 비례 할당법

② 우선 순위가 높은 프로세스가 낮은 프로세스에 할당된 프레임들 중에서 선택하는 방법

9.6.3 전역 대 국부 할당(Global Versus Local Allocation)

▶ 페이지 교체 알고리즘의 종류

① 전역 교체(global replacement): 전체 프레임 중에서 선택

- 각 프로세스에 할당되는 프레임 수 가변

- 각 프로세스의 페이지 부재율 및 수행 시간 가변

② 국부 교체(local replacement): 해당 프로세스에 할당된 프레임 중에서 선택

- 각 프로세스에 할당되는 프레임 수 불변

- 각 프로세스의 페이지 부재율 및 수행 시간 불변

* 전역 교체가 보다 좋은 성능을 보이는 일반적인 방법임

9.7 스레싱(Thrashing)

▶ 개념: 지나치게 자주 페이지 교환이 일어나는 현상 - “프로그램 수행시간 < 페이지 교환 시간”

  → 심각한 성능 저하 초래

9.7.1 스레싱의 원인(Cause of Thrashing)

  

▶ 중앙처리장치의 이용률 ↔ 다중 프로그래밍의 정도: [그림 9.14] 스레싱

▶ 발생 과정: 

① 중앙처리장치의 이용률이 낮음

② 운영체제는 다중 프로그래밍의 정도를 높임

③ 페이지 부재율이 상승됨

④ 프로세스들이 페이징 처리 장치에서 대기함

⑤ 준비 큐가 비게 되어 중앙처리장치의 이용률이 낮아짐

⑥ 운영체제는 다중 프로그래밍의 정도를 더욱 높임: 악순환

⑦ 스레싱 발생

▶ 스레싱 방지 방법: 각 프로세스가 필요로 하는 프레임을 제공해야 함

- 프로세스 실행의 지역성 모델(locality model) 정의

- 지역(local): 실제로 함께 사용되는 페이지의 집합

[그림 9.15] 기억장치 참조 패턴의 국부성

ex) 서브루틴의 호출 시, 새로운 지역 정의: 

  → 서브루틴의 명령어들, 지역 변수들, 전역 변수들의 집합

- 프로세스에게 현재의 지역을 만족시키는 충분한 프레임을 제공함으로써 스레싱을 방지할 수 있음

9.7.2 작업 집합 모델(Working-Set Model)

▶ 작업 집합(working set): 지역의 근사치

→ 작업 집합 창(working set window) (일정 시간, 일정 참조 횟수)에서 참조한 페이지 집합

[그림 9.16] 작업 설정 모델( = 10인 경우)

▶ 작업 집합의 정확도: 의 선택에 좌우됨

- 小: 전체 지역을 충족하지 못함

- 大: 여러 지역이 중복됨

▶ 시스템 내의 각 프로세스에 대한 작업 세트의 크기: 

- 전체 요구 프레임: 

- 총 유효 프레임 수: m

→ 만일 D > m이면, 스레싱 발생 가능

▶ 작업 집합 모델의 사용법

- 각 프로세스에 작업 집합의 크기에 맞는 충분한 프레임을 할당하되,

- 여분 발생 시에는 다른 프로세스를 작동시키고, 부족 시에는 한 프로세스를 중지시켜 확보함 

→ 다중 프로그래밍의 정도를 가능한 높이면서도 스레싱을 방지할 수 있음

▶ 난점: 작업 집합의 추적

- 일정 간격 타이머 인터럽트(timer interrupt)와 참조 비트(reference bit)를 활용 

→ 타이머 인터럽트마다 참조 비트를 복사하여 필요한 만큼 저장하여 작업 집합을 구함

9.7.3 페이지 부재 빈도(Page-Fault Frequency)

▶ 개념: 페이지 부재율을 직접 조절함으로써 스레싱을 방지하는 방법

[그림 9.17] 페이지 부재 빈도

→ 각 프로세스의 페이지 부재율에 대한 상한과 하한을 정하고,

- 상한 초과시: 프레임을 더 할당 → 여분 프레임이 없는 경우, 한 프로세스를 선택하여 중지시킴

- 하한 미만시: 프레임을 회수

9.8 기타 고려 사항(Other Considerations)

9.8.1 프리페이징(Prepaging)

▶ 개념: 프로세스의 시작 혹은 교체된 프로세스의 재시작의 경우, 필요한 것으로 간주되는 모든 페이지를 한꺼번에 기억장치에 가져옴으로써 페이지 부재를 감소시키는 방법

- 작업 집합 정보의 저장 필요

- 프리페이징에 드는 비용이 적어야 하고, 프리페이징에 의해 가져온 페이지가 사용되지 않는 비율이 적어야 함

9.8.2 페이지 크기(Page Size)

▶ 고려 사항

- 페이지 테이블 크기(↓) ↔ 페이지 크기(↑)

- 내부 단편화(↓) ↔ 페이지 크기(↓)

- 입출력 시간(↓) ↔ 페이지 크기(↑): 회전 지연의 횟수 감소(회전 지연 시간 > 전송 시간)

- 지역성(↑) ↔ 페이지 크기(↓)

- 페이지 부재율(↓) ↔ 페이지 크기(↑)

→ 페이지 크기를 결정하는 것은 어려움

9.8.3 역 페이지 테이블(Inverted Page Table)

▶ 역 페이지 테이블: 8.5.4절 참조

→ 메모리의 프레임마다 하나의 ‘항목’을 가짐: <process-id, page-number>

- 장점: 각 페이지 테이블을 별도로 저장하는데 필요한 메모리 총량 감소

- 단점: 페이지를 참조할 때 탐색 시간 증가

▶ 역 페이지 테이블은 요구 페이징이 필요로 하는 프로세스의 전체 논리적 기억 공간을 포함 못함

→ 프로세스마다 ‘확장된 페이지 테이블(extended page table)’을 두되, 페이지 부재가 발생할 경우에만 디스크에서 불러들여 사용함

9.8.4 프로그램 구조(Program Structure)

▶ 개념: 요구 페이징은 사용자 프로그램으로부터 감춰지지만, 그 특성을 알면 시스템 성능 개선에 도움이 됨

▶ (예) p.350-351의 두 프로그램

  → 페이지 부재 횟수(페이지 크기 = 128워드)

  ① 128 * 128 = 16,348회

  ② 128회

9.8.5 입출력 상호잠금(Input/Output Interlock)

▶ 개념: 요구 페이징을 사용할 때 일부 페이지를 기억장치에 고정시키는 것이 필요

▶ 어떤 프로세스가 입출력을 위해 장치 큐에 들어간 사이에 해당 페이지가 다른 프로세스의 수행을 위해 교체되어선 안됨

[그림 9.18] 입출력을 위하여 사용되는 프레임이 메모리내에 존재해야 하는 이유를 나타내는 도표

(해결책)

① 사용자 기억장치가 아닌 시스템 기억 장치에서만 입출력이 일어나게 하는 방법

  “사용자 기억장치 ↔ 시스템 기억장치 ↔ 입출력 장치”

  → 오버헤드: ‘복사’

② 페이지들이 기억장치 속에서 잠금(lock)되게 하는 방법

  → 각 프레임마다 잠금 비트(lock-bit)를 두어, 입출력하는 동안 교체되지 않게 함

▶ 새로 읽은 페이지가 적어도 한번 사용되기 전에 우선 순위 교체에 의해 교체 당하는 것을 방지하기 위해 잠금 비트를 사용할 수 있음

  → 잠금 비트가 설정된 후 해제되지 않거나 과도한 잠금이 발생하지 않도록 해야 함

9.8.6 실시간 처리(Real-Time Processing)

▶ 실시간 시스템은 거의 가상 메모리를 사용하지 않음

  → 가상 메모리를 사용하는 경우, 해당 페이지를 잠금할 수 있게 함

9.9 요구 세그먼테이션(Demand Segmentation)

▶ 개념: 세그먼트 단위로 메모리를 할당

ex) OS/2

▶ 특징: 요구 페이징에 비해 효율은 떨어지지만 하드웨어가 부족한 경우에 적합

▶ 세그먼트 디스크립터(descriptor): 세그먼트 크기, 보호 정보, 위치 정보

- 유효 비트(valid bit): 해당 세그먼트가 메모리에 있는지를 나타내는 비트

- 접근 비트(accessed bit): 세그먼트 부재로 교체할 세그먼트의 선택을 위해 사용하는 비트

→ 요구 페이징에서의 참조 비트와 동일한 역할: 세그먼트 큐에 최근에 사용된 세그먼트가 헤드 부분에 위치하도록 하고 끝 부분의 세그먼트를 교체하면 됨