Τεχνικές Εκτίμησης Υπολογιστικών Συστημάτων και Δικτύων — Ιούνιος 2021¶

Μεταγραφή από τις φωτογραφίες received_312713083810131.jpeg (Θέμα 1), received_1010399243102432.jpeg (Θέμα 2) και IMG_20210611_185005.jpg (Θέμα 3).

received_312713083810131.jpeg¶

ΘΕΜΑ 1

Ένας εκτυπωτής υπολογιστικού κέντρου, δέχεται εργασίες για εκτύπωση που φθάνουν με Poisson τρόπο και μέσο ρυθμό 6 εργασίες/ώρα. Η διάρκεια της εκτύπωσης των εργασιών, ακολουθεί την εκθετική κατανομή με μέση τιμή 6 min/εργασία. Υπάρχει μία ουρά αναμονής των εργασιών για εκτύπωση, με πρακτικά άπειρη χωρητικότητα.

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

Αντικατάσταση του παλιού εκτυπωτή (μέσου ρυθμού εκτύπωσης $\mu$), με έναν καινούργιο διπλάσιας ταχύτητας, δηλαδή με μέσο ρυθμό εκτύπωσης $2\mu$.
Προσθήκη ενός ίδιου με τον παλιό εκτυπωτή (μέσος ρυθμός εκτύπωσης $\mu$), ο οποίος έχει δική του ουρά αναμονής, στην οποία θα κατευθύνεται το μισό φορτίο. Δηλαδή, θα έχουμε δύο ίδιους εκτυπωτές $\mu$, με ανεξάρτητη ουρά ο καθένας, κάθε μία από τις οποίες θα δέχεται φορτίο $\lambda/2$.
Προσθήκη ενός ίδιου με τον παλιό εκτυπωτή, αλλά με μία κοινή ουρά αναμονής, η οποία θα δέχεται το σύνολο του φορτίου $\lambda$. Η εργασία στην κορυφή της ουράς, επιλέγει (τυχαία) όποιον από τους δύο εκτυπωτές είναι άεργος.

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

ΣΗΜΕΙΩΣΗ: Στο σύστημα αναμονής M/M/2 με δύο εξυπηρετητές, ο καθένας από τους οποίους έχει μέσο ρυθμό εξυπηρέτησης $\mu$, ο μέσος χρόνος απόκρισης $T$ δίνεται από τη σχέση:

\[T = \frac{1/\mu}{(1-\rho)(1+\rho)}\]

received_1010399243102432.jpeg¶

[Λείπει από τη φωτογραφία: η επικεφαλίδα της ερώτησης στο πάνω μέρος της οθόνης· διακρίνεται μόνο το τέλος της: «Ελεύθερου Κειμένου — 0 βαθμοί»]

ΘΕΜΑ 2

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

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

a. Χαρακτηρίστε την αλυσίδα και τις καταστάσεις της. Παρουσιάστε τον πίνακα μεταβάσεων $P$ της αλυσίδας.

b. Αν η αλυσίδα έχει μόνιμη κατάσταση, βρείτε τις πιθανότητες μόνιμης κατάστασης.

c. Πως μεταβάλλονται τα παραπάνω, αν δεν έχουμε ισοπίθανη μετακίνηση από τον κόμβο 4 (μόνο), αλλά η πιθανότητα μετακίνησης από τον κόμβο 4 στον κόμβο 3 είναι διπλάσια από την πιθανότητα μετακίνησης από τον 4 στον 1. Σχολιάστε τις τυχόν διαφορές και ομοιότητες με τις απαντήσεις σας στα (a), (b).

[Σχήμα: γράφος με 4 κόμβους 1, 2, 3, 4 και τις αμφίδρομες ακμές 1–2, 1–4, 2–3, 3–4. Τα τμήματα 1–4 και 2–3 διασταυρώνονται στο κέντρο, χωρίς κόμβο στο σημείο τομής]

IMG_20210611_185005.jpg¶

ΘΕΜΑ 3

Σας δίνεται το παρακάτω κλειστό δίκτυο τεσσάρων Συστημάτων Αναμονής ΣΑ1, ΣΑ2, ΣΑ3, ΣΑ4, στο οποίο υπάρχουν $N = 3$ εργασίες.

Δίνεται: $\mu = 4$ εργασίες/sec. Όλες οι εξυπηρετήσεις είναι εκθετικές, ενώ όλες οι ουρές έχουν πρακτικά άπειρο μήκος.

Χρησιμοποιώντας τον αλγόριθμο του Buzen, απαντήστε στα παρακάτω:

