Αρχική ΑΕΠΠ - Δομές Δεδομένων Λειτουργικά Συστήματα Δίκτυα Υπολογιστών ΙΙ Βάσεις Δεδομένων Παιδαγωγικά - Διδακτική

Εισαγωγικά

Εισαγωγή στα Λ.Σ. Βασικές Δομές Η/Υ Βασικές Δομές Λ.Σ

Διεργασίες

Διεργασίες Χρονοπρογραμματισμός Συγχρονισμός

Αδιέξοδα

Μνήμη

Μονοπρογραμματισμός Εναλλαγή Εικονική Μνήμη Κατάτμηση

Είσοδος / Έξοδος

Σύστημα Αρχείων

Διεπαφή Υλοποίηση

 Ιστορικό Πρόσφατες αλλαγές Εκτύπωση Αναζήτηση

Ιστορικό: OS.Swapping

Απόκρυψη μικρών αλλαγών - Αλλαγές κώδικα

06-08-2008 (18:26) από Άρης -
Πρόσθεση σειρών 164-166:
06-08-2008 (12:57) από 194.63.237.23 -
Αλλαγή σειράς 105 από:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8K, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 107 από:
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 0K, 4Κ, 8K, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειρών 109-110 από:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 0K, 4Κ, 8K, 9K, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 113 από:
Τοποθετείται στο κενό 12Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 12Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 0K, 15Κ
Αλλαγή σειράς 115 από:
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 0Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 0K, 15Κ
Αλλαγή σειρών 117-118 από:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, , 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 9Κ. Νέα λίστα: 0, 4Κ, 20Κ, 18Κ, 7Κ, 0Κ, 0K, 15Κ
Αλλαγή σειράς 121 από:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 123 από:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8K, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειρών 125-126 από:
Τοποθετείται στο κενό 15Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 15Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 9Κ, 12Κ, 6Κ
Αλλαγή σειράς 129 από:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 131 από:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειρών 133-134 από:
Τοποθετείται στο κενό 9Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, , 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 9Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 0Κ, 12Κ, 15Κ
Διαγραφή σειρών 142-153:

Ερώτηση

Δεδομένων των παρακάτω κενών μνήμης (διαμερισμάτων) 100K, 500K, 200K, 300K, και 600K (με αυτή τη σειρά), πως θα τοποθετήσει καθένας από τους αλγόριθμους πρώτης τοποθέτησης, καλύτερης τοποθέτησης και χειρότερης τοποθέτησης τις παρακάτω αιτήσεις;

  1. 212K,
  2. 417K,
  3. 112K,
  4. 426K

Ποιος αλγόριθμος, στη συγκεκριμένη άσκηση, κάνει πιο αποδοτική διαχείριση μνήμης;

Αλλαγή σειρών 148-154 από:
  • 212K τοποθετούνται στο διαμέρισμα των 500K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 500-212 = 388K
  • 417K τοποθετούνται στο διαμέρισμα των 600K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 600-417 = 183K
  • 112K τοποθετούνται στο διαμέρισμα των 200Κ. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 200-112 = 88K
  • 426Κ. Η αίτηση περιμένει γιατί δεν υπάρχει διαμέρισμα που να μπορεί να την ικανοποιήσει.
Συνολικός κατακερματισμός: 659Κ
Διεργασίες σε αναμονή: 1
σε:
  • 100 λέξεις τοποθετούνται στο τμήμα των 300 λέξεων. Νέα λίστα: 200, 800
  • 500 λέξεις τοποθετούνται στο τμήμα των 800 λέξεων. Νέα λίστα: 200, 300
  • 200 λέξεις τοποθετούνται στο τμήμα των 200 λέξεων. Νέα λίστα: 0, 300
  • 300 λέξεις τοποθετούνται στο τμήμα των 300 λέξεων. Νέα λίστα: 0, 0
Αλλαγή σειρών 154-160 από:
  • 212K τοποθετούνται στο διαμέρισμα των 300K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 300-212 = 88K
  • 417K τοποθετούνται στο διαμέρισμα των 500K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 500-417 = 83K
  • 112K τοποθετούνται στο διαμέρισμα των 200Κ. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 200-112 = 88K
  • 426Κ τοποθετούνται στο διαμέρισμα των 600Κ. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 600-426 = 174K
