>><<

->Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8K, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 10Κ. Νέα λίστα: 0K, 4Κ, 8K, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 18Κ. Νέα λίστα: 0K, 4Κ, 8K, 9K, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 12Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 0K, 15Κ

->Τοποθετείται στο κενό 10Κ. Νέα λίστα: 0Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 0K, 15Κ

->Τοποθετείται στο κενό 9Κ. Νέα λίστα: 0, 4Κ, 20Κ, 18Κ, 7Κ, 0Κ, 0K, 15Κ

->Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8K, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 15Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 9Κ, 12Κ, 6Κ

->Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 9Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8Κ, 7Κ, 0Κ, 12Κ, 15Κ

** 100 λέξεις τοποθετούνται στο τμήμα των 300 λέξεων. Νέα λίστα: 200, 800
** 500 λέξεις τοποθετούνται στο τμήμα των 800 λέξεων. Νέα λίστα: 200, 300
** 200 λέξεις τοποθετούνται στο τμήμα των 200 λέξεων. Νέα λίστα: 0, 300
** 300 λέξεις τοποθετούνται στο τμήμα των 300 λέξεων. Νέα λίστα: 0, 0

** 100 λέξεις τοποθετούνται στο τμήμα των 300 λέξεων. Νέα λίστα: 200, 800
** 500 λέξεις τοποθετούνται στο τμήμα των 800 λέξεων. Νέα λίστα: 200, 300
** 200 λέξεις τοποθετούνται στο τμήμα των 200 λέξεων. Νέα λίστα: 0, 300
** 300 λέξεις τοποθετούνται στο τμήμα των 300 λέξεων. Νέα λίστα: 0, 0

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

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

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

* Πρώτη Τοποθέτηση
** 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. Η αίτηση περιμένει γιατί δεν υπάρχει διαμέρισμα που να μπορεί να την ικανοποιήσει.

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

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

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

!! Ερώτηση

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

>>answer<<

!! Απάντηση

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

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

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

>><<

----

!! Ερώτηση

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

----

!! Ερώτηση

!! Απάντηση

----

!! Ερώτηση

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

>>answer<<

!! Απάντηση

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

>><<

----

!! Ερώτηση

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

>>answer<<

!! Απάντηση

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

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

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

>><<

----

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

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

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

->Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, {-20Κ-}, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 10Κ. Νέα λίστα: {-10Κ-}, 4Κ, {-20Κ-}, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 18Κ. Νέα λίστα: {-10Κ-}, 4Κ, {-20Κ-}, {-18Κ-}, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 12Κ. Νέα λίστα: 10Κ, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, {-12Κ-}, 15Κ

->Τοποθετείται στο κενό 10Κ. Νέα λίστα: {-10Κ-}, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, {-12Κ-}, 15Κ

->Τοποθετείται στο κενό 18Κ. Νέα λίστα: {-10Κ-}, 4Κ, 20Κ, 18Κ, 7Κ, {-9Κ-}, {-12Κ-}, 15Κ

->Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, {-20Κ-}, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, {-20Κ-}, {-18Κ-}, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 15Κ. Νέα λίστα: 10Κ, 4Κ, {-20Κ-}, {-18Κ-}, 7Κ, 9Κ, 12Κ, {-15Κ-}

->Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, {-20Κ-}, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, {-20Κ-}, {-18Κ-}, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 9Κ. Νέα λίστα: 10Κ, 4Κ, {-20Κ-}, {-18Κ-}, 7Κ, {-9Κ-}, 12Κ, 15Κ

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

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

* Πρώτη Τοποθέτηση
** 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

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

->Τοποθετείται στο κενό 20Κ. Νέα λίστα: 10Κ, 4Κ, {+20Κ+}, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 10Κ. Νέα λίστα: {+10Κ+}, 4Κ, 20Κ, 18Κ, 7Κ, 9Κ, 12Κ, 15Κ

->Τοποθετείται στο κενό 18Κ. Νέα λίστα: {+10Κ+}, 4Κ, {+20Κ+}, {+18Κ+}, 7Κ, 9Κ, 12Κ, 15Κ

* First-fit
** 212K is put in 500K partition. New list:
** 417K is put in 600K partition

%define=answer block bgcolor=#c4d4e7 border='1px dashed #31659c' padding-left='10px' padding-right='10px'%

----

!! Ερώτηση

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

>>answer<<

!! Απάντηση

* Πρώτη Τοποθέτηση
** Αίτηση 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<<

!! Answer



>><<

!! Ερώτηση

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

>>answer<<

!! Απάντηση

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

>><<

----

!! Question

'''What are variable partitions?'''

>>answer<<

!! Answer

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

>><<

----

!! Question

'''What is compaction? Why use it?'''

>>answer<<

!! 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<<

!! 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:'''

#%alpha% '''First fit'''
# '''Next fit'''
# '''Best fit'''
# '''Worst fit'''
# '''Quick fit'''

>>answer<<

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

>><<

----

! Εναλλαγή