toc

תוכן עניינים - מערכות הפעלה

פרק 1: מהי מערכת ההפעלה

• 1.1 מערכת ההפעלה כמכונה מדומה או כמכונה מורחבת - 13
• 1.2 מערכת ההפעלה כמנהל משאבי המערכת - 13
• 1.3 היסטוריה של מערכות הפעלה - 14
• 1.4 סקירה של חומרה - 14
• 1.5 גן החיות של מערכות הפעלה - 14
• 1.6 מושגים בסיסיים - 16
• 1.7 קריאות מערכת - 17
• 1.8 המבנה של מערכות הפעלה - 19
• 1.9 רשימת מושגים - 22
• 1.10 סיכום - 22
• 1.11 שאלות לחזרה - 22
• 1.12 רשימת מושגים - 23

פרק 2: תהליכים

• 2.1 חזרה על מבנה המעבד - 30

• 2.2 מבוא לתהליכים - 35

  • 2.2.1 מודל לתהליכים - 35
  • 2.2.2 יצירת תהליכים - 36
  • 2.2.3 סיום תהליכים - 36
  • 2.2.4 היררכיה של תהליכים - 37
  • 2.2.5 מכונת מצבים - 37
  • 2.2.6 יישום תהליכים - 41
  • 2.2.7 מודל לריבוי תכניות - 41

• 2.3 תהליכונים - 43

  • 2.3.1 שימוש בתהליכונים - 43
  • 2.3.2 מודל של תהליכונים - 44
  • 2.3.3 תהליכוני POSIX - 47
  • 2.3.4 מימוש תהליכונים במרחב משתמש - 47
  • 2.3.5 מימוש תהליכונים בגרעין המערכת - 48
  • 2.3.6 גישות מעורבות - 49
  • 2.3.7 הפעלת מתזמן - 49
  • 2.3.8 תהליכונים “קופצים” - 50
  • 2.3.9 אלתורים: ריבוי חוטי ביצוע מקוד שנועד לחוט ביצוע אחד - 51

• 2.4 תקשורת בין תהליכים - 52

  • 2.4.1 מירוץ קריטי - 53
  • 2.4.2 קטעים קריטיים (Critical Sections) - 55
  • 2.4.3 מניעה הדדית הכוללת המתנה פעילה - 55
    • מניעת הפסיקות - 55
    • משתני נעילה – Lock variables - 56
    • פתרון התור - 57
    • הפתרונות של דקר ושל פטרסון - 58
    • TSL - 60
  • 2.4.4 הרדמה והערה - 62
    • בעיית היצרן-צרכן - 63
  • 2.4.5 סמפורים - 64
    • פתרון של בעיית יצרן-צרכן באמצעות הסמפורים - 65
  • 2.4.6 מנעולים - 66
    • מנעולים בתהליכוני POSIX - 67
  • 2.4.7 מבני פיקוח - Monitors - 67
  • 2.4.8 העברת הודעות (Message Passing) - 70
    • מאפיינים של מנגנון העברת ההודעות - 71
    • פתרון בעיית יצרן-צרכן באמצעות העברת הודעות - 72
  • 2.4.9 מחסומים (Barriers) - 73

• 2.5 תזמון תהליכים - 74

  • 2.5.1 מבוא לתזמון תהליכים - 74
  • 2.5.2 תזמון במערכות אצווה - 77
    • FCFS – First-Come First-Served - 77
    • Shortest Job First - 77
    • Shortest Remaining Time Next - 78
    • תזמון בשלוש רמות (תת סעיף זה איננו מופיע בספר הלימוד) - 78
  • 2.5.3 תזמון במערכות אינטראקטיביות - 80
    • אלגוריתם RR – Round-Robin - 80
    • תזמון עם עדיפויות (קדימויות) - 81
    • ריבוי תורים - 82
    • Shortest Process Next - 82
    • תזמון מובטח - 84
    • Lottery scheduling - 84
    • Fair-Share Scheduling - 85
  • 2.5.4 תזמון במערכות זמן אמת - 85
  • 2.5.5 מדיניות (Policy) ומנגנונים (Mechanisms) - 86
  • 2.5.6 תזמון תהליכונים - 87

• 2.6 בעיות IPC קלאסיות - 88

  • 2.6.1 בעיית הפילוסופים הסועדים - 88
  • 2.6.2 בעיית הקוראים-כותבים - 90

• 2.7 סיכום - 93

• 2.8 בעיות פתורות - 94

• 2.9 שאלות לחזרה - 103

• 2.10 תרגילי תכנות לתרגול עצמי - 103

• 2.11 רשימת מושגים - 104

פרק 3: זיכרון

• 3.1 ניהול זיכרון ישיר - 113

  • 3.1.1 ניידות תוכניות במרחב זיכרון - 115
  • 3.1.2 החלפה בזיכרון - 117
  • 3.1.3 ניהול זיכרון פנוי - 118

