Σημειώσεις:Κατανεμημένοι Αλγόριθμοι:BFS
Από DistrSys
| BFS |
| Πρόβλημα: Κατανεμημένες Δομές Δίκτυο: Γενικό Κλάση: Συγκεντρωτικός |
|
|
| Πολυπλοκότητα |
| Χρονική: O(diam) Επικοινωνίας: O(m) |
|
|
| Στη σύνταξη του κειμένου συνεισέφεραν οι Μάριος Λογαράς, Απόστολος Φίλιππας, Βασίλειος Γεωργιτζίκης |
Η δημιουργία ενός επικαλυπτικού δέντρου πάνω από ένα δίκτυο διεργασιών προσφέρει λύσεις ή συντελεί στην αντιμετώπιση πολλών προβλημάτων που συναντά κανείς σε κατανεμημένα συστήματα. Η μετάδοση πληροφορίας με τη χρήση ενός τέτοιου δέντρου γίνεται γρηγορότερα και αποδοτικότερα.
Η εκτέλεση του αλγορίθμου SynchBFS έχει σαν αποτέλεσμα την δημιουργία ενός επικαλυπτικού κατά εύρος δέντρου πάνω από ένα ισχυρά συνεκτικό δίκτυο διεργασιών. Η δομή του δέντρου δεν είναι αποθηκευμένη σε κάποια κεντρική διεργασία και έτσι αποτελεί μια πλήρως κατανεμημένη δομή. Υποθέτουμε πως μια διεργασία u_0 αρχίζει την εκτέλεση του αλγορίθμου. (Εάν δεν υπάρχει κάποιο εξωτερικό γεγονός που να διαφοροποιεί τη διεργασία u_0 απο τις υπόλοιπες, μπορούμε να εκτελέσουμε έναν αλγόριθμο εκλογής αρχηγού ώστε να γίνει γνωστή η διεργασία αυτή. ) Η u_0 στέλνει στους γείτονες της ένα μήνυμα αναζήτησης “ζητώντας τους” να γίνει γονέας τους ενώ παράλληλα θέτει τη μεταβλητή της μαρκαρισμένη true. Όποια διεργασία λάβει μήνυμα αναζήτησης για πρώτη φορά γίνεται παιδί της διεργασίας από την οποία προήλθε το μήνυμα. Μια τέτοια διεργασία με τη σειρά της στέλνει και αυτή μήνυμα αναζήτησης στις γειτονικές τις διεργασίες.
|
|
|
Το αρχικό δίκτυο αποτελείται από 9 διεργασίες με ταυτότητες 1-9 και επικοινωνούν μεταξύ τους μέσω 14 καναλιών. Η διεργασία με ταυτότητα 1 ξεκινά την εκτέλεση του αλγορίθμου. Στον πρώτο γύρο , η διεργασία 1 ξεκινά την εκτέλεση του αλγορίθμου στέλνοντας μήνυμα αναζήτησης στις 2,5 (1ος γύρος,1ο βήμα). Με τη λήψη του μηνύματος και εφόσον οι 2,5 δεν είναι μαρκαρισμένες (μαρκαρισμένη = false) θέτουν την 1 ως γονέα και μαρκάρονται (1ος γύρος, 2ο βήμα).
 Αρχικοποίηση δικτύου |
 1ος γύρος - 1ο βήμα |
 1ος γύρος - 2ο βήμα |
Στο δεύτερο γύρο οι διεργασίες 5 και 2 στέλνουν μήνυμα αναζήτησης στις 1,3,8,9 και 1,4,7,9 αντίστοιχα. Η διεργασία 1 αγνοεί τα μηνύματα που έλαβε καθώς ανήκει ήδη στο δέντρο (2ος γύρος-1ο βήμα). Όλες οι υπόλοιπες διεργασίες μαρκάρονται. Οι διεργασίες 3,8,9 θέτουν την 5 για γονέα ενώ οι 4,7 την 2. Η διεργασία 9 επιλέγει τυχαία μια εκ των 2,5 για γονέα. Στο παράδειγμα επιλέγεται η 2 (2ος γύρος-2ο βήμα). Στον 3ο γύρο όλες οι διεργασίες που έλαβαν μήνυμα αναζήτησης στον προηγούμενο γύρο, στέλνουν τώρα μήνυμα αναζήτησης στους γείτονες τους: η 3 στέλνει στους 5,8 , η 8 στους 3,5,6,9, η 9 στους 2,4,5,8, η 4 στους 2,6,7,9, η 7 στους 2,4 (3ος γύρος-1ο βήμα).
 2ος γύρος-1ο βήμα |
 2ος γύρος-2ο βήμα |
 3ος γύρος-1ο βήμα |