[Σχήμα: μέρος του δικτύου με ΣΑ1 (εξυπηρέτηση $\mu$) και ΣΑ2, ΣΑ3 (εξυπηρέτηση $2\mu$ το καθένα) σε σειρά· από κόμβο διακλάδωσης οι πιθανότητες $r_{41} = 1/2$ (προς ΣΑ1) και $r_{42} = 1/2$ (προς ΣΑ2)] [Λείπει από τη φωτογραφία: το κάτω μέρος του σχήματος, δηλαδή το ΣΑ4 και οι συνδέσεις του]

a. Παρουσιάστε τη λύση του δικτύου $P_{n_1,n_2,n_3,n_4}$ στη μόνιμη κατάσταση. (ΠΡΟΤΑΣΗ: Επιλέξτε $\rho_2 = 1$ )

b. Ποιο από τα τέσσερα ΣΑ είναι σημείο συμφόρησης (bottleneck) του δικτύου και γιατί;

c. Ποια είναι η πιθανότητα να βρίσκονται όλες οι εργασίες στο ΣΑ1 και ποια η πιθανότητα να είναι όλες στο ΣΑ4;

d. Ποια είναι η πιθανότητα το ΣΑ3 να έχει 1 εργασία;

e. Ποιος είναι ο μέσος αριθμός πελατών, το throughput και το response time μιας εργασίας στο ΣΑ2;

f. Πως θα ορίζεται το συνολικό response time μιας εργασίας στο δίκτυο; Μπορείτε να το υπολογίσετε με μία πράξη έχοντας τα αποτελέσματα των προηγούμενων ερωτημάτων; Αν ναι, ποια είναι η τιμή της;

g. (+ 0,5 μονάδα bonus) Αν έχουμε μόνο μια εργασία στο δίκτυο ($N = 1$ εργασία), απαντήστε στα ερωτήματα (b), (c), (d), (e) χρησιμοποιώντας μια αλυσίδα Markov συνεχούς χρόνου, και όχι τον αλγόριθμο του Buzen.

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2021-06¶

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

ΘΕΜΑ 1¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Δίνονται $\lambda=6$ εργασίες/ώρα και μέσος χρόνος εξυπηρέτησης $6$ min $=0.1$ h, άρα $\mu=10$ εργασίες/ώρα. Το αρχικό σύστημα είναι M/M/1 με [ T_0=\frac{1}{\mu-\lambda}=\frac{1}{10-6}=\frac14\ \text{h}=15\ \text{min}. ]

Νέος εκτυπωτής με ρυθμό $2\mu=20$ εργασίες/ώρα. Πάλι M/M/1: [ \rho=\frac{\lambda}{2\mu}=\frac{6}{20}=0.3,\qquad T_1=\frac{1}{2\mu-\lambda}=\frac{1}{20-6}=\frac{1}{14}\ \text{h}\approx 4.286\ \text{min}. ]
Δύο ανεξάρτητοι εκτυπωτές με δική τους ουρά, ο καθένας δέχεται $\lambda/2=3$ εργασίες/ώρα και έχει $\mu=10$. Κάθε ουρά είναι M/M/1: [ T_2=\frac{1}{\mu-\lambda/2}=\frac{1}{10-3}=\frac17\ \text{h}\approx 8.571\ \text{min}. ]
M/M/2 με κοινή ουρά, συνολικό $\lambda=6$ και κάθε εξυπηρετητής $\mu=10$. Η χρησιμοποίηση ανά εξυπηρετητή είναι [ \rho=\frac{\lambda}{2\mu}=\frac{6}{20}=0.3. ] Από τον δοσμένο τύπο: [ T_3=\frac{1/\mu}{(1-\rho)(1+\rho)} =\frac{1/10}{(1-0.3)(1+0.3)} =\frac{10}{91}\ \text{h}\approx 6.593\ \text{min}. ]

Σύγκριση: [ T_1\approx 4.29\ \text{min}<T_3\approx 6.59\ \text{min}<T_2\approx 8.57\ \text{min}<T_0=15\ \text{min}. ] Καλύτερη λύση είναι η 1. Η κοινή ουρά της λύσης 3 αξιοποιεί καλύτερα τους δύο εξυπηρετητές από ό,τι οι δύο ανεξάρτητες ουρές της λύσης 2, γιατί δεν μένει εκτυπωτής αργός όσο υπάρχουν εργασίες στην άλλη ουρά· έτσι η 3 είναι καλύτερη από τη 2. Ωστόσο ένας μόνο διπλάσιας ταχύτητας εκτυπωτής δίνει μικρότερο χρόνο απόκρισης από δύο μισής ταχύτητας εκτυπωτές με κοινή ουρά, για ίση συνολική μέγιστη ικανότητα.

