תזמון

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

תזמון היא רשימה של פעולות (לרוב כתיבה, קראיה, ביטול והתחייבות) של תנועות שונות, כאשר הסדר בין הפעולות הוא סדר בזמן.

דוגמה לתזמון:

$D = \begin{bmatrix} T1 & T2 & T3 \\ R(X) & & \\ W(X) & & \\ Com. & & \\ & R(Y) & \\ & W(Y) & \\ & Com. & \\ && R(Z) \\ && W(Z) \\ && Abort \end{bmatrix}$

בדוגמה זו, התזמון D מורכב מהתנועות T3, T2, T1. התזמון מתאר אלו פעולות התנועות עושות על בסיס הנתונים כאשר:

R (X)

‎ מסמן קריאה (Read) של אובייקט X.

W (X)

‎ מסמן כתיבה (Write) לאובייקט X.

C o m .

‎ מסמן שהתנועה התחייבה (Commit).

A b o r t

מסמן שהתנועה התבטלה (Abort).

כלומר התזמון מתאר את רצף הפעולות הבא:
T1 קורא וכותבת לאובייקט X, ואז T2 קוראת וכותבת לאובייקט Y, ולבסוף T3 קוראת וכותבת לאובייקט Z ואז מתבטלת. זוהי דוגמה לתזמון סדרתי כי התנועות מתבצעות אחת אחר השנייה. מקובל לסמן תזמון סדרתי זה כך: T1:T2:T3.

[עריכה] סוגים של תזמונים

[עריכה] תזמון סדרתי

תזמון הוא סדרתי אם התנועות בו מתבצעות אחת אחרי השנייה, כמו התזמון D הנראה למעלה.

[עריכה] תזמון שווה-סדרתי

תזמון הוא שווה-סדרתי אם הוא שקול לתזמון סדרתי.

בתזמון E, סדר הפעולות שונה מתזמון D, אך הם שקולים כיוון ששינהם ישאירו את בסיס הנתונים באותו מצב בסוף פעולתם.

$E = \begin{bmatrix} T1 & T2 & T3 \\ R(X) & & \\ & R(Y) & \\ && R(Z) \\ W(X) & & \\ & W(Y) & \\ && W(Z) \\ Com. & Com. & Abort \end{bmatrix}$

[עריכה] תזמון מאפשר התאוששות

תזמון מאפשר התאוששות אם תנועותיו מתחייבות רק לאחר שכל התנועות שאת השינויים שהם קראו התחייבו.

$F = \begin{bmatrix} T1 & T2 \\ R(A) & \\ W(A) & \\ & R(A) \\ & W(A) \\ Com. & \\ & Com.\\ &\end{bmatrix} F2 = \begin{bmatrix} T1 & T2 \\ R(A) & \\ W(A) & \\ & R(A) \\ & W(A) \\ Abort & \\ & Abort \\ &\end{bmatrix}$

שני התזמונים מאפשרים התאוששות.F מאפשר התאוששות כיוון ש-T1 מתחייבת לפני T2, מה שהופך את הקריאה של T2 נכונה. ורק אז T2 מתחייבת. ב-F2, אם T1 מתבטלת, אז T2 חייבת להתבטל גם כיוון שהקריאה של A לא נכונה. בשני המקרים משאירים את בסיס התונים במצב עקבי.

[עריכה] תזמון לא מאפשר התאוששות

אם תנועה T1 מתבטלת, ותנועה T2 מתחייבת, אך T2 סמכה על T1 אז מדובר בתזמון שלא מאפשר התאוששות.

$G = \begin{bmatrix} T1 & T2 \\ R(A) & \\ W(A) & \\ & R(A) \\ & W(A) \\ & Com. \\ Abort & \\ &\end{bmatrix}$

[עריכה] תזמון המונע גלגול לאחור בשרשרת

תזמון שבו אם תנועה מתבטלת לא צריך לבטל תנועות אחרות הוא תזמון המונע גלגול לאחור בשרשרת. תזמונים מסוג זה הם תמיד ניתנים להתאוששות.

בדוגמה לעיל, למרות שF2 הוא תזמון מאפשר התאוששות הוא לא מונע גלגול לאחור בשרשרת.

לעומת זאת, F3 הוא תזמון המונע גלגול לאחור בשרשרת.

$F3 = \begin{bmatrix} T1 & T2 \\ & R(A) \\ R(A) & \\ W(A) & \\ & W(A) \\ Abort & \\ & Commit \\ &\end{bmatrix}$

[עריכה] שווה-סדרתיות בקונפליקט

[עריכה] קונפליקטים

שני פעולות או יותר נמצאות בקונפליקט אם:

הפעולות שייכות לתנועות שונות
לפחות אחת מהפעולות היא פעולת כתיבה
הפעולות ניגשות לאותו אובייקט

לדוגמה: בסדרת הפעולת הבאה יש קונפליקט:

T1:R(X), T2:W(X), T1:W(X)

ובאלה אין:

T1:R(X), T2:R(X), T3:R(X)
T1:R(X), T2:W(Y), T3:R(X)

[עריכה] שקילות בקונפליקט

שני תזמונים נקראים שקולים בקונפליקט אם מתקיימים התנאים הבאים:

בשני התזמונים יש את אותן תנועות.
הסדר של כל הזוגות של פעולות שבקופליקט זהה.

[עריכה] תזמון שווה סדרתי בקונפליקט

תזמון נקרא שווה סדרתי בקונפליקט אם הוא שקול בקונפליקט לתזמון סדרתי.

$G = \begin{bmatrix} T1 & T2 \\ R(A) & \\ & R(A) \\ W(B) & \\ Com. & \\ & W(A) \\ & Com. \\ &\end{bmatrix}$

התזמון G שווה סדרתי בקונפליקט, כיוון שהוא שקול בקונפליקט לT1:T2

[עריכה] שווה-סדרתיות במבט

[עריכה] שקילות במבט

שני תזמונים S1 ו-S2 נקראים שקולים במבט אם התנאים הבאים מתקיימים:

אם התנועה $T i$ ב-S1 קוראת לראשונה את אובייקט X, אז גם $T i$ ב-S2 תעשה זאת.
אם התנועה $T i$ ב-S1 קוראת את הערך באובייקט X שנכתב על ידי התנועה $T j$ , אז גם $T i$ ב-S2 תעשה זאת.
אם התנועה $T i$ ב-S1 כותבת אחרונה לאובייקט X, אז גם $T i$ ב-S2 תעשה זאת.

[עריכה] תזמון שווה סדרתי במבט

תזמון נקרא שווה סדרתי במבט אם הוא שקול במבט לתזמון סדרתי.

שימו לב שלפי הגדרה, כל תזמון שווה סדרתי בקונפליקט הוא שווה סדרתי במבט.

התזמון G בדוגמה הקודמת הוא הוא שווה סדרתי במבט וגם שווה סדרתי בקונפליקט. אך קיימים תזמונים שווה סדרתיים במבט שאינם שווה סדרתיים בקונפליקט, בתזמונים אלה יש תנועות המבצעות כתיבה עיוורת (כתיבה לאובייקט בלי לקרוא אותו קודם).

$H = \begin{bmatrix} T1 & T2 & T3 \\ R(A) & & \\ & W(A) & \\ & Com. & \\ W(A) & & \\ Com. & & \\ & & W(A) \\ & & Com. \\ & & \end{bmatrix}$