스케줄(컴퓨터 과학)

데이터베이스와 트랜잭션 처리(트랜잭션 관리) 분야에서 시스템의 스케줄(또는 이력)은 시스템에서 실행되는 트랜잭션의 실행을 기술하는 추상적인 모델이다. 종종 그것은 시간순으로 정렬된 작업(작업) 목록이며, 시스템에서 함께 실행되는 일련의 트랜잭션에 의해 수행된다. 특정 작업 사이의 시간 순서가 시스템에 의해 결정되지 않으면 부분 순서가 사용된다. 그러한 작업의 예로는 읽기 작업, 읽기, 쓰기, 중단, 커밋, 잠금 요청, 잠금 등이 있다. 일정표에 모든 거래 운영 유형이 포함되어야 하는 것은 아니며, 일반적으로 특정 현상에 대한 추론 및 설명에 필요한 선택적 운영 유형(예: 데이터 액세스 운영)만 포함된다. 스케줄과 스케줄 속성은 데이터베이스 동시성 제어 이론의 기본 개념이다.

형식 설명

스케줄의 예는 다음과 같다.

D

T1	T2	T3
R(X)
W(X)
컴
	R(Y)
	W(Y)
	컴
		R(Z)
		W(Z)
		컴

이 예에서 수평축은 스케줄 D에서 서로 다른 트랜잭션을 나타낸다. 수직축은 운영의 시간 순서를 나타낸다. 스케줄 D는 3개의 거래 T1, T2, T3으로 구성된다. 스케줄은 DBMS에서 볼 수 있는 트랜잭션의 동작을 기술한다. 첫 번째 T1 객체 X에 읽기 및 쓰기, 다음 커밋. 그런 다음 T2 Reads and Writs to object Y and Commits, 그리고 마지막으로 T3 Reads and Writs to object Z and Commits to object. 이는 시리얼 스케줄의 예로서, 즉, 세 가지 거래의 동작이 모두 순차적이고, 거래는 시간 내에 인터리빙되지 않기 때문에 시간의 중복이 없는 순차적 스케줄이다.

(목록이 아닌) 표로 위의 스케줄 D를 나타내는 것은 단지 각 거래의 운영을 한 눈에 파악할 수 있는 편의를 위한 것이다. 이 표기법은 아래 기사에 걸쳐 사용된다. 그러한 일정을 나타내기 위한 기술 문헌에서 더 일반적인 방법은 목록이다.

D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3

일반적으로, 데이터베이스의 동시성 통제에 대한 추론을 목적으로, 연산은 지속시간 없이 한 시점에 발생하는 원자성(원자성)으로 모델링된다. 이것이 만족스럽지 않을 경우, 시작 및 종료 시점과 가능한 다른 포인트 이벤트가 지정된다(경고). 실제 실행된 운영에는 항상 일정 기간과 그 안에서 사건이 발생하는 시간(예: "정확한" 시작 및 완료 시간)이 지정되지만 동시성 제어 추론에서는 대개 전체 운영 시간의 우선순위(각 운영의 상당히 복잡한 세부사항을 조사하지 않음) 문제만 발생한다. 어떤 작업이 다른 작업 이전 또는 이후에 이루어지는지 확인하십시오. 더욱이, 많은 경우에, 두 특정 운영 사이의 전후 관계는 다른 운영 쌍에 대해 지정되는 동안 중요하지 않으며 지정되어서는 안 된다.

일반적으로 일정의 거래는 인터리브(즉, 거래는 동시에 실행될 수 있음)할 수 있는 반면, 각 거래의 영업 간 시간 순서는 거래 프로그램의 암시에 따라 변경되지 않는다. 모든 거래의 모든 영업 사이의 시간 순서가 항상 중요하고 명시되어야 하는 것은 아니기 때문에, 스케줄은 일반적으로 전체 순서가 아닌 영업 사이의 부분 순서(영업 리스트에서와 같이 각 쌍의 순서가 결정되는 경우)이다. 또한 일반적인 경우, 각 거래는 몇 개의 프로세스로 구성될 수 있으며, 그 자체가 전체 순서가 아닌 부분적인 운영 순서에 의해 적절하게 표현된다. 따라서 일반적으로 스케줄은 모든 거래의 부분적인 순서를 포함하는 부분적인 운영 순서다.