Συνολικός κατακερματισμός: 433Κ
Διεργασίες σε αναμονή: 0
σε:
  • 100 λέξεις τοποθετούνται στο τμήμα των 300 λέξεων. Νέα λίστα: 200, 800
  • 500 λέξεις τοποθετούνται στο τμήμα των 800 λέξεων. Νέα λίστα: 200, 300
  • 200 λέξεις τοποθετούνται στο τμήμα των 200 λέξεων. Νέα λίστα: 0, 300
  • 300 λέξεις τοποθετούνται στο τμήμα των 300 λέξεων. Νέα λίστα: 0, 0
Αλλαγή σειρών 160-170 από:
  • 212K τοποθετούνται στο διαμέρισμα των 600K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 600-300 = 300K
  • 417K τοποθετούνται στο διαμέρισμα των 500K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 500-417 = 83K
  • 112K τοποθετούνται στο διαμέρισμα των 300K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 300-112 = 188K
  • 426K. Η αίτηση περιμένει γιατί δεν υπάρχει διαμέρισμα που να μπορεί να την ικανοποιήσει.
Συνολικός κατακερματισμός: 571Κ
Διεργασίες σε αναμονή: 1

Καλύτερη διαχείριση έχει κάνει ο αλγόριθμος καλύτερης τοποθέτησης που δημιούργησε τον μικρότερο κατακερματισμό και δεν άφησε αίτηση χωρίς εξυπηρέτηση.

σε:
  • 100 λέξεις τοποθετούνται στο τμήμα των 800 λέξεων. Νέα λίστα: 300, 700
  • 500 λέξεις τοποθετούνται στο τμήμα των 700 λέξεων. Νέα λίστα: 300, 200
  • 200 λέξεις τοποθετούνται στο τμήμα των 300 λέξεων. Νέα λίστα: 100, 200
  • 300 λέξεις. Η αίτηση δεν μπορεί να εξυπηρετηθεί γιατί δεν υπάρχει αρκετά μεγάλο τμήμα στη μνήμη γι' αυτήν.
Αλλαγή σειρών 168-169 από:

Σε έναν υπολογιστή υπάρχουν σε εξωτερικό κατακερματισμό κενά που δημιουργούν συνολική μνήμη 1GB. Αν ο ρυθμός μεταφοράς της μνήμης είναι 256ΜB/sec πόση ώρα θα χρειαστεί για να την συνενώσει;

σε:

Δεδομένων των παρακάτω κενών μνήμης (διαμερισμάτων) 100K, 500K, 200K, 300K, και 600K (με αυτή τη σειρά), πως θα τοποθετήσει καθένας από τους αλγόριθμους πρώτης τοποθέτησης, καλύτερης τοποθέτησης και χειρότερης τοποθέτησης τις παρακάτω αιτήσεις;

  1. 212K,
  2. 417K,
  3. 112K,
  4. 426K

Ποιος αλγόριθμος, στη συγκεκριμένη άσκηση, κάνει πιο αποδοτική διαχείριση μνήμης;

Αλλαγή σειρών 180-181 από:

Ο συνολικός χρόνος είναι: x*256MB/sec=1024MB => x=4sec

