DB 후루룩 & ONE EYED JACK Collaboration_ ★

다중 사용자 환경에서 둘 이상의 트랜잭션이 동시에 접속하여 해당 연산을 수행할 때, 문제 점이 전혀 발생하지 않도록 트랜잭션의 수행 을 적절히 제어해 주는 것을 말함. DBMS 예금 입출금 예금 입출금 외환 인터넷 뱅킹 예금 해지 예금 해지 대출 업무

무제어 병행 수행의 문제점 갱신 분실 모순성 연쇄 복귀 갱신 분실 : 하나의 트랙잭션이 갱신한 내용을 다른 트랙잭션이 덮어씀으로써 갱신의 무효화 되는 것이다. 모순성 : 다른 트랙잭션들이 해당 항목 값을 갱신하는 동안에 한 트랙잭션이 두 개의 항목 값 중 어떤 것은 갱신되기 전의 값을 읽고, 또 다른 것은 갱신된 후의 값을 읽게 되어 데이터의 불일치가 발생 하는 상황이다. 연쇄 복귀 : 두 트랙잭션이 동일한 데이터 내용을 접근할 때 발생하며, 한 트랙잭션이 데이터를 갱신한 다음 에 실패하여 rollback 연산을 수행하는 과정에서 갱신 과 rollback 연산을 실행하고 있는 사이에 해당 데이터를 읽어서 사용할 때 발생할 수 있는 문제이다.

트랜잭션 스케줄 직렬 스케줄 (Serial Schedule) 직렬 스케줄 (Serial Schedule) 직렬 가능 스케줄 (Serializable Schedule) 직렬 가능 스케줄 (Serializable Schedule) 비직렬 스케줄 (Non Serial Schedule) 비직렬 스케줄 (Non Serial Schedule)

직렬 스케줄 (Serial Schedule) 트랜잭션의 연산을 모두 순차적으로 실행하는 유형을 의미함 다중프로그래밍 환경에서는 CPU 의 활용도가 떨어짐

트랜잭션 ID : T_ 01 시간 트랜잭션 ID : T_ 02 Read(x) x = x+300 Write(x) Read(y) y = y Write(y) Read(x) x = x+300 Write(x) Read(y) y = y Write(y) Read(x) x= x * 2 Write(x) Read(y) y = y * 2 Write(y) Read(x) x= x * 2 Write(x) Read(y) y = y * 2 Write(y)

트랜잭션 T_ 01 트랜잭션 T_ 02 데이터베이스 결과 설명 Read(x) x = x+300 Write(x) Read(y) y = y Write(y) x = 1800 y= 1300 T_ 01 트랜잭션은 x 의 초기값 1500 과 y 의 초기값 1000 을 읽어 서 300 을 증가시킨 후 데이터 베 이스에 저장한다. Read(x) x= x * 2 Write(x) Read(y) y = y * 2 Write(y) x = 3600 y = 2600 T_02 트랜잭션은 데이터베이스에 저장된 x 의 값 1800 과 y 의 값 1300 을 읽어서 2 배 증가시킨 후 데이터 베이스에 저장한다. T_ 01  T_ 02 수행 순서의 직렬 스케줄 결과

트랜잭션 ID : T_ 01 시간 트랜잭션 ID : T_ 02 Read(x) x = x+300 Write(x) Read(y) y = y Write(y) Read(x) x = x+300 Write(x) Read(y) y = y Write(y) Read(x) x= x * 2 Write(x) Read(y) y = y * 2 Write(y) Read(x) x= x * 2 Write(x) Read(y) y = y * 2 Write(y)

트랜잭션 T_ 01 트랜잭션 T_ 02 데이터베이스 결과 설명 Read(x) x = x+300 Write(x) Read(y) y = y Write(y) x = 3000 y = 2000 T_ 02 트랜잭션은 x 의 초기값 1500 과 y 의 초기값 1000 을 읽어 서 2 배 증가시킨 후 데이터 베이스 에 저장한다. Read(x) x= x * 2 Write(x) Read(y) y = y * 2 Write(y) x = 3300 y = 2300 T_ 01 트랜잭션은 데이터베이스에 저장된 x 의 값 3000 과 y 의 값 2000 을 읽어서 300 증가시킨 후 데이 터베이스에 저장한다. T_ 02  T_ 01 수행 순서의 직렬 스케줄 결과