두 연산 사이의 시간 순서는 이러한 연산 쌍(예: 쌍(OP1, OP2)의 존재는 OP1이 항상 OP2 이전이라는 것을 의미함)으로 나타낼 수 있으며, 일반적인 경우의 스케줄은 그러한 순서 쌍들의 집합이다. 이러한 집합, 일람표는 노드로 작동하고 지시된 에지로 시간 순서가 있는 반복 지시 그래프(또는 지시된 주기 그래프, DAG)로 나타낼 수 있는 부분 순서다(주기는 사이클이 허용되지 않으므로 사이클에서 첫 번째 (임의) 주기가 사이클에서 (임의의) 또 다른 두 번째 작동 전후가 될 수 있다는 것을 의미하기 때문이다).ch는 시간에 대한 우리의 인식과 모순된다. 많은 경우, 그러한 그래프의 그래픽 표현은 일람표를 보여주기 위해 사용된다.

참고: 작업 목록(및 이 문서에서 사용된 표 표기법)은 항상 작업 간의 전체 순서를 나타내기 때문에 전체 순서가 아닌 스케줄은 목록으로 나타낼 수 없지만(그러나 항상 DAG로 나타낼 수 있음)

일정 유형

직렬

트랜잭션은 인터리브되지 않고 실행된다(위의 예 참조). 즉, 연속 예약은 실행 중인 트랜잭션이 종료될 때까지 트랜잭션이 시작되지 않는 예약이다.

직렬화 가능

연속 스케줄과 동일한 스케줄(결과)은 연속성 속성을 갖는다.

스케줄 E에서, 거래의 조치가 실행되는 순서는 D와 같지 않지만, 결국 E는 D와 같은 결과를 준다.

E

T1	T2	T3
R(X)
	R(Y)
		R(Z)
W(X)
	W(Y)
		W(Z)
컴	컴	컴

충돌하는 동작

다음과 같은 경우 두 가지 작용이 충돌한다고 한다(충돌 쌍).

작업은 서로 다른 트랜잭션에 속한다.
적어도 하나의 동작은 쓰기 작업이다.
작업이 동일한 개체에 액세스(읽기 또는 쓰기)

다음과 같은 일련의 동작이 충돌한다.

R1(X), W2(X), W3(X)(3쌍 충돌)

다음 작업 세트가 아닌 경우:

R1(X), R2(X), R3(X)
R1(X), W2(Y), R3(X)

갈등균등성

스케줄 S1과 S2는 다음과 같은 두 가지 조건이 충족되면 충돌과 동일하다고 한다.

공정표 S1과 S2는 모두 동일한 거래 집합(각 거래 내 조치 순서 포함)을 포함한다.
두 스케줄 모두 동일한 일련의 충돌 작업을 가지고 있다.

충돌-시리얼 가능

스케줄은 스케줄이 하나 이상의 시리얼 스케줄과 동일할 때 충돌-시리얼라이제이션 가능하다고 한다.

충돌-시리얼리티에 대한 또 다른 정의는 일정의 우선 순위 그래프/시리얼리티 그래프가, 커밋되지 않은 트랜잭션만 고려될 때, 그 우선 순위 그래프에 순환하는 경우에만(그래프가 커밋되지 않은 트랜잭션을 포함하도록 정의된 경우, 커밋되지 않은 트랜잭션을 포함하는 사이클이 충돌 없이 발생할 수 있음) 일정의 충돌-시리얼라이제이션이 가능하다는 것이다.t 연속성 위반).

G

T1	T2
R(A)
	R(A)
W(B)
컴
	W(A)
	컴

그것은 시리얼 스케줄 <T1,T2>와 상충되지만 <T2,T1>은 아니다.