Οι διεργασίες 2,3,4,5,7,8,9 αγνοούν τα μηνύματα αναζήτησης που έλαβαν. Η διεργασία 6 μαρκάρεται και επιλέγει τυχαία την 8 ως γονέα της (3ος γύρος-2ο βήμα). Κατα τον 4ο γύρο η διεργασία 6 στέλνει μήνυμα αναζήτησης στις γειτονικές τις 3,4 (4ος γύρος-1ο βήμα), οι οποίες το αγνοούν (4ος γύρος-2ο βήμα).
 3ος γύρος-2ο βήμα |
 4ος γύρος-1ο βήμα |
 4ος γύρος-2ο βήμα |
Στο τέλος της εκτέλεσης του αλγορίθμου, μετά από 4 γύρους και 28 μηνύματα, έχει κατασκευαστεί το δέντρο αναζήτησης κατά εύρος.
 Τελικό δίκτυο |
Τερματισμός
Ο αλγόριθμος τερματίζεται όταν όλες οι διεργασίες λάβουν μήνυμα αναζήτησης από τους γείτονές τους. Με την παραπάνω περιγραφή του αλγορίθμου οι διεργασίες δεν είναι σε θέση να γνωρίζουν πότε ο αλγόριθμος έχει τερματίσει. Σε ένα σύγχρονο σύστημα όμως η εσωτερική κατάσταση των διεργασιών δεν θα υποστεί καμία αλλαγή μετά από κάποια χρονική στιγμή. Οι διεργασίες βρίσκονται σε κατάσταση εξωτερικού τερματισμού.
Εαν ωστόσο θέλουμε η διεργασία u_0 να γνωρίζει πότε ο αλγόριθμος τερματίζεται μπορούμε να το πετύχουμε με την εισαγωγή δύο επιπλέον μηνυμάτων: Μια διεργασία που λαμβάνει μήνυμα αναζήτησης, απαντάει μη-γονέας στη διαδικασία από την οποία έλαβε το μήνυμα, εφόσον είναι μαρκαρισμένη ή έχει επιλέξει -τυχαία- μια άλλη διεργασία για γονέα της. Η απάντηση αυτή στέλνεται αμέσως μετά την παραλαβή του μηνύματος. Μια διεργασία που λαμβάνει μήνυμα αναζήτησης, απαντάει γονέας στη διαδικασία από την οποία έλαβε το μήνυμα, εφόσον έχει επιλέξει τη διεργασία αυτή για γονέα της. Η απάντηση αυτή όμως, δεν στέλνεται αμέσως, αλλά μόνο όταν η διεργασία έχει λάβει απάντηση (γονέας|μή-γονέας), από όλες τις διεργασίες στις οποίες έχει στείλει μήνυμα αναζήτησης. Με το τρόπο αυτό και αρχίζοντας από τα φύλλα του δέντρου που σχηματίστηκε, μηνύματα γονέας ανεβαίνουν προς τη ρίζα του δέντρου, στη διεργασία u_0. Όταν η u_0 λάβει οποιαδήποτε απάντηση, από όλες τις γειτονικές τις διεργασίες, γνωρίζει πως ο σχηματισμός του δέντρου έχει φτάσει στο τέλος του. Παράλληλα με την αλλαγή αυτή όλες οι διεργασίες, εκτός από τον γονέα τους, γνωρίζουν τώρα και τα παιδιά τους.
Ανάλυση Απόδοσης
Για να μπει μια διεργασία στο δέντρο αναζήτησης που κατασκευάζεται αρκεί να λάβει μήνυμα αναζήτησης. Κατά την εκτέλεση του γύρου i,όλες οι διεργασίες σε απόσταση i από την u_0 είναι βέβαιο πως έχουν λάβει ένα τέτοιο μήνυμα. Αν υποθέσουμε ότι η πιο μακρινή απο τη u_0 διεργασία βρίσκεται σε απόσταση r ,τότε μετά απο r γύρους η κατασκευή ενός BFS δέντρου θα έχει ολοκληρωθεί.
Η πολυπλοκότητα του αλγορίθμου σχετίζεται άμεσα με τα κανάλια επικοινωνίας που χρησιμοποιούνται (m) και με την διάμετρο του δικτύου (diam(G)).Η πολυπλοκότητα επικοινωνίας είναι Ο(m) ενώ η χρονική πολυπλοκότητα Ο(diam(G)).
Εάν στο μοντέλο εισάγουμε την υπόθεση πως οι διεργασίες είναι σε θέση να αναγνωρίζουν τα κανάλια από τα οποία έχουν λάβει μήνυμα αναζήτησης τότε μπορούμε να μειώσουμε τον αριθμό των μηνυμάτων που απαιτεί ο αλγόριθμος: Οι διεργασίες δεν στέλνουν μήνυμα αναζήτησης στα κανάλια από τα οποία προηγουμένως έχουν λάβει αντίστοιχο μήνυμα.
Υλοποίηση Αλγόριθμου
Στην συνέχεια παρουσιάζουμε την υλοποίηση του αλγόριθμου BFS με την χρήση της γλώσσας nesC στο περιβάλλον TinyOS.
Λόγω της ασύγχρονης λειτουργίας του συστήματος, η σωστή εκτέλεση του αλγόριθμου απαιτεί την ύπαρξη μιας ουράς για τα εξερχόμενα μηνύματα. Για αυτό τον λόγο χρησιμοποιούμε το component QueuedSend που προσφέρει το ίδιο interface SendMsg με το component GenericComm αλλά τοποθετεί τα μηνύματα σε μια ουρά. Tα αρχεία που υλοποιούν το component QueuedSend είναι στον φάκελο /opt/tinyos-1.x/tos/lib/Queue. Κατά την μεταγλώτισση της εφαρμογή μας, για να συμπεριληφθεί σωστά το component QueuedSend πρέπει να εισάγουμε στο Makefile την εξής γραμμή:
PFLAGS= -I%T/lib/Queue
Η υλοποίηση του αλγόριθμουBFS, σε υψηλό επίπεδο, αποτελείται από το module BFSM που περιέχει την λογική της διαδικασίας, το component GenericComm που χρησιμοποιείται για την παραλαβή Active Messages και το component QueuedSend που χρησιμοποιείται για την αποστολή Active Messages. Το διάγραμμα διασύνδεσης απεικονίζεται γραφικά στην παρακάτω εικόνα.
 Algorithm BFS |
