Τεχνικές Εκτίμησης Υπολογιστικών Συστημάτων και Δικτύων — Ιανουάριος 2024¶
Μεταγραφή από τη φωτογραφία 2.PNG (μόνο Θέμα 4).
2.PNG¶
ΘΕΜΑ 4 (35%)
Σας δίνεται το παρακάτω απλό μοντέλο κεντρικού εξυπηρετητή (central server model):
[Σχήμα: «Ν εργασίες» → CPU (μ1) → διακλάδωση: με πιθανότητα q προς Γρήγορος Δίσκος (μ2), με πιθανότητα 1-q προς Αργός Δίσκος (μ3)· και οι δύο δίσκοι επιστρέφουν στην είσοδο των εργασιών. Χειρόγραφες σημειώσεις στο σχήμα: 0,6 δίπλα στο q και 0,4 δίπλα στο 1-q.]
Δίνονται οι μέσοι χρόνοι της (εκθετικής) εξυπηρέτησης: \(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.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2024-01¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 4¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Έστω κόμβοι \(1=\text{CPU}\), \(2=\text{γρήγορος δίσκος}\), \(3=\text{αργός δίσκος}\). Οι σχετικές συχνότητες επισκέψεων είναι [ e_1=1,\qquad e_2=q=0{,}6,\qquad e_3=1-q=0{,}4. ] Οι μέσοι χρόνοι εξυπηρέτησης είναι \(s_1=45\), \(s_2=25\), \(s_3=90\) ms, άρα τα κατάλληλα βάρη του γινομένου (service demands) είναι [ D_1=e_1s_1=45,\qquad D_2=e_2s_2=0{,}6\cdot25=15,\qquad D_3=e_3s_3=0{,}4\cdot90=36 \text{ ms}. ]
Για το κλειστό δίκτυο με \(N=2\), η σταθερή κατανομή είναι ανάλογη του [ \prod_{i=1}^3 D_i^{n_i},\qquad n_1+n_2+n_3=N. ] Οι καταστάσεις και τα βάρη τους είναι: [ \begin{array}{c|cccccc} (n_1,n_2,n_3)&(2,0,0)&(0,2,0)&(0,0,2)&(1,1,0)&(1,0,1)&(0,1,1)\ \hline \text{βάρος} &45^2=2025&15^2=225&36^2=1296&45\cdot15=675&45\cdot36=1620&15\cdot36=540 \end{array} ] Άρα [ G(2)=2025+225+1296+675+1620+540=6381. ] (Με τον αλγόριθμο Buzen: \(G(0)=1\), \(G(1)=45+15+36=96\), και \(G(2)=2925+36\cdot96=6381\).)
(a1) Bottleneck¶
[ D_1=45>D_3=36>D_2=15. ] Bottleneck είναι η \textbf{CPU}, γιατί έχει το μεγαλύτερο συνολικό φόρτο εξυπηρέτησης ανά εργασία. Πράγματι, για \(N=2\), η CPU έχει τη μεγαλύτερη χρησιμοποίηση: [ U_1=\frac{480}{709},\qquad U_3=\frac{384}{709},\qquad U_2=\frac{160}{709}. ]
(a2) Ποσοστό χρόνου που η CPU είναι άεργη¶
Η CPU είναι άεργη όταν \(n_1=0\), δηλαδή στις καταστάσεις \((0,2,0)\), \((0,0,2)\), \((0,1,1)\). Έτσι [ P_{\text{idle,CPU}} =\frac{225+1296+540}{6381} =\frac{2061}{6381} =\frac{229}{709} \approx 0{,}3230. ] Άρα η CPU είναι άεργη περίπου \(\boxed{32{,}30\%}\) του χρόνου.
(a3) Πιθανότητα και οι 2 εργασίες να είναι στον γρήγορο δίσκο¶
Αυτό αντιστοιχεί στην κατάσταση \((0,2,0)\), δηλαδή \(n_2=2\) (ένας σε εξυπηρέτηση και ένας σε αναμονή, αφού ο δίσκος είναι single-server): [ P(n_2=2)=\frac{225}{6381} =\frac{25}{709} \approx 0{,}03526. ] Άρα [ \boxed{P\approx 3{,}526\% }. ]
(a4) Μέσος αριθμός εργασιών στον αργό δίσκο¶
[ E[n_3] =\frac{1\cdot(1620+540)+2\cdot1296}{6381} =\frac{4752}{6381} =\frac{528}{709} \approx 0{,}7447. ] Άρα [ \boxed{E[n_3]\approx 0{,}7447 \text{ εργασίες}}. ]
(b) Επαλήθευση με αλυσίδα Markov¶
Οι καταστάσεις της αλυσίδας Markov (με \(N=2\)) είναι: [ A=(2,0,0),\ B=(0,2,0),\ C=(0,0,2),\ D=(1,1,0),\ E=(1,0,1),\ F=(0,1,1). ] Οι ρυθμοί μετάβασης είναι: [ \begin{aligned} &A\to D:\mu_1q,\quad A\to E:\mu_1(1-q),\ &B\to D:\mu_2,\ &C\to E:\mu_3,\ &D\to B:\mu_1q,\quad D\to F:\mu_1(1-q),\quad D\to A:\mu_2,\ &E\to F:\mu_1q,\quad E\to C:\mu_1(1-q),\quad E\to A:\mu_3,\ &F\to E:\mu_2,\quad F\to D:\mu_3. \end{aligned} ] Οι εξισώσεις σταθερής κατάστασης \(\pi Q=0\) είναι: [ \begin{aligned} \pi_A\mu_1&=\pi_D\mu_2+\pi_E\mu_3,\ \pi_B\mu_2&=\pi_D\mu_1q,\ \pi_C\mu_3&=\pi_E\mu_1(1-q),\ \pi_D(\mu_1+\mu_2)&=\pi_A\mu_1q+\pi_B\mu_2+\pi_F\mu_3,\ \pi_E(\mu_1+\mu_3)&=\pi_A\mu_1(1-q)+\pi_C\mu_3+\pi_F\mu_2,\ \pi_F(\mu_2+\mu_3)&=\pi_D\mu_1(1-q)+\pi_E\mu_1q. \end{aligned} ] Λύνοντάς τις με \(\sum \pi_i=1\), \(\mu_1=1/45\), \(\mu_2=1/25\), \(\mu_3=1/90\), \(q=0{,}6\), προκύπτει [ (\pi_A,\pi_B,\pi_C,\pi_D,\pi_E,\pi_F) = \frac{1}{6381} (2025,225,1296,675,1620,540). ] Επομένως επαληθεύονται: [ P_{\text{idle,CPU}}=\pi_B+\pi_C+\pi_F =\frac{225+1296+540}{6381} =\frac{229}{709}, ] [ P(n_2=2)=\pi_B=\frac{225}{6381}=\frac{25}{709}, ] και [ E[n_3]=2\pi_C+\pi_E+\pi_F =\frac{2\cdot1296+1620+540}{6381} =\frac{528}{709}. ] Τα αποτελέσματα συμφωνούν πλήρως με τον αλγόριθμο Buzen.