Λειτουργικά συστήματα I

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Εισαγωγή

Καλώς ήρθατε

Λειτουργικά Συστήματα Ι

Διομήδης Σπινέλλης <dspin@aegean.gr (mailto:dspin@aegean.gr)>
Εισαγωγή στη θεωρία, πράξη, και χρήση των λειτουργικών συστημάτων
Θεωρητική διδασκαλία
Εργαστήριο
Ασκήσεις
Πρόοδος
Εξετάσεις
Θεωρία Τετάρτη 12:00-14:00
Εργαστήριο Τετάρτη 16:00-18:00

Τι περιλαμβάνει το μάθημα

Εισαγωγή
Διεργασίες
Διαχείριση μνήμης
Αλγόριθμοι διαχείρισης μνήμης
Συστήματα αρχείων
Θέματα ασφάλειας
Είσοδος και έξοδος
Αδιέξοδα
Δομή του λειτουργικού συστήματος Unix
Δομή του λειτουργικού συστήματος Windows-NT
Ανασκόπηση - επανάληψη

Οι σημειώσεις

Δε θα μοιράζονται
Βασίζονται στο βιβλίο Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. Εκδόσεις Παπασωτηρίου, 1993.
Προσβάσιμες από το WWW:http://kerkis.math.aegean.gr/~dspin/os1 (http://kerkis.math.aegean.gr/~dspin/os1)
Δεν καλύπτουν όλο το μάθημα

Ο ρόλος του λειτουργικού συστήματος

Προγραμματισμός ενός Η/Υ σε επίπεδα

Υλικό
Μικροπρόγραμμα (microcode)
Γλώσσα μηχανής
Λειτουργικό σύστημα (operating system)
Προγράμματα εφαρμογών (application programs)

Το λειτουργικό σύστημα ως εκτεταμένη μηχανή (extended machine)

Απομονώνει τον προγραμματιστή από την πολυπλοκότητα του υπολογιστή
Διευκολύνει τη μεταφερσιμότητα (portability) των εφαρμογών.
Παρουσιάζει στις εφαρμογές ιδεατό (virtual) υλικό

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

Επιτρέπει τον πολυπρογραμματισμό
Επιτρέπει τη χρήση από πολλούς χρήστες
Επιβάλλει πολιτικές διαχείρισης και ασφάλειας

Ιστορική ανασκόπηση

Συστήματα μαζικής επεξεργασίας (batch processing system)
Πολυπρογραμματισμός (multiprogramming) (IBM 360)
Ετεροχρονισμός (spooling)
Καταμερισμός του χρόνου (timesharing) (MULTICS)
Διαλογική επεξεργασία (interactive processing) (Unix, CP/M, MS-DOS)
Κατανεμημένα λειτουργικά συστήματα (distributed operating systems) (Mach, Amoeba)
Γραφική επικοινωνία (Windows 95, NT)

Δομή

Μονολιθικά συστήματα
Στρωματοποιημένα συστήματα
Ιδεατές μηχανές
Μοντέλο εξυπηρετούμενου εξυπηρετητή
Μοντέλο μικροπυρήνα (microkernel) (διαχωρισμός μηχανισμού / πολιτικής)

Γενική βιβλιογραφία

Maurice J. Bach. The Design of the UNIX Operating System. Prentice-Hall, 1986.
F. P. Brooks. The Mythical Man Month. Addison-Wesley, 1975.
Intel Corporation. i486 Processor Programmer's Reference Manual. McGraw-Hill, 1990.
Computing systems. Published by the Usenix Association.
H. M. Deitel and M. S. Kogan. The Design of OS/2. Addison-Wesley, 1992.
Dorothy Elizabeth Robling Denning. Cryptography and Data Security. Addison-Wesley, 1983.
Peter J. Denning. Computers Under Attack: Intruders, Worms, and Viruses. Addison-Wesley, 1990.
European UNIX systems User Group. Conference Proceedings, 1988-1991.
John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers, 1990.
C. A. R. Hoare. Communicating Sequential Processes. Prentice–Hall, 1985.
Brian W. Kernighan and Rob Pike. The UNIX Programming Environment. Prentice-Hall, 1984.
Samuel J. Leffler, Marshall Kirk McKusick, Michael J. Karels, and John S. Quarterman. The Design and Implementation of the 4.3BSD Unix Operating System. Addison-Wesley, 1988.
Operating systems review. Published by the Association for Computing Machinery.
W. Richard Stevens. Advanced Programming in the UNIX Environment. Addison-Wesley, 1992.
AT & T, editor. UNIX System Readings and Applications, volume I, II. Prentice-Hall, 1987.
Andrew S. Tanenbaum. Operating Systems: Design and Implementation. Prentice-Hall, 1987.
USENIX Association. Conference Proceedings, 1986-1997.
Mitchell Waite, editor. UNIX Papers for UNIX Developers and Power Users. Howard W. Sams & Company, 1987.

Βιβλιογραφία

Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 3-38 Εκδόσεις Παπασωτηρίου, 1993.

Ασκήσεις

Άσκηση OS01

Να αναφέρετε προβλήματα που θα ανέκυπταν αν η χρήση των Η/Υ γινόταν χωρίς τη διαμεσολάβηση λειτουργικού συστήματος.
Δώστε ένα παράδειγμα από τη δική σας εμπειρία για κάθε μια από τις βασικές έννοιες του λειτουργικού συστήματος.
Αν θεωρήσουμε το Internet ως ένα μεγάλο λειτουργικό σύστημα, ποιά είναι η δομή του;

Διεργασίες

Εκτέλεση διεργασιών

Διαφορά διεργασίας και προγράμματος
Ιεραρχίες διεργασιών
Καταστάσεις διεργασιών

Μεταβάσεις

Αναστολή λόγω αναμονής εξωτερικού συμβάντος
- Επιλογή της διεργασίας από το χρονοπρογραμματιστή
- Λήξη της αναμονής του εξωτερικού συμβάντος

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

Διαχείριση διεργασιών	Διαχείριση μνήμης	Διαχείριση αρχείων
Καταχωρητές Δείκτης εντολών προγράμματος Λέξη κατάστασης προγράμματος Δείκτης στοίβας Κατάσταση διεργασίας Χρόνος εκκίνησης διεργασίας Χρόνος χρήσης CPU	Δείκτες σε τμήμα κώδικα Δείκτες σε τμήμα δεδομένων Ταυτότητα χρήστη και ομάδας Χάρτης δυαδικών ψηφίων για σήματα	Πρωταρχική διαδρομή Περιγραφείς αρχείων Δυαδικά ψηφία δημιουργίας αρχείων (umask)

Εκτέλεση διακοπής
- Καταχώρηση δείκτη εντολών και κατάστασης στη στοίβα
- Νέος δείκτης εντολών από διάνυσμα διακοπής (interrupt vector)
- Εκτέλεση διαδικασίας συμβολικής γλώσσας
- Φύλαξη καταχωρητών
- Αλλαγή κατάστασης
- Εκτέλεση διεργασίας χρονοπρογραμματισμού
- Επιλογή επόμενης διεργασίας
- Επιστροφή στη διαδικασία συμβολικής γλώσσας
- Επιστροφή στη νέα τρέχουσα διεργασία

Συνθήκες ανταγωνισμού

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

Παράδειγμα

int counter;

process_one()
{
	int i;

	i = counter;
	i = i + 1;
	counter = i;
}

process_two()
{
	int i;

	i = counter;
	i = i + 1;
	counter = i;
}

Κρίσιμα τμήματα

Το τμήμα του κώδικα μιας διεργασίας το οποίο δεν είναι ασφαλές να εκτελεστεί παράλληλα με άλλη διεργασία ονομάζεται κρίσιμο τμήμα (critical section).

Κάθε λύση στο πρόβλημα του αμοιβαίου αποκλεισμού (mutual exclusion) μεταξύ των κρίσιμων τμημάτων πρέπει να εξασφαλίζει:

Μια το πολύ διεργασία μπορεί να εκτελεί ένα κρίσιμο τμήμα.
Δεν επιτρέπονται υποθέσεις σχετικά με την ταχύτητα ή το πλήθος των επεξεργαστών.
Διεργασία που δε βρίσκεται σε κρίσιμο τμήμα δεν επιτρέπεται να αναστείλει άλλες διεργασίες
Ο χρόνος στον οποίο μια διεργασία θα εισέλθει στο κρίσιμο τμήμα της πρέπει να είναι πεπερασμένος.

Ενεργός αναμονή

Ορισμένοι τρόποι για την επίτευξη του αμοιβαίου αποκλεισμού είναι οι παρακάτω:

Απενεργοποίηση των διακοπών
Αυστηρή εναλλαγή
Λύση του Peterson (προσθήκη μεταβλητής "ενδιαφέροντος")
Η εντολή TSL

Όλες οι παραπάνω λύσεις επιβάλουν στη διαδικασία που αναμένει να εκτελεί εντολές.

Απενεργοποίηση και αφύπνιση

Η οργάνωση της διαδιεργασιακής επικοινωνίας γίνεται χρησιμοποιόντας αφηρημένες βασικές αρχές διαδιεργασιακής επικοινωνίας (interprocess communication primitives). To ζεύγος

απενεργοποίηση (sleep).
αφύπνιση (wakeup).

είναι μια τέτοια αρχή. Με τις κλήσεις αυτές μπορεί να εκφραστεί το πρόβλημα του παραγωγού-καταναλωτή (producer-consumer).


const N = 100;

int queue[N];
int count;

void
producer(void)
{
	int item;

	for (;;) {
		create(&item);
		if (count == N)
			sleep();
		count = count + 1;
		queue[count - 1] = item;
		if (count == 1)
			wakeup(consumer);
	}
}

void
consumer(void)
{
	int item;

	for (;;) {
		if (count == 0)
			sleep();
		item = queue[count - 1];
		count = count - 1;
		if (count == N - 1)
			wakeup(producer);
		consume(&item);
	}
}

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

Σημαφόροι

To ζεύγος των σημαφόρων (semaphores)

UP
DOWN

επιτρέπει την οργάνωση της διαδιεργασιακής επικοινωνίας μια και αυτοί εκφράζουν ατομικές ενέργειες (atomic action). Με τις κλήσεις αυτές μπορεί να λυθεί το πρόβλημα του παραγωγού-καταναλωτή.

const N = 100;

semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void
producer(void)
{
	int item;

	for (;;) {
		create(&item);
		down(&empty);

		down(&mutex);
		count = count + 1;
		queue[count - 1] = item;
		up(&mutex)

		up(&full);
	}
}

void
consumer(void)
{
	int item;

	for (;;) {
		down(&full);

		down(&mutex);
		item = queue[count - 1];
		count = count - 1;
		up(&mutex);

		up(&empty);
		consume(&item);
	}
}

Παρακολουθητές

Οι παρακολουθητές (monitors) είναι δομή της γλώσσας προγραμματισμού που εξασφαλίζει ότι σε μια συγκεκριμένη χρονική στιγμή μπορεί να εκτελείται. το πολύ μια διαδικασία μέσα στον παρακολουθητή.

Η δομή αυτή εξασφαλίζει τον αμοιβαίο αποκλεισμό κρισίμων τμημάτων. H αναστολή διεργασιών που δεν μπορούν να συνεχίσουν εξασφαλίζεται με τη χρήση των μεταβλητών συνθήκης (condition variables)

wait
signal

Μεταβίβαση μηνύματος

Άλλος τρόπος διαδιεργασιακής επικοινωνίας είναι η χρήση της μεταβίβαση μηνύματος (message passing) που μπορεί να εκφραστεί με τις διαδικασίες:

send(destination, message)
receive(destination, message)

Ο συντονισμός της αποστολής και της παραλαβής μπορεί να γίνει:

με τη χρήση γραμματοκιβωτίων (mailbox) ή
με τον καθορισμό συνάντησης (rendezvous).

Με τις κλήσεις αυτές μπορεί να εκφραστεί το πρόβλημα του παραγωγού-καταναλωτή.


const N = 100;

int queue[N];

void
producer(void)
{
	int item;
	message m;

	for (;;) {
		create(&item);
		receive(consumer, &m);
		build_message(item, &m);
		send(consumer, &m);
	}
}

void
consumer(void)
{
	int item;
	message m;

	for (i = 0;  i < 100; i++)
		send(producer, &m);
	for (;;) {
		receive(producer, &m);
		extract_item(&m, &item);
		send(producer, &m);
		consume(&item);
	}
}

Κλασικά προβλήματα

To πρόβλημα των συνδαιτημόνων φιλοσόφων

Λύσεις (σωστές και λανθασμένες):

Λαμβάνουμε το αριστερό πηρούνι και περιμένουμε το δεξί
Χρήση ενός σημαφόρου για όλους τους φιλοσόφους
Χρήση ενός σημαφόρου ανά φιλόσοφο και μεταβλητής κατάστασης

Χρονοπρογραμματισμός

Τη σειρά εκτέλεσης των διεργασιών αναλαμβάνει ο χρονοδρομολογητής (scheduler) με βάση τον αλγόριθμο χρονοπρογραμματισμού (scheduling algorithm). Αυτός πρέπει να εξασφαλίζει:

