שאלת מבחן במערכות הפעלה - האוניברסיטה הפתוחה 2015

קורס: מערכות הפעלה

אוניברסיטה: האוניברסיטה הפתוחה

שנה: 2015

סמסטר: א

נושאים: תזמון, תזמון CPU, SJF, החלפת הקשר, LJF, הפקעה

רמת קושי: בינוני-קשה

ביל וסטיב החליטו לחבל בקוד הפתוח של מערכות Linux באמצעות הכנסת זמן שהייה גרוע ככל האפשר למערכת. בשאלה זו נעזור להם לתכנן זמן גרוע ככל האפשר. ביל הציע לממש את מדיניות הזימון LJF – Longest Job First. מדיניות זו הפוכה בהתנהגותה ממדיניות SJF שלמדנו. כלומר, הניחו שכל התהליכים מגיעים יחד וזמני הביצוע ידועים מראש, ונריץ את התהליכים לפי זמן הביצוע בסדר יורד, כשכל תהליך רץ מתחילתו ועד סופו. א. האם מדיניות LJF היא הגרועה ביותר מבין כל המדיניות בלי הפקעה, לפי מדד זמן השהיה הממוצע? הוכיחו או תנו דוגמה נגדית. ב. סטיב טוען שקיימות מדיניות עם הפקעה גרועות יותר מ-LJF. האם סטיב צודק? הסבירו. אם כן, תנו דוגמה. ג. נניח שהגיעו למערכת $n$ תהליכים. נסמן את זמני הריצה שלהם ב-$t_i$ ואת זמני השהיה שלהם תחת SJF ב-$S_i$. (שימו לב, זמן השהיה כולל את זמן הריצה). מהו זמן ההשהיה של התהליך ה-$i$ תחת LJF? הניחו שזמני הריצה של כל התהליכים שונים.

רמז: עבור סעיף א', בטאו את זמן השהיה הממוצע כסכום משוקלל והראו שכדי למקסם אותו יש לסדר את זמני הריצה בסדר יורד. עבור סעיף ב', חשבו כיצד הפקעה יכולה לעכב את סיומם של תהליכים קצרים עוד יותר מאשר ב-LJF. עבור סעיף ג', כתבו ביטויים אלגבריים לזמני ההשהיה בשתי המדיניות ומצאו קשר ביניהם.

