Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- skipped:
- 2. Λυση του Peterson, Σηματοφοροι, Προβλημα φιλοσοφων, Προβλημα αναγνωστων-γραφεων
- 3. 42!!!!, ~45 πολυ μεγαλες μνημες, Συγκριση αλγοριθμων, τμηματοποιηση
- 1 {
- Κλήσεις συστήματος: a computer program requests a service from the kernel of the operating system it is executed on.
- }
- 2 {
- Πολυπρογραμματισμος: οταν ενα λειτουργικο μπορει να εκτελεσει παραπανω απο 1 προγραμματα «ταυτοχρονα»
- Στοχος χρονοπρογραμματισμου: Ποια διεργασια θα εκτελεστει μετα απο καποια διακοπη;
- Κατηγοριες Συστηματων:
- -Συστηματα Δεσμης:
- Μεγάλη διεκπεραιωτική ικανότητα και μικρός μέσος χρόνος
- Εξυπηρετηση με βαση τη σειρα αφιξης
- Εξυπηρετηση με βαση τη μικροτερη διαρκεια
- Εξυπηρέτηση με βάση το μικρότερο υπόλοιπo
- Εξυπηρετηση με βαση τη μικροτερη διαρκεια
- Εγγυημενος χρονοπρογραμματισμος (1/n)
- Λοταρια
- Χρονοπρογραμματισμος δικαιης διανομης(κατι σαν τον εγγυημενο χρονοπρογραμματισμο αλλα σε επιπεδο χρηστων)
- -Συστήματα αλληλεπίδρασης: Χαμηλός χρόνος απόκρισης σε αιτήσεις, Τήρηση αναλογιών (οι «απλές» εξυπηρετούνται γρήγορα)
- Προτεραιοτητες:
- -Αναθεση κβαντου αναλογα με προταιρεοτητα{1 στην υψηλη, 2 στην χαμηλη,...} Οταν μια διεργασια εξαντλει το κβανο της υποβιβαζεται
- -Αναθεση προτεραιοτητας με βαση την συμπεριφορα: εστω οτι χρησιμοποιει ποσοστο f του κβαντου τοτε εχει προτεραιοτητα 1/f
- -Συστήματα πραγματικού χρόνου: Τήρηση των προθεσμιών των διεργασιών, Προβλεψιμότητα και ομαλότητα χρονοπρογραμματισμού
- Μη προεκτοπιστικοί αλγόριθμοι:
- – Η τρέχουσα διεργασία εκτελείται μέχρι να μπλοκαριστεί
- Προεκτοπιστικοί αλγόριθμοι:
- – Η τρέχουσα διεργασία εκτελείται μέχρι κάποιο όριο
- Χρονοπρογραμματισμος: κβαντο = x time > χρονος εναλλαγης διεργασιων
- Καλη λυση στον χρονοπρογρμαματισμο ειναι η λοταρια
- Μνημη flash: Δεν υπάρχει χρόνος αναζήτησης/περιστροφής
- Νηματα σε επιπεδο χρηστη:
- -Αν μπλοκαρει το νημα μπλοκαρει και η διεργασια
- Σε επιπεδο πυρηνα:
- -Μεγαλο κοστος για δημιουργια νεων νηματων, παρακαμψη μεσω διατηρησης νηματων σε ανενεργη κατασταση
- +Αντιμετωπιζονται τα μπλοκαριματα, μπορει να επιλεξει αλλο νημα της ιδιας διεργασιας
- Αναδυομενο νημα: δημιουργειται για την εξυπηρετηση καποιου μνμτος(πχ σερβερ)
- Μετατροπη κωδικα για νηματα:
- -Μη επανεισαγωμενες βιβλιοθηκες, δημιουργια νεων βιβλιοθηκων
- -Χειρισμος σηματων ανα νημα ή ανα διεργασια
- Αναμονη με απασχοληση: προσπαθουν συνεχεια να μπουν μεχρι να τα καταφερουν, σπαταλαει πορους, μπορει να εχουμε deadlock
- αντιμετωπιση: sleep & wakeup
- Βελτιωση: απενεργοποιηση διακοπων, επικινδυνο γτ αν κρασαρει η εφαρμογη κρασαρει το συστημα
- }
- Μνήμη {
- First fit: απ την αρχη της μνημης οποια κανει
- Next fit: επομενη μνημη που κανει
- Best fit: η μικροτερη οπη που χωραει
- Worst fit: η μεγαλυτερη οπη που χωραει
- Quick fit: εχω ετοιμες λιστες των πχ 4,5,6KB
- Εικονικη μνημη: υπερθεματα(overlays) κομματια του προγραμματος τα οποια φορτωνονται σταδιακα στη μνημη οταν χρειαστουν
- Σελιδες του προγραμματος αντιστοιχουν σε πλαισια σελιδας(page frames)
- Καθε διευθυνση αποτελειται απο 2 διευθυνσεις:
- -Αριθμος εικονικης σελιδας (περισσοτερο σημαντικα bit)
- -Offset μεσα στην σελιδα (λιγοτερο σημαντικα bit)
- Πινακας σελιδων headers:
- Bit προστασιας (R, R/W Χ,ΝΧ)
- Bit τροποποιησης
- Bit αναφορας: η σελιδα εχει χρησιμοποιηθει προσφατα
- Bit κρυφης μνημης: ειναι ή οχι στην κρυφη μνημη
- MMU: translation between virtual & physical addresses
- TLB: associative cache
- Ηπια αστοχια: η σελιδα δεν υπαρχει στην TLB αλλα υπαρχει στη μνημη
- Αυστηρή αστοχία: η σελιδα δεν υπαρχει ουτε στην TLB ουτε στην μνημη
- Αλγοριθμος NRU: Bits A(αναγνωση), Τ(τροποποιηση)
- Προσομοιωση αν δεν το υποστηριζει το υλικο: ολες οι σελιδες σημειωνονται ως απουσες, στην προσπελαση γινεται σφαλμα κ διακοπη συστηματος, το συστημα ενημερωνει το bit A και μετα βαζει την καταχωρηση κανονικα στον πινακα. Αντιστοιχα με τον Τ
- Κατηγοριες:
- 0: A:0, T:0
- 1: A:0, T:1
- 2: A:1, T:0
- 3: A:1, T:1
- Επιλεγει σελιδα απο 0 προς 3
- Το συστημα περιοδικα μηδενιζει το bit A, τα bit T αν δεν γραφτει στον δισκο δεν μηδενιζεται, μπορει και το συστημα καποια στιγμη να το γραψει μονο του(σπανια)
- -Αλγοριθμος FIFO
- -Αλγοριθμος δευτερης ευκαιριας. Διαλεγει με FIFO, αν Α=1 τοτε Α=0 και την βαζει στο τελος. Ψαχνει για μια παλια και αχρησιμοποιητη σελιδα
- -Αλγοριθμος Ρολογιου: Κυκλικη λιστα σαν ρολοι, προσθεση: μπαινει ακριβως πριν τον δεικτη ετσι ωστε να γινει μια πληρης περιστροφη.....Αν εχουμε σφαλμα κοιταμε εκει που δειχνει ο δεικτης, αν Α=1 το κανουμε 0 και προχωραμε τον δεικτη κατα 1. Αλλιως διαγραφεται
- -Αλγοριθμος LRU:
- 1η προσεγγιση: timestamps(counter) σε καθε εγγραφη στον TLB
- -Προσομοιωση LRU(σε λογισμικο):
- NFU(Not Frequently Used): Σε καθε σελιδα εχουμε εναν μετρητη ο οποιος αποθηκευεται στον TLB. Καθε φορα που εχουμε χτυπο του ρολογιου προσθετουμε το bit Α στον μετρητη και μηδενιζουμε τον μετρητη
- Πρεπει να εισαγουμε την aging(γηρανση): σε καθε διακοπη του ρολογιου οι μετρητες ολισθαινονται προς τα δεξια(σαν να κανουμε /2) και βαζω στο αριστερο ακρο το bit A οποτε ειναι σαν να εχουμε ενα bitmap για το αν χρησιμοποιηθηκε στο τελευταιο, προ τελευταιο διαστημα κλπ
- Συνολο εργασιας διεργασιας: Οι σελιδες που χρησιμοποιει μια διεργασια μια τρεχουσα περιοδο(πχ 5 σελ κωδικα και 5 σελ δεδομενων)
- Αρα προσπαθουμε οταν φερνουμε σελιδες να φερνουμε σελιδες οι οποιες ειναι στο συνολο εργασιας κ οταν απομακρυνουμε να απομακρυνουμε σελιδες που δεν ειναι στο συνολο εργασιας
- Οταν η διεργασια πρεπει να χρησιμοποιηθει ξανα κανει προσελιδοποιηση(prepaging) ετσι ωστε να μην συμβουν πολλα σφαλματα σελιδων
- Αλγοριθμος συνολου εργασιας: σε καθε χτυπο του ρολογιου αν Α==1 τοτε βαζουμε το τρεχων timestamp
- οποτε απομακρυνουμε απ το συνολο εργασιας σελιδες που εχουν ωρα να απομακρυνθουν
- Για καθε σελιδα αν εχει ηλικια > t μπορει να αντικατασταθει αλλιως απ τις πιο προσφατες αντικαταστουμε τις πιο παλιες
- WSClock:
- σαν αλγοριθμος ρολογιου με συνολο εργασιας(δλδ χρησιμοποιει μετρητες για να δουμε τις παλιες σελιδες),
- Οι σελιδες οργανωνονται σε κυκλικη λιστα
- Αν θελουμε να βγαλουμε καποια σελιδα: Αν Α==1 μηδενιζουμε και προχωραμε.
- Αν Α==0 τοτε συγκρινουμε ηλικια με το t. Av ηλικια>t τοτε η σελιδα επιλεγεται.
- Αν η σελιδα ειναι καθαρη τοτε αντικαθιστανται αλλιως προγραμματιζεται για εγγραφη και προχωραμε στην επομενη
- Ο αλγοριθμος δεν σταματα αμεσως μολις βρεθει μια σελιδα, σταματα μολις βρεθουν αρκετες σελιδες προς αντικατασταση ή/και εγγραφη ετσι ωστε οταν χρειαστουμε νεες σελιδες να εχουμε στη διαθεση μας αρκετες σελιδες(παραμετρος n)
- Αν κανουμε πληρη κυκλο και δεν εχει βρεθει διαθεσιμη σελιδα κανουμε συνεχεια:
- Αν εχουμε ηδη χρονοπρογραμματισει μια εγγραφη καποια στιγμη θα ειναι διαθεσιμος ο χωρος οποτε συνεχιζουμε τους κυκλους
- Αν ολες οι σελιδες που περασαμε ειναι καθαρες τοτε παιρνουμε μια σελιδα στην τυχη και την αντικαθιστουμε
- recheck
- Οι καθολοικες πολιτικες μνημης λειτουργουν καλυτερα
- Τοπικοτητα:
- μερικες φορες αν στην τοπικοτητα, δλδ 1/ν ειναι πολυ μεγαλο τοτε μπορει μερικες εφαρμογες να μην μπορουν να λειτουργησουν.
- Αλγοριθμος Συχνοτητας Σφαλματων Σελιδας(PFF): εχουμε εναν γραφο με κατακορυφο αξονα τα σφαλματα και οριζοντιο τον αριθμο σελιδων, σαν την lnx
- αν εχουμε σφαλματα μικροτερα απ το ελαχιστο τοτε ισως εχουμε περιττο αριθμο σελιδων οποτε πρεπει να μειωσουμε, αλλιως αν εχουμε σφαλματα μεγαλυτερα απ το ανω οριο.......
- Αν ο ελεγχος φορτιου δειχνει οτι το PFF ειναι συστηματικα ψηλα παντου κανει swapping καποιες διεργασιες
- Μεγαλες σελιδες: αυξανουν την εσωτερικη κατατμηση
- Μικρες σελιδες: απαιτουν μεγαλο πινακα σελιδων
- Κοινοχρηστες σελιδες: καταμερισμος του κομματιου κωδικα
- Εχουμε πινακα σελιδων κωδικα, που ισως ειναι καταμερισμενος και πινακα σελιδων περιοχης δεδομενων δεδομενων
- Μετα το fork() δειχνουν στον ιδιο πινακα δεδομενων, ο οποιος ειναι read-only. Οταν παει καποιος να γραψει, το συστημα βλεπει οτι στην πραγματικοτητα δεν ειναι read only απλα προς το παρον καταμεριζομενη στις 2 σελιδες και το χουμε read only για να δημιουργιθει παγιδα οταν παει να γραψει καποιος. Αυτο γινεται ομως για καθε σελιδα δλδ μπορει πιο μετα να τερματισουν και οι 2 και οι μισες σελιδες να ειναι κοινοχρηστες επειδη δεν χρειαστηκε να αντιγραφουν. Ενα πλεονεκτημα ειναι οτι αν αμεσως μετα κανει exec η μια διεργασια γλυτωνει την τσαμπα αντιγραφη της μνημης
- Κοινοχρηστες βιβλιοθηκες:
- Στατικη συνδεση(δλδ το κομματι της βιβλιοθηκης να ειναι ενσωματωματομενες στο προμγραμμα) δεν συμφερει διοτι καθε προγραμμα εχει παρει συγκεκριμενες λειτουργιες απο καθε βιβλιοθηκη και ειναι χυμα στην σελιδα
- DLL = Δυναμικες κοινοχρηστες βιβλιοθηκες, δλδ το προγραμμα σημειωνει απο πριν ποιες βιβλιοθηκες θα χρησιμοποιησει, δεν ενσωματονεται τπτ
- Oι DLL φορτωνονται ολοκληρες στη μνημη, οχι συγκεκριμενες συναρτησεις λογω του οτι ειναι κοινοχρηστες
- Καθε διεργασια ρυθμιζει τους δεικτες στην βιβλιοθηκη
- Προϋποθεσεις ανεξαρτητης βιβλιοθηκης:
- 1. πρεπει να ειναι ανεξαρτητης θεσης δλδ ο κωδικας να εκτελειται σε οποιοδηποτε σημειο κ αν φορτωθει, δεν πρεπει να εχει εξαρτησεις απο απολυτες διευθυνσεις, μονο σχετικα αλματα και σχετικες διευθυνσεις
- 2. θα πρεπει να φορτωνεται γενικα σε οριο σελιδας, δεν μπορει να ειναι σε διευθυνση n σε ενα προγραμμα και σε διευθυνση n+1 σε αλλο γτ δεν θα μπορουν να ευθυγραμμιστουν
- Δαιμονας καθαρισμου: ξυπναει περιοδικα και αν εχουμε λιγες διαθεσιμες σελιδες επιλεγει μερικες για αφαιρεση, αν ειναι τροποπ. τις στελνει κ για εγγραφη
- Ο δαιμονας δεν διωχνει τις σελιδες, αν ζητηθουν δλδ ξανα ειναι διαθεσιμες απλα κανει τις εγγραφες στον δισκο
- Swap: δεν εχει συστημα αρχειων, αναφορα απευθειας στα μπλοκ
- Χρηση αρχειων ως περιοχων εναλλαγης(windows): + πιο ευελικτη διαχειρηση χωρου, - πιο αργη αντιστοιχηση(δεν παρακαμπτεται το συστημα αρχειων)
- Ο κωδικας του προγραμματος δεν παει στο swap γιατι ετσι κ αλλιως υπαρχει στο αντιστοιχο αρχειο του στον σκληρο δισκο
- }
- Συστηματα αρχειων {
- Τυποι αρχειων:
- 1. Κανονικα αρχεια
- 2. Φακελοι
- 3. Ειδικα αρχεια χαρακτηρων: σειριακες συσκευες
- 4. Ειδικα αρχεια μπλοκ: συσκευες αποθηκευσης
- }
- Ασφαλεια {
- Επίθεσης επιστροφής στη libc: επιστροφη στην system()
- Προγραμματισμός προσανατολισμένος στο σημείο επιστροφής: εκτελεση τμηματων σε πολλα σημεια κωδικα, σε καθε επιστορφη παμε στο επομενο σημειο. Ουσιαστικα φτιαχνουμε κωδικα απο μικρες ακολουθιες εντολων
- }
- Παλια θεματα:
- recheck:
- . [10] Στην ψηφιακή υπογραφή ενός αρχείου πρώτα χρησιμοποιούμε μία συνάρτηση
- κατακερματισμού στο αρχείο για να παράξουμε ένα μπλοκ σταθερού μήκους και μετά
- κρυπτογραφούμε αυτό το μπλοκ με το ιδιωτικό μας κλειδί. Γιατί δεν κρυπτογραφούμε όλο το
- αρχείο με το ιδιωτικό μας κλειδί;
- δεν ξερω:
- [10] Ποια κατηγορία διεργασιών οργανώνεται στις ουρές του χρονοπρογραμματιστή (scheduler), οι εμποδισμένες (blocked) ή οι έτοιμες (ready), και γιατί; Σε τι είδους ουρές οργανώνονται οι διεργασίες της άλλη κατηγορίας;
- [10] Στην κρυφή μνήμη μπλοκ (block cache) των συστημάτων αρχείων, ποια μπλοκ πρέπει
- να γράφονται πιο γρήγορα στο δίσκο όταν τροποποιούνται, τα μπλοκ των καταλόγων ή τα
- μπλοκ των απλών αρχείων, και γιατί;
- 7. [10] Στη διαχείριση αδιεξόδων, ο εντοπισμός και ανάκαμψη (detection and recovery) μπορεί
- να χρησιμοποιεί σχεδόν τον ίδιο αλγόριθμο με την αποφυγή αδιεξόδων (deadlock avoidance).
- Σε τι διαφέρουν λοιπόν οι δύο προσεγγίσεις;
- 10. [10] Στα συστήματα Linux ο χρήστης αρχικά δίνει το όνομα (username) και τον κωδικό
- (password) του σε μία διεργασία επιπέδου πυρήνα, αλλά αφού συνδεθεί στο σύστημα ο
- φλοιός (shell) του εκτελείται σε επίπεδο χρήστη. Γιατί η αλλαγή από επίπεδο σε πυρήνα σε
- επίπεδο χρήστη πρέπει να γίνει αφού ελεγχθεί ο κωδικός του χρήστη και όχι πριν;
- [10] Σε ένα σύστημα UNIX/Linux αφού καλέσουμε την κλήση fork(), η διεργασία γονέας και η
- διεργασία παιδί είναι αρχικά πανομοιότυπες. Αν θεωρήσουμε ότι η μνήμη της διεργασίας
- αποτελείται από κώδικα, δεδομένα και στοίβα, ποια από αυτά τα κομμάτια μπορεί να
- διαφοροποιηθούν όσο εκτελούνται οι δύο αυτές διεργασίες, και γιατί;
- [10] Γιατί οι λύσεις αμοιβαίου αποκλεισμού (busy waiting) που χρησιμοποιούν αναμονή με
- απασχόληση (με χρήση εντολών τύπου TSL και XCHG) αντί για εμποδισμό διεργασιών
- θεωρούνται σπάταλες από πλευράς πόρων επεξεργασίας; Πότε έχει νόημα να
- χρησιμοποιείται αναμονή με απασχόληση αντί για εμποδισμός;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement