1 of 42

עצים בינארים

צביקה ברגר

רקורסיות

צביקה ברגר

מערכות הפעלה

​

תזמונים

צביקה ברגר

בס"ד

2 of 42

CPU Scheduler

בס"ד

  • בוחר מבין התהליכים אשר נמצאים ב- ready queue (במצב ready ובזיכרון) את התהליך אשר יקבל את המעבד
  • אירועים בהם יש טעם להפעיל את ה- CPU scheduler:
    • כאשר תהליך עובר ממצב �running ל- waiting
    • כאשר תהליך עובר ממצב �running ל- ready
    • כאשר תהליך עובר ממצב�waiting ל- ready
    • כאשר תהליך מסיים את פעולתו (terminates)
  • כאשר ה- scheduler פועל רק באירועים מהסוג הראשון והרביעי אנו אומרים שה- scheduling הוא nonpreemptive
    • ברגע שהמעבד הוקצה לתהליך כלשהו, התהליך ירוץ ויחזיק במעבד עד שיסיים או שיעבור למצב waiting

3 of 42

First-Come, First-Served (FCFS) Scheduling

בס"ד

  • הרעיון: הראשון שמגיע הוא הראשון שרץ (את כל הזמן ריצה שלו) ממומש כמו תור FIFO.

4 of 42

Shortest-Job-First (SJF) Scheduling

בס"ד

  • הרעיון: נריץ קודם את התהליך עם זמן הריצה הקטן ביותר.

שני סוגים:

      • Nonpreemptive: ברגע שתהליך משובץ מריצים את כולו.
      • Preemptive: אם מגיע תהליך חדש עם זמן ריצה מהיר יותר נעצור את התהליך הנוכחי ונריץ את התהליך החדש שהגיע.

5 of 42

Shortest-Job-First (SJF) Scheduling

בס"ד

  • הרעיון: נריץ קודם את התהליך עם זמן הריצה הקטן ביותר.
      • Nonpreemptive: ברגע שתהליך משובץ מריצים את כולו.

6 of 42

Shortest-Job-First (SJF) Scheduling

בס"ד

  • הרעיון: נריץ קודם את התהליך עם זמן הריצה הקטן ביותר.
      • Preemptive: אם מגיע תהליך חדש עם זמן ריצה מהיר יותר נעצור את התהליך הנוכחי ונריץ את התהליך החדש שהגיע.

7 of 42

Priority Scheduling

בס"ד

  • הרעיון: לכל תהליך ניתן ערך של קדימות (priority) ונוציא מה-ready queue את התהליך אם העדיפות הגבוהה ביותר (או הנמוכה – תלוי הגדרה).

שני סוגים:

      • Nonpreemptive: ברגע שתהליך משובץ מריצים את כולו.
      • Preemptive: אם מגיע תהליך חדש עם זמן ריצה מהיר יותר נעצור את התהליך הנוכחי ונריץ את התהליך החדש שהגיע.

​

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

8 of 42

Round Robin (RR)

בס"ד

  • הרעיון: נקבע time quantum q ונריץ כל תהליך למשך q זמן (לפי סדר הגעתם לתור).

q = 20

9 of 42

Multilevel Queue

בס"ד

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

10 of 42

סיכום

בס"ד

ראינו מספר שיטות לתזמונים:

    • First-Come, First-Served – התהליך שמגיע ראשון נריץ ראשון.
    • Shortest-Job-First - נריץ את התהליך עם זמן הריצה הקטן ביותר.
      • Nonpreemptive: ברגע שתהליך משובץ מריצים את כולו.
      • Preemptive: אם מגיע תהליך חדש עם זמן ריצה מהיר יותר נעצור את התהליך הנוכחי ונריץ את התהליך החדש שהגיע.
    • Priority Scheduling – לכל תהליך יש ערך של קדימות ונריץ לפי סדר הקדימויות.
      • Nonpreemptive: ברגע שתהליך משובץ מריצים את כולו.
      • Preemptive: אם מגיע תהליך חדש עם זמן ריצה מהיר יותר נעצור את התהליך הנוכחי ונריץ את התהליך החדש שהגיע.
    • Round Robin – ניתן זמן מעבד קבוע לכל תהליך ונריץ אותם לפי סדר הגעתם.
    • Multilevel Queue – מספר שכבות של תור שכל אחד ימומש בסר כרצונו.

11 of 42

LCA

בס"ד

בס"ד

Question 1

12 of 42

מועד א 2022

בס"ד

13 of 42

פתרון

בס"ד

14 of 42

LCA

בס"ד

בס"ד

Question 2

15 of 42

מועד ב 2022

בס"ד

16 of 42

פתרון

בס"ד

17 of 42

LCA

בס"ד

בס"ד

Question 3

18 of 42

מועד א 2021

בס"ד

19 of 42

פתרון

בס"ד

20 of 42

LCA

בס"ד

בס"ד

Question 4

21 of 42

2021 מועד ב

בס"ד

22 of 42

פתרון

בס"ד

23 of 42

LCA

בס"ד

בס"ד

Question 5

24 of 42

2020 מועד א

בס"ד

25 of 42

פתרון

בס"ד

26 of 42

LCA

בס"ד

בס"ד

Question 6

27 of 42

2020 מועד ב

בס"ד

28 of 42

פתרון

בס"ד

29 of 42

LCA

בס"ד

בס"ד

Question 7

30 of 42

2008 מועד א

בס"ד

31 of 42

פתרון

בס"ד

32 of 42

LCA

בס"ד

בס"ד

Question 8

33 of 42

2019 מועד ב

בס"ד

34 of 42

פתרון

בס"ד

35 of 42

LCA

בס"ד

בס"ד

Question 9

36 of 42

2019 מועד ב

בס"ד

37 of 42

פתרון

בס"ד

38 of 42

LCA

בס"ד

בס"ד

Question 10

39 of 42

2018 מועד ב

בס"ד

40 of 42

פתרון

בס"ד

41 of 42

פתרון

בס"ד

42 of 42

LCA

בס"ד

בס"ד

שאלות?