분류 전체보기 (44) 썸네일형 리스트형 [운영체제] CPU 스케줄링: 알고리즘의 평가 - (1) 알고리즘의 평가(Algorithm Evaluation) - 시스템에 맞는 CPU 스케줄링 알고리즘을 선택하는 방법 1. 알고리즘을 선택하는 데 사용할 기준을 정의한다. 2. 선택 기준이 정의되면, 선택 기준에 따라 알고리즘들을 평가한다. 결정론적 모델링(Deterministic Modeling) 평가 방법 중 중요한 부류 중 하나가 분석적 평가(analytic evaluation)이다. 분석적 평가는 알고리즘 성능 평가하는 공식이나 값을 생성하기 위해 주어진 알고리즘과 시스템 부하를 이용한다. 결정론적 모델링(deterministic modeling)은 분석적 평가의 한 가지 유형이다. 이는 미리 정의된 특정 작업 부하를 이용하여 각 알고리즘의 성능을 정의한다. 결정론적 모델링의 장점은 단순하고 빠르고,.. [데이터베이스] 질의 처리와 최적화 - (1) 질의 처리 단계(Query Processing Procedure) 1. parsing과 translation: parser는 사용자가 작성한 질의의 문법이 맞는지 확인하고, 질의를 parse tree로 변환한다. 그 후 parse tree는 관계 대수 표현식으로 변환된다. 2. optimization: 먼저, 하나의 관계 대수식에 대해 동등한 관계 대수식을 가지는 많은 수의 질의 평가 계획(query execution plan)을 생성된다. 그 후, 각 질의 평가 계획을 구성하고 있는 relational operation들이 수행되었을 때 result size를 통계적으로 추정한다. 이때, 딕셔너리 데이터베이스에 저장되어 있는 통계적 수치들을 이용해서 result size를 추정하게 된다. (튜플의 개수.. [데이터베이스] 동시성 제어 - (2) 교착 상태 처리 - 잠금 기반 규약의 단점 아래의 스케줄을 살펴보면, lock-S(B)는 T4가 T3가 B에 대한 lock을 해제하기를 기다리도록 하고, lock-X(A)는 T3이 T4가 A에 대한 lock을 해제하기를 기다리도록 한다. 따라서 T3와 T4는 더 이상 진행되지 못하고 무한히 기다리는 교착 상태(dead lock)에 빠지게 된다. 또한 잠금 기반 규약은 기아(starvation) 현상이 발생할 수 있다. 이는 aging 기법을 사용해서 해결할 수 있다. - 교착 상태 예방 교착 상태를 예방하는 한 가지 방법으로 timeout-based schemes가 있다. 이는 lock을 요청한 트랜잭션이 일정한 시간 동안 기다리다가, 그 시간 안에 lock을 얻지 못하면 스스로 롤백해서 다시 시작하는 .. [데이터베이스] 동시성 제어 - (1) 동시성 문제 1. lost update problem: 두 트랜잭션이 같은 데이터 항목에 동시에 접근해 데이터 항목의 값을 갱신할 때, 두 트랜잭션 모두 정상적으로 실행됐음에도 불구하고 한 트랜잭션이 갱신한 값이 사라지는 문제가 발생한다. 2. uncommitted dependency: 한 트랜잭션 T1이 데이터 항목 X의 값을 갱신한 후,다른 트랜잭션 T2가 변경된 X의 값을 읽었을 때 트랜잭션 T1이 롤백되면, 저장된 X와 트랜잭션 T2가 읽은 X의 값이 일치하지 않는 문제가 발생한다. 3. inconsistent analysis problem: 한 트랜잭션의 실행 중에 다른 트랜잭션이 실행될 때, 데이터베이스의 일관성이 깨지는 문제가 발생할 수 있다. 잠금 기반의 규약(Lock-Based Proto.. [데이터베이스] 복구 시스템 - (3) 복구 알고리즘 - 트랜잭션 롤백 트랜잭션 롤백은 시스템 failure 후 복구 과정이 아닌 정상적인 상황에서 발생한다. 트랜잭션 $T_{i}$의 롤백은 다음과 같이 수행된다. 1. 로그를 역방향으로 스캔한다. $T_{i}$의 로그 레코드 를 만나면, 데이터 항목 $X_{j}$에 값 $V_{1}$을 기록하고, undo 작업에 대한 로그 레코드 를 기록한다. 이때, 이런 로그 레코드를 보상 로그 레코드(compensation log record)라고 부른다. 2. 를 만나면 역방향 탐색을 중단한다. 그리고 로그 레코드를 로그에 기록한다. - 시스템 failure 후의 복구 두 가지 단계를 거쳐 복구가 이루어진다. redo 단계: 마지막 검사점부터 순방향으로 로그를 탐색하며 모든 트랜잭션의 갱신 작업을 red.. [데이터베이스] 복구 시스템 - (2) 복구와 원자성(Recovery and Atomicity) failure에도 불구하고 원자성을 보장하기 위해서, 데이터베이스를 변경하기 전에 먼저 안정 저장 장치(stable storage)에 데이터베이스 변경과 관련된 정보를 기록해야 한다. 그중 가장 널리 사용하는 방법은 로그 기반 복구(log-based recovery)이다. - 로그 기반 복구(log-based recovery) 로그(log)는 안정 저장 장치에 유지되고, 연속된 로그 레코드(log record)로 구성되며, 데이터베이스의 모든 갱신 작업을 기록한다. 트랜잭션 $T_{i}$가 시작할 때, 로그 레코드 가 써진다(write). 트랜잭션 $T_{i}$가 write(X) 연산을 실행하기 전에, 로그 레코드 가 써진다. ($V_{1}$: 쓰.. [데이터베이스] 복구 시스템 - (1) 실패 분류(Failure Classification) 1. 트랜잭션 실패(transaction failure): 트랜잭션 실패를 유발하는 두 가지 원인이 있다. 논리적 오류: 잘못된 입력, 데이터 부재, 오버플로, 자원의 한계 초과 등 internal error로 인해 트랜잭션이 완료할 수 없는 상태를 의미한다. 시스템 오류: deadlock과 같은 error condition에 의해 데이터베이스 시스템이 트랜잭션을 종료해야 하는 상태를 의미한다. 2. 시스템 장애(system crash): 파워 고장이나 하드웨어 혹은 소프트웨어 오류로 인해 시스템이 정지되고 휘발성 저장 장치의 내용이 손실되고 트랜잭션 처리가 중단되는 상태를 의미한다. 이때, 시스템 장애가 발생해도 비휘발성 저장 장치의 내용은 손상되지.. [데이터베이스] 트랜잭션 - (2) 복구 가능한 스케줄(Recoverable Schedule) 복구 가능한 스케줄(recoverable schedule)이란 모든 트랜잭션 쌍 $T_{i}$와 $T_{j}$에 대해, $T_{i}$가 이전에 기록한 데이터 항목을 $T_{j}$가 읽었다면 $T_{i}$의 commit 연산이 $T_{j}$의 commit 연산보다 먼저 발생하는 스케줄을 말한다. 다음은 복구 불가능한 스케줄의 예시이다. 비연쇄적인 스케줄(Cascadeless Schedules) 하나의 트랜잭션의 취소로 인해 다른 트랜잭션들이 롤백되는 현상을 연쇄적 롤백(cascading rollback)이라고 한다. 이는 많은 양의 작업이 취소되기 때문에 비효율적인 방법이다. 따라서, 연쇄적 롤백이 발생하지 않도록 스케줄에 제한을 주어야 하는데, .. 이전 1 2 3 4 5 6 다음
