תזמון

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

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

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

$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.

[עריכה] הצורך בתזמון

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

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

$D' = \begin{bmatrix} T1 & T2 \\ & R(X) \\ R(X) & \\ W(X) & \\ & W(X) \\ \end{bmatrix}$

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

[עריכה] תזמון סדרתי (בר-סידור)

תזמון הוא סדרתי אם התנועות בו מתבצעות אחת אחרי השנייה, כמו התזמון 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}$

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

מאחר שהבדיקה האם תזמון הוא שווה סדרתי במבט היא NP-שלמה, שווה סדרתיות במבט אין כמעט שימושים מעשיים.

[עריכה] ההירארכיה בין סוגי התזמונים

להלן דיאגרמת ון של ההירארכיה בין סוגי התזמונים:

קטגוריה: מבני נתונים

See also ebooksgratis.com: no banners, no cookies, totally FREE.