위임 명령

약속 순서(CO, 커밋 순서 또는 커밋 순서-시리얼라이즈빌리티) 일정 속성을 준수하는 경우 스케줄은 커밋 순서(커밋 순서-시리얼라이저블) 또는 커밋 순서 순서 지정이 가능하다고 한다. 즉, 거래 약속 사건의 시간 순서가 해당 일정의 반복적인 우선 순위 그래프(시리얼리티 그래프, 갈등 그래프)에 의해 유도된 대로, 각 거래의 우선 순위(부분) 순서와 양립할 수 있음을 의미한다. 이것은 그것 또한 분쟁시연성이 있다는 것을 암시한다. CO 속성은 분산 시스템에서 글로벌 연속성을 달성하는 데 특히 효과적이다.

의견: 1990년에 발견된 약속 순서는 분명히 (Vernstein et al. 1987)에 언급되지 않았다. 그것의 정확한 정의는 (Weikum과 Vossen 2001)에 나타나지만, 그것의 관련 기술과 이론에 대한 설명은 부분적이고 부정확하며 오해의 소지가 있다.^{[according to whom?]} 책임 주문 및 출처에 대한 광범위한 내용은 책임 주문 및 책임 주문 기록을 참조하십시오.

동등성 보기

S1과 S2의 두 스케줄은 다음과 같은 조건이 충족될 때 시야와 동일하다고 한다.