비직렬 스케줄 (Non Serial Schedule) 트랜잭션 직렬 수행 순서와 상관없이 병행 수행하는 스케줄을 의미

트랜잭션 ID : T_ 01 시간 트랜잭션 ID : T_ 02 Read(x) x = x+300 Write(x) Read(x) x = x+300 Write(x) Read(x) x= x * 2 Write(x) Read(x) x= x * 2 Write(x) Read(y) y = y Write(y) Read(y) y = y Write(y) Read(y) y = y * 2 Write(y) Read(y) y = y * 2 Write(y)

트랜잭션 T_ 01 트랜잭션 T_ 02 데이터베이스 결과 설명 Read(x) y = y Write(x) x = 1800 y = 1000 T_ 01 트랜잭션은 X 의 초기값 1500 을 읽어서 300 을 증가시킨 후데이터베이스에 저장한다. Read(x) x = x * 2 Write(x) x = 3600 y = 1000 T_ 02 트랜잭션은 데이터베이스에 저장된 X 값 1800 을 읽어서 2 배 증가시킨 후 데이터베이스에 저장한다. Read(y) y = y Write(y) x = 3600 y = 1300 T_ 01 트랜잭션은 y 의 초기값 1000 을 읽어서 300 을 증가시킨후 데이터베이스에 저장한다 Read(x) y = y * 2 Write(y) x = 3600 y = 2600 T_ 02 트랜잭션은 데이터베이스에 저장된 y 의 값 1300 을 읽어서 2 배 증가시킨 후 데이터베이스에 저장한다.

트랜잭션 ID : T_ 01 시간 트랜잭션 ID : T_ 02 Read(x) x = x+300 Read(x) x = x+300 Read(x) x= x * 2 Write(x) Read(x) x= x * 2 Write(x) Read(y) y = y Write(x) Read(y) y = y Read(y) y = y * 2 Write(y) Read(y) y = y * 2 Write(y)

트랜잭션 T_ 01 트랜잭션 T_ 02 데이터베이스 결과 설명 Read(x) x = x x = 1500 y = 1000 T_ 01 트랜잭션은 x 의 초기값 1500 을 읽어서 300 을 증가시킨 후 버퍼에 저장한다. Read(x) x = x * 2 Write(x) x = 3000 y = 1000 T_ 02 트랜잭션은 데이터베이스에 저장된 x 값 1500 을 읽어서 2 배 증가시킨 후 데이터베이스에 저 장한다. Write(x) Read(y) y = y x = 1800 y = 1000 T_ 01 트랜잭션은 y 의 초기값 1000 을 읽어서 300 을 증가시킨후 버퍼에 저장한다. Read(y) y = y * 2 Write(y) x = 1800 y = 2000 T_ 02 트랜잭션은 데이터베이스에 저장된 y 의 값 1000 을 읽어서 2 배 증가시킨 후 데이터베이스에 저 장한다. Write(y) x = 1800 y = 1300 T_ 01 트랜잭션은 데이터베이스에 저장된 y 의 값 1300 을 데이터베이스에 저장한다

직렬 가능 스케줄 (Serializable Schedule) 직렬 스케줄과 동등한 비직렬 스케줄을 일컫는 스케줄

1. 만약 두 개의 트랜잭션 READ 연산만 수행 할 것이라면, 상호 간섭이 발생되 지 않으며, 연산의 순서도 중요하지 않다 2. 만약 두 개의 트랜잭션이 같은 데이터 항목에 접근하지 않는다면 상호 간섭이 발생 되지 않으며, 연산의 순서도 중요하지 않다. 3. 만약 트랜잭션 T_01 이 데이터 항목 X 와 Write 연산을 하고, 트랜잭션 T_02 가 데 이터 항목 X 에 Read 연산이나 Write 연산을 한다면 실행순서는 중요하다. 직렬 가능 스케줄의 특징