σε:
  • Πρώτη Τοποθέτηση
    • 212K τοποθετούνται στο διαμέρισμα των 500K. Νέα λίστα: 100K, 288K, 200K, 300K, 600K
    • 417K τοποθετούνται στο διαμέρισμα των 600K. Νέα λίστα: 100K, 288K, 200K, 300K, 183K
    • 112K τοποθετούνται στο διαμέρισμα των 200Κ. Νέα λίστα: 100K, 288K, 88K, 300K, 183K
    • 426Κ. Η αίτηση περιμένει γιατί δεν υπάρχει διαμέρισμα που να μπορεί να την ικανοποιήσει.
  • Καλύτερη Τοποθέτηση
    • 212K τοποθετούνται στο διαμέρισμα των 300K. Νέα λίστα: 100K, 500K, 200K, 88K, 600K
    • 417K τοποθετούνται στο διαμέρισμα των 500K. Νέα λίστα: 100K, 83K, 200K, 88K, 600K
    • 112K τοποθετούνται στο διαμέρισμα των 200Κ. Νέα λίστα: 100K, 83K, 88K, 88K, 600K
    • 426Κ τοποθετούνται στο διαμέρισμα των 600Κ. Νέα λίστα: 100K, 83K, 88K, 88K, 174K
  • Χειρότερη Τοποθέτηση
    • 212K τοποθετούνται στο διαμέρισμα των 600K. Νέα λίστα: 100K, 500K, 200K, 300K, 188K
    • 417K τοποθετούνται στο διαμέρισμα των 500K. Νέα λίστα: 100K, 83K, 200K, 300K, 188K
    • 112K τοποθετούνται στο διαμέρισμα των 300K. Νέα λίστα: 100K, 83K, 200K, 88K, 188K
    • 426K. Η αίτηση περιμένει γιατί δεν υπάρχει διαμέρισμα που να μπορεί να την ικανοποιήσει.

Καλύτερη διαχείριση έχει κάνει ο αλγόριθμος καλύτερης τοποθέτησης ο οποίος δεν άφησε αίτηση χωρίς εξυπηρέτηση.

Αλλαγή σειρών 206-207 από:

Υποθέστε ότι ένας υπολογιστής με 1GB μνήμης για τους χρήστες εκτελεί τη διαδικασία της συνένωσης μια φορά κάθε δευτερόλεπτο. Αν χρειάζεται 1μsec για να αντιγράψει ένα byte και ένα μέσο κενό έχει μέγεθος ίσο με το 0.4 του μέσου τμήματος, ποιο ποσοστό του χρόνου της CPU θα καταναλώνεται για την συνένωση;

σε:

Σε έναν υπολογιστή υπάρχουν σε εξωτερικό κατακερματισμό κενά που δημιουργούν συνολική μνήμη 1GB. Αν ο ρυθμός μεταφοράς της μνήμης είναι 256ΜB/sec πόση ώρα θα χρειαστεί για να την συνενώσει;

Αλλαγή σειρών 212-217 από:

Αφού το μέσο κενό έχει μέγεθος ίσο με το 0.4 του μέσου τμήματος, το 40% της μνήμης είναι κενό, δηλαδή τα 0.4GB.

H ταχύτητα μεταφοράς από και προς τη μνήμη είναι 1Byte/10-6sec.

Ο συνολικός χρόνος είναι: x*1Byte/10-6sec = 0.4*220Byte => x = 1048576 * 10-6sec => x = 1,05sec

σε:

Ο συνολικός χρόνος είναι: x*256MB/sec=1024MB => x=4sec

Πρόσθεση σειρών 217-234:

Ερώτηση

Υποθέστε ότι ένας υπολογιστής με 1GB μνήμης για τους χρήστες εκτελεί τη διαδικασία της συνένωσης μια φορά κάθε δευτερόλεπτο. Αν χρειάζεται 1μsec για να αντιγράψει ένα byte και ένα μέσο κενό έχει μέγεθος ίσο με το 0.4 του μέσου τμήματος, ποιο ποσοστό του χρόνου της CPU θα καταναλώνεται για την συνένωση;

Απάντηση

Αφού το μέσο κενό έχει μέγεθος ίσο με το 0.4 του μέσου τμήματος, το 40% της μνήμης είναι κενό, δηλαδή τα 0.4GB.

H ταχύτητα μεταφοράς από και προς τη μνήμη είναι 1Byte/10-6sec.

Ο συνολικός χρόνος είναι: x*1Byte/10-6sec = 0.4*220Byte => x = 1048576 * 10-6sec => x = 1,05sec


25-07-2008 (08:34) από 194.63.237.23 -
Αλλαγή σειρών 139-140 από:

Question

σε:

Ερώτηση