פתרון: א. כן, מדיניות **LJF (Longest Job First)** היא הגרועה ביותר מבין כל המדיניות ללא **הפקעה** (non-preemptive) לפי מדד **זמן השהיה הממוצע (average turnaround time)**. **הוכחה:** נניח שישנם $n$ תהליכים, $P_1, P_2, \dots, P_n$, עם זמני ריצה $t_1, t_2, \dots, t_n$. כל התהליכים מגיעים בזמן 0. במדיניות ללא הפקעה, סדר הרצת התהליכים הוא תמורה $\pi$ של $\{1, 2, \dots, n\}$. זמן השהיה של התהליך שנמצא במקום ה-$k$ בסדר ההרצה, $P_{\pi(k)}$, הוא זמן סיומו: $W_{\pi(k)} = \sum_{j=1}^{k} t_{\pi(j)}$. סך כל זמני השהיה הוא $\sum_{k=1}^{n} W_{\pi(k)} = \sum_{k=1}^{n} \sum_{j=1}^{k} t_{\pi(j)}$. נשנה את סדר הסכימה. זמן הריצה של התהליך הראשון, $t_{\pi(1)}$, נכלל בזמן השהיה של כל $n$ התהליכים. זמן הריצה של התהליך השני, $t_{\pi(2)}$, נכלל בזמן השהיה של $n-1$ התהליכים (החל מהשני ואילך). באופן כללי, זמן הריצה של התהליך במקום ה-$j$, $t_{\pi(j)}$, נכלל בזמני השהיה של $n-j+1$ תהליכים. לכן, סך זמני השהיה הוא: $S = \sum_{j=1}^{n} (n-j+1) t_{\pi(j)} = n \cdot t_{\pi(1)} + (n-1) \cdot t_{\pi(2)} + \dots + 1 \cdot t_{\pi(n)}$. כדי למקסם את הסכום $S$ (ובכך למקסם את זמן השהיה הממוצע $S/n$), עלינו להתאים את המקדמים הגדולים ביותר לזמני הריצה הגדולים ביותר. המקדמים הם סדרה יורדת: $n > n-1 > \dots > 1$. לכן, עלינו לסדר את זמני הריצה, $t_{\pi(j)}$, גם כן בסדר יורד. מדיניות **LJF** עושה בדיוק את זה: היא מריצה את התהליכים בסדר יורד של זמני הריצה שלהם. כל מדיניות אחרת תבצע "החלפה" כלשהי בסדר זה, אשר לפי אי-שוויון הסדרות, תקטין את הסכום $S$. לפיכך, **LJF** מניבה את זמן השהיה הממוצע הגרוע ביותר האפשרי. $\blacksquare$ ב. כן, סטיב צודק. קיימות מדיניות עם **הפקעה** (preemptive) הגורמות לזמן שהיה ממוצע גרוע יותר מ-**LJF**. הסיבה היא שהפקעה מאפשרת "לעכב" באופן מלאכותי את סיומם של תהליכים קצרים, מעבר למה שמדיניות ללא הפקעה יכולה לעשות. **דוגמה:** נניח שני תהליכים המגיעים בזמן 0: $P_1$ עם זמן ריצה $t_1 = 10$. $P_2$ עם זמן ריצה $t_2 = 1$. * **תחת LJF (ללא הפקעה):** $P_1$ רץ ראשון, ואחריו $P_2$. זמן השהיה של $P_1$ הוא $W_1 = 10$. זמן השהיה של $P_2$ הוא $W_2 = 10 + 1 = 11$. זמן שהיה ממוצע: $\frac{10+11}{2} = 10.5$. * **תחת מדיניות עם הפקעה "זדונית":** 1. נריץ את $P_1$ (התהליך הארוך) במשך $10 - \epsilon$ יחידות זמן, כאשר $\epsilon$ הוא מספר חיובי קטן מאוד. 2. נבצע **החלפת הקשר** (context switch) ונריץ את $P_2$ עד סיומו (יחידת זמן 1). 3. נבצע החלפת הקשר חזרה ל-$P_1$ ונריץ אותו למשך $\epsilon$ הזמן שנותר. זמני הסיום יהיו בקירוב: $W_2 \approx 11$ ו-$W_1=11$. זמן השהיה הממוצע ישאף ל-11, שהוא גרוע יותר מ-10.5. לדוגמה, עבור $\epsilon=0.1$: - $P_1$ רץ מ-0 עד $9.9$. - $P_2$ רץ מ-$9.9$ עד $10.9$. הוא מסיים בזמן $10.9$. לכן, $W_2 = 10.9$. - $P_1$ רץ מ-$10.9$ עד $11$. הוא מסיים בזמן $11$. לכן, $W_1 = 11$. זמן שהיה ממוצע: $\frac{11+10.9}{2} = 10.95$, שהוא גרוע יותר מ-LJF. ג. נסמן את זמני הריצה השונים, המסודרים בסדר עולה: $p_1 < p_2 < \dots < p_n$. כל תהליך $i$ עם זמן ריצה $t_i$ מתאים ל-$p_k$ כלשהו, כלומר $t_i = p_k$. תחת מדיניות **SJF**, התהליכים רצים בסדר $p_1, p_2, \dots, p_n$. זמן השהיה של תהליך $i$ (שזמן ריצתו $t_i=p_k$) הוא סכום זמני הריצה של כל התהליכים שרצו לפניו וזמן הריצה שלו עצמו. לפי הגדרת השאלה, זהו $S_i$: $S_i = \sum_{j=1}^{k} p_j$ תחת מדיניות **LJF**, התהליכים רצים בסדר ההפוך: $p_n, p_{n-1}, \dots, p_1$. התהליכים שרצים לפני תהליך $i$ (שזמן ריצתו $t_i=p_k$) הם כל התהליכים עם זמן ריצה ארוך משלו, כלומר $p_{k+1}, \dots, p_n$. לכן, זמן השהיה של תהליך $i$ תחת LJF, נסמנו $L_i$, הוא: $L_i = \left(\sum_{j=k+1}^{n} p_j\right) + p_k = \sum_{j=k}^{n} p_j$ כעת, נחפש קשר בין $S_i$ ל-$L_i$. נסמן את סך כל זמני הריצה ב-$T = \sum_{j=1}^{n} p_j$. נבחן את הסכום $S_i + L_i$: $S_i + L_i = \left(\sum_{j=1}^{k} p_j\right) + \left(\sum_{j=k}^{n} p_j\right)$ האיבר $p_k$ מופיע בשני הסכומים. לכן: $S_i + L_i = \left(\sum_{j=1}^{n} p_j\right) + p_k$ מאחר ש-$T = \sum_{j=1}^{n} p_j$ ו-$p_k = t_i$, קיבלנו: $S_i + L_i = T + t_i$. מכאן, זמן ההשהיה של התהליך ה-$i$ תחת LJF הוא: $L_i = T + t_i - S_i$

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

