Μονοπρογραμματισμός χωρίς Εναλλαγή και Σελιδοποίηση

Το σύστημα στο οποίο υπάρχει στη μνήμη κάθε φορά μία μόνο διεργασία και τη χρησιμοποιεί στο σύνολό της (για την ακρίβεια ένα κομμάτι της το κατέχει το Λ.Σ.), είναι το απλούστερο σύστημα διαχείρισης που υπάρχει.

Παρόλι την απλότητα, η μελέτη του μονοπρογραμματισμού θέτει τα πρώτα προβλήματα διαχείρισης μνήμης που πρέπει να αντιμετωπίσουμε.

Question

What is the system manager’s main problem in using fixed partitions?

Answer

Determining the optimum number of partitions and their size.

Question

Ένα υπολογιστικό σύστημα έχει αρκετό χώρο για να διατηρήσει τέσσερα προγράμματα στην κύρια μνήμη του. Τα προγράμματα αυτά μένουν αδρανή αναμένοντας είσοδο/έξοδο (Ε/Ε) το μισό χρόνο. Ποιο ποσοστό του χρόνου της CPU σπαταλιέται;

Answer

Η αναμονή για Ε/Ε είναι 50%, άρα p=0.5. Οι διεργασίες είναι τέσσερις οπότε n=4.

Βαθμός Χρήσης CPU = 1 - pⁿ = 1 - 0.5⁴ = 0,9375 ή 93,75%

Το ποσοστό του χρόνου της CPU σπαταλιέται είναι: 100 - 93,75 = 6,25%

Ερώτηση

Υποθέτουμε ότι ένας υπολογιστής έχει 2GBytes μνήμης από τα οποία το λειτουργικό σύστημα χρησιμοποιεί το 1GB και κάθε πρόγραμμα χρήστη χρησιμοποιεί 512MB. Αν όλα τα προγράμματα έχουν αναμονή λόγω Ε/Ε, 60%

ποιος είναι ο βαθμός χρήσης της CPU;
σε τι ποσοστό θα ανέβει η βαθμός χρήσης να προσθέσουμε 1GB ακόμη;

Απάντηση

Διαθέσιμο είναι το 1GB. Αφού το κάθε πρόγραμμα χρησιμοποιεί 512MB μπορούν να υπάρχουν μέχρι 2 προγράμματα ταυτόχρονα στη μνήμη (n=2). Η αναμονή για Ε/Ε είναι 60%, δηλαδή p=0.6.

Βαθμός Χρήσης CPU = 1 - pⁿ = 1 - 0.6² = 0.64 (64%)

Με 1GB ακόμη στη μνήμη μπορούμε να έχουμε συνολικά επιπλέον 2 προγράμματα, έτσι n=4

Βαθμός Χρήσης CPU = 1 - pⁿ = 1 - 0.6⁴ = 0.8704 (87,04%)

Ο βαθμός χρήσης έχει ανέβει σε ποσοστό (0.8704 - 0.64)/0.64 = 0,36 (36%)

Ερώτηση

Θεωρείστε ένα υπολογιστικό κέντρο του οποίου οι διεργασίες συμπεριλαμβάνουν μεταφορές πληροφοριών Ε/Ε που φθάνουν το 80% του χρόνου εκτέλεσής τους. Σ' αυτό το σύστημα καταφθάνουν τέσσερις διεργασίες όπως φαίνεται στον παρακάτω πίνακα. Ο μηχανισμός χρονοπρογραμματισμού είναι η εξυπηρέτηση εκ περιτροπής (round robin).

Διεργασία	Χρόνος Άφιξης	Διάρκεια (min)
1	0	4
2	10	3
3	15	2
4	20	2

Υπολογίστε το χρόνο ολοκλήρωσης για κάθε διεργασία
Φτιάχτε το διάγραμμα Gantt.

Απάντηση

