Algorithms in DS Flashcards
What is Deadlock?
Trains approach each other at a crossing, both come to a full stop. Neither shall start up again until the other has gone
Conditions for Deadlock? (4)
Mutual Exclusion- one resource must be non-shareable
Hold and Wait- A process is holding a resource and is requesting one currently held by a different process
No Preemption- Once a process has acquired a resource, nothing can force it to relinquish
Circular Wait- Processes waiting for one another in such a way that there is a cycle of dependencies between them
Strategies for dealing with deadlock?
Prevent- make sure the four conditions are never possible at the same time
Avoid- Even if it is possible for all 4 conditions to be true at the same time, make sure it doesn’t happen
Detect- if all 4 conditions do hold at the same time, do something about it
What two architectures have we seen for DS? Describe
Client-Server: server processes coordinate communication on behalf of clients. Roles are different.
Peer-to-Peer: Processes talk directly to one another to avoid the overhead of going through a server. Peers are more or less homogeneous.
What is a thin client?
The terminal can’t provide much functionality. All the processing and interpretation is being done on the server which takes on most of the work. Every client you add increases the load.
What is a thick client?
Has a fair amount of functionality that can operate independently of its corresponding server.
Increased administrative overhead.
What is Data synchronisation and Process synchronisation?
Data synchronisation: keeping multiple copies of a dataset in coherence with one another.
Process Synchronisation: multiple process need to act together to achieve a certain overall purpose
Describe the two generals problem
two generals are only able to communicate with one another by sending a messenger through enemy territory. The experiment asks how they might reach an agreement on the time to launch an attack, while knowing that any messenger they send could be captured.
Give the argument for reductio ad absurdum for the two generals problem
Take an exchange of messages that appears in a coordinated solution. Assume the last message gets lost, if they still succeed the message wasn’t vital. Repeat until no messages are exchanged. No messages isn’t a solution so our original assumption was wrong
What is the only thing we can say about when a message will be received?
a message wont arrive at its destination before it is sent
What is a logical clock?
can be used to give a distributed incremental pseudo time to events in a DS
Give an example of a logical clock
Lamport Clocks:
each processor has a logical clock
when an event occurs on a processor, it increments its clock by 1
When a processor sends a message it also sends it logical clock to the other processor.
When the processor receives the message, if its logical clock < (other clock + 1) then clock = (other clock + 1) else keep its clock
What is a critical section?
A sequence of events that have to occur successfully in a particular order otherwise abort
How do you create a critical section?
Create a Mutex (mutual exclusion lock). Once one client has locked the mutex, noone else can. Once finished, it is unlocked
Describe the process of a process wanting to enter a critical section
Describe how processes respond
Generate timestamp
Send request (process, timestamp) to everyone
Wait for a reply from everyone to say its ok
Enter critical section
Response: if already in critical section, defer reply. Otherwise send reply. If this process wants to enter critical section and its time stamp is > other, allow the other. Otherwise, defer reply
