Τεχνικές Εκτίμησης Υπολογιστικών Συστημάτων και Δικτύων — Σεπτέμβριος 2015¶
Μεταγραφή από το αρχείο septembrios_15.pdf (2 σελίδες, 4 θέματα).
septembrios_15.pdf¶
Δ' & Ε' ΕΤΟΣ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΤΕΧΝΙΚΕΣ ΕΚΤΙΜΗΣΗΣ ΥΠΟΛΟΓΙΣΤΙΚΩΝ ΣΥΣΤΗΜΑΤΩΝ Εξέταση Σεπτεμβρίου 2015
ΘΕΜΑ 1 (20%)¶
Η απόδοση ενός υπολογιστή υπό σχεδιασμό, εξαρτάται από τους εξής τρεις παράγοντες με τρία επίπεδα ο καθένας: (1) Τύπος CPU: Pentium, Alpha, SPARC. (2) Λειτουργικό Σύστημα: Windows, Linux, UNIX. (3) Τύπος σκληρού δίσκου: Α, Β, Γ. Προσδιορίστε τον αριθμό των πειραμάτων που απαιτούνται για το σχεδιασμό της απόδοσης του συστήματος στις παρακάτω περιπτώσεις: (a) Υπάρχει σημαντική αλληλεπίδραση μεταξύ των τριών παραγόντων. (b) Δεν υπάρχει αλληλεπίδραση μεταξύ των παραγόντων. (c) Η επιλογή σκληρού δίσκου δεν παίζει σημαντικό ρόλο.
ΘΕΜΑ 2 (25%)¶
Θεωρήστε μια γραμμή modem η οποία χρησιμοποιείται για τη μετάδοση χαρακτήρων των 8 bits. Η γραμμή έχει χωρητικότητα (capacity) 4 Mbps και υποθέτουμε ότι ο χρόνος μετάδοσης των δεδομένων ακολουθεί την εκθετική κατανομή. Τα δεδομένα φθάνουν για μετάδοση στη γραμμή με τρόπο Poisson και με μέσο ρυθμό 450.000 cps (characters per second). Πριν τη γραμμή υπάρχει ένα buffer πρακτικά άπειρης χωρητικότητας όπου περιμένουν τα δεδομένα για μετάδοση. Ζητούνται τα παρακάτω: (a) Ποιο είναι το εύρος ζώνης (bandwidth) της γραμμής, σε cps; (b) Ποιος είναι ο μέσος αριθμός χαρακτήρων που περιμένουν στο buffer για να μεταδοθούν; (c) Ποιος είναι ο μέσος χρόνος απόκρισης (response time) ενός χαρακτήρα;
ΘΕΜΑ 3 (20%)¶
Μία συσκευή μετάδοσης πακέτων δεδομένων μπορεί να βρεθεί σε τρεις καταστάσεις: 1. Μετάδοση πακέτου 2. Προετοιμασία για μετάδοση πακέτου 3. Αδράνεια
Όταν η συσκευή είναι σε κατάσταση Μετάδοσης, ανάλογα με το αν υπάρχουν στη συνέχεια πακέτα προς μετάδοση, με πιθανότητα 1/2 μεταβαίνει σε κατάσταση Προετοιμασίας και με πιθανότητα 1/2 σε κατάσταση Αδράνειας. Όταν είναι σε κατάσταση Προετοιμασίας, με πιθανότητα 3/4 μεταβαίνει σε κατάσταση Μετάδοσης και με πιθανότητα 1/4 θα ακυρωθεί η μετάδοση πακέτων και θα μεταβεί σε κατάσταση Αδράνειας. Τέλος, την κατάσταση Αδράνειας, ακολουθεί πάντα κατάσταση Προετοιμασίας. (a) Να σχεδιάσετε το διάγραμμα καταστάσεων – πιθανοτήτων μεταβάσεων της αλυσίδας Markov διακριτού χρόνου που μοντελοποιεί την παραπάνω λειτουργία. (b) Σε ποια από τις τρεις καταστάσεις είναι πιθανότερο να βρίσκεται η συσκευή; Πόση είναι η πιθανότητα αυτή;
ΘΕΜΑ 4 (35%)¶
Σας δίνεται το παρακάτω απλό μοντέλο κεντρικού εξυπηρετητή (central server model):
[Σχήμα: Κλειστό δίκτυο ουρών με N εργασίες. Μονάδα CPU με ρυθμό μ1. Μετά την CPU διακλάδωση: προς τα πάνω με πιθανότητα q=0.6 προς Γρήγορος Δίσκος με ρυθμό μ2, προς τα κάτω με πιθανότητα 1-q=0.4 προς Αργός Δίσκος με ρυθμό μ3. Οι έξοδοι των δύο δίσκων επιστρέφουν στην είσοδο της CPU.]
Δίνονται οι μέσοι χρόνοι της (εκθετικής) εξυπηρέτησης: \(1/\mu_1 = 45\text{ms}\), \(1/\mu_2 = 25\text{ms}\), \(1/\mu_3 = 90\text{ms}\) και η πιθανότητα δρομολόγησης \(q = 0{,}6\). (a) Για αριθμό εργασιών \(N = 2\) να επιλύσετε το σύστημα χρησιμοποιώντας τον αλγόριθμο του Buzen και να υπολογίσετε τα: (a1) Ποιος κόμβος του δικτύου είναι bottleneck και γιατί; (a2) Ποσοστό του χρόνου που είναι άεργη η CPU. (a3) Πιθανότητα να είναι ταυτόχρονα και οι 2 εργασίες στο γρήγορο δίσκο. (a4) Μέσο αριθμό εργασιών στον αργό δίσκο. (b) Να επιβεβαιώσετε τα παραπάνω αποτελέσματα λύνοντας το δίκτυο απευθείας με χρήση αλυσίδας Markov.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2015-09.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):septembrios_15_1.pdf
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2015-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
(a) Αφού υπάρχει σημαντική αλληλεπίδραση και των τριών παραγόντων, απαιτείται πλήρες παραγοντικό σχέδιο: [ 3\cdot 3\cdot 3=3^3=27 ] πειράματα.
(b) Αν δεν υπάρχει αλληλεπίδραση, αρκεί η μελέτη των κύριων επιδράσεων. Με ένα επίπεδο αναφοράς και δύο επιπλέον επίπεδα για κάθε παράγοντα: [ 1+3(3-1)=1+3\cdot 2=7 ] πειράματα.
(c) Αν ο τύπος σκληρού δίσκου δεν παίζει σημαντικό ρόλο, τον σταθεροποιούμε σε ένα επίπεδο και μένουν οι δύο άλλοι παράγοντες με 3 επίπεδα ο καθένας: [ 3\cdot 3=9 ] πειράματα.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Η γραμμή είναι ουρά \(M/M/1\). Η χωρητικότητα είναι [ C=4\text{ Mbps}=4\cdot 10^6\text{ bits/s}. ] Κάθε χαρακτήρας έχει \(8\) bits, άρα ο ρυθμός εξυπηρέτησης σε χαρακτήρες είναι [ \mu=\frac{4\cdot 10^6}{8}=500000\text{ cps}. ] Ο ρυθμός αφίξεων είναι \(\lambda=450000\text{ cps}\), άρα [ \rho=\frac{\lambda}{\mu}=\frac{450000}{500000}=0{,}9<1. ]
(a) Το εύρος ζώνης σε cps είναι [ \mu=500000\text{ cps}. ]
(b) Ο μέσος αριθμός χαρακτήρων που περιμένουν στο buffer, δηλαδή στην ουρά χωρίς αυτόν που εξυπηρετείται, είναι [ L_q=\frac{\rho^2}{1-\rho} =\frac{0{,}9^2}{1-0{,}9} =\frac{0{,}81}{0{,}1}=8{,}1 ] χαρακτήρες. Αν συμπεριληφθεί και ο χαρακτήρας υπό μετάδοση, τότε \(L=\rho/(1-\rho)=9\).
(c) Ο μέσος χρόνος απόκρισης στο σύστημα είναι [ W=\frac{1}{\mu-\lambda} =\frac{1}{500000-450000} =\frac{1}{50000}\text{ s} =2\cdot 10^{-5}\text{ s} =20\ \mu\text{s}. ] Ο μέσος χρόνος αναμονής μόνο στο buffer είναι \(W_q=L_q/\lambda=18\ \mu\text{s}\).
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Έστω καταστάσεις: \(T=\) Μετάδοση, \(P=\) Προετοιμασία, \(I=\) Αδράνεια.
(a) Οι μεταβάσεις είναι: [ T\xrightarrow{1/2}P,\qquad T\xrightarrow{1/2}I, ] [ P\xrightarrow{3/4}T,\qquad P\xrightarrow{1/4}I, ] [ I\xrightarrow{1}P. ] Δεν υπάρχουν μεταβάσεις προς την ίδια κατάσταση.
(b) Έστω \(\pi_T,\pi_P,\pi_I\) οι πιθανότητες μόνιμης κατάστασης. Οι εξισώσεις ισορροπίας είναι [ \pi_T=\frac34\pi_P, ] [ \pi_P=\frac12\pi_T+\pi_I, ] [ \pi_I=\frac12\pi_T+\frac14\pi_P. ] Από την πρώτη: \(\pi_T=\frac34\pi_P\). Αντικαθιστώντας στην τρίτη: [ \pi_I=\frac12\cdot\frac34\pi_P+\frac14\pi_P =\frac38\pi_P+\frac28\pi_P =\frac58\pi_P. ] Με κανονικοποίηση: [ \pi_P+\pi_T+\pi_I =\pi_P\left(1+\frac34+\frac58\right) =\pi_P\frac{8+6+5}{8} =\frac{19}{8}\pi_P=1, ] άρα [ \pi_P=\frac{8}{19},\qquad \pi_T=\frac{6}{19},\qquad \pi_I=\frac{5}{19}. ] Επομένως η συσκευή βρίσκεται πιθανότερα σε κατάσταση Προετοιμασίας, με πιθανότητα [ \boxed{\pi_P=\frac{8}{19}\approx 0{,}4211.} ]
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Οι σχετικοί ρυθμοί επισκέψεων είναι [ e_1=1,\qquad e_2=q=0{,}6,\qquad e_3=1-q=0{,}4. ] Οι μέσοι χρόνοι εξυπηρέτησης είναι [ s_1=45\text{ ms},\quad s_2=25\text{ ms},\quad s_3=90\text{ ms}. ] Άρα τα service demands είναι [ D_1=e_1s_1=45\text{ ms}, ] [ D_2=e_2s_2=0{,}6\cdot25=15\text{ ms}, ] [ D_3=e_3s_3=0{,}4\cdot90=36\text{ ms}. ]
(a1) Το bottleneck είναι η CPU, διότι έχει το μεγαλύτερο service demand: [ D_1=45\text{ ms} > D_3=36\text{ ms} > D_2=15\text{ ms}. ] Δηλαδή, παρόλο που ο αργός δίσκος έχει μεγαλύτερο χρόνο εξυπηρέτησης ανά επίσκεψη, επισκέπτεται λιγότερο συχνά από την CPU.
Για τον αλγόριθμο του Buzen, διαιρούμε όλους τους \(D_i\) με \(3\text{ ms}\) χωρίς να αλλάξουν οι πιθανότητες: [ d_1=15,\qquad d_2=5,\qquad d_3=12. ] Τότε [ G(0)=1, ] [ G(1)=d_1+d_2+d_3=15+5+12=32, ] και με αναδρομή Buzen: [ G(0,1)=1,\quad G(1,1)=15,\quad G(2,1)=225, ] [ G(0,2)=1,\quad G(1,2)=15+5=20,\quad G(2,2)=225+5\cdot20=325, ] [ G(0,3)=1,\quad G(1,3)=20+12=32,\quad G(2,3)=325+12\cdot32=709. ] Άρα [ G(2)=709. ] Οι πιθανότητες των καταστάσεων \((n_1,n_2,n_3)\) με \(n_1+n_2+n_3=2\) είναι [ p(n_1,n_2,n_3)=\frac{d_1^{n_1}d_2^{n_2}d_3^{n_3}}{709}. ] Ειδικότερα: [ p(2,0,0)=\frac{225}{709},\quad p(0,2,0)=\frac{25}{709},\quad p(0,0,2)=\frac{144}{709}, ] [ p(1,1,0)=\frac{75}{709},\quad p(1,0,1)=\frac{180}{709},\quad p(0,1,1)=\frac{60}{709}. ]
(a2) Η CPU είναι άεργη όταν \(n_1=0\): [ P(n_1=0)=p(0,2,0)+p(0,0,2)+p(0,1,1) =\frac{25+144+60}{709} =\frac{229}{709} \approx0{,}3230. ] Άρα η CPU είναι άεργη ποσοστό [ \boxed{32{,}30\%} ] του χρόνου.
(a3) Και οι δύο εργασίες στον γρήγορο δίσκο σημαίνει κατάσταση \((0,2,0)\): [ p(0,2,0)=\frac{25}{709}\approx0{,}03526. ] Άρα [ \boxed{P=2{,}526\%.} ]
(a4) Ο μέσος αριθμός εργασιών στον αργό δίσκο είναι [ E[n_3] =\frac{1\cdot180+1\cdot60+2\cdot144}{709} =\frac{180+60+288}{709} =\frac{528}{709} \approx0{,}7447. ] Άρα [ \boxed{E[n_3]=\frac{528}{709}\approx0{,}745\text{ εργασίες}.} ]
(b) Για άμεση επιβεβαίωση με αλυσίδα Markov συνεχούς χρόνου, χρησιμοποιούμε τις καταστάσεις [ A=(2,0,0),\ B=(0,2,0),\ C=(0,0,2), ] [ D=(1,1,0),\ E=(1,0,1),\ F=(0,1,1). ] Οι μη μηδενικοί ρυθμοί μεταβάσεων είναι: [ A\to D:\ q\mu_1,\qquad A\to E:\ (1-q)\mu_1, ] [ B\to D:\ \mu_2, ] [ C\to E:\ \mu_3, ] [ D\to A:\ \mu_2,\qquad D\to B:\ q\mu_1,\qquad D\to F:\ (1-q)\mu_1, ] [ E\to A:\ \mu_3,\qquad E\to C:\ (1-q)\mu_1,\qquad E\to F:\ q\mu_1, ] [ F\to D:\ \mu_3,\qquad F\to E:\ \mu_2. ] Επιλύοντας τις εξισώσεις ισορροπίας [ \pi Q=0,\qquad \sum_i\pi_i=1, ] με [ \mu_1=\frac{1}{45},\qquad \mu_2=\frac{1}{25},\qquad \mu_3=\frac{1}{90},\qquad q=0{,}6, ] προκύπτει [ (\pi_A,\pi_B,\pi_C,\pi_D,\pi_E,\pi_F) = \frac{1}{709}(225,25,144,75,180,60). ] Αυτό ταυτίζεται με τις πιθανότητες που βρήκαμε με τον αλγόριθμο του Buzen. Επομένως: [ P(\text{CPU άεργη})=\pi_B+\pi_C+\pi_F =\frac{25+144+60}{709} =\frac{229}{709}, ] [ P(\text{και οι 2 στον γρήγορο δίσκο})=\pi_B=\frac{25}{709}, ] και [ E[n_3]=\frac{180+60+2\cdot144}{709} =\frac{528}{709}. ] Τα αποτελέσματα επιβεβαιώνονται.