includes BFSMsg;
configuration BFS{
provides interface StdControl;
provides interface SpanningTreeControl;
}
implementation {
components BFSM, QueuedSend, GenericComm, TimerC;
BFSM.SendMsg -> QueuedSend.SendMsg[AM_BFSMSG];
BFSM.ReceiveMsg -> GenericComm.ReceiveMsg[AM_BFSMSG];
StdControl = GenericComm;
StdControl = QueuedSend;
BFSControl = BFSM;
BFSM.Timer -> TimerC.Timer[unique("Timer")];
}
Το αρχείο BFSMsg.h ορίζει την δομή των μηνυμάτων του αλγόριθμου και τις απαραίτητες σταθερές. Η δομή του μηνύματος BFSMsg είναι πολύ απλή:
- Το πεδίο id χρησιμοποιείται για την αποθήκευση της ταυτότητας που πρόκειται να σταλεί.
- Το πεδίο height χρησιμοποιείται για την αποθήκευση του ύψους που έχει η διεργασία εφόσον βρίσκεται στο δέντρο που κατασκευάζεται.
typedef struct BFSMsg {
uint16_t id;
uint16_t height;
} BFSMsg;
enum {
AM_BFSMSG = 15
};
enum {
UNKNOWN_PARENT = 65534,
JOINED = 1,
NOT_JOINED = 0
};
Το module BFSM χρησιμοποιεί τα interfaces SendMsg,ReceiveMsg και Timer ενώ παρέχει το BFSControl.
module BFSM {
provides {
interface BFSControl;
}
uses {
interface SendMsg;
interface ReceiveMsg;
interface Timer;
}
}
Οι διεργασίες διατηρούν (α) μια μεταβλητή uint16_t m_ID με την ταυτότητα της διεργασίας, (β) μια μεταβλητή uint16_t m_parentID με την ταυτότητα της διεργασίας γονέα τους (γ) μια μεταβλητή uint8_t m_joined η οποία παίρνει τη τιμή JOINED όταν η διεργασία μπει στο δέντρο (δ) μια μεταβλητή uint16_t m_height όπου η διεργασία διατηρεί το ύψος της στο δέντρο και (ε) μια μεταβλητή uint16_t m_rounds που αντιπροσωπεύει τους γύρους εκτέλεσης του αλγορίθμου για την διεργασία.
implementation {
uint16_t m_ID;
uint16_t m_parentID;
uint8_t m_joined;
uint16_t m_height;
uint8_t rounds;
TOS_Msg m_msg;
//...
Η αρχικοποίηση του αλγόριθμου γίνεται ως εξής:
async command result_t BFSControl.init(uint16_t deviceID) {
atomic {
m_joined = NOT_JOINED;
m_ID = deviceID;
m_parentID = UNKNOWN_PARENT;
m_height = 0;
}
dbg(DBG_BOOT, "BFS: initialized.\n");
return SUCCESS;
}
//..
Η αποστολή μηνύματος αναζήτησης από τη διεργασία περιλαμβάνει τα εξής:
task void sendSearchMessage() {
// Access message body
BFSMsg * msgdata = (BFSMsg *) m_msg.data;
// Set message contents
atomic {msgdata->id = m_ID;
msgdata->height = m_height;}
// Try to send the message
call SendMsg.send(TOS_BCAST_ADDR, sizeof(BFSMsg), &m_msg);
dbg(DBG_TEMP, "BFS: Sending \tBFSMsg(%d)\n",
msgdata->id);
}
Κατά τη λήψη ενός μηνύματος η διεργασία εκτελεί τους κατάλληλους ελέγχους. Εάν δεν βρίσκεται ήδη στο δέντρου θέτει για στην m_parentID το ID που περιέχει το μήνυμα. Εάν βρίσκεται ήδη στο δέντρο ελέγχει εάν η m_height είναι μεγαλύτερη απο τη height που μεταφέρει το μήνυμα. Τότε εάν χρειάζεται, αλλάζει γονέα θέτοντας m_parentID το ID που περιέχει το μήνυμα. Εφόσον γίνει η αλλαγή γονέα η διεργασία ενημερώνει τις γειτονικές της για το νέο της ύψος στέλνοντας μήνυμα αναζήτησης.
/**
* Process a message received from the neighborhood based on the state
* of the local variables
*
* @return Always returns SUCCESS
**/
event TOS_MsgPtr ReceiveMsg.receive(TOS_MsgPtr recv_packet) {
// Access message body
BFSMsg * msgdata = (BFSMsg *) recv_packet->data;
uint16_t joined;
uint16_t height;
atomic {joined = m_joined;
height = m_height;}
dbg(DBG_TEMP, "BFS: Received \tBFSMsg(%d)\n",
msgdata->id);
// Check if we have already joined the tree
if (joined == JOINED) {
//Check if parent should be changed
if(height > msgdata->height+1)
//better parent!
atomic{
m_parentID = msgdata->id;
m_height = msgdata->height+1;
dbg(DBG_TEMP,"New Parent (%d,\t%d)\n",m_parentID,m_height);
}
}
else {
// join the tree under the ID of the process
// that sent this search message
atomic{
m_parentID = msgdata->id;
m_joined = JOINED;
m_height = msgdata->height+1;
}
// Send new search message
post sendSearchMessage();
}
return recv_packet;
}
Η έναρξη και ο τερματισμός του αλγορίθμου ελέγχονται ως εξής:
/** * Start the tree construction process. * * @return ReturnSUCCESSif process started successfully. * If process is in progress returnFAIL. **/ async command result_t BFSControl.start() { uint16_t parentID; atomic parentID = m_parentID; // Check if already finished if (parentID != UNKNOWN_PARENT) return FAIL; dbg(DBG_USR1, "BFS: started\n"); call Timer.start(TIMER_REPEAT,3000); return SUCCESS; } /** * Generate the event of the completion of the * spanning tree construction process **/ task void reportJoined() { uint16_t parentID; uint16_t height; atomic parentID = m_parentID; atomic height = m_height; dbg(DBG_BOOT, "BFS: joined.\n"); signal BFSControl.joined(parentID, height); } /** * Respond to theSendMsg.sendDoneevent by generating debuging * information * * @return Always returnsSUCCESS**/ event result_t SendMsg.sendDone(TOS_MsgPtr msg, bool success) { // Access message body BFSMsg * msgdata = (BFSMsg *) msg->data; dbg(DBG_TEMP, "Sent \tBFSMsg(%d)\n", msgdata->id); // Report that process joined the tree post reportJoined(); return SUCCESS; }
Λόγω ασυγχρονισμού οι διεργασίες στέλνουν σε τακτά χρονικά διαστήματα μηνύματα αναζήτησης στις γειτονικές τους διεργασίες. Ο αλγόριθμος τερματίζεται μετά από diam γύρους. Τα παραπάνω υλοποιούνται με τη χρήση ενός Timer . Ο αριθμός diam είναι 15.
event result_t Timer.fired(){
post sendSearchMessage();
atomic rounds++;
if (rounds>15){
call Timer.stop();
post reportJoined();}
return SUCCESS;}
}