Για τη διεργασία 1, έχουμε: Αξιοποίηση CPU = 1-pⁿ=1-0.8¹=0.2 (20%). Δηλαδή, απασχολεί την CPU για το 20% του χρόνου. Έτσι, σε 1min η διεργασία 1 θα έχει τρέξει για 60x20/100=12sec. Αν είναι μόνη της στο σύστημα χρειάζεται πραγματικό χρόνο για να εκτελέσει τα 4min που θέλει: x*0.2 = 4 => x = 20min.

Η διεργασία 2 είναι παράλληλα με την 1 στο σύστημα: Αξιοποίηση CPU = 1-pⁿ=1-0.8²=0.36 Ο αλγόριθμος RR δίνει ίσο ποσοστό απασχόλησης σε κάθε διεργασία. Έτσι, έχουμε CPU/Διεργασία = 0.36/2 = 0.18

Με την 3 στο σύστημα: Αξιοποίηση CPU = 1-pⁿ=1-0.8³=0.49 και CPU/Διεργασία = 0.49/3 = 0.16

Με την 4 στο σύστημα: Αξιοποίηση CPU = 1-pⁿ=1-0.8⁴=0.59 και CPU/Διεργασία = 0.59/4 = 0.15

Έχουμε, λοιπόν,

Από 0 μέχρι 10: Διεργασία 1. Έχει αποκλειστική απασχόληση της CPU και διεκπεραιώνει: (10 – 0)*0.2 = 2min από το συνολικό χρόνο της.
Από 10 μέχρι 15: Διεργασία 1 & 2. Η κάθε μία έχει το 18% της CPU, έτσι διεκπεραιώνονται για χρόνο: (15 – 10)*0.18 = 0.9min.
Από 15 μέχρι 20: Διεργασία 1 & 2 & 3. Η κάθε μία έχει το 16% της CPU, έτσι διεκπεραιώνονται για χρόνο: (20 – 15)*0.16 = 0.8min
Από 20 και μετά: Διεργασία 1 & 2 & 3 & 4. Η κάθε μία έχει το 15% της CPU, έτσι για κάθε λεπτό που περνάει διεκπεραιώνονται για χρόνο: 1*0.15 = 0.15min

Στον παρακάτω πίνακα φαίνεται η κατάσταση τη χρονική στιγμή 20.

Διεργασία	0 - 10	10 - 15	15 - 20	Διεκπεραίωση	Υπόλοιπο
1	2	0.9	0.8	3.7	0.3
2	0	0.9	0.8	1.7	1.3
3	0	0	0.8	0.8	1.2
4	0	0	0	0	2

Η στήλη Διεκπεραίωση μας δείχνει πόσα λεπτά από τα συνολικά κάθε διεργασίες έχει διεκπεραιωθεί.

Η διεργασία 1 έχει υπόλοιπο 0.3. Απασχολώντας τη CPU για το 15% χρειάζεται για να ολοκληρώσει: x*0.15=0.3 => x=2min. Άρα στο 22ο λεπτό ολοκληρώνει η 1. Τα νέα υπόλοιπα (όλες έχουν "προχωρήσει" για 0.3min):

Διεργασία	Υπόλοιπο
2	1
3	0.9
4	1.7

Από το 22o και μετά έχουμε 3 διεργασίες όπου η κάθε μία έχει το 16% της CPU. Η διεργασία 3 έχει το μικρότερο υπόλοιπο και ο χρόνος που χρειάζεται για να ολοκληρώσει είναι: x*0.16=0.9 => x =5.6. Άρα ολοκληρώνει στο 27.6 λεπτό. Τα νέα υπόλοιπα:

Διεργασία	Υπόλοιπο
2	0.1
3	0.8

Έχουμε 2 διεργασίες με κάθε μία να έχει το 18% της CPU. Η διεργασία 2 χρειάζεται χρόνο: x*0.18=0.1 => x=0.5. Ολοκληρώνει λοιπόν στο 28.2 και το υπόλοιπο της 4 είναι 0.7.

Για να ολοκληρώσει και η 4 χρειάζεται: x*0.2 = 0.7 => x = 3.5. Έτσι, στο 31.7 τελειώνει και η 4.

Το διάγραμμα Gantt έχει ως εξής.