ΚΕΦΑΛΑΙΟ 3: Λειτουργικά Συστήματα

● 3.1 Η εξέλιξη των λειτουργικών συστημάτων

● 3.2 Αρχιτεκτονική λειτουργικών συστημάτων

● 3.3 Συντονισμός των δραστηριοτήτων του υπολογιστή

● 3.4 Χειρισμός ανταγωνισμού μεταξύ διεργασίων

● 3.5 Ασφάλεια

Οι διαφάνειες βασίζονται σε μεγάλο βαθμό σε αυτές που συνοδεύονται με το προτεινόμενο σύγγραμμα, καθώς και στις διαφάνειες προηγούμενων ετών του κ. Κουρκουμπέτη. 1

Λειτουργικό Σύστημα ● Ένα λειτουργικό σύστημα είναι το λογισμικό που:

– Ελέγχει τη συνολική λειτουργία του υπολογιστή. • επιτρέπει πολλά προγράμματα (διαδικασίες, processes) να

μοιράζονται ταυτόχρονα τους πόρους του υπολογιστή

– Παρέχει τα μέσα για την αποθήκευση και την ανάκτηση εγγράφων.

– Εκτελεί προγράμματα. – Παρέχει τη διασύνδεση μέσω της οποίας ο χρήστης ζητάει

την εκτέλεση του προγράμματος.

2

Παραδείγματα λειτουργικών συστημάτων • Windows (Microsoft): PC • Mac OS (Apple) • Solaris (Sun Microsystems, τώρα Oracle) • Linux • UNIX: για μεγαλύτερα συστήματα υπολογιστών

Για κινητά / PDAs • iPhone OS (Apple) • Blackberry OS (Research in Motion) • Windows Phone (Microsoft) • Symbian OS (Nokia) • Android (Google)

3

Βασικές αρχές • Εργασία (job): ένα πρόγραμμα προς εκτέλεση

– Στα πρώτα συστήματα υπολογιστών, μια μηχανή ετοιμαζόταν ειδικά για την εκτέλεση μιας εργασίας

– Υπήρχε ένα άτομο (computer operator) για να φορτώνει τα δεδομένα στον Η/Υ και να κανονίζει την πρόσβαση διαφορετικών χρηστών

• 1ος σταθμός: Ομαδική επεξεργασία (batch processing): εκτέλεση πολλών προγραμμάτων μαζί χωρίς αλληλεπίδραση με τον χρήστη – Οι εργασίες περιμένουν σε μια ουρά αναμονής (queue) – First-In First-Out (FIFO) – Στην πραγματικότητα, διαφορετικές εργασίες έχουν

διαφορετικές προτεραιότητες (priorities)

4

Λειτουργικό Σύστημα • Ο υπολογιστής σαν ‘σκέτο’ hardware έχει

περιορισμένη χρησιμότητα – δυσκολία στο φόρτωμα και τρέξιμο κώδικα – λεπτομέρειες Ι/Ο, interrupt handling,... – δυνατότητα τρεξίματος πολλών προγραμμάτων – τρέχει μόνο κώδικα μηχανής – Απαίτηση για αλληλεπίδραση με τον χρήστη – Απαίτηση για επεξεργασία σε πραγματικό χρόνο

5

Ομαδική επεξεργασία (batch processing)

6

Βασικές Αρχές (2) • Αρχικά, κάθε εργασία συνοδευόταν από μια λίστα από

εντολές που περιέγραφαν την εκτέλεσή της • Γλώσσα Ελέγχου Εργασίας (Job Control Language) • Ο computer operator τις διάβαζε και τις εκτελούσε με το χέρι • 2ος σταθμός: αλληλεπιδραστική επεξεργασία (interactive

processing) • 3ος σταθμός: Επεξεργασία σε πραγματικό χρόνο (real-time

processing) – Υπάρχουν προθεσμίες (deadlines) μέσα στις οποίες πρέπει να

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

δυσαρεστημένος

7

Αλληλεπιδραστική επεξεργασία

8

Υποστήριξη πολλών χρηστών • Εξυπηρέτηση πολλών χρηστών με διαμοιρασμό χρόνου (time-

sharing) • Αρχή του πολυ-προγραμματισμού (multi-programming) με την

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

εκτελεστεί μια άλλη στο επόμενο χρονικό διάστημα

• Λέγεται και πολλαπλή πρόσβαση με διαίρεση χρόνου (time division multiple access, TDMA)

9

Υποστήριξη πολλών χρηστών (2)

• Με το να εκτελείται μια εργασία σε κάθε χρονικό διάστημα, αν το χρονικό διάστημα είναι μικρό, δημιουργείται η «ψευδαίσθηση» ότι εκτελούνται πολλές εργασίες παράλληλα

• Διαμοιρασμός χρόνου: Συνήθως αναφέρεται στην εξυπηρέτηση πολλών χρηστών με τον τρόπο που αναφέραμε