1. 스케줄에 포함된 각 트랜잭션에 대한 노드를 생성한다. 2. 트랜잭션 T_I 가 Write(X) 를 실행한 후, T_j 가 read(X) 를 실행하면, 간선 (T_I-> T_j) 를 생성 한다. 3. 트랜잭션 T_I 가 Read(X) 를 실행한 후 T_j 가 Write(X) 를 실행하면 간선 (T_I -> T_j) 를 생성 한다. 4. 트랜잭션 T_I 가 write(X) 를 실행한 후, T_j 가 Write(X) 를 실행하면, 간선 (T_I -> T_j) 를 생 성한다. 선행 그래프를 그리는 방법 ( 순서 )

트랜잭션 ID : T_ 01 시간 트랜잭션 ID : T_ 02 Read(x) x = x+300 Write(x) Read(x) x = x+300 Write(x) Read(x) x= x * 2 Write(x) Read(x) x= x * 2 Write(x) Read(y) y = y Write(y) Read(y) y = y Write(y) Read(y) y = y * 2 Write(y) Read(y) y = y * 2 Write(y)

T_ 01 T_ 02 X Y

트랜잭션 ID : T_ 01 시간 트랜잭션 ID : T_ 02 Read(x) x = x+300 Write(x) Read(x) x = x+300 Write(x) Read(x) x= x * 3 Write(x) Read(y) y = y * 3 Write(y) Read(x) x= x * 3 Write(x) Read(y) y = y * 3 Write(y) Read(y) y = y Write(y) Read(y) y = y Write(y)

T_ 01 T_ 02 Y X

직렬 가능성이 보장되는 병행제어 기법은 각각 의 제어 기법마다 규약이나 규정을 정해 놓고, 모든 트랜잭션들은 해당 규약이나 규정을 따라 주기만 하면, 직렬 가능한 스케줄로 보장받게 되는 것이다. -> 로킹 기법 여러 트랜잭션들이 동일한 데이터 항목에 대해 임의적인 병행 접근을 하지 못하도록 제어 한다.

-> 로킹 기법 ATM1 ATM2 ATM3 Lock

로킹 기법에서 사용하는 잠금 (lock) 연산의 대상 로킹 단위가 극단적으로 데이터베이스가 된다면 병행성이 없게 되고, 반대로 속성이 된다면 최대의 병행성을 제공 받을 수 있으므 로 적절한 로킹 단위의 결정이 필요하다. 데이터베이스릴레이션 ( 파일 ) 투플 ( 레코드 ) 속성 ( 필드 ) 구현 용이 병행성이 낮음 구현 복잡 병행성이 높음 로킹 단위 (Locking Granularity)

확장 단계 (Growing phase) 트랜잭션들은 잠금 (lock) 연산만을 수행할 수 있고 해제 (unlock) 연 산은 수행할 수 없다. 축소 단계 (Shrinking phase) 트랜잭션들은 해제 (unlock) 연산만을 수행할 수 있고 잠금 (lock) 연 산은 수행할 수 없다.

두 개 이상의 트랜잭션들로 구성된 집합 안에 있는 각 트랜잭션 T 가 그 집합 안에 있는 다른 트랜잭션 T ′ 에 의해 로크된 어떤 항목을 기다릴 때 발생한다. read_lock(Y); Read_item(Y ); write_lock(X); read_lock(X); Read_item(X ); write_lock(Y); T1’T2’ 시간 (a) (b) T1’ 그림 15.5 교착상태의 예. (a) 교착상태에 있는 T1 ′ 과 T2 ′ 의 부분 스케줄. (b) (a) 에 있는 부분 스케줄에 대한 대기 그래프.

트랜잭션 A 가 1 행에 대한 공유 잠금을 획득합니다. 트랜잭션 B 가 2 행에 대한 공유 잠금을 획득합니다. 트랜잭션 A 가 2 행에 대한 배타적 잠금을 요청하고 트랜잭션 B 가 2 행에 대해 소유하고 있는 공유 잠금을 종료 및 해제할 때까지 트랜 잭션 A 가 차단됩니다. 트랜잭션 B 가 1 행에 대한 배타적 잠금을 요청하고 트랜잭션 A 가 1 행에 대해 소유하고 있는 공유 잠금을 종료 및 해제할 때까지 트랜 잭션 B 가 차단됩니다. 트랜잭션 B 가 완료되어야 트랜잭션 A 도 완료될 수 있지만 트랜잭 션 B 는 트랜잭션 A 에 의해 차단된 상태입니다. 이러한 상태를 순 환 종속 관계라고 합니다. 트랜잭션 A 는 트랜잭션 B 에 종속되고 트랜잭션 B 는 트랜잭션 A 에 종속된 형태로 순환됩니다.