Δικαιοσύνη (fairness)
Αποδοτικότητα (efficiency)
Ελάχιστο χρόνο απόκρισης (response time)
Ελάχιστο χρόνο διεκπεραίωσης (turnaround time)
Μέγιστο ρυθμό απόδοσης (throughput)

Διακρίνουμε

χρονοπρογραμματισμό προεκχώρισης (preemptive scheduling)
μη προεκχωρητικό χρονοπρογραμματισμό (nonpreemptive scheduling)

Ως πολιτική χρονοπρογραμματισμού μπορούμε να έχουμε:

χρονοπρογραμματισμό εξυπηρέτησης εκ' περιτροπής (round robin scheduling)
χρονοπρογραμματισμό προτεραιοτήτων (priority scheduling)
συντομότερη εργασία πρώτα (shortest job first)
Εγγυημένο χρονοπρογραμματισμό
Χρονοπρογραμματισμό δύο επιπέδων (για κύρια και βοηθητική μνήμη)

Βιβλιογραφία

Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 39-101 Εκδόσεις Παπασωτηρίου, 1993.

Maurice J. Bach. The Design of the UNIX Operating System, pages 146–268, 355–389. Prentice-Hall, 1986.
Samuel J. Leffler, Marshall Kirk McKusick, Michael J. Karels, and John S. Quarterman. The Design and Implementation of the 4.3BSD Unix Operating System, pages 69–107, 281–309. Addison-Wesley, 1988.
Andrew S. Tanenbaum. Operating Systems: Design and Implementation, pages 45–105. Prentice-Hall, 1987.

Εργασία στο εργαστήριο

Παρακολουθήστε την έξοδο της εντολής ps:

athena:~> ps -aux | more
USER       PID %CPU %MEM SIZE  RSS TTY STAT START   TIME COMMAND
Barekos  30536  0.0  1.7  426  560  ?  S    17:16   0:00 -tcsh
Barekos  30541  0.1  1.0  136  332  ?  S    17:17   0:02 bot
bin         42  0.0  0.7   80  220  ?  S   Oct 22   0:03 /usr/sbin/rpc.portmap
dspin    29194  0.0  1.8  448  592 pp1 S    15:48   0:02 -tcsh
dspin    31282  0.0  0.7   96  224 pp1 R    17:56   0:00 ps aux
dspin    31283  0.0  0.4   40  152 pp1 S    17:56   0:00 more
gkarydas 30544  0.0  1.7  426  556  ?  S    17:17   0:00 -tcsh
gkarydas 30553  0.2  1.0  168  344  ?  S    17:17   0:04 bot
root         1  0.0  0.6   48  216  ?  S   Oct 22   2:22 init auto
root         6  0.0  0.2   32   76  ?  S   Oct 22   0:01 bdflush (daemon)
root         7  0.0  0.2   32   84  ?  S   Oct 22   0:39 update (bdflush)
root        23  0.0  0.5   56  188  ?  S   Oct 22   0:24 /usr/sbin/crond -l10
root        39  0.0  0.5   57  188  ?  S   Oct 22   0:15 /usr/sbin/syslogd
root        40  0.2  0.6   40  212  ?  S   Oct 22  24:51 /usr/sbin/klogd
root        44  0.0  0.7   68  224  ?  S   Oct 22   0:23 /usr/sbin/inetd
root        46  0.0  0.5   64  164  ?  S   Oct 22   0:03 /usr/sbin/lpd
root        48  0.0  0.4   60  140  ?  S   Oct 22   0:03 /usr/sbin/rpc.ugidd -d
root        52  0.0  0.4  108  152  ?  S   Oct 22   0:03 /usr/sbin/rpc.mountd
root        54  0.0  0.6  124  196  ?  S   Oct 22   0:03 /usr/sbin/rpc.nfsd
root        61  0.0  0.8  784  260  ?  S   Oct 22   0:32 /usr/local/www/httpd -d

Βλέπετε τα χαρακτηριστικά κάθε διεργασίας καθώς και την κατάστασή της.

Δοκιμάστε να δείτε το δάσος των διεργασιών:

athena:~> ps -af
> ps -af
  PID TTY STAT  TIME COMMAND
   69 v02 S     0:00 /sbin/agetty 38400 tty2
   70 v03 S     0:00 /sbin/agetty 38400 tty3
  277 v01 S     0:00 /sbin/agetty 38400 tty1
17325 v04 S     0:00 /sbin/agetty 38400 tty4
16063 pq2 S     0:00 -bin/tcsh
29267 pq3 S     0:00 -bin/tcsh
29310 pq3 S     0:00  \_ ftp
11372 pq0 S     0:00 -bin/tcsh
11389 pq1 S     0:00 -bin/tcsh
29194 pp1 S     0:02 -tcsh
31295 pp1 S     0:00  \_ vi
31296 pp1 S     0:00      \_ -bin/tcsh
31297 pp1 R     0:00          \_ ps -af

Στον κατάλογο /proc μπορείτε να δείτε στοιχεία των διεργασιών:

athena:~> cd /proc/self
athena:/proc/self> ls -l
total 0
-r--r--r--   1 dspin    users           0 Oct 29 18:01 cmdline
lrwx------   1 dspin    users          64 Oct 29 18:01 cwd -> [0001]:1913257986
-r--------   1 dspin    users           0 Oct 29 18:01 environ
lrwx------   1 dspin    users          64 Oct 29 18:01 exe -> [0301]:36649
dr-x------   2 dspin    users           0 Oct 29 18:01 fd/
pr--r--r--   1 dspin    users           0 Oct 29 18:01 maps|
-rw-------   1 dspin    users           0 Oct 29 18:01 mem
lrwx------   1 dspin    users          64 Oct 29 18:01 root -> [0301]:2
-r--r--r--   1 dspin    users           0 Oct 29 18:01 stat
-r--r--r--   1 dspin    users           0 Oct 29 18:01 statm
athena:/proc/self> cat environ
TERM=vt100HZ=100HOME=/home2/staff/dspinSHELL=/bin/tcshPATH=/bin:/usr/bin:/usr/lo
cal/bin:/usr/X386/bin:/usr/TeX/binUSER=dspinLOGNAME=dspinMAIL=/var/spool/mail/ds
pin
athena:/proc/self>

Μπορείτε να δείτε την κατάσταση των διακοπών από το αρχείο /proc/interrupts:

kerkis:/proc$ more /proc/interrupts
 0:    1499266   timer
 1:          2   keyboard
 2:          0   cascade
 4:          4 + serial
10:      29113   3c509
13:          1   math error
14:      62272 + ide0

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

Απλή διαχείριση μνήμης

Η διαχείριση μνήμης (memory managemenr) επιτρέπει στο λειτουργικό σύστημα την καλύτερη δυνατή κατανομή μνήμης ανάμεσα σε διεργασίες.

Σε συστήματα που εξυπηρετούν μια διεργασία η μνήμη μπορεί να οργανωθεί ως εξής:

Πρόγραμμα χρήστη

Λειτουργικό σύστημα στη RAM

Λειτουργικό σύστημα σε ROM

Πρόγραμμα χρήστη

Οδηγοί συσκευών σε ROM (BIOS)

Πρόγραμμα χρήστη

Λειτουργικό σύστημα σε RAM

Προλυπρογραμματιστικά συστήματα μπορούν να διαχειριστούν τη μνήμη σε σταθερά τμήματα.
Η αύξηση της μνήμης αυξάνει την αξιοποίηση του επεξεργαστή αυξάνοντας το βαθμό πολυπρογραμματισμού.
Η διαχείριση της μνήμης μπορεί να επιτευχθεί με το διαχωρισμό της σε σταθερά τμήματα. Οι εργασίες για τα τμήματα αυτά μπορούν να επιλέγονται:
- από μια ουρά για όλα τα τμήματα.
- από μια ουρά ανά τμήμα ανάλογα με το μέγεθός του.
Η μετατόπιση (relocation) επιτρέπει σε προγράμματα και δεδομένα να εκτελούνται αδιάφορα από το τμήμα της μνήμης στο οποίο έχουν φορτωθεί.
Η προστασία (protection) απομονώνει τις διαφορετικές διεργασίες. Το λειτουργικό σύστημα διασφαλίζει ότι κάθε διεργασία απαγορεύει σε άλλες διεργασίες την πρόσβαση στη μνήμη της. Αυτό μπορεί να επιτευχθεί με τη χρήση ειδικών καταχωρητών:
- του καταχωρητή βάσης (base register) και
- του καταχωρητή ορίου (limit register)

Εναλλαγή

Η εναλλαγή (swapping) μέσω της μετακίνησης διεργασιών από τη μνήμη στο δίσκο και αντίστροφα επιτρέπει την ταυτόχρονη εκτέλεση περισσοτέρων διεργασιών απ' όσες χωράν στην κεντρική μνήμη.

Σε συστήματα που βασίζονται σε εναλλαγή η διαχείριση της μνήμης γίνεται με βάση μεταβλητά τμήματα.

Καταμερισμός μνήμης

Η διαχείριση της μνήμης μπορεί να γίνει με:

συμπίεση μνήμης (memory compaction)
χάρτη δυαδικών ψηφίων (bit map)
συνδεδεμένη λίστα (linked list)
το σύστημα των φίλων (buddy system)

Η επιλογή του τμήματος της μνήμης από τη λίστα μπορεί να γίνει με ένα από τα παρακάτω κριτήρια:

πρώτη τοποθέτηση (first fit) (υπερβολική χρήση των πρώτων τμημάτων)
επόμενη τοποθέτηση (next fit) (χειρότερη απόδοση)
καλύτερη τοποθέτηση (best fit) (χειρότερη απόδοση και κατακερματισμός)
χειρότερη τοποθέτηση (worst fit) (χειρότερη απόδοση και κατακερματισμός)
γρήγορη τοποθέτηση (quick fit)

Ιδεατή μνήμη

Η ιδεατή μνήμη (virtual memory) παρουσιάζει στις διεργασίες παραπάνω μνήμη από αυτή που διαθέτει το σύστημα. Αυτό γίνεται χρησιμοποιώντας ιδεατές διευθύνσεις (virtual addresses) οι οποίες μεταφράζονται σε πραγματικές από τη μονάδα διαχείρισης μνήμης (memory management unit).

Ο χώρος των ιδεατών διευθύνσεων διαιρείται σε ίσα μέρη: τις σελίδες (pages).
Ο χώρος της φυσικής μνήμης (physical memory) διαιρείται αντίστοιχα σε πλαίσια σελίδας (page frames).
Ένα bit παρουσίας (present bit) για κάθε ιδεατή σελίδα δηλώνει αν η αντίστοιχη σελίδα βρίσκεται στην πραγματική μνήμη.
Αν δεν υπάρχει καλείται το λειτουργικό σύστημα με αιτία το λάθος παρουσίας (page fault).
Το λειτουργικό σύστημα πρέπει να αντικαταστήσει τη σελίδα με βάση τον πίνακα σελίδων (page table).
Αυτός μπορεί να οργανωθεί σε πολλαπλά επίπεδα ή και αντεστραμμένα για οικονομία μνήμης.
Η πρόσβαση σε αυτόν γίνεται με τη βοήθεια της ενδιάμεσης μνήμης μετάφρασης (translation lookaside buffer) που είναι υλοποιημένη με συσχετιστική μνήμη (associative memory).
Η αποδοτικότητά της μετράται με βάση το ποσοστό επιτυχιών (hit ratio)

Αντικατάσταση σελίδων

Η αντικατάσταση των σελίδων μπορεί να γίνει:

με αλγόριθμο βέλτιστης αντικατάστασης σελίδας (optimal page replacement algorithm) με βάση το χρόνο της μελλοντικής χρήσης της.
Ο θεωρητικά βέλτιστος αυτός αλγόριθμος είναι αδύνατο να υλοποιηθεί στην πράξη αφού προϋποθέτει πρόβλεψη της μελλοντικής συμπεριφοράς των διεργασιών.
με βάση τη σελίδα που δε χρησιμοποιήθηκε πρόσφατα (Not Recently Used).
- Κάθε σελίδα διαθέτει δύο bit τα οποία περιέχουν 1 αν η σελίδα αυτή έχει διαβαστεί ή γραφεί.
- Περιοδικά τα bit αυτά τίθενται σε 0 και με τον τρόπο αυτό μπορούν να βρεθούν σελίδες που δεν έχουν πρόσφατα χρησιμοποιηθεί.
- Η εγγραφή των bit μπορεί να γίνεται από τον επεξεργαστή, ή από το λειτουργικό σύστημα με τη χρήση του λάθους σελίδας σε κάθε πρώτη πρόσβαση μετά την εκκαθάρισή τους.
με βάση την αρχή πρώτη σελίδα μέσα πρώτη σελίδα έξω (first page in first page out) (FIFO)
με τον αλγόριθμο αντικατάστασης δεύτερης ευκαιρίας (second chance replacement algorithm).
Τροποποίηση του παραπάνω αλγορίθμου έτσι ώστε σελίδες που έχουν χρησιμοποιηθεί πρόσφατα όταν είναι υποψήφιες για αντικατάσταση να μεταφέρονται πάλι στην αρχή της ουράς.
με τον αλγόριθμο του ρολογιού.
Τροποποίηση του παραπάνω αλγορίθμου έτσι ώστε ο έλεγχος για τις σελίδες που έχουν χρησιμοποιηθεί να γίνεται κυκλικά και να μη μεταφέρονται στην αρχή της ουράς.
με βάση την αρχή λιγότερο πρόσφατα χρησιμοποιούμενης σελίδας (least recently used)
Κάθε σελίδα σχετίζεται με έναν μετρητή χρόνου ο οποίος περιέχει το χρόνο της τελευταίας πρόσβασης. Οι σελίδες με την παλιότερη πρόσβαση είναι αυτές που απομακρύνονται.
με βάση την αρχή λιγότερο συχνά χρησιμοποιούμενης σελίδας (not frequently used)
Κάθε σελίδα σχετίζεται με έναν μετρητή ο οποίος μετράει τον αριθμό των προσβάσεων στη σελίδα. Η σελίδες με τις λιγότερες προσβάσεις είναι αυτές που απομακρύνονται. Ο αλγόριθμος μπορεί να τροποποιηθεί με την προσθήκη της έννοιας της γήρανσης (aging) όπου οι μετρητές διαιρούνται με το 2 σε τακτικά χρονικά διαστήματα.