• Multi-tasking (πολυ-εκτέλεση): εκτέλεση πολλών εργασιών ενός χρήστη ταυτόχρονα

10

2 σημαντικές έννοιες

• Εξισορρόπηση φόρτου (load balancing): δυναμική ανάθεση εργασιών σε διαφορετικούς επεξεργαστές ώστε όλοι οι επεξεργαστές να χρησιμοποιούνται αποδοτικά

• Scaling: «Σπάσιμο» μιας εργασίας σε πολλές

μικρότερες, ανάλογα με τον αριθμό των διαθέσιμων επεξεργαστών

11

Είδη λογισμικού ● Λογισμικό εφαρμογών (application software):

– Εκτελεί συγκεκριμένες εργασίες ανάλογα με τις ανάγκες του χρήστη, με σκοπό την αξιοποίηση του υπολογιστή.

● Λογισμικό συστήματος (system software): – Εκτελεί τις κοινές εργασίες των υπολογιστικών

συστημάτων. – Παρέχει την υποδομή για το λογισμικό

εφαρμογών. – Βοηθητικό λογισμικό (utility software)

12

Κατηγορίες λογισμικού

13

Στοιχεία λειτουργικού συστήματος (1)

14

Στοιχεία λειτουργικού συστήματος (2) ● Φλοιός ή κέλυφος (shell): το τμήμα μέσω του οποίου διεξάγεται η

επικοινωνία του χρήστη με τη μηχανή. – Γραφικό περιβάλλον διεπαφής με το χρήστη (Graphical User

Interface, GUI) • Διαχειριστής παραθύρων (windows manager)

● Ο Πυρήνας (kernel) περιέχει τα στοιχεία λογισμικού που εκτελούν τις βασικές λειτουργίες που απαιτούνται από το σύστημα – Διαχειριστής αρχείων (file manager) – Οδηγός συσκευών (device driver) – Διαχειριστής μνήμης (memory manager) – Χρονοπρογραμματιστής (scheduler) και διεκπεραιωτής (dispatcher): ο

scheduler αποφασίζει ποιες διεργασίες θα εκτελεστούν, ο διεκπεραιωτής ελέγχει την ανάθεση χρόνου σε αυτές

15

Διαχειριστής αρχείων (file manager)

● Ο διαχειριστής αρχείων συντονίζει τη χρήση των λειτουργιών μαζικής αποθήκευσης του υπολογιστή. (π.χ. Σκληρός δίσκος) και περιέχει πληροφορίες πρόσβασης για τα αρχεία – Κατάλογοι (directories) ή φάκελοι (folders): ομάδες ή

συγκεντρώσεις αρχείων που δημιουργούνται από το χρήστη.

• Ιεραρχική οργάνωση – Διαδρομή (path): η θέση ενός αρχείου στην ιεραρχία του

καταλόγου. Π.χ: animals/prehistoric/dinosaurs – Περιγραφέας αρχείων: οι απαραίτητες πληροφορίες για

την απόκτηση πρόσβασης σε ένα ανοικτό αρχείο.

16

Οδηγός συσκευών (device driver)

• Είναι μονάδες λογισμικού για επικοινωνία με τους ελεγκτές (controllers) των περιφερειακών συσκευών ή απευθείας με αυτές – Π.χ. Οδηγός (driver) για εκτυπωτή, για οθόνη, για σκληρό

δίσκο

• Ο οδηγός είναι εξειδικευμένος και αναλαμβάνει την

καθοδήγηση των περιφερειακών συσκευών

17

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

• Ανάγκη αποθήκευσης πληροφορίας – μεγάλη χρονική διάρκεια αποθήκευσης – εύκολη πρόσβαση – προγράμματα, δεδομένα χρήση δευτερεύουσας μνήμης (δίσκοι,...) μονάδα αποθήκευσης: αρχείο λειτουργίες: δημιουργία (create), διαγραφή (delete),

προσπέλαση (open, close, read, write), προστασία (εξουσιοδοτημένη προσπέλαση)

18

Διαχειριστής μνήμης ● Ο διαχειριστής μνήμης συντονίζει τη χρήση της κύριας μνήμης

● Ιδιαίτερα σημαντικός στην περίπτωση πολλών χρηστών ή πολλών εργασιών (multi-tasking) που εκτελούνται παράλληλα

● Πολλά προγράμματα και μπλοκ δεδομένων συνυπάρχουν στην κύρια μνήμη ● Εικονική μνήμη (virtual memory): προσομοίωση επιπλέον χώρου

μνήμης – Δημιουργείται εναλλάσσοντας μονάδες δεδομένων που καλούνται σελίδες,

μεταξύ του πραγματικού χώρου κυρίας μνήμης και του μέσου αποθήκευσης – Π.χ. Αν μια εργασία χρειάζεται 8GB μνήμης αλλά η κύρια μνήμη είναι 4GB. – Ο διαχειριστής μνήμης κρατάει τα υπόλοιπα 4GB αποθηκευτικού χώρου στον

