Διεργασίες

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

• Διαφορά διεργασίας και προγράμματος
• Ιεραρχίες διεργασιών
• Καταστάσεις διεργασιών
  • Εκτελούμενη (running)
  • Εκτελέσιμη (runnable)
  • Υπό αναστολή (blocked)
• Μεταβάσεις
  • Αναστολή λόγω αναμονής εξωτερικού συμβάντος
    Επιλογή άλλης διεργασίας από τον χρονοπρογραμματιστή (scheduler)
    • Επιλογή της διεργασίας από το χρονοπρογραμματιστή
    • Λήξη της αναμονής του εξωτερικού συμβάντος
  • Πίνακας διεργασιών

    Διαχείριση διεργασιών	Διαχείριση μνήμης	Διαχείριση αρχείων
    Καταχωρητές Δείκτης εντολών προγράμματος Λέξη κατάστασης προγράμματος Δείκτης στοίβας Κατάσταση διεργασίας Χρόνος εκκίνησης διεργασίας Χρόνος χρήσης 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) μεταξύ των κρίσιμων τμημάτων πρέπει να εξασφαλίζει:

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

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

  Ορισμένοι τρόποι για την επίτευξη του αμοιβαίου αποκλεισμού είναι οι παρακάτω:
  • Απενεργοποίηση των διακοπών
  • Αυστηρή εναλλαγή
  • Λύση του 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           
  

  • Περιεχόμενα

   Τελευταία αλλαγή: Δευτέρα, 2 Αυγούστου 2004 12:27 πμ
   Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».