Σχεδιασμός σελιδοποίησης

Σύνολο εργασίας (working set) είναι το σύνολο των σελίδων που χρησιμοποιούνται από μια διεργασία μια δεδομένη χρονική στιγμή.
Όταν η διαθέσιμη μνήμη μιας διεργασίας είναι σημαντικά μικρότερη από το σύνολο εργασίας της τότε σημειώνεται απότομη πτώση της απόδοσης (thrashing)
Η προσέγγιση με βάση το μοντέλο συνόλου εργασίας (working set model) έχει την εξής βάση: πριν εκτελεστεί μια διεργασία καταβάλλεται προσπάθεια έτσι ώστε να βρίσκεται το σύνολο εργασίας της στη μνήμη.
Για το σκοπό αυτό φορτώνονται οι σελίδες στη μνήμη με τη διαδικασία της προσελιδοποίησης (prepaging).
H επιλογή της σελίδας που θα αντικατασταθεί μπορεί να γίνει είτε λαμβάνοντας υπόψη μόνο τις σελίδες της διαδικασίας στην οποία ανήκει το σφάλμα σελίδας υλοποιώντας δηλαδή έναν τοπικό αλγόριθμο αντικατάστασης σελίδων (local page replacement algorithm) ή κοιτάζοντας όλες τις σελίδες του λειτουργικού συστήματος υλοποιώντας δηλαδή έναν ολικό αλγόριθμο αντικατάστασης σελίδων (global page replacement algorithm).
Το μέγεθος της σελίδας είναι ευθέως ανάλογο με τη μνήμη που σπαταλάται σε σελίδες που είναι μερικώς μόνο γεμάτες και αντιστρόφως ανάλογο με το χώρο που απαιτείται για τη φύλαξη των πινάκων σελίδων και την ενδιάμεση μνήμη μνήμη μετάφρασης.

Επανεκκίνηση εντολής

Μια εντολή μηχανής μπορεί να διακοπεί στη μέση της εκτέλεσής της. Την επανεκκίνηση της εντολής

μπορεί να αναλάβει ο επεξεργαστής από το σημείο στο οποίο σταμάτησε ή
το λειτουργικό σύστημα από την αρχική της κατάσταση.

Θέματα υλοποίησης

Κλείδωμα σελίδων

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

Σελιδοποίηση κώδικα και δεδομένων

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

Διαμοιραζόμενες σελίδες

Ειδικά τις σελίδες του κώδικα ή στατικών δεδομένων (π.χ. το κείμενο βοηθείας μιας εφαρμογής) μπορούν να τις μοιράζονται και περισσότερες από μια διαδικασίες μια και αυτές δεν μεταβάλλονται.

Διεργασία σελιδοποίησης

Η διεργασία σελιδοποίησης (paging daemon) τρέχει στο περιθώριο με σκοπό να ερευνά τις σελίδας και να καταγράφει σελίδες που είναι υποψήφιες για αντικατάσταση.

Κατάτμηση

Η κατάτμηση (segmentation) επιτρέπει το διαχωρισμό της μνήμης μιας διεργασίας σε πολλά γραμμικά τμήματα. Τα τμήματα αυτά για κάθε διεργασία μπορούν να περιέχουν:

Τον κώδικα
Τη στοίβα
Τα αρχικοποιημένα δεδομένα
Το χώρο ανάπτυξης της δυναμικής μνήμης

Η κατάτμηση επιτρέπει:

την εύκολη μεταφορά του κώδικα, αφού κάθε τμήμα του εκφράζεται σχετικά με την αρχή του τμήματος.

την προστασία των δεδομένων ανάλογα με τον τύπο τους. Π.χ.

Κώδικας	Μόνο εκτέλεση
Αρχικοποιημένα δεδομένα	Μόνο ανάγνωση
Σωρός	Ανάγνωση και εγγραφή
Δυναμική μνήμη	Ανάγνωση και εγγραφή

Την υλοποίηση διαμοιραζομένων βιβλιοθηκών (shared libraries)

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

Βιβλιογραφία

Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 103-198 Εκδόσεις Παπασωτηρίου, 1993.

Maurice J. Bach. The Design of the UNIX Operating System, pages 271–352. Prentice-Hall, 1986.
Bruce Javob and Trevor Mudge. Virtual memory: Issues of implementation. Computer, 31(6):33–43, June 1998.
Samuel J. Leffler, Marshall Kirk McKusick, Michael J. Karels, and John S. Quarterman. The Design and Implementation of the 4.3BSD Unix Operating System, pages 109–163. Addison-Wesley, 1988.
Andrew S. Tanenbaum. Operating Systems: Design and Implementation, pages 191–247. Prentice-Hall, 1987.

Εργασία στο εργαστήριο

Παρατηρήστε στοιχεία της μνήμης από την έξοδο της εντολής vmstat:

vmstat 1
 procs                  memory    swap        io    system         cpu
 r b w  swpd  free  buff cache  si  so   bi   bo   in   cs  us  sy  id
 1 0 0     0   300  6572  9032   0   0   17    3  106   17   1   1  99
 1 0 0     0   272  6372  8892   0   0    0   73  145   25  94   5   1
 1 0 0     0  1552  6284  8784   0   0   74   47  141  153  54  43   3
 1 0 0     0  1228  6284  8784   0   0    0    0  105    9  97   3   0
 1 0 0     0   852  6284  8784   0   0    0    0  105   13  97   3   0
 1 0 0     0  2552  6284  8768   0   0    0   45  139  133  73  23   4
 1 0 0     0   960  6348  8768   0   0    1   77  130   55  74  13  14
 1 0 0     0   952  6348  8768   0   0    0   12  113   63  81  19   0
 1 0 0     0   964  6348  8772   0   0    2   24  123   82  73  25   2
 1 0 0     0  1052  6348  8772   0   0    0   24  122   83  83  16   2
 1 0 0     0  2484  6348  8772   0   0    0   36  131  120  67  32   1
 1 0 0     0  2416  6348  8772   0   0    0  113  136   68  80  15   6
 2 0 0     0  2404  6348  8772   0   0    0   48  141  164  57  40   3

και από το περιεχόμενο του αρχείου meminfo:

kerkis:/proc$ more /proc/meminfo
        total:    used:    free:  shared: buffers:  cached:
Mem:  31559680 31137792   421888 15089664  3870720  7208960
Swap:        0        0        0
MemTotal:     30820 kB
MemFree:        412 kB
MemShared:    14736 kB
Buffers:       3780 kB
Cached:        7040 kB
SwapTotal:        0 kB
SwapFree:         0 kB

Συστήματα αρχείων

Απαιτήσεις

Η φύλαξη δεδομένων σε αρχεία ικανοποιεί τις παρακάτω απαιτήσεις:

Αποθήκευση και ανάκτηση μεγάλων ποσοτήτων δεδομένων
Διατήρηση των δεδομένων μετά τον τερματισμό μιας διεργασίας
Πρόσβαση πολλών διεργασιών στα ίδια δεδομένα

Ονοματολογία

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

Ονομασία μόνο με κεφαλαία, ανάκτηση ανεξάρτητα από τον τύπο των γραμμάτων (π.χ. MS-DOS)
Ονομασία με πεζά και κεφαλαία ανάκτηση ανεξάρτητα από τον τύπο των γραμμάτων (π.χ. Windows-NT)
Ονομασία με πεζά και κεφαλαία ανάκτηση σύμφωνα με τον τύπο των γραμμάτων (π.χ. Unix)

Σε ορισμένα λειτουργικά συστήματα η επέκταση του αρχείου (filename extension) έχει ειδική σημασία. Αυτή μπορεί να υποστηρίζεται μέσω ενός γενικού αντικειμενοστρεφούς σχεδιασμού του λειτουργικού συστήματος (π.χ. Windows NT) ή λόγω παραδοχών που γίνονται από τις εφαρμογές του (π.χ. MS-DOS, Unix, VMS). Για παράδειγμα στο Windows-NT ορισμένοι τύποι επέκτασης είναι οι παρακάτω:

.exe	Εκτελέσιμο αρχείο
.txt	Αρχείο κειμένου
.bat	Εκτελέσιμο αρχείο εντολών του φλοιού
.bmp	Αρχείο χαρτογραφικής εικόνας
.htm	Αρχείο με κείμενο HTML (Internet)
.hlp	Αρχείο με δεδομένα βοήθειας
.doc	Αρχείο της εφαρμογής Microsoft Word
.xls	Αρχείο της εφαρμογής Microsoft Excel
.c	Αρχείο πηγαίου κώδικα C
.pas	Αρχείο πηγαίου κώδικα Pascal
.for	Αρχείο πηγαίου κώδικα Fortran
.bas	Αρχείο πηγαίου κώδικα Basic
.obj	Μεταγλωττισμένος κώδικας
.lib	Βιβλιοθήκη μεταγλωττισμένου κώδικα
.dll	Δυναμική βιβλιοθήκη

Δομή, τύποι και προσπέλαση αρχείων

Τύποι

Πολλά λειτουργικά συστήματα διακρίνουν ειδικούς τύπους αρχείων:

κανονικά αρχεία (regular files)
ειδικά αρχεία τμημάτων (block special files)
ειδικά αρχεία χαρακτήρων (character special files)
κατάλογοι (character special files)
ψευδοαρχεία (pseudo files)

Δομή

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

Αδόμητα αρχεία (Unix, Windows-NT, MS-DOS)
Ακολουθίες εγγραφών (CP/M, Concurrent - Interdata - Perkin Elmer OS/32)
Αρχεία με κλειδί (Perkin Elmer OS/32)

Σε λειτουργικά συστήματα με αδόμητα αρχεία το περιεχόμενο των αρχείων ορίζεται με σύμβαση. Διακρίνονται αρχεία κειμένου (ASCII) καθώς και δυαδικά αρχεία. Το περιεχόμενο των δυαδικών αρχείων προσδιορίζεται συνήθως από το επίθεμά τους ή/και τη χρήση ενός μαγικού αριθμού (magic number).

Προσπέλαση

Σε παλαιότερα λειτουργικά συστήματα υπήρχε η διάκριση μεταξύ αρχείων σειριακής προσπέλασης (sequential access) και αρχείων τυχαίας προσπέλασης (random access).

Ιδιοχαρακτηριστικά

Στα περισσότερα λειτουργικά συστήματα κάθε αρχείο συσχετίζεται με πρόσθετες πληροφορίες, που καλούνται ιδιοχαρακτηριστικά του αρχείου (file attributes). Αυτές μπορεί να είναι:

Περιγραφή της προστασίας του αρχείου (ανάγνωση, μεταβολή)
Ταυτότητα του δημιουργού και του ιδιοκτήτη
Τρόποι προσπέλασης (σειριακή, τυχαία)
Ένδειξη τροποποίησης
Ένδειξη κρυφού αρχείου
Ένδειξη προσωρινού αρχείου
Ένδειξη εφεδρείας
Μήκος εγγραφής
Στοιχεία του κλειδιού
Ημερομηνία και ώρα δημιουργίας
Ημερομηνία και ώρα τελευταίας προσπέλασης
Ημερομηνία και ώρα τελευταίας μεταβολής
Ημερομηνία και ώρα τελευταίας μεταβολής των ιδιοχαρακτηριστικών
Τρέχον μέγεθος
Μέγιστο μέγεθος

Κλήσεις ΛΣ για χρήση αρχείων

Η πρόσβαση στα αρχεία γίνεται μέσω κλήσεων στο λειτουργικό σύστημα. Οι σημαντικότερες από αυτές είναι:

create: Δημιουργία ενός νέου αρχείου
open: Αρχή της πρόσβασης στο αρχείο
read: Ανάγνωση από το αρχείο
write: Εγγραφή στο αρχείο
seek: Μετακίνηση του δείκτη στο αρχείο
close: Τέλος της πρόσβαση στο αρχείο

Η κλήσεις open και create επιστρέφουν κατά κανόνα έναν μικρό ακέραιο τον περιγραφέα του αρχείου (file descriptor) ο οποίος χρησιμοποιείται στη συνέχεια για κάθε άλλη κλήση που έχει σχέση με το συγκεκριμένο αρχείο. Με τον τρόπο αυτό απλουστεύεται η πρόσβαση στο αρχείο μέσω του ονόματός του.

