Τεχνικές Εκτίμησης Υπολογιστικών Συστημάτων και Δικτύων — Ιανουάριος 2025¶
Μεταγραφή από τη φωτογραφία 25_.jpg (3 θέματα).
25_.jpg¶
ΤΕΧΝΙΚΕΣ ΕΚΤΙΜΗΣΗΣ ΥΠΟΛΟΓΙΣΤΙΚΩΝ ΣΥΣΤΗΜΑΤΩΝ¶
Εξέταση Ιανουαρίου 2025¶
ΘΕΜΑ 1 (20%)¶
(a) Περιγράψετε και συγκρίνετε τα τρία συστήματα αναμονής G/M/4/80/100, G/M/4/100/100, G/M/4/120/100. Αν θέλετε να συνδυάσετε την καλύτερη δυνατή εξυπηρέτηση όλων των χρηστών με όσο το δυνατό μικρότερο κόστος κατασκευής, ποιο θα επιλέγατε ως μοντέλο για το πραγματικό σας σύστημα και γιατί;
(b) Θέλουμε να κατασκευάσουμε έναν προσομοιωτή για το δίκτυο του Θέματος 3. Ποια γεγονότα θα πρέπει να συγκροτούν τη λίστα γεγονότων;
ΘΕΜΑ 2 (35%)¶
Στον παρακάτω γράφο, ένα αντικείμενο μετακινείται κάθε ένα sec, από κόμβο σε κόμβο πάνω στις αμφίδρομες ακμές του σχήματος, επιλέγοντας ισοπίθανα από τις δυνατές διαδρομές.
[Σχήμα: Γράφος με 4 κόμβους (1, 2, 3, 4) συνδεδεμένους με ακμές: 1-2, 3-4, και χιαστί 1-4, 2-3.]
Θεωρήστε την αλυσίδα Markov διακριτού χρόνου, οι καταστάσεις της οποίας αντιστοιχούν στον κόμβο του γράφου στον οποίο βρίσκεται το αντικείμενο.
(a) Σχεδιάστε το διάγραμμα καταστάσεων – πιθανοτήτων μεταβάσεων της αλυσίδας. Χαρακτηρίστε την αλυσίδα και τις καταστάσεις της. Παρουσιάστε τον πίνακα μεταβάσεων \(\vec{P}\) της αλυσίδας.
(b) Αν η αλυσίδα έχει μόνιμη κατάσταση, βρείτε τις πιθανότητες μόνιμης κατάστασης.
(c) Πως μεταβάλλονται τα αποτελέσματα του (b) αν δεν έχουμε ισοπίθανη μετακίνηση από τον κόμβο 4 (μόνο), αλλά η πιθανότητα μετακίνησης από τον κόμβο 4 στον κόμβο 1 είναι τριπλάσια από την πιθανότητα μετακίνησης από τον 4 στον 3. Σχολιάστε τα αποτελέσματα σε σχέση με αυτά του (b).
ΘΕΜΑ 3 (45%)¶
Σας δίνεται το παρακάτω απλό μοντέλο κεντρικού εξυπηρετητή (central server model).
Οι εργασίες φθάνουν με εκθετικό τρόπο από το περιβάλλον στη CPU με μέσο ρυθμό \(\lambda = 2\) εργασίες/sec. Δίνεται ότι \(r_{30} = 0,06\) και \(r_{31} = 0,4\). Αν γνωρίζουμε ότι όλες οι εξυπηρετήσεις είναι εκθετικές και \(\mu_3 = 200\) εργασίες/sec για τη CPU και \(\mu_1 = 20\) εργασίες/sec, \(\mu_2 = 25\) εργασίες/sec για τους δύο δίσκους, ζητούνται τα παρακάτω:
(a) Οι ρυθμαποδόσεις (throughputs) των τριών επιμέρους συστημάτων.
(b) Οι χρησιμοποιήσεις \(\rho_i\), \(i = 1, 2, 3\) των τριών συστημάτων. Ποιο είναι το bottleneck του δικτύου και γιατί;
(c) Την πιθανότητα να είναι ακριβώς μία εργασία ταυτόχρονα σε κάθε ένα από τα επιμέρους συστήματα.
(d) Ο μέσος αριθμός εργασιών σε κάθε σύστημα και στο δίκτυο συνολικά.
(e) Ο μέσος χρόνος απόκρισης (response time) μιας εργασίας σε μία επίσκεψη: (1) σε κάθε επιμέρους σύστημα, και στο δίκτυο συνολικά. Συγκρίνετε και σχολιάστε τα αποτελέσματά σας στις δύο περιπτώσεις.
(f) Ποια είναι η μέγιστη τιμή που μπορεί να πάρει το \(\lambda\), για να μην υπερφορτωθεί και γίνει ασταθές το δίκτυο;
[Σχήμα: Μοντέλο κεντρικού εξυπηρετητή: Ροή εισόδου \(\lambda\) στην CPU (\(\mu_3\)). Έξοδος από CPU διακλαδώνεται με πιθανότητα \(r_{31}\) προς Δίσκο 1 (\(\mu_1\)), με \(r_{30}\) προς Ολοκλήρωση Εργασίας, και προς Δίσκο 2 (\(\mu_2\)). Οι έξοδοι από Δίσκο 1 και Δίσκο 2 ανατροφοδοτούνται στην είσοδο της CPU.]
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2025-01¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
(a) Στην Kendall με συμβολισμό \(A/B/c/K/N\), το \(K\) είναι χωρητικότητα συστήματος και το \(N\) πληθυσμός χρηστών. Άρα: - \(G/M/4/80/100\): \(K=80<N=100\), άρα δεν μπορούν να βρίσκονται ταυτόχρονα και οι 100 χρήστες στο σύστημα· μέρος τους αποκλείεται/χάνεται λόγω περιορισμένης χωρητικότητας. Έχει μικρότερο κόστος χώρου αναμονής, αλλά χειρότερη εξυπηρέτηση συνολικά. - \(G/M/4/100/100\): \(K=N=100\), άρα όλοι οι χρήστες μπορούν δυνητικά να βρίσκονται στο σύστημα· δεν υπάρχει απώλεια λόγω χωρητικότητας. - \(G/M/4/120/100\): \(K=120>N=100\), άρα ως προς την αποδοχή χρηστών συμπεριφέρεται όπως το \(G/M/4/100/100\), αφού ποτέ δεν μπορούν να παρουσιαστούν πάνω από 100 εργασίες. Οι επιπλέον 20 θέσεις δεν χρησιμοποιούνται και αυξάνουν άσκοπα το κόστος.
Επομένως για καλύτερη δυνατή εξυπηρέτηση όλων των χρηστών με το ελάχιστο δυνατό κόστος κατασκευής επιλέγεται το
[
G/M/4/100/100.
]
(b) Για τον προσομοιωτή του κεντρικού συστήματος του Θέματος 3, στη λίστα μελλοντικών γεγονότων πρέπει να περιλαμβάνονται: 1. Εξωτερική άφιξη εργασίας στο σύστημα/CPU (και προγραμματισμός της επόμενης). 2. Ολοκλήρωση εξυπηρέτησης στην CPU. 3. Ολοκλήρωση εξυπηρέτησης στον Δίσκο 1 (επιστροφή στην CPU). 4. Ολοκλήρωση εξυπηρέτησης στον Δίσκο 2 (επιστροφή στην CPU). 5. Τερματισμός της προσομοίωσης (βοηθητικό γεγονός).
Στην ολοκλήρωση της CPU αποφασίζεται με βάση τις \(r_{30},r_{31},r_{32}\) αν η εργασία εξέρχεται, πηγαίνει στον Δίσκο 1 ή στον Δίσκο 2. Αν υπάρχουν ουρές, η έναρξη εξυπηρέτησης γίνεται αμέσως όταν ελευθερωθεί αντίστοιχος εξυπηρετητής και υπάρχει πελάτης, οπότε συνήθως δεν χρειάζεται ξεχωριστό μελλοντικό γεγονός «έναρξης εξυπηρέτησης».
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
(a) Οι ακμές του γράφου είναι \(1-2\), \(2-3\), \(3-4\), \(4-1\), δηλαδή ένας κύκλος \(1\leftrightarrow2\leftrightarrow3\leftrightarrow4\leftrightarrow1\). Από κάθε κόμβο η μετάβαση σε οποιονδήποτε από τους δύο γείτονες γίνεται με πιθανότητα \(1/2\). Άρα [ P= \begin{pmatrix} 0&1/2&0&1/2\ 1/2&0&1/2&0\ 0&1/2&0&1/2\ 1/2&0&1/2&0 \end{pmatrix}. ] Η αλυσίδα είναι πεπερασμένη, μη υποβιβάσιμη (irreducible), θετικά επαναληπτική και περιοδική με περίοδο \(2\), αφού ο γράφος είναι διμερής με σύνολα \(\{1,3\}\) και \(\{2,4\}\). Άρα δεν είναι απεριοδική/εργοδική με τη στενή έννοια, αλλά έχει μοναδική στάσιμη κατανομή.
(b) Λόγω συμμετρίας του κύκλου, η μόνιμη κατανομή είναι ομοιόμορφη: [ \pi_1=\pi_2=\pi_3=\pi_4=\frac14. ] Επαληθεύεται από \(\pi P=\pi\), π.χ. [ \pi_1=\frac12\pi_2+\frac12\pi_4=\frac14. ] Λόγω περιοδικότητας, το όριο \(\lim_{n\to\infty}P^n\) δεν συγκλίνει γενικά, αλλά η στάσιμη κατανομή είναι μοναδική.
(c) Τώρα μόνο για τον κόμβο 4 έχουμε [ p_{41}=\frac34,\qquad p_{43}=\frac14, ] ενώ οι άλλες μεταβάσεις μένουν \(1/2\). Ο πίνακας γίνεται [ P'= \begin{pmatrix} 0&1/2&0&1/2\ 1/2&0&1/2&0\ 0&1/2&0&1/2\ 3/4&0&1/4&0 \end{pmatrix}. ] Έστω \(\pi=(\pi_1,\pi_2,\pi_3,\pi_4)=(a,b,c,d)\). Οι εξισώσεις ισορροπίας είναι: [ a=\frac12 b+\frac34 d,\quad b=\frac12 a+\frac12 c,\quad c=\frac12 b+\frac14 d,\quad d=\frac12 a+\frac12 c. ] Από τις εξισώσεις για \(b,d\) παίρνουμε \(b=d\). Θέτοντας \(b=d=x\): [ a=\frac54 x,\qquad c=\frac34 x. ] Από \(a+b+c+d=1\): [ \left(\frac54+1+\frac34+1\right)x=4x=1 \Rightarrow x=\frac14. ] Άρα [ \pi=\left(\frac5{16},\frac14,\frac3{16},\frac14\right) =\left(\frac5{16},\frac4{16},\frac3{16},\frac4{16}\right). ] Η αλυσίδα παραμένει μη υποβιβάσιμη και περιοδική με περίοδο \(2\). Σε σχέση με το (b), η κατανομή δεν είναι πλέον ομοιόμορφη: αυξάνεται η πιθανότητα στον κόμβο 1, μειώνεται στον κόμβο 3, ενώ οι κόμβοι 2 και 4 μένουν στο \(1/4\). Αυτό οφείλεται στην προτίμηση της μετάβασης \(4\to1\) έναντι της \(4\to3\).
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Θεωρώ έναν εξυπηρετητή σε κάθε κόμβο (CPU, Δίσκος 1, Δίσκος 2). Από το σχήμα, η πιθανότητα μετάβασης από CPU σε Δίσκο 2 είναι [ r_{32}=1-r_{30}-r_{31}=1-0.06-0.4=0.54. ]
(a) Έστω \(X_i\) ο ρυθμός διέλευσης (throughput) από τον κόμβο \(i\). Ισχύει [ X_3=\lambda+r_{31}X_3+r_{32}X_3 \quad\Rightarrow\quad X_3=\frac{\lambda}{r_{30}}=\frac{2}{0.06}=\frac{100}{3}\approx33.333\ \text{εργ./s}. ] Άρα [ X_1=r_{31}X_3=0.4\cdot\frac{100}{3}=\frac{40}{3}\approx13.333\ \text{εργ./s}, ] [ X_2=r_{32}X_3=0.54\cdot\frac{100}{3}=18\ \text{εργ./s}. ] Δηλαδή [ X_1=\frac{40}{3},\qquad X_2=18,\qquad X_3=\frac{100}{3}\ \text{εργ./s}. ]
(b) Οι χρησιμοποιήσεις είναι [ \rho_1=\frac{X_1}{\mu_1}=\frac{40/3}{20}=\frac23\approx0.6667, ] [ \rho_2=\frac{X_2}{\mu_2}=\frac{18}{25}=0.72, ] [ \rho_3=\frac{X_3}{\mu_3}=\frac{100/3}{200}=\frac16\approx0.1667. ] Bottleneck είναι ο Δίσκος 2, γιατί έχει τη μεγαλύτερη χρησιμοποίηση: [ \rho_2=0.72>\rho_1=0.6667>\rho_3=0.1667. ] Αυτός ο κόμβος θα κορεσθεί πρώτος όταν αυξηθεί το εξωτερικό φορτίο.
(c) Σε ανοιχτό δίκτυο Jackson με εκθετικές εξυπηρετήσεις, οι οριακές κατανομές των αριθμών εργασιών στους κόμβους είναι ανεξάρτητες γεωμετρικές: [ P(N_i=n)=(1-\rho_i)\rho_i^n,\qquad n=0,1,2,\dots ] Άρα [ P(N_1=1)=(1-\rho_1)\rho_1=\frac13\cdot\frac23=\frac29, ] [ P(N_2=1)=(1-\rho_2)\rho_2=\frac7{25}\cdot\frac{18}{25}=\frac{126}{625}, ] [ P(N_3=1)=(1-\rho_3)\rho_3=\frac56\cdot\frac16=\frac5{36}. ] Επομένως η ζητούμενη πιθανότητα είναι [ P(N_1=N_2=N_3=1) =\frac29\cdot\frac{126}{625}\cdot\frac5{36} =\frac7{1125} \approx0.00622. ] Δηλαδή περίπου \(0.622\%\).
(d) Για κάθε κόμβο, \(E[N_i]=\dfrac{\rho_i}{1-\rho_i}\). Άρα [ E[N_1]=\frac{2/3}{1/3}=2, ] [ E[N_2]=\frac{18/25}{7/25}=\frac{18}{7}\approx2.5714, ] [ E[N_3]=\frac{1/6}{5/6}=\frac15=0.2. ] Ο συνολικός μέσος αριθμός εργασιών στο δίκτυο είναι [ E[N]=E[N_1]+E[N_2]+E[N_3] =2+\frac{18}{7}+\frac15 =\frac{167}{35}\approx4.7714. ]
(e) Ο μέσος χρόνος απόκρισης ανά επίσκεψη στον κόμβο \(i\) (αναμονή + εξυπηρέτηση) είναι [ R_i=\frac{1}{\mu_i-X_i}. ] Άρα [ R_1=\frac{1}{20-\frac{40}{3}} =\frac{3}{20}=0.15\ \text{s}, ] [ R_2=\frac{1}{25-18} =\frac17\approx0.142857\ \text{s}, ] [ R_3=\frac{1}{200-\frac{100}{3}} =\frac{3}{500}=0.006\ \text{s}. ] Ο συνολικός μέσος χρόνος απόκρισης μιας εργασίας στο δίκτυο, από την εξωτερική άφιξη έως την οριστική αναχώρηση, είναι με τον νόμο του Little: [ R_{\text{δικτύου}}=\frac{E[N]}{\lambda} =\frac{167/35}{2} =\frac{167}{70}\approx2.3857\ \text{s}. ] Ισοδύναμα, [ R_{\text{δικτύου}} =\frac{X_1R_1+X_2R_2+X_3R_3}{\lambda}. ] Παρατηρούμε ότι ο CPU έχει πολύ μικρό χρόνο ανά επίσκεψη, αλλά επισκέπτεται κατά μέσο όρο \(1/r_{30}\approx16.67\) φορές ανά εργασία. Οι δίσκοι συμβάλλουν περισσότερο στη συνολική καθυστέρηση: ο Δίσκος 2 είναι bottleneck λόγω μεγαλύτερης χρησιμοποίησης, ενώ ο Δίσκος 1 έχει ελαφρώς μεγαλύτερο χρόνο ανά επίσκεψη επειδή έχει μικρότερο ρυθμό εξυπηρέτησης.
(f) Για ευστάθεια απαιτείται \(\rho_i<1\) για όλους τους κόμβους: [ \lambda<r_{30}\mu_3=0.06\cdot200=12, ] [ \lambda<\frac{r_{30}\mu_1}{r_{31}} =\frac{0.06\cdot20}{0.4}=3, ] [ \lambda<\frac{r_{30}\mu_2}{r_{32}} =\frac{0.06\cdot25}{0.54} =\frac{25}{9}\approx2.7778. ] Επομένως ο περιοριστικός κόμβος είναι ο Δίσκος 2 και [ \lambda_{\max}=\frac{25}{9}\approx2.7778\ \text{εργ./s}. ] Για ασυμπτωτική ευστάθεια απαιτείται αυστηρά [ \lambda<\frac{25}{9}\ \text{εργ./s}. ] Στο όριο \(\lambda=25/9\) ο Δίσκος 2 φτάνει \(\rho_2=1\) και το σύστημα γίνεται ασταθές/κορεσμένο.