DB 후루룩 & ONE EYED JACK Collaboration_ ★. 다중 사용자 환경에서 둘 이상의 트랜잭션이 동시에 접속하여 해당 연산을 수행할 때, 문제 점이 전혀 발생하지 않도록 트랜잭션의 수행 을 적절히 제어해 주는 것을 말함. DBMS 예금 입출금 예금.

Presentation on theme: "DB 후루룩 & ONE EYED JACK Collaboration_ ★. 다중 사용자 환경에서 둘 이상의 트랜잭션이 동시에 접속하여 해당 연산을 수행할 때, 문제 점이 전혀 발생하지 않도록 트랜잭션의 수행 을 적절히 제어해 주는 것을 말함. DBMS 예금 입출금 예금."— Presentation transcript:

1 DB 후루룩 & ONE EYED JACK Collaboration_ ★

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

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

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

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

6 트랜잭션 ID : T_ 01 시간 트랜잭션 ID : T_ 02 Read(x) x = x+300 Write(x) Read(y) y = y + 300 Write(y) Read(x) x = x+300 Write(x) Read(y) y = y + 300 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)

7 트랜잭션 T_ 01 트랜잭션 T_ 02 데이터베이스 결과 설명 Read(x) x = x+300 Write(x) Read(y) y = y + 300 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 수행 순서의 직렬 스케줄 결과

8 트랜잭션 ID : T_ 01 시간 트랜잭션 ID : T_ 02 Read(x) x = x+300 Write(x) Read(y) y = y + 300 Write(y) Read(x) x = x+300 Write(x) Read(y) y = y + 300 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)

9 트랜잭션 T_ 01 트랜잭션 T_ 02 데이터베이스 결과 설명 Read(x) x = x+300 Write(x) Read(y) y = y + 300 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 수행 순서의 직렬 스케줄 결과

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

11 트랜잭션 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 + 300 Write(y) Read(y) y = y + 300 Write(y) Read(y) y = y * 2 Write(y) Read(y) y = y * 2 Write(y)

12 트랜잭션 T_ 01 트랜잭션 T_ 02 데이터베이스 결과 설명 Read(x) y = y + 300 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 + 300 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 배 증가시킨 후 데이터베이스에 저장한다.

13 트랜잭션 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 + 300 Write(x) Read(y) y = y + 300 Read(y) y = y * 2 Write(y) Read(y) y = y * 2 Write(y)

14 트랜잭션 T_ 01 트랜잭션 T_ 02 데이터베이스 결과 설명 Read(x) x = x + 300 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 + 300 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 을 데이터베이스에 저장한다

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

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

17 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) 를 생 성한다. 선행 그래프를 그리는 방법 ( 순서 )

18 트랜잭션 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 + 300 Write(y) Read(y) y = y + 300 Write(y) Read(y) y = y * 2 Write(y) Read(y) y = y * 2 Write(y)

19 T_ 01 T_ 02 X Y

20 트랜잭션 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 + 300 Write(y) Read(y) y = y + 300 Write(y)

21 T_ 01 T_ 02 Y X

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

23 -> 로킹 기법 ATM1 ATM2 ATM3 Lock

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

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

26 두 개 이상의 트랜잭션들로 구성된 집합 안에 있는 각 트랜잭션 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) 에 있는 부분 스케줄에 대한 대기 그래프.

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

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

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

30 타임스탬프 순서 (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 를 성공적으로 기록한 가장 최근의 트랜잭션이다.