ביל הציע לממש את מדיניות הזימון LJF – Longest Job First. מדיניות זו הפוכה בהתנהגותה ממדיניות SJF שלמדנו. כלומר, הניחו שכל התהליכים מגיעים יחד וזמני הביצוע ידועים מראש, ונריץ את התהליכים לפי זמן הביצוע בסדר יורד, כשכל תהליך רץ מתחילתו ועד סופו.

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

n

תהליכים. נסמן את זמני הריצה שלהם ב-

t_{i}

ואת זמני השהיה שלהם תחת SJF ב-

S_{i}

. (שימו לב, זמן השהיה כולל את זמן הריצה). מהו זמן ההשהיה של התהליך ה-

i

תחת LJF? הניחו שזמני הריצה של כל התהליכים שונים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 922015סמסטר א

★★★★★

תזמוןתזמון CPUSJFהחלפת הקשרLJFהפקעה

עבור סעיף א', בטאו את זמן השהיה הממוצע כסכום משוקלל והראו שכדי למקסם אותו יש לסדר את זמני הריצה בסדר יורד. עבור סעיף ב', חשבו כיצד הפקעה יכולה לעכב את סיומם של תהליכים קצרים עוד יותר מאשר ב-LJF. עבור סעיף ג', כתבו ביטויים אלגבריים לזמני ההשהיה בשתי המדיניות ומצאו קשר ביניהם.

א. כן, מדיניות LJF (Longest Job First) היא הגרועה ביותר מבין כל המדיניות ללא הפקעה (non-preemptive) לפי מדד זמן השהיה הממוצע (average turnaround time).
הוכחה:
נניח שישנם

n

תהליכים,

P_{1}, P_{2}, \dots, P_{n}

, עם זמני ריצה

t_{1}, t_{2}, \dots, t_{n}

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

π

של

{1, 2, \dots, n}

.
זמן השהיה של התהליך שנמצא במקום ה-

k

בסדר ההרצה,

P_{π (k)}

, הוא זמן סיומו:

W_{π (k)} = \sum_{j = 1}^{k} t_{π (j)}

.
סך כל זמני השהיה הוא

\sum_{k = 1}^{n} W_{π (k)} = \sum_{k = 1}^{n} \sum_{j = 1}^{k} t_{π (j)}

.
נשנה את סדר הסכימה. זמן הריצה של התהליך הראשון,

t_{π (1)}

, נכלל בזמן השהיה של כל

n

התהליכים. זמן הריצה של התהליך השני,

t_{π (2)}

, נכלל בזמן השהיה של

n - 1

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

j

t_{π (j)}

, נכלל בזמני השהיה של

n - j + 1

תהליכים.
לכן, סך זמני השהיה הוא:

S = \sum_{j = 1}^{n} (n - j + 1) t_{π (j)} = n \cdot t_{π (1)} + (n - 1) \cdot t_{π (2)} + \dots + 1 \cdot t_{π (n)}

.
כדי למקסם את הסכום

S

(ובכך למקסם את זמן השהיה הממוצע

S / n

), עלינו להתאים את המקדמים הגדולים ביותר לזמני הריצה הגדולים ביותר. המקדמים הם סדרה יורדת:

n > n - 1 > \dots > 1

. לכן, עלינו לסדר את זמני הריצה,

t_{π (j)}

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

S