Για παράδειγμα η παρακάτω συνάρτηση αντιγράφει ένα αρχείο σε ένα άλλο (Unix):

/*
 * Copy file specified by path1 to path2
 * Return 0 on success -1 on error
 * (dds)
 */
int
copyfile(char *path1, char *path2)
{
	char	buf[512];		/* Copy buffer */
	int	ifd, ofd;		/* File descriptors */
	int	nrbytes;		/* Bytes read */
	int	nwbytes;		/* Bytes written */
	struct	stat sbuf;		/* Attribute buffer */

	/* Get attributes of source file */
	if (stat(path1, &sbuf) == -1)
		return (-1);

	/* Open source file */
	if ((ifd = open(path1, O_RDONLY)) < 0)
		return (-1);

	/* Create destination file */
	if ((ofd = creat(path2, sbuf.st_mode & 0777)) < 0) {
		close(ifd);
		return (-1);
	}

	/* Copy source to destination in chunks */
	while ((nrbytes = read(ifd, buf, sizeof(buf))) > 0) {
		if ((nwbytes = write(ofd, buf, nrbytes)) != nrbytes) {
			nrbytes = -1;
			break;
		}
	}

	/* Close source file */
	if (close(ifd) < 0) {
		close(ofd);
		return (-1);
	}

	/* Close destination file */
	if (close(ofd) < 0) {
		return (-1);
	}

	/* Success! */
	return (0);
}

Αρχεία που απεικονίζονται στη μνήμη

Η πρόσβαση σε αρχεία μπορεί να γίνει και χωρίς τη χρήση read/write/seek με την απευθείας απεικόνισή τους στη μνήμη. Ο τρόπος προσφέρει διαφάνεια στην πρόσβαση και καλύτερες επιδόσεις, ειδικά όταν συνδυάζεται με κατάτμηση για την 1-1 απεικόνιση διευθύνσεων του αρχείου με διευθύνσεις μνήμης και σελιδοποίηση για την ανίχνευση κάθε ανάγνωσης και εγγραφής σχετικής με το αρχείο. Η πρόσβαση στα αρχεία με τον τρόπο αυτό γίνεται μέσω κλήσεων στο λειτουργικό σύστημα και στη συνέχεια χρήσης της αντίστοιχης μνήμης (μέσω δεικτών ή πινάκων). Οι σχετικές κλήσεις είναι:

map: Σύνδεση μιας περιοχής της μνήμης με ένα αρχείο
unmap: Τερματισμός της αντίστοιχης σύνδεσης

Στο Unix οι αντίστοιχες κλήσεις είναι οι:

void *mmap(void  *start,  size_t length, int prot , int flags, 
	   int fd, off_t offset);

int munmap(void *start, size_t length);

Υλοποίηση αρχείων

Η υλοποίηση του συστήματος των αρχείων μπορεί να γίνει με διάφορους τρόπους κατανομής του χώρου του δίσκου. Κάθε τρόπος πρέπει να επιτρέπει σειριακή και τυχαία πρόσβαση στο αρχείο. Μερικοί τρόποι είναι οι παρακάτω:

Συνεχής κατανομή του χώρου του δίσκου.
Κατανομή του χώρου με μορφή συνδεδεμένης λίστας.
Κατανομή με μορφή συνδεδεμένης λίστας δεικτών σε τμήματα (FAT)
Με τη χρήση πινάκων δεικτών (i-nodes)

Ιεραρχικά συστήματα καταλόγων

Για την οργάνωση των αρχείων πολλά λειτουργικά συστήματα υλοποιούν ιεραρχική δομή καταλόγων (tree directory structure).
Η πρόσβαση σε ένα αρχείο μπορεί να γίνει
- είτε με απόλυτο όνομα διαδρομής (absolute file path) ή με
- σχετικό όνομα διαδρομής (relative file path) ως προς τον τρέχοντα κατάλογο (current directory).

Κλήσεις ΛΣ για χρήση καταλόγων

Η πρόσβαση στους καταλόγους γίνεται μέσω κλήσεων στο λειτουργικό σύστημα. Οι σημαντικότερες από αυτές είναι:

delete: Διαγραφή ενός αρχείου από έναν κατάλογο
get attributes: Ανάγνωση των ιδιοχαρακτηριστικών ενός αρχείου
set attributes: Αλλαγή των ιδιοχαρακτηριστικών ενός αρχείου
rename: Μετονομασία ενός αρχείου (ή καταλόγου)
mkdir: Δημιουργία ενός καταλόγου
rmdir: Διαγραφή ενός καταλόγου
opendir: Αρχή πρόσβασης στα στοιχεία ενός καταλόγου
readdir: Ανάγνωση στοιχείων από έναν κατάλογο
closedir: Τέλος της πρόσβασης στον κατάλογο
link: Σύνδεση δύο αρχείων μεταξύ τους
symlink: Συμβολική σύνδεση δύο αρχείων μεταξύ τους

Υλοποίηση καταλόγων

Οι κατάλογοι τυπικά υλοποιούνται ως πίνακες που περιέχουν:

το όνομα του αρχείου
στοιχεία για τη θέση των δεδομένων του
στοιχεία για τα ιδιοχαρακτηριστικά του

Διαχείριση χώρου

Η διαχείριση του χώρου του δίσκου γίνεται με τη χρήση τμημάτων σταθερού μεγέθους (512 bytes - 32 Kbyte).
Το μέγεθος των τμημάτων εξαρτάται από περιορισμούς του υλικού και του λειτουργικού συστήματος.
Το μέγεθος των τμημάτων επηρεάζει άμεσα τη σπατάλη χώρου στο δίσκο.
Τα ελεύθερα τμήματα μπορούν να απεικονίζονται:
- με συνδεδεμένη λίστα ή
- με χάρτη bits.
Συχνά το λειτουργικό σύστημα επιβάλλει όρια χρήσης (quota) χώρου στο δίσκο για κάθε χρήστη.

Αξιοπιστία συστημάτων αρχείων

Το λειτουργικό σύστημα ή εξωτερικά προγράμματα μεριμνούν για

τη διαχείριση κατεστραμμένων τμημάτων του δίσκου
την αντιγραφή των περιεχομένων του δίσκου σε άλλο μέσο εφεδρεία (backup). Για λόγου ταχύτητας υλοποιείται συχνά σύστημα προοδευτικής εφεδρείας (incremental backup).
τη συνέπεια του συστήματος των αρχείων (fsck, scandisk, chkdsk).
την επαναφορά διαγραμμένων αρχείων

Επίδοση συστημάτων αρχείων

Για τη μείωση του χρόνου πρόσβασης στα αρχεία χρησιμοποιείται συχνά η τεχνική της κρυφής μνήμης (cache memory). Αυτή μπορεί να υλοποιηθεί σε συνδυασμό με το σύστημα σελιδοποίησης και με τη χρήση αντίστοιχων τεχνικών επιλογής των τμημάτων που θα φυλαχθούν σε αυτή. Για την εξασφάλιση των δεδομένων που γράφονται στα αρχεία οι εγγραφές σε περιοχές του δίσκου που αντιστοιχούν σε κρυφή μνήμη μεταφέρονται άμεσα και στο δίσκο, ή μεταφέρονται στο δίσκο σε τακτά χρονικά διαστήματα. Ορισμένες υλοποιήσεις διαφοροποιούν την εγγραφή των δεδομένων ανάλογα με το είδος τους (δεδομένα ή μεταδεδομένα).
Για τη βελτίωση της απόδοσης του συστήματος αρχείων υλοποιούνται συχνά τεχνικές οι οποίες βοηθούν στην κατανομή δεδομένων στα οποία θα γίνεται η πρόσβαση χρονικά κοντά σε αντίστοιχα κοντινές περιοχές του δίσκου.
Με τη δημιουργία και διαγραφή αρχείων μπορεί να συμβεί η δομή του συστήματος αρχείων να υποστεί σοβαρό κατακερματισμό (fragmentation). Λόγω της αντίστοιχης πτώσης της απόδοσης ο σχεδιασμός του συστήματος μπορεί να αποτρέπει τον κατακερματισμό, ή να διαθέτει ειδικό πρόγραμμα που να τον αποκαθιστά.

Βιβλιογραφία

Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 199-248 Εκδόσεις Παπασωτηρίου, 1993.

Maurice J. Bach. The Design of the UNIX Operating System, pages 38–140. Prentice-Hall, 1986.
Samuel J. Leffler, Marshall Kirk McKusick, Michael J. Karels, and John S. Quarterman. The Design and Implementation of the 4.3BSD Unix Operating System, pages 187–223. Addison-Wesley, 1988.
Andrew S. Tanenbaum. Operating Systems: Design and Implementation, pages 251–337. Prentice-Hall, 1987.

Εργασία στο εργαστήριο

Διαβάστε τη σελίδα του εγχειριδίου του Unix για τις κλήσεις open και stat. Προσέξτε τις παραμέτρους που λαμβάνουν και τον αριθμό των πιθανών λαθών που ελέγχουν.

kerkis:/proc$ man  2 open | head -20



OPEN(2)                    System calls                   OPEN(2)


NAME
       open, creat - open and possibly create a file or device

SYNOPSIS
       #include <sys/types.h>
       #include <sys/stat.h>
       #include <fcntl.h>

       int open(const char *pathname, int flags);
       int open(const char *pathname, int flags, mode_t mode);
       int creat(const char *pathname, mode_t mode);

DESCRIPTION
       open  attempts to open a file and return a file descriptor              
...

Μετρήστε το χρόνο που χρειάζεται η αντιγραφή ενός αρχείου στο ψευδοαρχείο /dev/null. Εκτελέστε την εντολή ξανά και συγκρίνετε τους χρόνους. Παρατηρήστε το αποτέλεσμα της κρυφής μνήμης.

athena:~> cd /usr/man/man1
athena:/usr/man/man1>     
athena:/usr/man/man1> time cat pgp.1 >/dev/null
0.000u 0.030s 0:00.20 15.0% 0+0k 0+0io 16pf+0w
athena:/usr/man/man1> time cat pgp.1 > /dev/null
0.000u 0.030s 0:00.02 150.0% 0+0k 0+0io 16pf+0w
athena:/usr/man/man1>

Θέματα ασφάλειας

Το περιβάλλον ασφάλειας

Σε πληροφοριακά συστήματα ελλοχεύει ο κίνδυνος τα δεδομένα που φυλάσσονται σε αυτό να:

χαθούν, καταστραφούν, ή σβηστούν,
αλλοιωθούν
διαδοθούν χωρίς την απαιτούμενη δικαιοδοσία

Επιπλέον το ίδιο το σύστημα μπορεί να:

χρησιμοποιηθεί χωρίς άδεια,
γίνει αντικείμενο βανδαλισμού.

Ενδεχόμενα κίνητρα για τις παραπάνω πράξεις μπορεί να είναι:

περιέργεια,
άμεσο οικονομικό όφελος,
πρόκληση,
εμπορική και βιομηχανική κατασκοπία,

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

Πολιτικές και μηχανισμοί ασφαλείας

Η προστασία ενός πληροφοριακού συστήματος γίνεται με βάση κάποια πολιτική ασφαλείας (security policy) η οποία κατ' ελάχιστο ορίζει ποιος έχει πρόσβαση σε τι και υλοποιείται με βάση ορισμένους μηχανισμούς ασφαλείας (security mechanisms). Παράδειγμα πολιτικής ασφαλείας είναι η διαβάθμιση των στρατιωτικών εγγράφων. Παράδειγμα μηχανισμού ασφαλείας είναι το σύστημα προστασίας των αρχείων του Unix.

Πιστοποίηση ταυτότητας

Βασικό στοιχείο για την προστασία ενός συστήματος είναι η ταυτοποίηση του χρήστη. Αυτή μπορεί να βασίζεται σε:

μια μυστική πληροφορία (κάτι που γνωρίζει ο χρήστης),
μια συσκευή (κάτι που κατέχει ο χρήστης),
βιομετρικά χαρακτηριστικά (κάτι που είναι ο χρήστης),
τον τόπο (κάπου που βρίσκεται ο χρήστης).

Προσδιορισμός προστασίας

Η προστασία των αρχείων ή άλλων στοιχείων του συστήματος (λ.χ. συσκευών, διαμοιρασμένης μνήμης, σηματοφόρων κ.λπ.) μπορεί να οργανωθεί με βάση περιοχές προστασίας (security domain) στις οποίες ο χρήστης ο χρήστης έχει ορισμένα δικαιώματα (rights).
Αυτή μπορεί να υλοποιηθεί με βάση μια λίστα ελέγχου προσπέλασης (access control list) ή μια λίστα προσδιορισμού δικαιωμάτων (capability list).

Μερικά προβλήματα