ΘΕΜΑ 2¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Οι ακμές είναι $1-2$, $2-3$, $3-4$, $4-1$, άρα κάθε κόμβος έχει δύο γείτονες.

a. Η αλυσίδα είναι πεπερασμένη, ομογενής, μη-διαχωρίσιμη (irreducible) και θετικά επαναληπτική. Επειδή ο γράφος είναι διμερής, με διαμέριση $\{1,3\}$ και $\{2,4\}$, η περίοδος κάθε κατάστασης είναι $2$· άρα η αλυσίδα είναι περιοδική και δεν έχει οριακή κατανομή με την κλασική έννοια, έχει όμως μοναδική στάσιμη κατανομή.

Με σειρά καταστάσεων $(1,2,3,4)$: [ 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}. ]

b. Ο πίνακας είναι διπλά στοχαστικός και η αλυσίδα συνδεδεμένη, άρα η μοναδική στάσιμη κατανομή είναι η ομοιόμορφη: [ \pi=\left(\frac14,\frac14,\frac14,\frac14\right). ] Λόγω περιοδικότητας, η ακολουθία $P^n$ δεν συγκλίνει στον πίνακα με γραμμές $\pi$· η $\pi$ είναι η μέση χρονική κατανομή/στάσιμη κατανομή.

c. Αν από τον κόμβο $4$ η μετάβαση στο $3$ είναι διπλάσια πιθανή από τη μετάβαση στο $1$, τότε [ P(4\to1)=\frac13,\qquad P(4\to3)=\frac23, ] ενώ οι άλλες πιθανότητες μένουν ίσες. Ο πίνακας γίνεται [ P'= \begin{pmatrix} 0 & 1/2 & 0 & 1/2\ 1/2 & 0 & 1/2 & 0\ 0 & 1/2 & 0 & 1/2\ 1/3 & 0 & 2/3 & 0 \end{pmatrix}. ] Η αλυσίδα παραμένει μη-διαχωρίσιμη, θετικά επαναληπτική και περιοδική με περίοδο $2$, αφού το γράφημα υποστήριξης είναι το ίδιο διμερές. Η στάσιμη κατανομή δεν είναι πλέον ομοιόμορφη. Έστω $\pi=(\pi_1,\pi_2,\pi_3,\pi_4)$· λύνοντας $\pi P'=\pi$ και $\sum_i\pi_i=1$: [ \pi_1=\frac12\pi_2+\frac13\pi_4,\quad \pi_2=\frac12\pi_1+\frac12\pi_3, ] [ \pi_3=\frac12\pi_2+\frac23\pi_4,\quad \pi_4=\frac12\pi_1+\frac12\pi_3. ] Προκύπτει [ \pi'=\left(\frac{5}{24},\frac14,\frac{7}{24},\frac14\right). ] Δηλαδή η μη ισοπίθανη μετάβαση αυξάνει τη στάσιμη πιθανότητα του κόμβου $3$ και μειώνει εκείνη του κόμβου $1$, ενώ οι κόμβοι $2$ και $4$ μένουν στο $1/4$. Η περιοδικότητα και η μη ύπαρξη οριακής κατανομής (με την αυστηρή έννοια) διατηρούνται.

ΘΕΜΑ 3¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στην εικόνα IMG_20210611_185005.jpg και σε συνδυασμό με το πανομοιότυπο κλειστό δίκτυο της εξέτασης Ιουνίου 2015 (2015-06.md), η τοπολογία του κλειστού δικτύου τεσσάρων συστημάτων αναμονής (ΣΑ1, ΣΑ2, ΣΑ3, ΣΑ4) με $N=3$ εργασίες είναι: - Μετά το ΣΑ4, οι εργασίες διακλαδίζονται προς το ΣΑ1 με $r_{41} = 1/2$ και προς το ΣΑ2 με $r_{42} = 1/2$. - Η έξοδος του ΣΑ2 οδηγεί απευθείας στο ΣΑ3 ($r_{23} = 1$). - Οι έξοδοι των ΣΑ1 και ΣΑ3 ενώνονται και οδηγούν στην είσοδο του ΣΑ4 ($r_{14} = 1, r_{34} = 1$). - Ρυθμοί εξυπηρέτησης: $\mu_1 = \mu = 4$, $\mu_2 = 2\mu = 8$, $\mu_3 = 2\mu = 8$, $\mu_4 = \mu = 4$ εργασίες/sec.

Σχετικοί ρυθμοί επισκέψεων και φορτία (Buzen): Από τις εξισώσεις κίνησης $v_i = \sum_j v_j r_{ji}$: $$v_1 = \frac{1}{2} v_4, \quad v_2 = \frac{1}{2} v_4, \quad v_3 = v_2 = \frac{1}{2} v_4, \quad v_4 = v_1 + v_3 = v_4$$ Επιλέγοντας $v_4 = 2$, έχουμε $(v_1, v_2, v_3, v_4) = (1, 1, 1, 2)$. Τα σχετικά φορτία είναι $\alpha_i = v_i / \mu_i = \left(\frac{1}{4}, \frac{1}{8}, \frac{1}{8}, \frac{2}{4}\right)$. Ακολουθώντας την πρόταση της εκφώνησης για $\rho_2 = 1$ (πολλαπλασιασμός με $2\mu = 8$): $$\rho_1 = 2, \quad \rho_2 = 1, \quad \rho_3 = 1, \quad \rho_4 = 4$$

Πίνακας αλγορίθμου Buzen ($g(m, n) = g(m-1, n) + \rho_m g(m, n-1)$):

$m$ \ $n$	$0$	$1$	$2$	$3$
$0$	$1$	$0$	$0$	$0$
$1$ ($\rho_1 = 2$)	$1$	$2$	$4$	$8$
$2$ ($\rho_2 = 1$)	$1$	$3$	$7$	$15$
$3$ ($\rho_3 = 1$)	$1$	$4$	$11$	$26$
$4$ ($\rho_4 = 4$)	$1$	$8$	$43$	$198$

Η σταθερά κανονικοποίησης είναι $G(3) = g(4, 3) = 198$ (και $G(2) = 43, G(1) = 8, G(0) = 1$).

Απαντήσεις στα ερωτήματα:¶

a. Λύση μόνιμης κατάστασης: $$p(n_1, n_2, n_3, n_4) = \frac{1}{G(3)} \rho_1^{n_1} \rho_2^{n_2} \rho_3^{n_3} \rho_4^{n_4} = \frac{1}{198} \cdot 2^{n_1} \cdot 1^{n_2} \cdot 1^{n_3} \cdot 4^{n_4}$$ για όλα τα $(n_1, n_2, n_3, n_4)$ μη αρνητικών ακεραίων με $n_1 + n_2 + n_3 + n_4 = 3$.

b. Σημείο συμφόρησης (bottleneck): Το σημείο συμφόρησης είναι το ΣΑ4, διότι έχει το μέγιστο σχετικό φορτίο $\rho_4 = 4 = \max_i \rho_i$ (αντίστοιχα $v_4/\mu_4 = 1/2$ είναι το μεγαλύτερο), άρα έχει τη μεγαλύτερη πιθανότητα κορεσμού.

c. Πιθανότητες όλων των εργασιών σε ΣΑ1 και ΣΑ4: - Όλες στο ΣΑ1 ($n_1=3, n_2=0, n_3=0, n_4=0$): $$P(\text{όλες στο ΣΑ1}) = \frac{\rho_1^3}{G(3)} = \frac{2^3}{198} = \frac{8}{198} = \frac{4}{99} \approx 0{,}0404$$ - Όλες στο ΣΑ4 ($n_4=3$): $$P(\text{όλες στο ΣΑ4}) = \frac{\rho_4^3}{G(3)} = \frac{4^3}{198} = \frac{64}{198} = \frac{32}{99} \approx 0{,}3232$$

d. Πιθανότητα το ΣΑ3 να έχει 1 εργασία ($n_3 = 1$): Υπολογίζοντας το άθροισμα $\sum_{n_1+n_2+n_4 = 2} 2^{n_1} 1^{n_2} 4^{n_4} = g_{M \setminus \{3\}}(2) = 35$: $$P(n_3 = 1) = \frac{1^1 \cdot 35}{198} = \frac{35}{198} \approx 0{,}1768$$

e. Μέσος αριθμός πελατών, throughput και response time στο ΣΑ2: - Χρησιμοποίηση ΣΑ2: $U_2 = \rho_2 \frac{G(2)}{G(3)} = 1 \cdot \frac{43}{198} = \frac{43}{198} \approx 0{,}2172$. - Throughput ($X_2$): $X_2 = \mu_2 \cdot U_2 = 8 \cdot \frac{43}{198} = \frac{344}{198} = \frac{172}{99} \approx 1{,}7374\text{ εργασίες/sec}$. - Μέσος αριθμός πελατών ($E[n_2]$): $$E[n_2] = \sum_{k=1}^{3} P(n_2 \ge k) = \frac{52}{198} = \frac{26}{99} \approx 0{,}2626\text{ εργασίες}$$ - Response time ($R_2$): Από το νόμο του Little: $$R_2 = \frac{E[n_2]}{X_2} = \frac{52/198}{344/198} = \frac{52}{344} = \frac{13}{86} \approx 0{,}1512\text{ sec}$$

f. Συνολικό response time μιας εργασίας στο δίκτυο: Ορίζεται ως ο μέσος χρόνος $R_{\text{total}}$ που χρειάζεται μια εργασία για να ολοκληρώσει έναν πλήρη κύκλο στο δίκτυο (περνώντας από το ΣΑ4). Από τον νόμο του Little για ολόκληρο το κλειστό δίκτυο: $$R_{\text{total}} = \frac{N}{X_{\text{sys}}} = \frac{N}{X_4}$$ Όπου $X_4 = \mu_4 \cdot U_4 = 4 \cdot \left(4 \cdot \frac{G(2)}{G(3)}\right) = 16 \cdot \frac{43}{198} = \frac{688}{198} = \frac{344}{99}\text{ εργασίες/sec}$. Επομένως, με μία πράξη: $$R_{\text{total}} = \frac{3}{344/99} = \frac{297}{344} \approx 0{,}8634\text{ sec}$$

g. Bonus: Επίλυση με αλυσίδα Markov συνεχούς χρόνου για $N = 1$: Όταν $N=1$, η μοναδική εργασία βρίσκεται κάθε στιγμή σε ένα από τα τέσσερα συστήματα, άρα οι καταστάσεις είναι $\{1, 2, 3, 4\}$. Οι ρυθμοί μετάβασης είναι: - $q_{14} = \mu_1 = 4$ - $q_{23} = \mu_2 = 8$ - $q_{34} = \mu_3 = 8$ - $q_{41} = r_{41} \mu_4 = \frac{1}{2} \cdot 4 = 2$ - $q_{42} = r_{42} \mu_4 = \frac{1}{2} \cdot 4 = 2$

Από τις εξισώσεις ισορροπίας $\pi Q = 0$: - Κατάσταση 1: $4 \pi_1 = 2 \pi_4 \implies \pi_1 = \frac{1}{2} \pi_4$ - Κατάσταση 2: $8 \pi_2 = 2 \pi_4 \implies \pi_2 = \frac{1}{4} \pi_4$ - Κατάσταση 3: $8 \pi_3 = 8 \pi_2 \implies \pi_3 = \pi_2 = \frac{1}{4} \pi_4$ - Κανονικοποίηση $\pi_1 + \pi_2 + \pi_3 + \pi_4 = 1 \implies \left(\frac{1}{2} + \frac{1}{4} + \frac{1}{4} + 1\right)\pi_4 = 1 \implies 2\pi_4 = 1 \implies \pi_4 = \frac{1}{2}$. Άρα: $$\pi_1 = \frac{1}{4}, \quad \pi_2 = \frac{1}{8}, \quad \pi_3 = \frac{1}{8}, \quad \pi_4 = \frac{1}{2}$$

Απαντήσεις για $N=1$: - (b) Σημείο συμφόρησης παραμένει το ΣΑ4 (έχει τη μέγιστη πιθανότητα κατάληψης $\pi_4 = 1/2 = 50\%$). - (c) $P(\text{στο ΣΑ1}) = \pi_1 = 1/4 = 0{,}25$, $P(\text{στο ΣΑ4}) = \pi_4 = 1/2 = 0{,}50$. - (d) $P(n_3 = 1) = \pi_3 = 1/8 = 0{,}125$. - (e) Για το ΣΑ2: - Μέσος αριθμός πελατών: $E[n_2] = \pi_2 = 1/8 = 0{,}125$. - Throughput: $X_2 = \mu_2 \pi_2 = 8 \cdot (1/8) = 1\text{ εργασία/sec}$. - Response time: $R_2 = \frac{E[n_2]}{X_2} = \frac{1/8}{1} = \frac{1}{8} = 0{,}125\text{ sec} = \frac{1}{\mu_2}$ (αφού για $N=1$ δεν υπάρχει χρόνος αναμονής στην ουρά).

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή

\(m\) \ \(n\)	\(0\)	\(1\)	\(2\)	\(3\)
\(0\)	\(1\)	\(0\)	\(0\)	\(0\)
\(1\) (\(\rho_1 = 2\))	\(1\)	\(2\)	\(4\)	\(8\)
\(2\) (\(\rho_2 = 1\))	\(1\)	\(3\)	\(7\)	\(15\)
\(3\) (\(\rho_3 = 1\))	\(1\)	\(4\)	\(11\)	\(26\)
\(4\) (\(\rho_4 = 4\))	\(1\)	\(8\)	\(43\)	\(198\)