σκληρό δίσκο ! – Αποθηκεύει εκεί τα 4GB δεδομένων (τα διαιρεί σε μονάδες, τις σελίδες

(pages) – Μεταφέρει τις σελίδες από και προς την μνήμη ώστε οι σελίδες που κάθε

φορά χρειάζονται από την διαδικασία να βρίσκονται στην κύρια μνήμη – Δημιουργείται η ψευδαίσθηση ότι υπάρχουν 8GB κύριας μνήμης

19

Διαχείριση μνήμης

• Εκχώρηση μνήμης • Προστασία

– διαδικασία Α δεν μπορεί να προσπελάσει την μνήμη της διεργασίας Β

• Χρησιμοποίηση – ελευθερία χρησιμοποίησης οποιοδήποτε τμήματος μνήμης

από διεργασίες – διεργασίες χρησιμοποιούν πολλά τεμάχια μνήμης μη συνεχή

μεταξύ τους – δυνατότητα μεταφοράς μιας διεργασίας μέσα στην μνήμη

20

Εκκίνηση • O Program Counter στην CPU έχει σχεδιαστεί να ξεκινά από μια

συγκεκριμένη διεύθυνση κάθε φορά που γίνεται εκκίνηση του υπολογιστή

• Θα μπορούσε το λειτουργικό σύστημα να βρίσκεται πάντα στην κύρια μνήμη – Αλλά αυτή είναι πτητική (volatile), χάνει τα δεδομένα της όταν ο Η/Υ σβήνει

• Λύση: ένα μικρό μέρος της μνήμης γίνεται εκ κατασκευής μη πτητικό (non-volatile) – Read-only memory (ROM)

• Boot loader: πρόγραμμα εγκατεστημένο στη ROM, εκτελείται 1ο όταν ανοίγει ο υπολογιστής

• Οι εντολές στον boot loader κατευθύνουν την CPU να μεταφέρει το λειτουργικό σύστημα στην κυρίως μνήμη – Από τον σκληρό δίσκο (PC), ή από την μνήμη flash (smart-phones), ή από μια

άλλη μηχανή (σε υπολογιστικά συστήματα σε πανεπιστήμια) • Ο boot loader κατευθύνει την CPU να κάνει jump στην θέση μνήμης που

βρίσκεται το λειτουργικό σύστημα

21

Διαδικασία εκκίνησης ● Η διαδικασία εκκίνησης (boot strapping ή booting) εκτελείται κάθε

φορά που ο υπολογιστής τίθεται σε λειτουργία. ● Μεταφέρει βασικά στοιχεία του λειτουργικού συστήματος από το

μέσο αποθήκευσης (όπου είναι αποθηκευμένο) στην κύρια μνήμη.

22

3-23

Διεργασίες • Πρόγραμμα: ένα στατικό σύνολο από εντολές • Διεργασία (process): Η δραστηριότητα της εκτέλεσης ενός

προγράμματος • Κατάσταση διεργασίας (process state): Τρέχουσα κατάσταση της

δραστηριότητας, αλλάζει με το χρόνο – Μετρητής προγράμματος (program counter) – Καταχωρητές γενικής χρήσης – Σχετιζόμενο τμήμα της κύριας μνήμης

• Διαχείριση διεργασιών μέσω του λειτουργικού συστήματος – Κάθε διεργασία έχει τους απαιτούμενους πόρους (θέσεις μνήμης, CPU,

πρόσβαση σε περιφερειακές συσκευές, πρόσβαση σε αρχεία) που χρειάζεται – Διεργασίες δεν παρεμβάλλονται και δεν εμποδίζουν η μια την άλλη – Διεργασίες που χρειάζεται να ανταλλάζουν πληροφορία, μπορούν να το

κάνουν

Κατάσταση της διεργασίας Κατάσταση της διεργασίας = PC + εικόνα της μνήμης + καταχωρητών = πλήρης πληροφορία για να σταματήσουμε και να ξανασυνεχίσουμε την διεργασία

Διεργασία Α (τρέχει)

Διεργασία Β (σταματημένη)

PC

program

data

PC

PC 0001101...

Α Β C

Πίνακας διεργασιών

24

Διαχείριση διεργασιών ● Χρονοπρογραμματιστής (scheduler):

– Διατηρεί στον πίνακα διεργασιών ένα σύνολο πληροφοριών για όλες τις διεργασίες. ● Έτοιμη (ready) διεργασία (δηλ. Μπορεί να ξεκινήσει ή να συνεχίσει)

ή σε αναμονή (waiting) (δηλ. Περιμένει κάποιο εξωτερικό γεγονός να συμβεί, π.χ. Μήνυμα από κάποια άλλη διεργασία, κτύπημα στο πληκτρολόγιο κλπ)

● Προτεραιότητες ● Εισάγει νέες διεργασίες στον πίνακα, βγάζει διεργασίες που

ολοκληρώθηκαν ● Ο παραπάνω πίνακας διατηρείται στην μνήμη

● Η πληροφορία αυτή χρησιμοποιείται από τον Διεκπεραιωτή (Dispatcher)

25

Διαχείριση διεργασιών (2) ● Διεκπεραιωτής (ή Διανομέας, Dispatcher)

– Το στοιχείο του πυρήνα που εξασφαλίζει την πραγματοποίηση των προγραμματισμένων διεργασιών.

– Επιβλέπει την εκτέλεσή τους – Δίνει ένα χρονομερίδιο (time slice) σε μία διεργασία που

είναι έτοιμη. • Χρονομερίδιο: milli-secs ή micro-secs

– Εκτελεί την μεταγωγή (switching) διεργασιών όταν το χρονομερίδιο της τρέχουσας διεργασίας τελειώσει ● Λέγεται και θεματικό μεταγωγή (Context-switching) ● Διακοπή είναι το σήμα που παράγεται στο τέλος του χρονο-

μεριδίου ● Ο χειριστής διακοπών (σε επόμενη διαφάνεια) είναι μέρος του

διεκπεραιωτή.

26

Σημασία Διαχείρισης Διεργασιών • Διεργασία Α (διάρκεια 100 sec, έτοιμη τη στιγμή 0) • Διεργασία Β (διάρκεια 10 sec, έτοιμη τη στιγμή 0+dt) • Αν:

• Χρόνος ολοκλήρωσης Α: στα 100 sec • Χρόνος ολοκλήρωσης Β: στα 110 sec • Μέσος χρόνος ολοκλήρωση: (100+110)/2 = 105 sec. • Αν εκτελώ κάθε μια εναλλάξ για 5 sec

• Χρόνος ολοκλήρωσης Α: στα 110 sec • Χρόνος ολοκλήρωσης Β: στα 20 sec • Μέσος χρόνος ολοκλήρωση: (110+20)/2 = 65 sec.

27

Σημασία Διαχείρισης Διεργασιών (2) • Περισσότερες από 1 μονάδες εκτέλεσης:

– Παραλληλισμός • Πολλοί ταμίες (μονάδες εκτέλεσης, εξυπηρετητές)

εξυπηρετούν πολλούς πελάτες, έναν πελάτη την φορά καθένας – Πόσο γρηγορότερη γίνεται η εκτέλεση τελικα;

• Ιδανικά Ν φορές πιο γρήγορα, αν έχουμε Ν παράλληλες μονάδες εκτέλεσης

• Επιβαρύνσεις • Π.χ. συγκρίνετε το χρόνο που θα γινόταν μια άσκηση αν

– Α. Δουλεύατε μόνος/η σας – Β. Με άλλον ένα άτομο – Γ. Με μια ομάδα 10 ατόμων

28

Χρονοπρογραμματισμός • Στόχος η καλή διαχείριση των πόρων του συστήματος (μνήμη,

CPU, δίσκος • Πρόβλημα: Ποιος είναι ο καλύτερος τρόπος να τρέξεις m

διεργασίες σε n επεξεργαστές • Ελαχιστοποίηση χρόνου απόκρισης / χρόνου ολοκλήρωσης

– Χρόνος απόκρισης: χρόνος από το κλικ του ποντικιού μέχρι το κλείσιμο του παραθύρου

– Χρόνος ολοκλήρωσης: ο χρόνος από τότε που υποβλήθηκε μια εργασία μέχει την ολοκλήρωσή της

• Μεγιστοποίηση του ρυθμού παραγωγής αποτελεσμάτων (ρυθμοαπόδοση, throughput) – Εκμετάλλευση των πόρων του συστήματος με τον καλύτερο δυνατό τρόπο – Ελαχιστοποίηση των «έμμεσων» προβλημάτων (context switching, κλπ)

29

Χρονοπρογραμματισμός FCFS ή FIFO • FCFS = First-come First-serve • FIFO = First-in First-out • Εκτέλεση διεργασιών με την σειρά άφιξής τους • Πλεονέκτημα: απλό

• Μειονέκτημα: • Η απόδοση εξαρτάται από την σειρά άφιξης

• Όχι καλό (όχι δίκαιο) για τις εργασίες που φτάνουν αργότερα • Όχι καλό αν μια μεγάλη έργασία φτάνει νωρίς

30

Παράδειγμα FIFO • Διεργασία Α διάρκειας 100sec, Β διάρκειας 2 sec, Γ διάρκειας 3 sec • Η, εναλλακτικά, θεωρείστε υπολογιστικούς κύκλους • Φτάνουν σχεδόν ταυτόχρονα (η Α λίγο πριν την Β, και η Β λίγο πριν την Γ)

• Αν φτάνουν με σειρά Β,Γ,Α:

• Πρόβλημα αν μια υπολογιστικά μεγάλη διεργασία φτάσει πρώτη (μπλοκάρει όλες τις άλλες που φτάνουν μετά από αυτήν)

31

Παράδειγμα FIFO (2) • Διάγραμμα Gantt: Να υπολογιστεί ο μέσος χρόνος αναμονής με την

παρακάτω διάρκεια (burst time) και σειρά άφιξης στην ουρά • P1: 20, P2: 12, P3: 8, P4: 16, P5: 4

• Χρόνοι αναμονής: • P1: 0 • P2: 20 • P3: 32 • P4: 40 • P5: 56 • Μέσος χρόνος αναμονής: 29.6

P1

20

P2

32

P3 P4 P5

40 56 60

32

Χρονοδρομολόγηση με Εναλλαγές (Round Robin, RR) • Το προηγούμενο πρόβλημα απαλοίφεται αν οι υπολογιστικά μεγάλες

διεργασίες δεν μονοπωλούν τον επεξεργαστή • Ρολόι • Εκτέλεση κάθε διεργασίας από την CPU για μια περίοδο ρολογιού

– Έπειτα, προχώρησε στην επόμενη διεργασία – Συνέχισε, μέχρι ο γύρος να ολοκληρωθεί για όλες τις διεργασίες

• Δίκαιος τρόπος: Ο RR χρησιμοποιείται πολύ συχνά με διάφορες παραλλαγές

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

• Για διεργασίες παρόμοιου μεγέθους π.χ. Α=100, Β=100

• Μέσος χρόνος ολοκλήρωσης; Τι θα έκανε η FIFO;

33

RR: Περίοδος • Μεγάλη περίοδος: μεγαλύτερη περίπτωση οι

διεργασίες να τερματίσουν ή να μπλοκάρουν πριν τελειώσει η περίοδος που εκτελούνται – Καταναλώνεται χρόνος άσκοπα

• Μικρή περίοδος: καλύτερος μέσος χρόνος αναμονής, αλλά μεγάλη επιβάρυνση – Υπάρχει συνεχές context-switching

• Επιθυμούμε περίοδο αρκετά μεγαλύτερη από το χρόνο μεταγωγής

• Συνήθης τιμή για την περίοδο: 100 msec – Κόστος μετατωγής: < 1%

34

Παράδειγμα Round Robin

• Διάρκεια της διεργασίας στην CPU και σειρά στην ουρά: – P1: 20, P2: 12, P3: 8, P4: 16, P5: 4 – Περίοδος RR = 4

• Διάγραμμα Gantt chart, υπολογισμός μέσου χρόνου αναμονής

• Συνολική αναμονή: – P1: 16 + 12 + 8 + 4 = 40 – P2: 4 + 16 + 12 = 32 – P3: 8 + 16 = 24 – P4: 12 + 16 + 8 = 36 – P5: 16

• Μέσος όρος: 29.6

P1 P2

4

P3 P4 P5 P1

8 12 16 20 24

P2 P3

28

P4 P1 P2 P4

32 36 40 44 48

P1 P4

52

P1

56 60

completes completes completes completes completes

35

Παράδειγμα για context-switching

• Mέσος χρόνος αναμονής για RR (round robin) με:

– Διεργασίες: P1: 24, P2: 4, P3: 4 με αυτή τη σειρά άφιξης

– Περίοδος = 4, χρόνος context-switching = 1 – P1: 0 + 11 + 4 = 15 – P2: 5 – P3:10

• Μέσος χρόνος αναμονής: 10

P1 P2 P3 P1 P1 P1 P1 P1 4 5 9 10 14 15 19 20 24 25 29 30 34 35 39

36

Χρονοδρομολόγηση με Προτεραιότητες • Ανάθεση προτεραιότητας σε κάθε διεργασία

– Ιεράρχηση διεργασιών • Κάθε φορά επιλέγεται μια από τις έτοιμες (ready) διεργασίες

με τη μεγαλύτερη προτεραιότητα • Διεργασίες ίδιας προτεραιότητας δρομολογούνται με RR • Στατικές ή δυναμικές προτεραιότητες • Προτεραιότητες ανάλογα με:

– Σημασία της διεργασίας – Χρόνος από την τελευταία εκτέλεση – Αξιοποίηση συσκευών Ι/Ο: Υψηλή προτεραιότητα στις διεργασίες που

εκτελούν πολύ Ι/Ο

37

Προτεραιότητες • Ανάθεση αριθμού προτεραιότητας

– 0 η υψηλότερη προτεραιότητα (ή η χαμηλότερη) • FIFO: όλες οι διεργασίες έχουν ίδιες προτεραιότητες • Shortest Job First, SJF (επόμενη διαφάνεια): η

προτεραιότητα είναι αντίστροφα ανάλογη προς τη διάρκεια της διεργασίας

• Οι προτεραιότητες μπορεί να είναι: – Εσωτερικές:

• Π.χ. Σύμφωνα με παράγοντες σχετικούς με το Λ/Σ (απαιτήσεις σε μνήμη)

– Εξωτερικές, π.χ. Σπουδαιότητα για τον χρήστη – Στατικές: σταθερές για όλη τη διάρκεια της διεργασίας – Δυναμικές:

• Αλλάζουν κατά τη διάρκεια της διεργασίας • Π.χ. Σα συνάρτηση της χρήσης CPU ή του χρόνου αναμονής (λύση για

το πρόβλημα του μπλοκαρίσματος)

38

Πρώτα η Συντομότερη Διεργασία (Shortest Job First, SJF)

• Εκτέλεση της συντομότερης διεργασίας • Η, ισοδύναμα, shortest-time-to-completion-first (πρώτα η διεργασία

με το λιγότερο υπολειπόμενο χρόνο εκτέλεσης)

• Βέλτιστη ως προς τον συνολικό χρόνο ολοκλήρωσης: – Δηλ. Αυτή είναι η πολιτική που ελαχιστοποιεί το συνολικό (άρα και τον μέσο)

χρόνο ολοκλήρωσης) • Απόδειξη: Βάζοντας τη γρήγορη διεργασία πριν την αργή ευνοούμε

την γρήγορη περισσότερο από ότι επιβαρύνουμε την αργή – Αλλάζοντας τη σειρά εκτέλεσης, πάντοτε αυξάνεται ο συνολικός χρόνος

εκτέλεσης 39

SJF: Shortest Job First • Διεργασίες και διάρκειες (burst times): P1: 20, P2: 12, P3: 8,

P4: 16, P5: 4

• Χρόνοι αναμονής: – P1: 40 – P2: 12 – P3: 4 – P4: 24 – P5: 0

• Μέσος χρόνος αναμονής: 16

P1

4

P2

12

P3 P4 P5

24 40 60

40

Προεκτοπισιμότητα και Μη • Διεργασίες Α,Β,Γ,... με διαφορετική προτεραιότητα • Προεκτοπίσιμη (pre-emptive) πολιτική χρονοδρομολόγησης: Αν

εκτελείται μια διεργασία x και φτάσει μια διεργασία y, η x διακόπτεται αν η y είναι μεγαλύτερης προτεραιότητας από την y – Η εκτέλεση της y συνεχίζεται μέχρι την ολοκλήρωσή της, εφόσον δεν

φτάσει άλλη διεργασία μεγαλύτερης προτεραιότητας από την y – Όταν ολοκληρωθεί η y, συνεχίζεται η εκτέλεση της x

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

• Μη προεκτοπίσιμη (non pre-emptive) πολιτική χρονοδρομολόγησης: Αν εκτελείται μια διεργασία x και φτάσει μια διεργασία y, η x δεν διακόπτεται σε καμιά περίπτωση – Η y θα εκτελεστεί εφόσον ολοκληρωθεί η x

41

Ποιες πολιτικές χρονοδρομολόγησης μπορεί να είναι προεκτοπίσιμες; (Preemptive)

• FΙFO – Μη προεκτοπίσιμη (non-preemptive)

• SJF (Shortest Job First) – Pre-emptive ή μη – Επιλογή όταν μια νέα διεργασία φτάνει

• Με προτεραιότητες: – Pre-emptive ή μη – Επιλογή όταν αλλάζει η προτεραιότητα μιας

διεργασίας ή όταν φτάνει μια μεγαλύτερης προτεραιότητας διεργασία

42

Χειριστής Διακοπών • Κάθε φορά που ο dispatcher δίνει ένα slice σε μια

διεργασία, παράγει ένα σήμα διακοπής (interrupt) • H CPU σταματά την διεργασία που εκτελεί τώρα

– Σώζει την τρέχουσα κατάσταση της διεργασίας – Εκτελεί ένα πρόγραμμα χειριστής διακοπών (interrupt handler)

που βρίσκεται στη μνήμη – Μεταφέρει τον έλεγχο στον διεκπεραιωτή – Ο διεκπεραιωτής επιλέγει μια διεργασία από τον πίνακα, ξεκινά

τον μετρητή και επιτρέπει στην διεργασία να ξεκινήσει

43

Σύνοψη ζητημάτων λειτουργικού συστήματος • Απαραίτητες λειτουργίες:

– Χρονοπρογραμματισμός (scheduling) διεργασιών – Διεκπεραίωση (Dispatching) : εναλλάσσει την CPU μεταξύ

διαδικασιών – Χειρισμός Διακοπών (Interrupt handling): ερμηνεύει σήματα

διακοπής, και ενεργοποιεί τις αντίστοιχες ρουτίνες (interrupts) – Δυνατότητα ανάκτησης στο μέλλον της κατάστασης της

διεργασίας που διακόπτεται τώρα – Εκχώρηση πόρων: μνήμη, Ι/Ο, CPU – Προστασία πόρων μεταξύ διαφορετικών διεργασιών

44

Πολυ-προγραμματισμός: χειρισμός Ι/Ο

Process (διεργασία) A Process B Process C

I/O I/O I/O

συνολικός χρόνος εκτέλεσης

Θεματική αλλαγή (context switching)

περιμένει

Με χρήση πολυ-προγραμματισμού

Χωρίς πολυ-προγραμματισμό

Μπορεί να μην έχουμε πάντοτε διεργασία έτοιμη να τρέξει 45

Πολυπρογραμματισμός: χρονομερισμός (time-slicing) μεταξύ διεργασιών

Χρονομερισμός: κάθε διεργασία τρέχει για ένα χρονομερίδιο (time slice)

46

Διεκπεραιωτής (dispatcher)

process = διεργασία = πρόγραμμα + περιβάλλον (μνήμη + καταχωρητές) process switching: εναλλαγή της CPU μεταξύ διαφορετικών διεργασιών

READY

BLOCKED

RUNNING

καταστάσεις μιας διεργασίας

επιλογή από διεκπεραιωτή

αρχή τέλος

τέλος slice

αρχή Ι/Ο, ζητάει πόρους που δεν υπάρχουν την στιγμή αυτή

τέλος Ι/Ο, πόροι ελευθερώ- θηκαν

READY ουρά

BLOCKED διεργασίες

RUNNING

47

Νήματα (threads) • Νήμα (thread) είναι η μικρότερη δυνατή ακολουθία εντολών

που μπορεί ένας χρονοπρογραμματιστής (scheduler) ενός λειτουργικού συστήματος να διαχειριστεί ανεξάρτητα – Δηλ. Είναι μια στοιχειώδης διεργασία

• Πολλά νήματα μπορεί να συνυπάρχουν σε μια διεργασία και μπορούν να μοιράζονται πόρους του υπολογιστή – Π.χ. Μνήμη

• Πολυνηματισμός (multi-threading) • Πολλά νήματα εκτελούν τις ίδιες εντολές • Η CPU μεταπηδάει (switch) μεταξύ διαφορετικών νημάτων, όπως μεταξύ διαφορετικών διεργασιών

48

Ανταγωνισμός μεταξύ διεργασιών • Ανταγωνισμός διεργασιών για πόρους (resources)

– Πρόσβαση σε αρχεία – Μνήμη – CPU – Χώρος στον πίνακα διεργασιών (scheduling) – Χρονο-μερίδια (dispatcher)

● Σηματοφορείς (semaphores): μία σημαία (flag) ελέγχου που λέει εάν κάποιος πόρος είναι τώρα σε χρήση – Clear (ελεύθερη), set (σε χρήση), π.χ. Τον εκτυπωτή – Μπορεί κάποια διεργασία A να διακοπεί αφού έχει ανιχνευτεί clear

αλλά πριν γίνει set (διότι μεσολαβεί αρκετός χρόνος για να ανακτηθεί η σημαία από την μνήμη, να αλλάξει από την CPU, και να αποθηκευτεί πίσω στην μνήμη)

– Μια άλλη διεργασία Β ξεκινά, ζητά και αυτή τον εκτυπωτή πιθανή σύγκρουση

– Λύση: Ο έλεγχος και η ενεργοποίηση γίνονται ταυτόχρονα για την κατάλληλη λειτουργία (test & set instruction)

• Ή ενεργοποιώντας μια εντολή “interrupt disable” που αγνοεί τις διακοπές διεργασιών για όσο διαρκεί το test & set

49

Ανταγωνισμός μεταξύ διεργασιών (2) ● Κρίσιμη περιοχή (critical region): ακολουθία εντολών

που πρέπει να εκτελείται από μόνο μία διεργασία τη φορά. – Συνήθως προστατεύεται από το σηματοφορέα. – Για να μπει σε μια κρίσιμη περιοχή, μια διεργασία πρέπει να

βρει το σηματοφορέα clear και να τον θέσει set πριν μπει – Όταν βγει από την κρίσιμη περιοχή, πρέπει να την θέσει clear – Αν μια διεργασία δει το σηματοφορέα set, περιμένει μέχρι

αυτός να γίνει clear • Αμοιβαίος αποκλεισμός (mutual exclusion): η

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

50

Αδιέξοδο ● Αδιέξοδο (deadlock) είναι η κατάσταση κατά την οποία η

εκτέλεση δύο ή περισσοτέρων διεργασιών εμποδίζεται από το να συνεχιστεί.

● Παράδειγμα 1: μια διεργασία Α έχε πρόσβαση στον εκτυπωτή και περιμένει για πρόσβαση στο CD player, μια διεργασία Β το ανάποδο

● Παράδειγμα 2: ένα σύνολο από διεργασίες πρέπει να δημιουργήσουν υπο-διεργασίες, αλλά δεν υπάρχει χώρος στον πίνακα διεργασιών

● Συνθήκες που οδηγούν σε αδιέξοδο (όλες μαζί): 1. Ανταγωνισμός για μη κοινόχρηστους πόρους. 2. Τουλάχιστον δύο πόροι χρειάζονται και από τις δύο διεργασίες. 3. Ένας παραχωρημένος πόρος δεν μπορεί να ανακτηθεί βίαια.

51

Ένα αδιέξοδο που προέκυψε από τον ανταγωνισμό για μία μη κοινόχρηστη σιδηροδρομική διασταύρωση

52

Χρονοπρογραμματισμός και εκχώρηση πόρων

READY

BLOCKED

RUNNING

καταστάσεις μιας διεργασίας επιλογή από διανομέα

αρχή τέλος

Τέλος slice

αρχή Ι/Ο, ζητάει πόρους που δεν υπάρχουν την στιγμή αυτή

τέλος Ι/Ο, πόροι ελευθερώ- θηκαν

Πόροι: μνήμη, χρόνος CPU, Ι/Ο συσκευή

Εκχώρηση πόρων: στατική, δυναμική -> deadlock

53

Παροχέτευση (spooling) ● Μια συνήθης λύση για τα αδιέξοδα είναι το σκότωμα (killing)

της διεργασίας ● Στοχεύει στην απαλοιφή της 3ης συνθήκης ● Ανίχνευση και διόρθωση

● Η παροχέτευση είναι μία τεχνική για την αποδοχή της πρόσβασης πολλών διεργασιών σε έναν κοινό πόρο.

● Αναβάλει την αιτούμενη διεργασία για μία προσφορότερη στιγμή στο μέλλον – Π.χ. Αν χρειάζεται πρόσβαση από 2 διεργασίες στον οδηγό του

εκτυπωτή, το λειτουργικό σύστημα κατευθύνει μια από τις δυο στο να αποθηκεύσουν τα δεδομένα στον σκληρό δίσκο και αργότερα όταν ο εκτυπωτής είναι ελεύθερος να τα μεταφέρει στον οδηγό του εκτυπωτή

– Κάνει ένα μη κοινόχρηστο πόρο να φαίνεται κοινόχρηστος. ● Αγνοεί τις τεχνικές του αποκλεισμού.

54

Χειρισμός Ι/Ο

READY

BLOCKED

RUNNING

αρχή Ι/Ο (σύγχρονου)

τέλος Ι/Ο

διαδικασία spooler

διαδικασία A

printer

next

ready

ουρά αιτήσεων Διαδικασία Α: δεν μπλοκάρει γιατί μεταθέτει στον spooler την εκτέλεση του ασύγχρονου Ι/Ο

Συναλλαγές Ι/Ο: - σύγχρονες (η διαδικασία χρειάζεται άμεσα το αποτέλεσμα για να συνεχίσει) - ασύγχρονες (το αποτέλεσμα δεν επηρεάζει την διαδικασία)

55

Ασφάλεια από εξωτερικές επιθέσεις

● Ασφάλεια με την έννοια της αξιοπιστίας ● Ασφάλεια με την έννοια της προστασίας των πόρων

του υπολογιστή από μη εξουσιοδοτημένους χρήστες ● Λογαριασμοί (accounts) χρηστών

● Πιο συνηθισμένη προστασία: απαιτεί password και όνομα χρήστη. – Πρόβλημα αποτελεί η κλοπή του password. – Πρόβλημα αποτελεί επίσης η αυτοματοποιημένη πρόβλεψη

προφανών κωδικών – Τρόποι αντιμετώπισης:

● Αναφορά όλων των εσφαλμένων προβλέψεων. ● Ενημέρωση του χρήστη για τη σύνδεση του στο σύστημα.

56

Ασφάλεια • Λογισμικό ελέγχου (auditing software): καταγραφή και

ανάλυση των δραστηριοτήτων που γίνονται εντός του συστήματος – Π.χ. Μια σειρά από αποτυχημένες προσπάθειες για login – Π.χ. Έλεγχος με το αν μια διεργασία εμπίπτει στο σύνολο αυτών που

εκτελούνται με βάση το προφίλ του χρήστη

• Λογισμικό όσφρησης (sniffing software): τρέχει στο παρασκήνιο, καταγράφει δραστηριότητες του χρήστη – Χρησιμοποιείται από κάποιον εισβολέα στο σύστημα

57

Ασφάλεια από εσωτερικές απειλές ● Εισβολέας (intruder): μη εξουσιοδοτημένος χρήστης, εκτός

συστήματος ● Κακοήθης (malicious) χρήστης: εξουσιοδοτημένος ● Τα λειτουργικά συστήματα αποτρέπουν την παράνομη

πρόσβαση στους πόρους ενός Η/Υ, η οποία θα μπορούσε να έχει καταστροφικές συνέπειες για το σύστημα. Χρησιμοποιούν: – Διαφορετική μνήμη για διαφορετικές διεργασίες. – Υπάρχουν δυο επίπεδα λειτουργίας CPU (προνομιούχoς – privileged, και

μη προνομιούχoς) • Στο 1ο, η CPU εκτελεί όλες τις εντολές, στο 2ο ένα περιορισμένο υποσύνολο

– Οι προνομιούχες εντολές (αυτές που εκτελούνται στην 1η περίπτωση) επιτρέπονται μόνο στον πυρήνα

• Π.χ εντολές αλλαγής των pointers στη μνήμη

58