S1의 트랜잭션 $T_{i}$ $T_{i}$ ${\$ 가 객체 X의 초기값을 읽는다면, S2의 $T_{i}$ $T_{i}$ $T_{i}$ {\ $displaystyle T_{i}$ 도 마찬가지다.
S1의 트랜잭션 $T_{i}$ $T_{i}$ ${\$ 가 객체 X에 대해 S1의 $T_{j}$ 트랜잭션 $T_{j}$ {\ $displaystyle T_{j}$ 에 의해 쓰여진 값을 읽는다면, $T_{i}$ 의 트랜잭션 $T_{i}$ Ti {\ $displaystyty T_{i}$ 도 $T_{i}$ 마찬가지다.
만약 S1의 $T_{i}$ 거래 $T_{i}$ ${\$ 가 객체 X의 값을 쓰는 최종 거래라면 S2의 거래 $T_{i}$ $T_{i}$ ${\$ 도 마찬가지다.

뷰-시리얼 가능

스케줄이 일부 시리얼 스케줄과 동일한 경우 뷰-시리얼라이제이션이 가능하다고 한다. 정의에 따라 모든 충돌 연속 예약은 보기 연속성이 있다는 점에 유의하십시오.

G

T1	T2
R(A)
	R(A)
W(B)

위의 예(갈등-직렬화 가능성의 논의의 예와 동일)는 동시에 보기-직렬화 및 충돌-직렬화 가능하다는 점에 유의하십시오. 그러나, 충돌 서열이 가능하지 않은 뷰-시리얼 가능한 스케줄이 있다. 즉, 거래가 블라인드 쓰기를 수행하는 스케줄:

H

T1	T2	T3
R(A)
	W(A)
	컴
W(A)
컴
		W(A)
		컴

위의 예는 충돌-시리얼이 가능한 것은 아니지만, 뷰와 동등한 시리얼 스케줄 <T1, T2, T3>을 가지고 있기 때문에 뷰시리얼이 가능하다.

스케줄이 뷰-시리얼라이징 가능한지 여부를 결정하는 것은 NP-완전하므로 뷰-시리얼라이징성은 실질적인 관심이 거의 없다.^{[citation needed]}

회수가능

트랜잭션은 변경사항을 읽고 커밋한 모든 트랜잭션 후에만 커밋됨.

F

T1	T2
R(A)
W(A)
	R(A)
	W(A)
컴
	컴

F2

T1	T2
R(A)
W(A)
	R(A)
	W(A)
중단
	중단

이 일정들은 회복할 수 있다. T1이 T2보다 먼저 커밋하기 때문에 F는 복구할 수 있다. T2가 읽은 값이 정확하다. 그러면 T2는 스스로 커밋할 수 있다. F2에서 T1이 중단되면 T2는 그것이 읽은 A의 값이 잘못되었기 때문에 중단해야 한다. 두 경우 모두 데이터베이스는 일관된 상태로 유지된다.

복구할 수 없음

거래 T1이 중단되고 거래 T2가 커밋되지만 T2가 T1에 의존한다면 우리는 회복 불가능한 일정을 가지고 있다.

G

T1	T2
R(A)
W(A)
	R(A)
	W(A)
	컴
중단

이 예에서, T2는 T1이 작성한 A의 값을 읽고 커밋하기 때문에 G는 복구할 수 없다. 나중에 T1이 중단되었으므로 T2가 읽은 값이 잘못되었지만 T2가 커밋되었기 때문에 이 일정은 복구할 수 없다.

캐스캐드리스

또한 "Cascading Aborts(ACA) 회피". 단일 트랜잭션 중단이 일련의 트랜잭션 롤백으로 이어지는 것을 방지. 계단식 중단을 방지하기 위한 전략은 거래가 동일한 일정에서 다른 거래에서 커밋되지 않은 변경사항을 읽는 것을 허용하지 않는 것이다.

다음은 회수가능에 관한 논의의 예와 같다.

F

T1	T2
R(A)
W(A)
	R(A)
	W(A)
컴
	컴

F2

T1	T2
R(A)
W(A)
	R(A)
	W(A)
중단
	중단

이 예에서는 F2를 복구할 수 있지만 계단식 중단을 피하지는 않는다. T2가 T1에 의해 작성된 미확정 값을 이미 읽었기 때문에 T1이 중단될 경우 일정의 정확성을 유지하기 위해서는 T2도 중단되어야 함을 알 수 있다.

다음은 계단식 중단을 방지하는 복구 가능한 일정이다. 그러나 (T1이 중단되기 때문에) A에 의한 업데이트는 항상 손실된다는 점에 유의하십시오.

F3

T1	T2
	R(A)
R(A)
W(A)
	W(A)
중단
	커밋

T1이 커밋되면 본 부칙은 일련화할 수 없다는 점에 유의하십시오. 계단식 중단은 회피하는 것으로 충분하지만 일정을 복구하기 위해 필요한 것은 아니다.

엄격한

스케줄이 엄격함 - 엄격함 속성이 있음 - T1, T2 두 트랜잭션에 대해 T1의 쓰기 작업이 T2의 충돌 작업(읽기 또는 쓰기)을 선행하는 경우, T1의 커밋 또는 중단 이벤트도 T2의 충돌 작업보다 선행한다.

어떤 엄격한 스케줄도 폭포수가 없지만, 반대는 아니다. 엄격성 덕분에 오류로부터 데이터베이스를 효율적으로 복구할 수 있다.

연속성 클래스 간의 계층적 관계

다음 표현식은 연속성과 복구성 클래스 간의 계층적(연결) 관계를 예시한다.

시리얼 ⊂ 약속-오더된 ⊂ 충돌-시리얼 가능 ⊂ 뷰-시리얼 가능 ⊂ 모든 스케줄
직렬 ⊂ 엄격한 ACA(Cascadless) ⊂ 복구 가능한 ⊂ 모든 일정 ⊂

벤 도표(아래)는 위의 절들을 그래픽으로 보여준다.

직렬화 및 복구 성능 클래스에 대한 벤 다이어그램

실제 구현

실제로, 대부분의 범용 데이터베이스 시스템은 충돌-직렬화 및 복구 가능(주로 엄격한) 일정을 채택한다.

참고 항목

일정(프로젝트 관리)

참조

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems, Addison Wesley Publishing Company, 1987, ISBN 0-201-10715-5
Gerhard Weikum, Gottfried Vossen: Transactional Information Systems, Elsevier, 2001, ISBN 1-55860-508-8

Search