• 3.2 זיכרון מדומה - 123

  • 3.2.1 דפדוף (Paging) - 123
  • 3.2.2 טבלת הדפים (Page Table) - 124
    • המבנה של שורה בטבלת דפים - 126
  • 3.2.3 כיצד להגביר מהירות פענוח כתובות - 127
    • TLB – Translation Lookaside Buffers - 127
  • 3.2.4 טבלת דפים למרחבי זיכרון גדולים - 134
    • טבלת דפים שכבתית (Multilevel Page Tables) - 134
    • טבלת דפים מהופכת (Inverted Page Tables) - 135

• 3.3 אלגוריתמים להחלפת דפים - 137

  • 3.3.1 אלגוריתם אופטימלי להחלפת הדפים - 138
  • 3.3.2 אלגוריתם NRU – Not Recently Used - 138
  • 3.3.3 תור: FIFO - 139
  • 3.3.4 ההזדמנות השנייה (second chance) - 139
  • 3.3.5 אלגוריתם השעון (clock page replacement) - 140
  • 3.3.6 אלגוריתם LRU – Least Recently Used - 141
  • 3.3.7 סימולציה של LRU בתוכנה - 142
  • 3.3.8 אלגוריתם המסתמך על קבוצת עבודה של תהליך - 143
  • 3.3.9 אלגוריתם WSClock - 145
  • 3.3.10 רשימה של האלגוריתמים להחלפת דפים - 146

• 3.4 שיקולים בתכנון של מערכות דפדוף בזיכרון - 148

  • 3.4.1 מדיניות החלפה מקומית לעומת מדיניות החלפה גלובאלית - 148
    • מדיניות לוקאלית (local page replacement policy) - 148
    • מדיניות גלובאלית (global page replacement policy) - 149
    • ניהול כמות הקצאת המסגרות אלגוריתם PFF (Page Fault Frequency) - 149
  • 3.4.2 קביעת רמת ריבוי של מקביליות - 150
  • 3.4.3 שיקולים לקביעת גודלו של דף - 151
    • שיקולים בעד דפים קטנים - 151
    • שיקולים בעד דפים גדולים - 152
  • 3.4.4 מרחבי כתובות נפרדים להוראות ול-data - 152
  • 3.4.5 דפים לשימוש משותף - 153
  • 3.4.6 ספריות לשימוש משותף - 153
  • 3.4.7 מיפוי קבצים לזיכרון - 153
  • 3.4.8 שדים מדפדפים ו-cleaning policy - 154
  • 3.4.9 ממשק מתכנת מול זיכרון וירטואלי - 155

• 3.5 שיקולי יישום - 156

  • 3.5.1 מעורבותה של מערכת ההפעלה בתהליך הדפדוף - 156
  • 3.5.2 סיכום דרך הטיפול בשגיאות דף - 157
  • 3.5.3 שחזור הוראות מכונה לאחר פסיקת דף - 158
  • 3.5.4 נעילת דפים בזיכרון - 159
  • 3.5.5 אחסון בדיסק - 159
    • שיטת swapping area הבסיסית - 159
    • השיטה הדינאמית - 160
  • 3.5.6 הפרדה בין מדיניות למנגנונים - 160

• 3.6 חלוקת הזיכרון לקטעים - 161

  • 3.6.1 יישום חלוקת הזיכרון לקטעים - 162
    • השיטה המעורבת: חלוקה לקטעים עם דפדוף - 163

• 3.7 סיכום - 164

• 3.8 בעיות פתורות - 165

• 3.9 שאלות לחזרה - 168

• 3.10 תרגילי תכנות לתרגול עצמי - 168

• 3.11 רשימת מושגים - 169

פרק 4: קבצים

• 4.1 שמות לקבצים - 188

• 4.2 המבנה הפנימי של קובץ - 188

• 4.3 טיפוסי קבצים - 189

• 4.4 גישה לקבצים - 191

• 4.5 מאפיינים של קבצים - 192

• 4.6 פעולות על קבצים - 193

• 4.7 דוגמה לשימוש בקריאות מערכת לעבודה עם מערכת קבצים - 194

• 4.8 מדריכים - 195

  • 4.8.1-4.8.2 ספריות - 195
  • 4.8.3 שמות מסלולים - 195
  • 4.8.4 פעולות על מדריכים - 196

• 4.9 יישום מערכת הקבצים - 197

  • 4.9.1 תסדיר מערכת הקבצים - 197
  • 4.9.2 יישום קבצים - 198
    • הקצאה רצופה - 198
    • רשימה משורשרת - 199
    • רשימה משורשרת הממומשת בעזרת טבלת אינדקס בזיכרון ראשי - 199
    • שיטת ה-I-NODES - 200
  • 4.9.3 יישום מדריכים - 201
  • 4.9.4 שיתוף קבצים בין משתמשים שונים - 203
  • 4.9.5 מערכת קבצים בצורת יומן (log-structured) - 204

• 4.10 ניהול שטח הדיסק - 205

  • מעקב אחר השטח החופשי בדיסק - 205
  • הגבלת השימוש בדיסק - 206