▸예방 (prevention) 교착 상태의 발생 요건 중 하나 이상을 미리 제거하여 아예 교착 상태가 일어나지 않게끔 방지하는 것이다. 가장 좋은 방법이긴 하나 자원의 이용이 극히 비효율적이다. 회피 (avoidance) 교착 상태의 발생 가능성을 미리 인정하고 교착 상태가 일어나려고 할 때 이를 적절히 피 해 가는 방법으로 교착 상태의 발생은 허용하지 않는다. 예방보다는 좀 더 효율적이나 자 원의 낭비는 여전히 많다. 교착 상태의 회피방법으로 Dijkstra 의 은행원의 알고리즘이 있는 데 이는 각 process 들이 필요로 하는 자원의 총 수와 운영 체제가 가지고 있는 자원의 총수 를 파악하여 운영 체제가 가지고 있는 총 수가 많으면 적절히 process 들을 수행시킨다. 각 process 들은 자기가 필요로 하는 자원의 총 수를 미리 제시하여야 하는데 사용자 수가 항 시 변하고 있고 자원이 고장 날 수도 있으므로 사용 가능한 자원의 총 수를 파악하기 힘들 다. ▸발견 (detection) 교착 상태의 발생을 허용하는 방법으로 실행 중에 추가의 노력이 들게 되는데 자원 할당 그래프를 사용하여 교착 상태의 발생을 항상 감시하여 그래프 상에 cycle 이 나타나면 교착 상태가 발생한 것일 수도 있으므로 자원을 역순으로 제거해 나간다. 이때 만일 소거 불능 이 되면 교착 상태에 빠진 것이 된다. 자원의 사용이 예방이나 회피보다 효율적이다. ▸복구 ( 회복,recovery) 교착 상태의 발생을 허용하는 방법으로 교착 상태가 발생하면 작업의 일부 또는 전부를 강 제로 희생시켜 버리는데 문제는 어느 process 를 희생시킬 것인가 하는 점이다. 자원의 사용 을 효율적으로 할 수 있다.

트랜잭션을 식별하기 위해서 DBMS 가 부여하는 유일한 식별자인 타임 스탬프 를 지정하여 트랜잭션간의 순서를 미리 선택함 - 데이터베이스 시스템에 들어오는 트랜잭션 순서대로 타임 스탬프를 지정하 여 동시성 제어의 기준으로 사용함 - 상충되는 연산들이 타임 스탬프 순서로 처리됨으로 직렬성 (Serializing) 이 보 장됨 (System Clock, Logical Counter) - 트랜잭션이 결코 기다리는 경우가 없으므로 교착상태 (Deadlock) 를 방지할 수 있음 - 문제점은 연쇄복귀 (Cascading Rollback) 를 초래할 수 있음

타임스탬프 순서 (timestamp ordering, TO) 트랜잭션의 수행순서는 각 트랜잭션의 타임스탬프에 기반을 둠 타임스탬프 순서 알고리즘 타임스탬프 순서 기법에서는 스케줄이 트랜잭션들의 타임스탬프의 순서에 해당 하는 특정 직렬 순서와 동치이다. 각 데이터베이스 항목 X 에 대해 두 개의 타임스탬프 값들을 연관시킨다. 1.read_TS(X): 항목 X 의 읽기 타임스탬프 (read timestamp) 로서 항목 X 를 성공적으로 읽은 트랜잭션들의 타임스탬프 중 가장 큰 값이다. 즉, read_TS(X) = TS(T) 이고 여기 서 T 는 X 를 성공적으로 읽은 가장 최근의 (youngest) 트랜잭션이다. 2.write_TS(X): 항목 X 의 쓰기 타임스탬프 (write timestamp) 로서 항목 X 를 성공적으 로 기록한 트랜잭션들의 타임스탬프 중 가장 큰 값이다. 즉, write_TS(X) = TS(T) 이 고 여기서 T 는 X 를 성공적으로 기록한 가장 최근의 트랜잭션이다.