Η λίστα ελευθέρων τμημάτων του συστήματος διαχείρισης μνήμης περιέχει αρχικά δύο τμήματα μεγέθους 300 και 800 λέξεων αντίστοιχα. Στη συνέχεια γίνονται κατά σειρά αιτήσεις για τμήματα μνήμης με μεγέθη 100, 500, 200 και 300 λέξεων. Πως εξυπηρετούνται οι αιτήσεις αυτές με τους αλγόριθμους πρώτης, καλύτερης και χειρότερης τοποθέτησης;


Ερώτηση

Αλλαγή σειρών 157-158 από:

Answer

σε:

Απάντηση

24-07-2008 (20:12) από Άρης -
Αλλαγή σειρών 181-213 από:

σε:

Ερώτηση

Σε έναν υπολογιστή υπάρχουν σε εξωτερικό κατακερματισμό κενά που δημιουργούν συνολική μνήμη 1GB. Αν ο ρυθμός μεταφοράς της μνήμης είναι 256ΜB/sec πόση ώρα θα χρειαστεί για να την συνενώσει;

Απάντηση

Ο συνολικός χρόνος είναι: x*256MB/sec=1024MB => x=4sec


Ερώτηση

Υποθέστε ότι ένας υπολογιστής με 1GB μνήμης για τους χρήστες εκτελεί τη διαδικασία της συνένωσης μια φορά κάθε δευτερόλεπτο. Αν χρειάζεται 1μsec για να αντιγράψει ένα byte και ένα μέσο κενό έχει μέγεθος ίσο με το 0.4 του μέσου τμήματος, ποιο ποσοστό του χρόνου της CPU θα καταναλώνεται για την συνένωση;

Απάντηση

Αφού το μέσο κενό έχει μέγεθος ίσο με το 0.4 του μέσου τμήματος, το 40% της μνήμης είναι κενό, δηλαδή τα 0.4GB.

H ταχύτητα μεταφοράς από και προς τη μνήμη είναι 1Byte/10-6sec.

Ο συνολικός χρόνος είναι: x*1Byte/10-6sec = 0.4*220Byte => x = 1048576 * 10-6sec => x = 1,05sec


24-07-2008 (19:16) από Άρης -
Αλλαγή σειρών 158-160 από:

Συνολικός κατακερματισμός: 659Κ Διεργασίες σε αναμονή: 1

σε:
Συνολικός κατακερματισμός: 659Κ
Διεργασίες σε αναμονή: 1
Αλλαγή σειρών 166-168 από:

Συνολικός κατακερματισμός: 433Κ Διεργασίες σε αναμονή: 0

σε:
Συνολικός κατακερματισμός: 433Κ
Διεργασίες σε αναμονή: 0
Αλλαγή σειρών 174-176 από:

Συνολικός κατακερματισμός: 571Κ Διεργασίες σε αναμονή: 1

σε:
Συνολικός κατακερματισμός: 571Κ
Διεργασίες σε αναμονή: 1
24-07-2008 (19:14) από Άρης -
Αλλαγή σειράς 105 από:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 107 από:
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειρών 109-110 από:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 113 από:
Τοποθετείται στο κενό 12Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 0Κ, 15Κ
σε:
Τοποθετείται στο κενό 12Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 115 από:
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 0Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 0Κ, 15Κ
σε:
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειρών 117-118 από:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 0Κ, 4Κ, 20Κ, 18Κ, 7Κ, 0Κ, 0Κ, 15Κ
σε:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, , 12Κ, 15Κ
Αλλαγή σειράς 121 από:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 123 από:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειρών 125-126 από:
Τοποθετείται στο κενό 15Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 9Κ, 12Κ, 6Κ
σε:
Τοποθετείται στο κενό 15Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 129 από:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 131 από:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειρών 133-134 από:
Τοποθετείται στο κενό 9Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 0Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 9Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, , 12Κ, 15Κ
Αλλαγή σειρών 141-142 από:

Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in order), how would each of the First-fit, Best-fit, and Worst-fit algorithms place processes of 212K, 417K, 112K, and 426K (in order)? Which algorithm makes the most efficient use of memory?

σε:

Δεδομένων των παρακάτω κενών μνήμης (διαμερισμάτων) 100K, 500K, 200K, 300K, και 600K (με αυτή τη σειρά), πως θα τοποθετήσει καθένας από τους αλγόριθμους πρώτης τοποθέτησης, καλύτερης τοποθέτησης και χειρότερης τοποθέτησης τις παρακάτω αιτήσεις;

  1. 212K,
  2. 417K,
  3. 112K,
  4. 426K

Ποιος αλγόριθμος, στη συγκεκριμένη άσκηση, κάνει πιο αποδοτική διαχείριση μνήμης;

Αλλαγή σειρών 153-157 από:
  • First-fit
    • 212K is put in 500K partition. New list:
    • 417K is put in 600K partition
σε:
  • Πρώτη Τοποθέτηση
    • 212K τοποθετούνται στο διαμέρισμα των 500K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 500-212 = 388K
    • 417K τοποθετούνται στο διαμέρισμα των 600K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 600-417 = 183K
    • 112K τοποθετούνται στο διαμέρισμα των 200Κ. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 200-112 = 88K
    • 426Κ. Η αίτηση περιμένει γιατί δεν υπάρχει διαμέρισμα που να μπορεί να την ικανοποιήσει.

Συνολικός κατακερματισμός: 659Κ Διεργασίες σε αναμονή: 1

  • Καλύτερη Τοποθέτηση
    • 212K τοποθετούνται στο διαμέρισμα των 300K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 300-212 = 88K
    • 417K τοποθετούνται στο διαμέρισμα των 500K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 500-417 = 83K
    • 112K τοποθετούνται στο διαμέρισμα των 200Κ. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 200-112 = 88K
    • 426Κ τοποθετούνται στο διαμέρισμα των 600Κ. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 600-426 = 174K

Συνολικός κατακερματισμός: 433Κ Διεργασίες σε αναμονή: 0

  • Χειρότερη Τοποθέτηση
    • 212K τοποθετούνται στο διαμέρισμα των 600K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 600-300 = 300K
    • 417K τοποθετούνται στο διαμέρισμα των 500K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 500-417 = 83K
    • 112K τοποθετούνται στο διαμέρισμα των 300K. Νέα λίστα: 100K, 500K, 200K, 300K, 600K. Κατακερματισμός 300-112 = 188K
    • 426K. Η αίτηση περιμένει γιατί δεν υπάρχει διαμέρισμα που να μπορεί να την ικανοποιήσει.

Συνολικός κατακερματισμός: 571Κ Διεργασίες σε αναμονή: 1

Καλύτερη διαχείριση έχει κάνει ο αλγόριθμος καλύτερης τοποθέτησης που δημιούργησε τον μικρότερο κατακερματισμό και δεν άφησε αίτηση χωρίς εξυπηρέτηση.

24-07-2008 (18:46) από Άρης -
Αλλαγή σειράς 105 από:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειράς 107 από:
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 0Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειρών 109-110 από:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 0Κ, 4Κ, 8Κ, 9Κ, 7Κ, 9Κ, 12Κ, 15Κ
σε:
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
Αλλαγή σειρών 147-148 από:
σε:
  • First-fit
    • 212K is put in 500K partition. New list:
    • 417K is put in 600K partition
24-07-2008 (18:37) από Άρης -
Πρόσθεση σειράς 1:
Πρόσθεση σειρών 89-150:

Ερώτηση

Θεωρείστε ένα σύστημα εναλλαγής στο οποίο η μνήμη περιέχει τα ακόλουθα μεγέθη κενών κατά σειρά: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ και 15Κ. Ποιο κενό χρησιμοποιείται για κάθε επιτυχημένη απαίτηση που έχει μέγεθος,

  1. 12Κ
  2. 10Κ

με τον αλγόριθμο πρώτης τοποθέτησης; Επαναλάβατε την άσκηση για τους αλγόριθμους της καλύτερης, της χειρότερης και της επόμενης τοποθέτησης.

Απάντηση

  • Πρώτη Τοποθέτηση
    • Αίτηση 12Κ
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
  • Αίτηση 10Κ
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 0Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
  • Αίτηση 9Κ
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 0Κ, 4Κ, 8Κ, 9Κ, 7Κ, 9Κ, 12Κ, 15Κ
  • Καλύτερη Τοποθέτηση
    • Αίτηση 12Κ
