Εναλλαγή

Ερώτηση

Τι ονομάζουμε εναλλαγή; (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:

First fit
Next fit
Best fit
Worst fit
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.

Ερώτηση

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

12Κ
10Κ
9Κ

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

Απάντηση

Πρώτη Τοποθέτηση
- Αίτηση 12Κ

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

Αίτηση 10Κ

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

Αίτηση 9Κ

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

Καλύτερη Τοποθέτηση
- Αίτηση 12Κ

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

Αίτηση 10Κ

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

Αίτηση 9Κ

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

Χειρότερη Τοποθέτηση
- Αίτηση 12Κ

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

Αίτηση 10Κ

Τοποθετείται στο κενό 18Κ. Νέα λίστα: 10Κ, 4Κ, 8Κ, 8K, 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Κ

Ερώτηση

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

Απάντηση

Πρώτη Τοποθέτηση
- 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 (με αυτή τη σειρά), πως θα τοποθετήσει καθένας από τους αλγόριθμους πρώτης τοποθέτησης, καλύτερης τοποθέτησης και χειρότερης τοποθέτησης τις παρακάτω αιτήσεις;

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 θα καταναλώνεται για την συνένωση;

Απάντηση

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

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

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