.
לפיכך, LJF מניבה את זמן השהיה הממוצע הגרוע ביותר האפשרי.

■

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

P_{1}

עם זמן ריצה

t_{1} = 10

P_{2}

עם זמן ריצה

t_{2} = 1

תחת LJF (ללא הפקעה):

P_{1}

רץ ראשון, ואחריו

P_{2}

.
זמן השהיה של

P_{1}

הוא

W_{1} = 10

.
זמן השהיה של

P_{2}

הוא

W_{2} = 10 + 1 = 11

.
זמן שהיה ממוצע:

\frac{10 + 11}{2} = 10.5

תחת מדיניות עם הפקעה "זדונית":

1. נריץ את

P_{1}

(התהליך הארוך) במשך

10 - ϵ

יחידות זמן, כאשר

ϵ

הוא מספר חיובי קטן מאוד.
2. נבצע החלפת הקשר (context switch) ונריץ את

P_{2}

עד סיומו (יחידת זמן 1).
3. נבצע החלפת הקשר חזרה ל-

P_{1}

ונריץ אותו למשך

ϵ

הזמן שנותר.
זמני הסיום יהיו בקירוב:

W_{2} \approx 11

ו-

W_{1} = 11

. זמן השהיה הממוצע ישאף ל-11, שהוא גרוע יותר מ-10.5. לדוגמה, עבור

ϵ = 0.1

$P_{1}$ רץ מ-0 עד $9.9$ .
$P_{2}$ רץ מ- $9.9$ עד $10.9$ . הוא מסיים בזמן $10.9$ . לכן, $W_{2} = 10.9$ .
$P_{1}$ רץ מ- $10.9$ עד $11$ . הוא מסיים בזמן $11$ . לכן, $W_{1} = 11$ .

זמן שהיה ממוצע:

\frac{11 + 10.9}{2} = 10.95

, שהוא גרוע יותר מ-LJF.

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

p_{1} < p_{2} < \dots < p_{n}

. כל תהליך

i

עם זמן ריצה

t_{i}

מתאים ל-

p_{k}

כלשהו, כלומר

t_{i} = p_{k}

.
תחת מדיניות SJF, התהליכים רצים בסדר

p_{1}, p_{2}, \dots, p_{n}

. זמן השהיה של תהליך

i

(שזמן ריצתו

t_{i} = p_{k}

) הוא סכום זמני הריצה של כל התהליכים שרצו לפניו וזמן הריצה שלו עצמו. לפי הגדרת השאלה, זהו

S_{i}

S_{i} = \sum_{j = 1}^{k} p_{j}

תחת מדיניות LJF, התהליכים רצים בסדר ההפוך:

p_{n}, p_{n - 1}, \dots, p_{1}

. התהליכים שרצים לפני תהליך

i

(שזמן ריצתו

t_{i} = p_{k}

) הם כל התהליכים עם זמן ריצה ארוך משלו, כלומר

p_{k + 1}, \dots, p_{n}

.
לכן, זמן השהיה של תהליך

i

תחת LJF, נסמנו

L_{i}

, הוא:

L_{i} = (\sum_{j = k + 1}^{n} p_{j}) + p_{k} = \sum_{j = k}^{n} p_{j}

כעת, נחפש קשר בין

S_{i}

ל-

L_{i}

. נסמן את סך כל זמני הריצה ב-

T = \sum_{j = 1}^{n} p_{j}

. נבחן את הסכום

S_{i} + L_{i}

S_{i} + L_{i} = (\sum_{j = 1}^{k} p_{j}) + (\sum_{j = k}^{n} p_{j})

האיבר

p_{k}

מופיע בשני הסכומים. לכן:

S_{i} + L_{i} = (\sum_{j = 1}^{n} p_{j}) + p_{k}

מאחר ש-

T = \sum_{j = 1}^{n} p_{j}

ו-

p_{k} = t_{i}

, קיבלנו:

S_{i} + L_{i} = T + t_{i}

.
מכאן, זמן ההשהיה של התהליך ה-

i

תחת LJF הוא:

L_{i} = T + t_{i} - S_{i}

שאלת מבחן במערכות הפעלה - האוניברסיטה הפתוחה 2015 - תזמון