Τοποθετείται στο κενό 12Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 0Κ, 15Κ
  • Αίτηση 10Κ
Τοποθετείται στο κενό 10Κ. Νέα λίστα: 0Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 0Κ, 15Κ
  • Αίτηση 9Κ
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 0Κ, 4Κ, 20Κ, 18Κ, 7Κ, 0Κ, 0Κ, 15Κ
  • Χειρότερη Τοποθέτηση
    • Αίτηση 12Κ
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
  • Αίτηση 10Κ
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 9Κ, 12Κ, 15Κ
  • Αίτηση 9Κ
Τοποθετείται στο κενό 15Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 9Κ, 12Κ, 6Κ
  • Επόμενη Τοποθέτηση
    • Αίτηση 12Κ
Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ
  • Αίτηση 10Κ
Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 9Κ, 12Κ, 15Κ
  • Αίτηση 9Κ
Τοποθετείται στο κενό 9Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 0Κ, 12Κ, 15Κ

Question

Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in order), how would each of the First-fit, Best-fit, and Worst-fit algorithms place processes of 212K, 417K, 112K, and 426K (in order)? Which algorithm makes the most efficient use of memory?

Answer

24-07-2008 (17:22) από Άρης -
Πρόσθεση σειρών 3-88:

Ερώτηση

Τι ονομάζουμε εναλλαγή; (swapping)

Απάντηση

Η μετακίνηση διεργασιών από την κύρια μνήμη στο δίσκο και αντίστροφα ονομάζεται εναλλαγή.


Question

What are variable partitions?

Answer

Partitions that can be moved in location, and can be changed in number.


Question

What is compaction? Why use it?

Answer

Movement of processes to eliminate small partitions. It allows smaller partitions to form fewer larger ones, to allow larger processes to run.


Question

Explain the difference between internal and external fragmentation.

Answer

Internal fragmentation is the area in a region or a page that is not used by the job occupying that region or page. This space is unavailable for use by the system until that job is finished and the page or region is released.


Question

We assume that the memory manager knows how much memory to allocate. Explain the following allocation algorithms:

  1. First fit
  2. Next fit
  3. Best fit
  4. Worst fit
  5. Quick fit

Answer

  • First fit. The memory manager scans along the list of segments until it finds a hole that is big enough. The hole is then broken up into two pieces, one for the process and one for the unused memory, except in the statistically unlikely case of an exact fit. First fit is a fast algorithm because it searches as little as possible.
  • Next fit. It works the same way as first fit, except that it keeps track of where it is whenever it finds a suitable hole. The next time it is called to find a hole, it starts searching the list from the place where it left off last time, instead of always at the beginning, as first fit does. Simulations show that next fit gives slightly worse performance than first fit.
  • Best fit. Best fit searches the entire list and takes the smallest hole that is adequate. Rather than breaking up a big hole that might be needed later, best fit tries to find a hole that is close to the actual size needed.
Best fit is slower than first fit because it must search the entire list every time it is called. Somewhat surprisingly, it also results in more wasted memory than first fit or next fit because it tends to fill up memory with tiny, useless holes. First fit generates larger holes on the average.
  • Worst fit. This algorithm always takes the largest available hole, so that the hole broken off will be big enough to be useful. Simulation has shown that worst fit is not a very good idea either.
  • Quick fit. Yet another allocation algorithm is quick fit, which maintains separate lists for some of the more common sizes requested. With quick fit, finding a hole of the required size is extremely fast, but it has the same disadvantage as all schemes that sort by hole size, namely, when a process terminates or is swapped out finding its neighbors to see if a merge is possible is expensive. If merging is not done, memory will quickly fragment into a large number of small holes into which no processes fit.

22-07-2008 (19:12) από Άρης -
Πρόσθεση σειρών 1-2:

Εναλλαγή

Τελευταία ενημέρωση: 06-08-2008 (18:26)

Copyright 2008 - Άρης Φεργάδης