Βανδαλισμός (vandalism): Η δόλια βλάβη η παρεμπόδιση χρήσης ενός πληροφοριακού συστήματος.
Δούρειος ίππος (Trojan horse): Ένα πρόγραμμα το οποίο παραβιάζει μια πολιτική ασφάλειας εμφανιζόμενο να εκτελεί άλλες λειτουργίες από αυτές που πραγματικά εκτελεί.
Ιός (Virus): Πρόγραμμα το οποίο κολλάει σε άλλα προγράμματα αλλάζοντας το εκτελέσιμο τμήμα τους.
Σκουλήκι (Worm): Πρόγραμμα το οποίο εξαπλώνεται πολλαπλασιαζόμενο από σύστημα σε σύστημα.
Ωρολογιακή βόμβα (Time bomb): Διάταξη (εκτός των προδιαγραφών) στον κώδικα ενός προγράμματος η οποία ενεργοποιείται μια συγκεκριμένη χρονική στιγμή.
Καταπακτή (trapdoor): Διάταξη στον κώδικα ενός προγράμματος η οποία επιτρέπει την παράκαμψη ενός μηχανισμού ασφαλείας.

Ασφάλεια στο Internet

Το Internet λόγω της μεγάλης διάδοσης που παρουσιάζει ορισμένα ιδιαίτερα προβλήματα και χαρακτηριστικά που σχετίζονται με την ασφάλεια:

rsh/rexec/rlogin: Προβληματική η πιστοποίηση του χρήστη
telnet/ftp: Μεταφορά των κωδικών και των δεδομένων χωρίς κρυπτογράφηση
NFS/SMB: Προβληματική η πιστοποίηση
SMTP: Εύκολη η δημιουργία πλαστών μηνυμάτων
WWW: Δύσκολη η υλοποίηση ασφαλών συναλλαγών
Εκτελέσιμο περιεχόμενο (π.χ. Java, ActiveX): Δύσκολος ο έλεγχος του περιεχομένου
Άλλες υπηρεσίες: Συχνές ανασφαλείς υλοποιήσεις

Για την εξασφάλιση από μερικούς κινδύνους δικτύων οργανισμών που δεν είναι δυνατό να διασφαλιστούν ανά μηχάνημα χρησιμοποιείται η τεχνολογία των πυρίμαχων τοίχων (firewall). Ο πυρίμαχος τοίχος τοποθετείται στην περίμετρο του δικτύου της εταιρίας και υλοποιεί μια καθορισμένη πολιτική ασφαλείας.

Ο ανθρώπινος παράγοντας

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

Βασικές αρχές κρυπτογραφίας

Μερικές λύσεις σε θέματα ασφαλείας βασίζονται στην κρυπτογραφία. Αυτή μπορεί να διασφαλίσει:

την εμπιστευτικότητα (confidentiality) με κρυπτογράφηση (cryptography),
την ακεραιότητα (integrity) (προορισμού, περιεχομένου, προέλευσης) με αυθεντικοποίηση (authentication)
την ταυτοποίηση (identification) με ψηφιακές υπογραφές (digital signatures)

Για την υλοποίηση των παραπάνω χρησιμοποιούνται αλγόριθμοι:

συμμετρικής κρυπτογράφησης (symmetric encryption)
κρυπτογράφησης δημοσίου κλειδιού (public key encryption)
αφομοίωσης μηνυμάτων (message digest)

Τέλος για τη φύλαξη και ασφαλή διανομή στοιχείων των ψηφιακών υπογραφών μπορούν να χρησιμοποιηθούν έμπιστες τρίτες οντότητες (trusted third parties)

Βιβλιογραφία

Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 248-278 Εκδόσεις Παπασωτηρίου, 1993.
Δημήτρης Γκρίτζαλης και Στέφανος Γκρίτζαλης Ασφάλεια λειτουργικών συστημάτων. Εκδόσεις ΜΙΤ Εκπαιδευτική - Αναπτυξιακή, 1993.

Peter J. Denning. Computers Under Attack: Intruders, Worms, and Viruses. Addison-Wesley, 1990.
Tom Forester and Perry Morrison. Computer Ethics: Cautionary Tales and Ethical Dilemmas in Computing. MIT Press, 1990.
F. T. Grampp and R. H. Morris. UNIX operating system security. Bell System Technical Journal, 63(8), October 1984.
Stefanos Gritzalis and Diomidis Spinellis. Addressing threats and security issues in World Wide Web technology. In Proceedings CMS '97 3rd IFIP TC6/TC11 International joint working Conference on Communications and Multimedia Security, pages 33–46, Athens, Greece, September 1997. IFIP, Chapman & Hall.
Stefanos Gritzalis and Diomidis Spinellis. Cryptographic protocols over open distributed systems: A taxonomy of flaws and related protocol analysis tools. In 16th International Conference on Computer Safety, Reliability and Security: SAFECOMP '97, pages 123–137, York, UK, September 1997. European Workshop on Industrial Computer Systems: TC-7, Springer Verlag.
Robert Morris. Password security: A case history. Communications of the ACM, 22(11):594–597, November 1979.
Charles Pfleeger. Security in Computing. Prentice-Hall, 1996.
Dennis M. Ritchie. On the security of UNIX. In UNIX Programmer's manual: Supplementary Documents, volume 2, pages 592–594. Holt, Rinehart and Winston, seventh edition, 1982.
Eugene H. Spafford. The internet worm program: An analysis. Technical Report CSD-TR-823, Purdue University, West Lafayette, IN 47907-2004, November 1988.
Ken L. Thompson. Reflections on trusting trust. Communications of the ACM, 27(8):761–763, 1984.

Εργασία στο εργαστήριο

Αρχεία που σχετίζονται με την ασφάλεια

Μελετήστε το περιεχόμενο των αρχείων:

/etc/passwd (5): Κωδικοί χρηστών (πλασματικοί)
/etc/shadow (5): Κωδικοί χρηστών (πραγματικοί, χωρίς δικαίωμα πρόσβασης)
/etc/group (5): Μέλη ομάδων
/etc/shells (5): Επιτρεπόμενοι φλοιοί
/etc/inetd.conf (5): Παρεχόμενες υπηρεσίες του Internet

Εντολές που σχετίζονται με την ασφάλεια

Μελετήστε τις εντολές:

chmod (1): Αλλαγή των χαρακτηριστικών προστασίας ενός αρχείου
chown (1): Αλλαγή του ιδιοκτήτη ενός αρχείου
chgrp (1): Αλλαγή της ομάδας-ιδιοκτήτη ενός αρχείου
newgrp (1): Αλλαγή της ομάδας ενός χρήστη

Κλήσεις που σχετίζονται με την ασφάλεια

Μελετήστε τις κλήσεις:

chmod (2): Αλλαγή των χαρακτηριστικών προστασίας ενός αρχείου
setuid (2): Αλλαγή του χρήστη που εκτελεί μια διεργασία

Είσοδος και έξοδος

Σχεδίαση υλικού

Οι συσκευές εσόδου εξόδου μπορούν να διαχωριστούν σε:
- συσκευές τμημάτων (block devices)
- συσκευές χαρακτήρων (character devices)
Οι συσκευές ελέγχονται με τη χρήση ελεγκτών συσκευών (device controller) που επικοινωνούν με την κεντρική μονάδα επεξεργασίας μέσω του διαύλου.
Σε μεγαλύτερα συστήματα η επικοινωνία μπορεί να γίνεται με τη χρήση εξειδικευμένων υπολογιστών εισόδου εξόδου.
Η επικοινωνία με του ελεγκτές γίνεται μέσω εντολών που στέλνονται μέσω διαύλου εισόδου / εξόδου ή μέσω ειδικών διευθύνσεων της μνήμης.
Ορισμένοι ελεγκτές για συσκευές που μεταφέρουν μεγάλο όγκο δεδομένων υποστηρίζουν απευθείας πρόσβαση στη μνήμη (direct memory access (DMA)). Αυτή υλοποιείται συνήθως με τη χρήση ενδιάμεσης μνήμης στον ελεγκτή.
Ορισμένοι ελεγκτές δίσκου υποστηρίζουν την υπερπήδηση (interleaving) τμημάτων του δίσκου έτσι ώστε να συμβαδίζει ο χρόνος περιστροφής του δίσκου με το χρόνο ανάγνωσης των στοιχείων από αυτόν.

Σχεδίαση λογισμικού

Το λογισμικό εισόδου εξόδου εξασφαλίζει:

ανεξαρτησία από τις συσκευές (device independence)
ενιαία ονοματολογία (unoform naming)
χειρισμό των σφαλμάτων (όσο είναι δυνατό)
απεικόνιση των ασύγχρονων (asynchronous) συσκευών που ελέγχονται με διακοπές (interrupt driven) σε σύγχρονες (synchronous).
τον έλεγχο χρήσης των διαμοιραζομένων (shareable) και αφοσιωμένων (dedicated) συσκευών.

Για την ικανοποίηση των παραπάνω ο έλεγχος εισόδου εξόδου σε ένα λειτουργικό σύστημα χωρίζεται στα παρακάτω στρώματα:

