EX23 - Broadcast messages and shared semaphores

With asynchronous message passing, we have a tool that gives the possibility to create broadcast messages and also shared semaphores

Question 1 - Reading in Andrew’s book

Read chapter 7.7 - Broadcast Algorithms in Andrews book (page 383-388). You find the book in the resources section.

Question 2 - Implementing the missing broadcast primitive in Python

We have seen how broadcast primitives work. Unfortunately, Python does not provide this kind of primitive out of the box.

Try to write in Python the broadcast primitive that broadcasts a message to all its recipient channels.

Solution

The solution is just to loop through all channels and send the message to each channel.

    # P();
    for i in range(N):
        channel[i].put(msg)
    # V();

This solution is not atomic, so a P()/V() around the loop would be a possibility to assure atomicity (as seen with the comments)

Question 3 - Logical clocks

Based on the example code of the lecture notes (256) about the logical clocks try to play processor and determine what are the logical clocks of the 3 processes at the end of this little example program (pseudo (python) code). Assume that all 3 process start automatically.

chA = Queue()
chB = Queue()
chC = Queue()

def processA:
    lc: int = 0

    chC.put(lc++)
    chB.put(lc++)
    ts = chA.get(); lc = max(lc, ts+1); lc++
    chC.put(lc++)
    ts = chA.get(); lc = max(lc, ts+1); lc++


def processB:
    lc: int = 0

    chC.put(lc++)
    ts = chB.get(); lc = max(lc, ts+1); lc++
    ts = chB.get(); lc = max(lc, ts+1); lc++
    chA.put(lc++)


def processC:
    lc: int = 0

    ts = chC.get(); lc = max(lc, ts+1); lc++
    ts = chC.get(); lc = max(lc, ts+1); lc++
    chA.put(lc++)
    chB.put(lc++)
    ts = chC.get(); lc = max(lc, ts+1); lc++

Solution

Two different solution has been found (are there eventually even more?)

One possible solution: lc_A = 8, lc_B = 7, lc_C = 7

Another possible solution: lc_A = 8, lc_B = 9, lc_C = 7

---