• 4.11 גיבוי מערכת הקבצים - 206

• 4.12 עקביות מערכת הקבצים (Consistency) - 207

• 4.13 ביצועים של מערכת הקבצים - 208

  • זיכרון מטמון – buffer cache - 208
  • הבאת בלוקים מראש - 209
  • צמצום התנועות של זרוע הדיסק על ידי פיזור של נתוני שירות של מערכת קבצים - 209

• 4.14 סיכום - 210

• 4.15 בעיות פתורות - 211

• 4.16 שאלות לחזרה - 214

• 4.17 רשימת מושגים - 215

פרק 5: חומרה של התקני קלט/פלט

• 5.1 התקני קלט/פלט - 222

• 5.2 בקרים - Device Controllers - 222

• 5.3 שיטות מיעון של התקני קלט/פלט - 223

• 5.4 גישה ישירה לזיכרון - 224

• 5.5 חזרה נוספת על פסיקות חומרה - 225

• 5.6 עקרונות למימוש קלט/פלט בתוכנה - 226

  • 5.6.1 מטרות תוכנת הקלט/פלט - 226
  • 5.6.2 קלט/פלט באמצעות המעבד הראשי - 227
  • 5.6.3 קלט/פלט מונחה אירועים - 228
  • 5.6.4 קלט/פלט באמצעות DMA - 228

• 5.7 תוכנת קלט/פלט - חלוקה לשכבות - 229

  • 5.7.1 מנהל הפסיקות - Interrupt Handler - 229
  • 5.7.2 מתאמי התקנים - Device Drivers - 229
  • 5.7.3 תוכנת קלט/פלט המשוחררת מאילוצי חומרה - 230
  • 5.7.4 תוכנת קלט/פלט ברמת תהליכי המשתמשים - 231

• 5.8 דיסקים - 232

  • 5.8.1 חומרת הדיסק - 232
    • דיסקים מגנטיים - 232
    • מערך דיסקים (RAID) - 234
      • RAID level 0 - 234
      • RAID level 1 - 234
      • RAID level 2 - 235
      • RAID level 3 - 236
      • RAID level 4 - 236
      • RAID level 5 - 237
      • RAID level 6 - 237
  • 5.8.3 אלגוריתמים לתזמון זרוע הדיסק - 237

• 5.9 סיכום - 240

• 5.10 בעיות פתורות - 240

• 5.11 שאלות לחזרה - 242

• 5.12 רשימת מושגים - 242

פרק 6: משאבים

• 6.1 משאבים שאינם ניתנים לחילוץ לעומת משאבים שניתנים לחילוץ - 250

• 6.2 הקצאת משאבים - 250

• 6.3 קיפאון - 251

  • 6.3.1 תנאים לקיפאון - 251
  • 6.3.2 מודל לקיפאון - 252

• 6.4 שיטת בת היענה - 254

• 6.5 גילוי קיפאון והיחלצות ממנו - 255

  • 6.5.1 גילוי קיפאון כאשר יש רק משאב יחיד מכל סוג - 255
  • 6.5.2 גילוי קיפאון כאשר המשאבים מחולקים למחלקות - 257
  • 6.5.3 היחלצות מקיפאון - 259
    • החלמה על ידי חילוץ כפוי - 259
    • היחלצות על ידי גלגול לאחור (Rollback) - 260
    • היחלצות על ידי הריגת תהליכים - 260

• 6.6 התחמקות מקיפאון - 261

  • 6.6.1 מסלולים להקצאה בטוחה של משאבים (Resource Trajectories) - 261
  • 6.6.2 מצבים בטוחים לעומת מצבים מסוכנים - 262
  • 6.6.3 אלגוריתם הבנקאים עבור משאב יחיד - 263
  • 6.6.4 אלגוריתם הבנקאים עבור מחלקות של משאבים - 264

• 6.7 מניעת קיפאון - 265

  • 6.7.1 תקיפת תנאי המניעה ההדדית - 265
  • 6.7.2 תקיפת תנאי ההחזקה וההמתנה - 266
  • 6.7.3 חילוץ כפוי - 266
  • 6.7.4 מניעת המתנה מעגלית - 266

• 6.8 נושאים נוספים הקשורים לקיפאון - 268

  • 6.8.1 נעילה בשני מעברים (Two-Phase Locking) - 268
  • 6.8.2-6.8.3 קיפאון שאינו קשור במשאבים מקובלים - 268
  • 6.8.4 הרעבה (Starvation) - 269

• 6.9 סיכום - 270

• 6.10 בעיות פתורות - 271

• 6.11 שאלות לחזרה - 275

• 6.12 רשימת מושגים - 275

נספח: מעט על בטיחות

• 9.1 מנגנוני הגנה - 280
  • 9.1.1 הגנה על ידי קביעת תחומים - Protection Domains - 280
  • 9.1.2 רשימות גישה - ACL - 281
  • 9.1.3 רשימות יכולת - C-lists - 282