Χειριστές διακοπών
Οδηγοί συσκευών
Λογισμικό Λ.Σ. ανεξάρτητο από τις συσκευές (ονοματολογία, προστασία)
Λογισμικό επιπέδου χρήστη (ετεροχρονισμός μέσω διεργασίας παροχής υπηρεσιών (daemon).

Υλοποίηση πρόσβασης σε δίσκους

Η χρονοδρομολόγιση του βραχίονα του δίσκου μπορεί να γίνει με τους παρακάτω τρόπους:
- Πρώτη εισερχόμενη Πρώτη εξυπηρετούμενη (First Come First Served (FCFS))
- Συντομότερη αναζήτηση πρώτη (Shortest Seek First (SSF))
- με τον αλγόριθμο του ανελκυστήρα
Πολλαπλοί δίσκοι μπορούν να χρησιμοποιηθούν παράλληλα για βελτίωση της ταχύτητας και της αξιοπιστίας τους με βάση την τεχνολογία
Πλεονάζουσα διάταξη φθηνών δίσκων (Redundant Array of Inexpensive Disks)
Σφάλματα του δίσκου μπορεί να τα χειριστεί ο ελεγκτής του ή το Λ.Σ.
Για τη βελτίωση της απόδοσης του δίσκου μπορεί να χρησιμοποιείται κρυφή μνήμη στον ελεγκτή, ή από το Λ.Σ.
Ειδική μορφή περιφερειακού τύπου δίσκου είναι ο δίσκος βασισμένος σε RAM.

Αξιοποίηση των ρολογιών

Το λειτουργικό σύστημα αξιοποιεί το ρολόι του υπολογιστή το οποίο είναι υλοποιημένο ως ένας μετρητής για να:

γνωρίζει το χρόνο της ημέρας
το χρονοπρογραμματισμό των διεργασιών
την παρακολούθηση της χρήσης της Κ.Μ.Ε.
το χειρισμό κλήσεων εγρήγορσης των χρηστών
τον έλεγχο περιφερειακών που απαιτούν χρονισμό μέσω χρονιστών επιτήρησης (watchdoc timers).
τη συλλογή στατιστικών στοιχείων

Επικοινωνία με το χρήστη

Η επικοινωνία με το χρήστη μπορεί να γίνει μέσω:

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

Το λογισμικό εισόδου μπορεί να παρέχει ακατέργαστη κατάσταση λειτουργίας (raw mode) και κατεργασμένη κατάσταση λειτουργίας (cooked mode). Η τελευταία υποστηρίζει την αλλαγή του κειμένου και την προβολή (echoing) των χαρακτήρων.

Βιβλιογραφία

Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 283-329 Εκδόσεις Παπασωτηρίου, 1993.

Maurice J. Bach. The Design of the UNIX Operating System, pages 312–352. Prentice-Hall, 1986.
Samuel J. Leffler, Marshall Kirk McKusick, Michael J. Karels, and John S. Quarterman. The Design and Implementation of the 4.3BSD Unix Operating System, pages 167–186, 225–278. Addison-Wesley, 1988.
Andrew S. Tanenbaum. Operating Systems: Design and Implementation, pages 110–177. Prentice-Hall, 1987.

Αδιέξοδα

Πόροι

Ένα σύνολο διεργασιών βρίσκεται σε αδιέξοδο (deadlock) αν κάθε διεργασία του συνόλου περιμένει ένα γεγονός που μόνο μια άλλη διεργασία του συνόλου μπορεί να προκαλέσει. (Tanenbaum)

Τα αδιέξοδα δημιουργούνται ως αποτέλεσμα της διαχείρισης των πόρων από τις διαδικασίες. Κάθε πόρος (resource) μπορεί να είναι προεκχωρήσιμος (preemptable) δηλαδή να αποδεσμευτεί από μια διεργασία που τον κατέχει χωρίς παρενέργιες ή μη προεκχωρήσιμος (nonpreemptable). Παραδείγματα της πρώτης κατηγορίας είναι ο δίσκος και η μνήμη. Παραδείγματα της δεύτερης κατηγορίας είναι ο εκτυπωτής και η μονάδα ταινίας. Τυπικά μια διεργασία χρησιμοποιεί έναν πόρο ως εξής:

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

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

Αδιέξοδα και μοντελοποίησή τους

Οι παρακάτω συνθήκες πρέπει να ικανοποιούνται για να δημιουργηθεί αδιέξοδο:

Αμοιβαίος αποκλεισμός: Κάθε πόρος είναι δεσμευμένος ή διαθέσιμος.
Δέσμευση και αναμονή: Διεργασίες που δεσμεύουν πόρους μπορούν να ζητούν και νέους.
Μη προεκχώρηση: Μόνο η διεργασία που έχει δεσμεύσει τους πόρους μπορεί να τους αποδεσμεύσει.
Κυκλική αναμονή: Οι διαδικασίες που ζητούν πόρους πρέπει να σχηματίζουν κύκλο.

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

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

Οι παρακάτω στρατηγικές μπορούν να χρησιμοποιηθούν για την αντιμετώπισή τους:

Αγνόηση του προβλήματος
Ανίχνευση και επανόρθωση
Δυναμική αποφυγή με προσεκτική κατανομή των πόρων
Πρόληψη με αναίρεση των παραπάνω αναγκαίων συνθηκών

Ανίχνευση και επανόρθωση

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

Προεκχώρηση του πόρου
Οπισθοδρόμηση της διεργασίας σε προηγούμενο σημείο ελέγχου (checkpoint)
Εξάλειψη κάποιων διεργασιών

Αποφυγή

Η αποφυγή του αδιεξόδου βασίζεται στη συντηρητική ικανοποίηση των αιτήσεων για πόρους με στόχο το σύστημα πάντα να βρίσκεται σε μια ασφαλή κατάσταση κατά την οποία δεν μπορεί να υπάρξει αδιέξοδο. Αιτήσεις που οδηγούν σε μη ασφαλείς καταστάσεις δεν ικανοποιούνται.

Πρόληψη

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

Αμοιβαίος αποκλεισμός: (Κάθε πόρος είναι δεσμευμένος ή διαθέσιμος.)
Αποφεύγεται η χρήση δεσμευμένων πόρων π.χ. με τη χρήση ετεροχρονισμού.
Δέσμευση και αναμονή: (Διεργασίες που δεσμεύουν πόρους μπορούν να ζητούν και νέους.)
Κάθε διεργασία ζητά από την αρχή τους πόρους που χρειάζεται.
Μη προεκχώρηση: (Μόνο η διεργασία που έχει δεσμεύσει τους πόρους μπορεί να τους αποδεσμεύσει.)
Δύσκολο πρακτικά να αναιρεθεί.
Κυκλική αναμονή: (Οι διαδικασίες που ζητούν πόρους πρέπει να σχηματίζουν κύκλο.)
Αίτηση για πόρους σύμφωνα με την απαρίθμησή τους.

Βάσεις δεδομένων

Σε βάσεις δεδομένων χρησιμοποιείται συχνά το κλείδωμα σε δύο φάσεις (two phase locking).

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

Βιβλιογραφία

Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 331-359 Εκδόσεις Παπασωτηρίου, 1993.

Δομή του λειτουργικού συστήματος Unix

Ιστορία

Χρονολογικός πίνακας του Unix

Τέλη δεκαετίας 1960: Τα Bell Labs (AT&T), GE και το MIT υλοποιούν το MULTICS (Multiplexed Information and Computing Services), ένα πολυχρηστικό λειτουργικό σύστημα. Το 1969 τα Bell Labs αποσύρονται από το έργο όταν αυτό έγινε υπερβολικά ακριβό και περίπλοκο.
1969: Ο Ken Thompson (BL) αναπτύσσει λειτουργικό σύστημα για έναν χρήστη για τον υπολογιστή DEC PDP-7
1970: Ο Brian Kernighan σχηματίζει το όνομα UNIX ως λογοπαίγνιο του MULTICS. Το σύστημα μεταφέρεται στο PDP-11. Υποστηρίζει δύο χρήστες, το παγνίδι Spacewar, και επεξεργασία κειμένου.
1973: Ο Dennis Ritchie αναπτύσσει σε συνεργασία με τον Thompson τη γλώσσα προγραμματισμού C και ξαναγράφουν το Unix στη γλώσσα αυτή.
Μέσα δεκαετίας 1970: Το UNIX (Version 6) διατίθεται δωρεάν σε πανεπιστήμια. Μεταφέρεται και σε άλλους υπολογιστές. Όλος ο πυρήνας αποτελείται από λιγότερες από 10000 γραμμές κώδικα.
Τέλη δεκαετίας 1970: Εργασία του Thompson μαζί με τον Bill Joy στο Πανεπιστήμιο του Berkeley (UCB) καταλήγει στην Berkeley Software Distribution (BSD). Αυτή υποστηρίζει μεταξύ άλλων ιδεατή μνήμη και σελιδοποίηση.
1980: Η Microsoft παράγει το XENIX. Κυκλοφορεί η πρώτη έκδοση 32 bit, το BSD 4.1.
1983: Κυκλοφορεί νέα έκδοση από την AT&T με το όνομα System V. Η AT&T την προωθεί ως πρότυπο με τελική μορφή την έκδοση SVR4 μετά την υιοθέτηση χαρακτηριστικών του BSD 4.2. Παράλληλα η Sun κυκλοφορεί το SunOS με τελική μορφή το Solaris. Το Unix διαχωρίζεται σε αντίπαλα στρατόπεδα.
1985: Η AT&T δημοσιεύει το πρότυπο SVID (System V Interface Definition). Η ομάδα X/OPEN (αργότερα UNIX International) δημοσιεύει αντίστοιχο πρότυπο. Το πρότυπο POSIX 1003.1 υιοθετείται ως κοινό πεδίο.
1988: Η Open Software Foundation (OSF) ανταγωνίζεται την UI με βάση το AIX της IBM. Στο πανεπιστήμιο Carnegie Mellon αναπτύσσεται ο μικρο-πυρήνας MACH.
Δεκαετία 1990: Αναπτύσσονται και διανέμονται εκδόσεις του Unix που δε βασίζονται σε κώδικα της AT&T. Τα BSDI, 386BSD, NetBSD και FreeBSD βασίζονται στη διανομή Net/2 και αργότερη στην 4.4BSD Lite του Berkeley με κώδικα για τον επεξεργαστή Intel 386 από τον Bill Jolitz, ενώ το Linux βασίζεται σε κώδικα που έγραψε από την αρχή ο Linux Torvalds.

Γενεαλογικό δένδρο του Unix

Το παρακάτω σχήμα (βασισμένο στο βιβλίο Life with Unix) παριστάνει τη γενεαλογία του Unix:

Κλήσεις του λειτουργικού συστήματος

Όλες οι κλήσεις του λειτουργικού συστήματος χαρακτηρίζονται εσωτερικά από έναν αριθμό με βάση τον οποίο δρομολογούνται στον αντίστοιχο κώδικα του πυρήνα. Ο παρακάτω πίνακας περιέχει τις πρώτες 20 κλήσεις του FreeBSD Unix:

#define SYS_syscall     0
#define SYS_exit        1
#define SYS_fork        2
#define SYS_read        3
#define SYS_write       4
#define SYS_open        5
#define SYS_close       6
#define SYS_wait4       7
                                /* 8 is old creat */
#define SYS_link        9
#define SYS_unlink      10
                                /* 11 is obsolete execv */
#define SYS_chdir       12
#define SYS_fchdir      13
#define SYS_mknod       14
#define SYS_chmod       15
#define SYS_chown       16
#define SYS_break       17
#define SYS_getfsstat   18
                                /* 19 is old lseek */
#define SYS_getpid      20

Για παράδειγμα ο παρακάτω κώδικας του πυρήνα υλοποιεί την κλήση getpid:

int
getpid(p, uap)
        struct proc *p;
        struct getpid_args *uap;
{
        p->p_retval[0] = p->p_pid;
        return (0);
}

Διεργασίες

Κάθε διεργασία φυλάσσεται στον πίνακα διεργασιών με βάση τα παρακάτω πεδία:

struct  proc {
        TAILQ_ENTRY(proc) p_procq;      /* run/sleep queue. */
        LIST_ENTRY(proc) p_list;        /* List of all processes. */

        /* substructures: */
        struct  pcred *p_cred;          /* Process owner's identity. */
        struct  filedesc *p_fd;         /* Ptr to open files structure. */
        struct  pstats *p_stats;        /* Accounting/statistics (PROC ONLY). */
        struct  plimit *p_limit;        /* Process limits. */
        struct  vm_object *p_upages_obj;/* Upages object */
        struct  sigacts *p_sigacts;     /* Signal actions, state (PROC ONLY). */


        int     p_flag;                 /* P_* flags. */
        char    p_stat;                 /* S* process status. */
        char    p_pad1[3];

        pid_t   p_pid;                  /* Process identifier. */
        LIST_ENTRY(proc) p_hash;        /* Hash chain. */
        LIST_ENTRY(proc) p_pglist;      /* List of processes in pgrp. */
        struct  proc *p_pptr;           /* Pointer to parent process. */
        LIST_ENTRY(proc) p_sibling;     /* List of sibling processes. */
        LIST_HEAD(, proc) p_children;   /* Pointer to list of children. */

        struct callout_handle p_ithandle; /*
                                              * Callout handle for scheduling
                                              * p_realtimer.
                                              */

        pid_t   p_oppid;         /* Save parent pid during ptrace. XXX */
        int     p_dupfd;         /* Sideways return value from fdopen. XXX */

        struct  vmspace *p_vmspace;     /* Address space. */

        /* scheduling */
        u_int   p_estcpu;        /* Time averaged value of p_cpticks. */
        int     p_cpticks;       /* Ticks of cpu time. */
        fixpt_t p_pctcpu;        /* %cpu for this process during p_swtime */
        void    *p_wchan;        /* Sleep address. */
        const char *p_wmesg;     /* Reason for sleep. */
        u_int   p_swtime;        /* Time swapped in or out. */
        u_int   p_slptime;       /* Time since last blocked. */

        struct  itimerval p_realtimer;  /* Alarm timer. */
        struct  timeval p_rtime;        /* Real time. */
        u_quad_t p_uticks;              /* Statclock hits in user mode. */
        u_quad_t p_sticks;              /* Statclock hits in system mode. */
        u_quad_t p_iticks;              /* Statclock hits processing intr. */
        struct  timeval *p_sleepend;    /* Wake time for nanosleep & friends */

        int     p_traceflag;            /* Kernel trace points. */
        struct  vnode *p_tracep;        /* Trace to vnode. */

        int     p_siglist;              /* Signals arrived but not delivered. */

        struct  vnode *p_textvp;        /* Vnode of executable. */

        char    p_lock;                 /* Process lock (prevent swap) count. */
        char    p_oncpu;                /* Which cpu we are on */
        char    p_lastcpu;              /* Last cpu we were on */
        char    p_pad2;                 /* alignment */

        short   p_locks;                /* DEBUG: lockmgr count of held locks */
        short   p_simple_locks;         /* DEBUG: count of held simple locks */
        register_t p_retval[2];         /* syscall aux returns */

        sigset_t p_sigmask;     /* Current signal mask. */
        sigset_t p_sigignore;   /* Signals being ignored. */
        sigset_t p_sigcatch;    /* Signals being caught by user. */

        u_char  p_priority;     /* Process priority. */
        u_char  p_usrpri;       /* User-priority based on p_cpu and p_nice. */
        char    p_nice;         /* Process "nice" value. */
        char    p_comm[MAXCOMLEN+1];

        struct  pgrp *p_pgrp;   /* Pointer to process group. */

        struct  sysentvec *p_sysent; /* System call dispatch information. */

        struct  rtprio p_rtprio;        /* Realtime priority. */

        struct  user *p_addr;   /* Kernel virtual addr of u-area (PROC ONLY). */
        struct  mdproc p_md;    /* Any machine-dependent fields. */

        u_short p_xstat;        /* Exit status for wait; also stop signal. */
        u_short p_acflag;       /* Accounting flags. */
        struct  rusage *p_ru;   /* Exit information. XXX */

        int     p_nthreads;     /* number of threads (only in leader) */
        void    *p_aioinfo;     /* ASYNC I/O info */
        int     p_wakeup;       /* thread id */
        struct proc *p_peers;   
        struct proc *p_leader;
};

Κάθε διεργασία μπορεί να βρίσκεται σε μια από τις παρακάτω καταστάσεις:

#define SIDL    1               /* Process being created by fork. */
#define SRUN    2               /* Currently runnable. */
#define SSLEEP  3               /* Sleeping on an address. */
#define SSTOP   4               /* Process debugging or suspension. */
#define SZOMB   5               /* Awaiting collection by parent. */

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

Διαχείριση αρχείων

Η διαχείριση αρχείων βασίζεται στη δομή δεδομένων του πίνακα δεικτών, inode, η οποία περιέχει πληροφορίες για κάθε αρχείο. Τα βασικά στοιχεία της δομής που βρίσκονται στη μνήμη περιέχουν στοιχεία για τη διαχείριση του πίνακα των δεικτών:

struct inode {
        struct   lock i_lock;   /* Inode lock. >Keep this first< */
        LIST_ENTRY(inode) i_hash;/* Hash chain. */
        struct  vnode  *i_vnode;/* Vnode associated with this inode. */
        struct  vnode  *i_devvp;/* Vnode for block I/O. */
        u_int32_t i_flag;       /* flags, see below */
        dev_t     i_dev;        /* Device associated with the inode. */
        ino_t     i_number;     /* The identity of the inode. */

        union {                 /* Associated filesystem. */
                struct  fs *fs;         /* FFS */
                struct  lfs *lfs;       /* LFS */
                struct  ext2_sb_info *e2fs;     /* EXT2FS */
        } inode_u;
        struct   dquot *i_dquot[MAXQUOTAS]; /* Dquot structures. */
        u_quad_t i_modrev;      /* Revision level for NFS lease. */
        struct   lockf *i_lockf;/* Head of byte-level lock list. */
        /*
         * The on-disk dinode itself.
         */
        struct  dinode i_din;   /* 128 bytes of the on-disk dinode. */
};

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

struct dinode {
        u_int16_t       di_mode;        /*   0: IFMT, permissions; see below. */
        int16_t         di_nlink;       /*   2: File link count. */
        u_int64_t       di_size;        /*   8: File byte count. */
        int32_t         di_atime;       /*  16: Last access time. */
        int32_t         di_atimensec;   /*  20: Last access time. */
        int32_t         di_mtime;       /*  24: Last modified time. */
        int32_t         di_mtimensec;   /*  28: Last modified time. */
        int32_t         di_ctime;       /*  32: Last inode change time. */
        int32_t         di_ctimensec;   /*  36: Last inode change time. */
        ufs_daddr_t     di_db[NDADDR];  /*  40: Direct disk blocks. */
        ufs_daddr_t     di_ib[NIADDR];  /*  88: Indirect disk blocks. */
        u_int32_t       di_flags;       /* 100: Status flags (chflags). */
        int32_t         di_blocks;      /* 104: Blocks actually held. */
        int32_t         di_gen;         /* 108: Generation number. */
        u_int32_t       di_uid;         /* 112: File owner. */
        u_int32_t       di_gid;         /* 116: File group. */
        int32_t         di_spare[2];    /* 120: Reserved; currently unused */
};

Διαχείριση καταλόγων

Οι κατάλογοι αρχείων του συστήματος έχουν την παρακάτω δομή:

struct  direct {
        u_int32_t d_ino;                /* inode number of entry */
        u_int16_t d_reclen;             /* length of this record */
        u_int8_t  d_type;               /* file type, see below */
        u_int8_t  d_namlen;             /* length of string in d_name */
        char      d_name[MAXNAMLEN + 1];/* name with length <= MAXNAMLEN */
};

Σε κάθε κατάλογο μπορούν να φυλαχθούν οι παρακάτω τύποι αρχείων:

#define DT_UNKNOWN       0	/* Άγνωστο */
#define DT_FIFO          1	/* Ουρά FIFO (σωλήνωση) */
#define DT_CHR           2	/* Συσκευή χαρακτήρων */
#define DT_DIR           4	/* Κατάλογος */
#define DT_BLK           6	/* Συσκευή τμημάτων */
#define DT_REG           8	/* Κανονικό αρχείο */
#define DT_LNK          10	/* Δεσμός */
#define DT_SOCK         12	/* Διαδιεργασιακή σύνδεση */

Διαχείριση συστημάτων αρχείων

Το σύστημα Unix υποστηρίζει πολλά διαφορετικά συστήματα αρχείων (Unix file system, Fast File System, ISO-9660 (CD-ROM file system), FAT, κ.λπ.). Ένα ιδεατό σύστημα αρχείων δρομολογεί τις κλήσεις με βάση ένα αντικειμενοστρεφές μοντέλο προς την υλοποίηση του αντίστοιχου συστήματος. Κάθε σύστημα αρχείων υποστηρίζει ορισμένες από τις παρακάτω κλήσεις:

access(struct vop_access_args *);
advlock(struct vop_advlock_args *);
chmod(struct vnode *, int, struct ucred *, struct proc *);
chown(struct vnode *, uid_t, gid_t, struct ucred *, struct proc *);
close(struct vop_close_args *);
create(struct vop_create_args *);
getattr(struct vop_getattr_args *);
link(struct vop_link_args *);
makeinode(int mode, struct vnode *, struct vnode **, struct componentname *);
missingop(struct vop_generic_args *ap);
mkdir(struct vop_mkdir_args *);
mknod(struct vop_mknod_args *);
mmap(struct vop_mmap_args *);
open(struct vop_open_args *);
print(struct vop_print_args *);
readdir(struct vop_readdir_args *);
readlink(struct vop_readlink_args *);
remove(struct vop_remove_args *);
rename(struct vop_rename_args *);
rmdir(struct vop_rmdir_args *);
setattr(struct vop_setattr_args *);
strategy(struct vop_strategy_args *);
symlink(struct vop_symlink_args *);

Σελιδοποίηση

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

struct vm_page {
        TAILQ_ENTRY(vm_page) pageq;     /* queue info for FIFO queue or free list (P) */
        TAILQ_ENTRY(vm_page) hashq;     /* hash table links (O) */
        TAILQ_ENTRY(vm_page) listq;     /* pages in same object (O) */

        vm_object_t object;             /* which object am I in (O,P) */
        vm_pindex_t pindex;             /* offset into object (O,P) */
        vm_offset_t phys_addr;          /* physical address of page */
        u_short queue;                  /* page queue index */
        u_short flags,                  /* see below */
                pc;                     /* page color */
        u_short wire_count;             /* wired down maps refs (P) */
        short hold_count;               /* page hold count */
        u_char  act_count;              /* page usage count */
        u_char  busy;                   /* page busy count */
        /* NOTE that these must support one bit per DEV_BSIZE in a page!!! */
        /* so, on normal X86 kernels, they must be at least 8 bits wide */
        u_char  valid;                  /* map of valid DEV_BSIZE chunks */
        u_char  dirty;                  /* map of dirty DEV_BSIZE chunks */
};

Αντίστοιχα η σελίδα μπορεί να βρίσκεται σε μια από τις παρακάτω καταστάσεις:

#define PG_BUSY         0x01            /* page is in transit (O) */
#define PG_WANTED       0x02            /* someone is waiting for page (O) */
#define PG_TABLED       0x04            /* page is in VP table (O) */
#define PG_FICTITIOUS   0x08            /* physical page doesn't exist (O) */
#define PG_WRITEABLE    0x10            /* page is mapped writeable */
#define PG_MAPPED       0x20            /* page is mapped */
#define PG_ZERO         0x40            /* page is zeroed */
#define PG_REFERENCED   0x80            /* page has been referenced */
#define PG_CLEANCHK     0x100           /* page has been checked for cleaning */

Όλες οι σελίδες ανοίκουν σε μια από 5 διαφορετικές λίστες ταξινομημένες σύμφωνα με το κριτήριο LRU (Least Recently Used - Λιγότερο πρόσφατη χρησιμοποιημένη).

free: Σελίδες έτοιμες για χρήση.
cache: Σελίδες σχεδόν έτοιμες για χρήση αφού ελευθερωθούν από τη χρήση βοηθητικής μνήμης.
inactive: Σελίδες που δεν έχουν χρησιμοποιηθεί πρόσφατα και είναι υποψήφιες για νέα χρήση.
active: Σελίδες που έχουν πρόσφατα χρησιμοποιηθεί.
zero: Ελεύθερες σελίδες που έχουν μηδενιστεί.

Βιβλιογραφία

Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 363-435 Εκδόσεις Παπασωτηρίου, 1993.

Maurice J. Bach. The Design of the UNIX Operating System. Prentice-Hall, 1986.
Samuel J. Leffler, Marshall Kirk McKusick, Michael J. Karels, and John S. Quarterman. The Design and Implementation of the 4.3BSD Unix Operating System. Addison-Wesley, 1988.
Don Libes and Sandy Ressler. Life with UNIX. Prentice-Hall, 1989.
AT & T, editor. UNIX System Readings and Applications, volume I, II. Prentice-Hall, 1987.
Andrew S. Tanenbaum. Operating Systems: Design and Implementation. Prentice-Hall, 1987.
Mitchell Waite, editor. UNIX Papers for UNIX Developers and Power Users. Howard W. Sams & Company, 1987.

Δομή του λειτουργικού συστήματος Windows-NT

Ιστορία

Η ανάπτυξη του λειτουργικού συστήματος Windows NT ξεκίνησε από τη Microsoft το 1988 ως αποτέλεσμα της απογοήτευσης της Microsoft σχετικά με το λειτουργικό σύστημα OS/2 το οποίο ανέπτυσσε σε συνεργασία με την IBM. Συγκεκριμένα, το OS/2 βασιζόταν σε τεχνολογικές αποφάσεις που δεν επέτρεπαν την εκμετάλλευση ανερχομένων τεχνολογιών όπως:

των επεξεργαστών τεχνολογίας RISC (Reduced Instruction Set Computer), και
των τεχνολογιών συμμετρικής πολυεπεξεργασίας (symmetric multiprocessing (SMP)).

Στην ανάπτυξη ηγετικό ρόλο έπαιξε ο Dave Cutler ο οποίος προερχόμενος από την εταιρία Digital ήταν βασικός αρχιτέκτονας του λειτουργικού συστήματος VAX VMS.

Στόχοι

Ο σχεδιασμός και η υλοποίηση των Windows NT βασίστηκαν σε ορισμένους βασικούς στόχους.

Μεταφερσιμότητα

Υποστήριξη πολλαπλών υπολογιστικών αρχιτεκτονικών
- Intel x86/Pentium
- DEC Alpha AXP
- MIPS R4x00 (δεν υποστηρίζεται πλέον)
- Intergraph Clipper (δεν υποστηρίχθηκε ποτέ εμπορικά;)
Απομόνωση των τμημάτων που έχουν άμεση σχέση με το υλικό.
Στη δομή περιλαμβάνεται ένα επίπεδο αφαίρεσης ιδιοτήτων του υλικού το Hardware Abstraction Layer (HAL).

Ασφάλεια

Σχεδιασμένο για να μπορεί να πιστοποιηθεί σε επίπεδο C2
Όλα τα αντικείμενα στα οποία η πρόσβαση μπορεί να γίνει από πάνω από μια οντότητα προστατεύονται μέσω μιας λίστας ελέγχου προσπέλασης.

Συμβατότητα

MS-DOS και Windows 3.X
LAN Manager (η υποστήριξη δικτύου PC της IBM)
Μη γραφικές εφαρμογές 16 bit του OS/2 1.X
Συστήματα αρχείων FAT (MS-DOS) και HPFS (OS/2)
POSIX (Unix)

Επεκτασιμότητα

Επεκτάσεις χωρίς προνομιούχο κώδικα (υποσυστήματα)
Οδηγοί συσκευών
Συστήματα αρχείων
Συστήματα αρχείων δικτύου (network redirectors)

Στιβαρότητα

(Προφανώς σε σχέση με άλλα λειτουργικά συστήματα της Microsoft)

Προβληματικές εφαρμογές δεν επηρεάζουν όλο το σύστημα
Όρια χρήσης ανά χρήστη για προστασία των πόρων του συστήματος
Όλες οι κλήσεις επιστρέφουν κωδικό λάθους
Δομημένη διαχείριση εξαιρέσεων (structured exception handling)

Διασυνδεσιμότητα

LAN Manager (IBM PC)
TCP/IP (Internet)
DECNet (Digital)
Υπηρεσίες SNA (ΙΒΜ mini/mainframe)
Macintosh (Apple)
Netware (Novell)

Διεθνοποίηση

Εύκολη τοπική προσαρμογή
Όλες οι συμβολοσειρές είναι σε Unicode

Μικροπυρήνας

Εκτελεστής
Υποσύστημα εισόδου εξόδου		Παρακολουθητής ασφάλειας	Διαδιεργασιακή επικοινωνία	Υπηρεσίες αντικειμένων	Ιδεατή μνήμη	Δομή διεργασίας
Συστήματα αρχείων	Διαχείριση αντικειμένων	Εκτελεστής
Οδηγοί συσκευών	Αφαίρεσης ιδιοτήτων του υλικού (HAL)	Μικροπυρήνας
Διεπαφή υλικού
Συσκευές εισόδου εξόδου	Απευθείας πρόσβαση στη μνήμη (DMA)	Απεικόνιση του διαύλου	Ρολόι και χρονόμετρα	Έλεγχος βοηθητικής μνήμης	Διεκπεραίωση διακοπών	Αρχιτεκτονική προνομίων

Τα Windows NT βασίζονται στη δομή του μικροπυρήνα. Αυτός προσφέρει τις παρακάτω υπηρεσίες:

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

Το σύνολο του κώδικα είναι περίπου 60Κ. Ο κώδικας εκτελείται χωρίς προεκχώρηση και σελιδοποίηση, αλλά με υποστήριξη διακοπών.

Τα αντικείμενα διεκπεραίωσης είναι:

νήματα (threads),
αμοιβαίος αποκλεισμός,
συμβάντα,
σημαφόροι,
χρονόμετρα,

Τα αντικείμενα ελέγχου είναι:

διεργασίες,
διακοπές,
ουρές συσκευών,
ασύγχρονες κλήσεις διαδικασιών,
κλήσεις διαδικασιών υπό αναβολή.

Εκτελεστής

Ο εκτελεστής αποτελεί το άνω τμήμα του πυρήνα και επικοινωνεί με τις διεργασίες του χρήστη. Περιλαμβάνει ξεχωριστά τμήματα τα οποία προσφέρουν συγκεκριμένες υπηρεσίες. Τμήματα του εκτελεστή μπορούν να βρίσκονται σε ιδεατή μνήμη μέσω σελιδοποίησης.

Υπηρεσίες διαχείρισης αντικειμένων

Οι υπηρεσίες διαχείρισης αντικειμένων προσφέρουν:

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

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

Το υποσύστημα διαχείρισης μνήμης προσφέρει:

περιβάλλον 4GB σελιδοποιημένης μνήμης,
αρχεία που απεικονίζονται στη μνήμη,
λειτουργίες μεταξύ διεργασιών,
σελίδες που αντιγράφονται κατά την εγγραφή τους,
πολλαπλά αρχεία σελιδοποίησης,
υποστήριξη για το διαχειριστή κρυφής μνήμης.

Υποσύστημα εισόδου εξόδου

Το υποσύστημα εισόδου και εξόδου προσφέρει:

ασύγχρονο μοντέλο εισόδου και εξόδου,
αντικείμενα στα οποία η πρόσβαση γίνεται με τον τρόπο open, operate, close,
υπηρεσίες για οδηγούς συσκευών και συστήματα αρχείων,
γενικευμένη κρυφή μνήμη, ενοποιημένη με το σύστημα διαχείρισης μνήμης.

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

Το σύστημα αρχείων NTFS έχει τα παρακάτω χαρακτηριστικά:

υποστηρίζει μεγάλους δίσκους και αρχεία με τη χρήση 64 bit για το μέγεθος του αρχείου,
επιτρέπει την αποκατάστασή του μετά από ανώμαλες καταστάσεις σε μικρό χρόνο,
όλα τα ονόματα των αρχείων φυλάσσονται σε UNICODE,
η πρόσβαση σε αρχεία γίνεται με βάση λίστες ελέγχου πρόσβασης,

Διαδιεργασιακή επικοινωνία

Η διαδιεργασιακή επικοινωνία γίνεται μέσω του μηχανισμού Local Procedure Call (τοπική κλήση διαδικασίας). Ο μηχανισμός αυτός αποτελεί μια αποδοτική υλοποίηση της κλήσης διαδικασιών σε απομακρυσμένους υπολογιστές (remote procedure call). Οι διεργασίες μπορούν να καλούν διαδικασίες σε άλλες διεργασίες μέσω του εκτελεστή και να μεταφέρουν δεδομένα μέσω διαμοιρασμένης μνήμης. Για λόγους ασφαλείας μια διεργασία εξυπηρετητή μπορεί να υποδυθεί τα χαρακτηριστικά ασφαλείας του πελάτη που την καλεί. Η εξυπηρέτηση της επικοινωνίας γίνεται μέσω ενός ξεχωριστού νήματος για κάθε σύνδεση μεταξύ δύο διεργασιών. Το ίδιο μοντέλο επικοινωνίας χρησιμοποιείται και για τις κλήσεις από τις διεργασίες προς το λειτουργικό σύστημα.

Πολιτική σελιδοποίησης

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

Υποσυστήματα

Τα υποσυστήματα (subsystems) των Windows ΝΤ επιτρέπουν τη μίμηση διαφορετικών συστημάτων:

Windows (περιλαμβάνει και εφαρμογές MS-DOS και Windows 3.1)
POSIX (για εφαρμογές Unix)
16 bit OS/2
περιβάλλον αποσφαλμάτωσης (ελέγχει εφαρμογές για λάθη)

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

Νήματα

Τα νήματα προσδίδουν στο λειτουργικό σύστημα τα παρακάτω πλεονεκτήματα:

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

Ακόμα, τα νήματα επιτρέπουν στις εφαρμογές:

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

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

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

Συγχρονισμός

Για την υλοποίηση συγχρονισμού προσφέρονται οι παρακάτω μηχανισμοί:

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

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

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

Η διαχείριση της μνήμης στα Windows NT έχει τα παρακάτω ιδιαίτερα χαρακτηριστικά:

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

Βιβλιογραφία

Helen Custer. Inside Windows NT. Microsoft Press, Redmond, WA, USA, 1992.
Usenix Association. USENIX Windows NT Workshop, Seattle, Washington, USA, August 1997.

Θέματα εξετάσεων

Πρόοδος 1997

ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΙΓΑΙΟΥ

Τμήμα Μαθηματικών

ΛΕΙΤΟΥΡΓΙΚΑ ΣΥΣΤΗΜΑΤΑ Ι

(1η Πρόοδος)

Διδάσκων: Διομήδης Σπινέλλης Νοέμβριος 1997

Θέμα 1ο:

Τι είναι ο χρονοδρομολογητής (scheduler);
Τι στόχους πρέπει να έχει ο αλγόριθμος χρονοπρογραμματισμού;

Θέμα 2ο:

Αναλύστε συνηθισμένες δομές δεδομένων με τις οποίες γίνεται η κατανομή χώρου στο δίσκο για την υλοποίηση αρχείων.
Σε τι διαφέρει η εναλλαγή (swapping) από τη σελιδοποίηση (paging);

Θέμα 3ο:

Σε τι διαφέρει η πολιτική από το μηχανισμό ασφαλείας; Δώστε παραδείγματα.
Για επιθέσεις σε υπολογιστικά συστήματα χρησιμοποιούνται μεταξύ άλλων και οι τεχνολογίες του "Δουρείου Ίππου" (Trojan Horse), της "Καταπακτής" (Trapdoor), και της "Ωρολογιακής Βόμβας" (Time Bomb). Εξηγήστε με παραδείγματα τι είναι οι τεχνολογίες αυτές.

Θέμα 4ο:

Σε τι χρησιμεύει το σύστημα αρχείων που προσφέρει το λειτουργικό σύστημα;

Θέμα 5ο:

Σχεδιάστε το ιεραρχικό δένδρο που θα προκύψει από την εκτέλεση των εντολών:
cd /; mkdir a b c a/a b/a; cd a; mkdir ../e ../a/f ../b/a/g; cd ../b/./; mkdir /a/k a/b ../a/./b /c
Με τη χρήση των εντολών uniq (αφαιρεί τις κοινές γραμμές από ένα ταξινομημένο αρχείο), sort (ταξινόμηση), makewords (σπάει ένα αρχείο σε μια λέξη ανά γραμμή), comm (βρίσκει τις μη κοινές γραμμές ανάμεσα σε δύο ταξινομημένα αρχεία), και του λεξικού /usr/dict/words περιγράψτε αδρά τη δομή ενός ορθογραφικού διορθωτή.

Θέμα 6ο:

Με βάση την παρακάτω σημειολογία κανονικών εκφράσεων:

^ Αρχή της γραμμής

$ Τέλος της γραμμής

. Οποιοδήποτε γράμμα

[abc] Ένα από τα γράμματα a, b, ή c

(Έκφραση) Το περιεχόμενο στην παρένθεση

\1 \2 ... \ν To περιεχόμενο της νοστής παρένθεσης

ορίστε κανονική έκφραση που να βρίσκει λέξεις με παλινδρομήματα 6 γραμμάτων (π.χ. glossolalia, staccato),
ορίστε κανονική έκφραση που να βρίσκει λέξεις με τρία συνεχόμενα φωνήεντα.

Διάρκεια εξέτασης 1.5 ώρα. Καλή επιτυχία!

Εξεταστική περιόδος Ιανουαρίου 1998

ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΙΓΑΙΟΥ

Τμήμα Μαθηματικών

ΛΕΙΤΟΥΡΓΙΚΑ ΣΥΣΤΗΜΑΤΑ Ι	Εξεταστική περίοδος Ιανουαρίου 1998
Διδάσκων: Διομήδης Σπινέλλης

Θέμα 1ο:

Κατά την παράλληλη εκτέλεση διεργασιών τι ονομάζουμε συνθήκη ανταγωνισμού; Δώστε ένα παράδειγμα.
Σε τι διαφέρει ο χρονοπρογραμματισμός προεκχώρισης (preemptive scheduling) από το μη προεκχωρητικό χρονοπρογραμματισμό (nonpreemptive scheduling); Πως μπορεί να υλοποιηθεί το κάθε είδος;

Θέμα 2ο:

Η Microsoft αποφασίζει να διπλασιάσει το μήκος της σελίδας του συστήματος σελιδοποίησης των Windows NT. Τι επιπτώσεις θα έχει η επιλογή αυτή στην εσωτερική δομή, τις απαιτήσεις μνήμης, και τις επιδόσεις του λειτουργικού συστήματος;
Ποιες τεχνικές μπορούν να χρησιμοποιηθούν για τη βελτίωση της επίδοσης του συστήματος αρχείων;

Θέμα 3ο:

Ποιες συνθήκες πρέπει να ικανοποιούνται για να δημιουργηθεί αδιέξοδο; Πως μπορούν να αντιμετωπιστούν τα αδιέξοδα;
Γιατί απαιτείται η πιστοποίηση της ταυτότητας του χρήστη για την προστασία ενός συστήματος; Πως μπορεί να πραγματοποιηθεί η πιστοποίηση αυτή; Δώστε ένα παράδειγμα.

Θέμα 4ο:

Σχεδιάστε το ιεραρχικό δένδρο που θα προκύψει από την εκτέλεση των εντολών:
cd /; mkdir a b c a/a b/a; cd a; mkdir ../e ../a/f ../b/a/g; cd ../b/./; mkdir /a/k a/b ../a/./b /c
Με τη χρήση των εντολών uniq -c (μετράει τις κοινές γραμμές σε ένα ταξινομημένο αρχείο), sort (ταξινόμηση), και makewords (σπάει ένα αρχείο σε μια λέξη ανά γραμμή) περιγράψτε αδρά τη δομή ενός προγράμματος που τυπώνει έναν πίνακα με τη συχνότητα κάθε λέξης σε ένα κείμενο. Ο πίνακας πρέπει να είναι ταξινομημένος ανάλογα με τη συχνότητα της κάθε λέξης.

Θέμα 5ο:

Με βάση την παρακάτω σημειολογία κανονικών εκφράσεων:

^ Αρχή της γραμμής

$ Τέλος της γραμμής

. Οποιοδήποτε γράμμα

* Καμία ή περισσότερες φορές

[abc] Ένα από τα γράμματα a, b, ή c

(έκφραση) Το περιεχόμενο στην παρένθεση

\1 \2 ... \ν To περιεχόμενο της ν-στής παρένθεσης

ορίστε κανονική έκφραση που να βρίσκει λέξεις που να αρχίζουν και να τελειώνουν με το ίδιο γράμμα (π.χ. erase, alpha, kodak).
ορίστε κανονική έκφραση που να βρίσκει λέξεις τριών γραμμάτων που να αρχίζουν και να τελειώνουν με σύμφωνο (π.χ. get, him).

Διάρκεια εξέτασης 1.5 ώρα. Καλή επιτυχία!

Εξεταστική περιόδος Σεπτεμβρίου 1998

ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΙΓΑΙΟΥ

Τμήμα Μαθηματικών

ΛΕΙΤΟΥΡΓΙΚΑ ΣΥΣΤΗΜΑΤΑ Ι

Εξεταστική περίοδος

Σεπτεμβρίου 1998

Διδάσκων: Διομήδης Σπινέλλης

Θέμα 1ο:

Περιγράψτε και συγκρίνετε μεταξύ τους δύο διαφορετικές λύσεις στο πρόβλημα του αμοιβαίου αποκλεισμού.

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

Θέμα 2ο:

Οι υπολογιστές του κέντρου πληροφορικής μπορούν να εκτελέσουν προγράμματα που απαιτούν μέχρι και 64ΜΒ μνήμης αν και διαθέτουν μόνο 32ΜΒ φυσικής μνήμης. Εξηγήστε λεπτομερειακά πως υλοποιείται η δυνατότητα αυτή.

Θέμα 3ο:

Τι λύσεις μπορεί να προσφέρει η κρυπτογραφία σε θέματα ασφάλειας; Εξηγήστε.

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

Θέμα 4ο:

Σχεδιάστε το ιεραρχικό δένδρο που θα προκύψει από την εκτέλεση των εντολών:
cd /; mkdir a b c b/a a/a; cd a; mkdir ../e ../a/f ../b/a/g; cd ../b/./; mkdir /a/k a/b ../a/./b /c

Εξηγήστε το τελικό αποτέλεσμα της παρακάτω σειράς εντολών του φλοιού sh:

for i in *.c
do
	echo "mv $i $i.old"
done | sh

Θέμα 5ο:

Με βάση την παρακάτω σημειολογία κανονικών εκφράσεων:

^ Αρχή της γραμμής

$ Τέλος της γραμμής

. Οποιοδήποτε γράμμα

* Καμία ή περισσότερες φορές

[abc] Ένα από τα γράμματα a, b, ή c

(έκφραση) Το περιεχόμενο στην παρένθεση

\1 \2 ... \ν To περιεχόμενο της ν-στής παρένθεσης

ορίστε κανονική έκφραση που να βρίσκει λέξεις που να περιέχουν με τη σειρά τα τέσσερα πρώτα γράμματα του λατινικού αλφαβήτου (π.χ. abducted, barbecued, fabricated).

ορίστε κανονική έκφραση που να βρίσκει λέξεις που να αρχίζουν και να τελειώνουν με το ίδιο ζεύγος χαρακτήρων (π.χ. tomato, amalgam, decade, eraser, sense).

Διάρκεια εξέτασης 1.5 ώρα.

Καλή επιτυχία!

Περιεχόμενα