We can define a process as a program that is currently being executed.

• Ready: ready for execution
• Running: executing process
• Blocked: waiting or blocked until another process gives the all clear

• Physical Concurrency
• Logical Concurrency

• shared variables: processes read and write to shared memory
  • 
• message passing: messages are sent through communication channels -

Region of code that needs to be executed atomically since resources are shared

• Busy Waiting

  Show

  Technique in which a process/task waits and constantly checks for a condition to be satisfied before proceeding with its execution

• Disabling Interrupts

  Show
  • The CPU will be unable to switch processes
  • Processes can use shared variables without another process accessing it

• Test-and-Set Intruction

  Show
  • Shared variable is lock which is initialized to false
  • Algorithm returns value that was sent and sets lock to true

  boolean lock = false;
  
    boolean TestAndSet (boolean &target){
        boolean rv = target;
        target = true;
        return rv;
    }
  
    while(1){
        while (TestAndSet(lock));
        critical section
        lock = false;
        remainder section
    }

It is similar to an integer but differs in:

• value can only be increased or decreased. No reading occurs
• after decreasing, if the value is negative then the thread is blocked until the semaphore is positive
• once a thread is released and increases the value of the semaphore, one waiting thread gets accesss

Yes

• P(S): decrements the value
• V(S): increments the value

sem = Semaphore(1)

// Process
sem.P()
  // critical section
sem.V()

• Solutions are clean
• Solutions are portable and efficient

• lock allows only one thread to enter the part that's locked and the lock is not shared with any other processes
• mutex is the same as a lock but it can be system wide
• semaphore does the same as a mutex but allows x number of threads to enter

Producer threads create items and place them in a buffer, meanwhile consumer threads remove them from the buffer. Producer threads should not be able to create items if the buffer is full, and consumers should not be able to remove items if buffer is empty.

Code can be found on page 57 of Litte Book of semaphores

buffer: number[] = [];
  mutex: semaphore = 1;
  items: semaphore = 0;
  
  Producer {
    mutex.P() // lock the mutex
      buffer.add(item)
      items.V() // increase number of items for consumer threads
    mutex.V() // release mutex
  }

  Consumer {
    items.P() // decrease number of items
    mutex.P() 
      buffer.pop() // remove item from buffer
    mutex.V()
  }

buffer: number[] = [];
  mutex: semaphore = 1;
  items: semaphore = 0;
  
  Producer {
    mutex.P() // lock the mutex
      buffer.add(item)
    mutex.V() // release mutex
    items.V() // increase number of items and signal consumer threads
  }

Consumer {
      mutex.P() 
        items.P() // decrease number of items
        buffer.pop() // remove item from buffer
      mutex.V()
    }

Recall that a producer cannot create new items if buffer is full. Also, the consumer cannot retrieve items if buffer is empty.

const bufferSize: number = N;
items: semaphore = 0;
...
if (items >= bufferSize)
  block()
...

buffer: number[bufferSize];
  mutex: semaphore = 1;
  items: semaphore = 0;
  spaces: semaphore = bufferSize;

  Producer {
    spaces.P(); // decrement number of available spaces
    mutex.P();
      buffer.add()
    mutex.V();
    items.V() // signal the consumer
  }

  Consumer {
    items.P(); // decrement number of items in buffer
    mutex.P();
      buffer.pop();
    mutex.V();
    spaces.V(); // increment spaces
  }

Occurs when a resource is read and written by concurrent threads. Ideally, you do not want to read the resource while it is being written.

• Multiple readers can be in the critical section simultaneously
• Writers have exclusive access to the critical section

isRoomEmpty: semaphore = 1;
  mutex: semaphore = 1;
  readers: number = 0;

  Reader {
    mutex.P();
      readers++;
      if(readers == 1) isRoomEmpty.P(); // first reader locks the room
    mutex.V();

    <READ/>

    mutex.P();
      readers--;
      if(readers == 0) isRoomEmpty.V(); // last readers frees the room
    mutex.V();
  }

  Writer {
    isRoomEmpty.P(); // writer waits for room to be empty
      <WRITE/>
    isRoomEmpty.V();
  }

In the previous implementation, writers can starve. This means that readers can keep coming in and writers might wait forever.

isRoomEmpty: semaphore = 1;
  mutex: semaphore = 1;
  turnstile: semaphore = 1;
  readers: number = 0;

  Reader {
    turnstile.P(); // decrease number
    turnstile.V(); // the final increase to reach 1 is given by the writer

    mutex.P();
      readers++;
      if(readers == 1) isRoomEmpty.P(); // first reader locks the room
    mutex.V();

    <READ/>

    mutex.P();
      readers--;
      if(readers == 0) isRoomEmpty.V(); // last readers frees the room
    mutex.V();
  }

  Writer {
    turnstile.P(); // let readers know a writer came in
    isRoomEmpty.P(); // writer waits for room to be empty
      <WRITE/>
    turnstile.V(); // notify readers
    isRoomEmpty.V(); // room is ready
  }

Little Book of Semaphores page 79

readerMutex: semaphore = 1;
  readers: number = 0;

  writerMutex: semaphore = 1;
  writers: number = 0;

  allowReaders: semaphore = 1;
  allowWriters: semaphore = 1;

  Reader {
    allowReaders.P();
      readerMutex.P();
        readers++;
        if(readers == 1) allowWriters.P(); // notify writers that readers are there
      readerMutex.V();
    allowReaders.V();

    <READ/>

    readerMutex.P();
      readers--;
      if(readers == 0) allowWriters.V(); //signal writers the are no more readers
    readerMutex.V();
  }

  Writer {
    writerMutex.P();
      writers++;
      if (writers == 1) allowReaders.P(); // notify readers to wait
    writerMutex.V();

    allowWriters.P();
      <WRITE/>
    allowWriters.V();

    writerMutex.P();
      writers--;
      if(writers == 0) allowReaders.V();
    writerMutex.V();
  }

A philosopher needs two forks to eat. Looking at the diagram, we can tell some of them will have to wait for an adjacent philosopher to finish eating.

Each philosopher, representing a thread, runs the following loop:

while (true) {
    think();
    getForks();
    eat();
    putForks();
  }

Each philosopher knows their number ranging from 0 to $n$. Each fork is also numbered from 0 to $n$. A philosopher $i$ grabs the left fork $i$ and the right fork $i+1$

The problem lies in the function $getForks()$ and $putForks()$. We need to implement them such that:

• Only one philosopher can hold a fork at a time
• No deadlocks
• No starvation
• Multiple philosophers eating

const getForks = (i: number) => {
    forks[getLeft(i)].P();
    forks[getRight(i)].P();
  }

  const putForks = (i: number) => {
    forks[getLeft(i)].V();
    forks[getRight(i)].V();
  }

maxPhilosophers: semaphore = n - 1;

  const getForks = (i: number) => {
    maxPhilosophers.P(); // only the first n - 1 philosophers can proceed

    forks[getLeft(i)].P();
    forks[getRight(i)].P();
  }

  const putForks = (i: number) => {
    forks[getLeft(i)].V();
    forks[getRight(i)].V();

    maxPhilosophers.V(); // notify the waiting philopher they can eat
  }

Collection of variables and procedures. Kinda like a class.

interface Condition {
    wait, // Process performing will be suspended and placed in the local queue
    signal, // One of the queued processes is popped
    queue // local queue of pending processes 
  }

  Monitor Test{
    variables: any;
    myConditions: Condition;

    procedure pn {...}
  }

• Outside processes cannot access the monitor's variables, but can call the procedures
• Only one process at a time can execute code inside the monitor

Monitor ProducerConsumer {
  items: number = 0; // # of items inside buffer
  full: condition;
  empty: condition;

  Procedure Produce {
    if (items == N) full.wait(); // can't produce since buffer is full
    <PRODUCE/> // should have released the wait
    items++;
    empty.signal(); // notify buffer is NOT empty & consumer can proceed
  }

  Procedure Consume {
    if (items == 0) empty.wait(); // can't consume since buffer is empty
    <CONSUME/>
    items--;
    full.signal(); // notify producer buffer is no longer full
  }
}

Monitor ReaderWriter {
  readers: number = 0;
  busy: boolean = false;
  reader: condition;
  writer: condition;

  Procedure beginRead {
    if (busy) reader.wait(); // wait until writer is done
    readers++;
    reader.signal(); // signal readers
  }

  Procedure endRead {
    reader--;
    if(readers == 0) writers.signal(); // notify writers there are no more readers
  }

  Procedure beginWrite {
    if(readers > 0 || busy) writer.wait(); // either reading or writing in process
    busy = true; // preparation
    writer.signal(); // notify writer it can proceed
  }

  Procedure endWrite {
    busy = false; // writer has finished
    if(reader.queue) reader.signal(); // notify reader it can proceed
    else writer.signal(); // if no readers, go to writer
  }
}

• Mutual exclusion in monitors is automatic while in semaphores, mutual exclusion needs to be implemented explicitly.
• Shared variables are global to all processes in the monitor while shared variables are hidden in semaphores
• Semaphores permit more than one thread to access the critical section, unlike monitors.
• In semaphores there is no spinning, hence no waste of resources due to no busy waiting.

• Three State Process Model in Operating System
• What Does “Busy Waiting” Mean in Operating Systems?
• What is mutual exclusion by using interrupt disabling?
• Hardware Synchronization Algorithms : Unlock and Lock, Test and Set, Swap
• Little Book of Semaphores
• What is the difference between lock, mutex and semaphore?
• Monitors in Process Synchronization
• Monitor vs Semaphore

Distributed Systems send and receive low level messages due to the absence of shared memory.

Say process $P$ wants to communicate with with process $Q$.

1. $P$ builds message in local address space
2. Sytem call sends message to $Q$
3. Both $P$ and $Q$ need to agree on what was sent

The Open Systems Interconnection Model identifies the various levels of communication, their purpose, as well as naming them. It is designed to allow open systems to communicate by using communication protocols.

Each layer offers one or more specific communication services to the layer above it. In this way, the problem of getting a message from A to B can be divided into manageable pieces, each of which can be solved independently of the others.

7 Layers:

• Physical Layer
• Data Link Layer
• Network Layer
• Transport Layer
• Session Layer
• Presentation Layer
• Application Layer

• File Transport Protocol (FTP)
• HyperText Transport Protocol (HTTP)
• Secure Shell (SSH)

Application that lives in the OSI application layer, but contains many general-purpose protocols that warrant their own layers.

It replaces the session and presentation layer

One endpoint of a two way communication link between two programs running on the network.

• socket: creates new communication endpoint
• bind: attaches local address to socket
• listen: readiness to accept client connection requests
• accept: block caller until connection request arrives
• connect: actively attempts to establish connection
• send: send data over connection
• receive: receive data over connection
• close: release connection

Server side executes the first 4 operations in order:

$socket \rightarrow bind \rightarrow listen \rightarrow accept$

1. When socket is called, caller creates new communication endpoint. The OS reserves resources for the specified resource.
2. bind associates local address with newly created socket. This tells the OS to receive messages on specified address and ports.
3. listen us called only in the case of connection-oriented communication. Allows OS to reserve buffers for specified amount of pending connection requests that are to be accepted.
4. accept blocks callers until receiving connection request. When request arrives, local OS creates copy of the socket and returns it to the caller.

Now we look at the client side.

5 . connect requires caller to specify where a connection request is to be sent. Client is blocked until connection is established.

• Both client and server perform send and receive operations.

8 . close is a symmetric operation.

Allow programs to call procedures located on other machines.

When a process on machine A calls a procedure on machine B:

1. calling process on A is suspended, and
2. execution of the called procedure takes place on B

Information can be transported from the caller to the callee in the parameters and can come back in the procedure result

• Procedures being executed in different address spaces
• Passing of parameters and results
• Either or both machines crashing

Yes, the goal if that the calling procedure should not be aware that the called procedure is executing on a different machine or vice versa. In simple words, we want to make it look like local procedure.

newlist = append(data, dbList);

Assumptions:

• dbList is globally defined
• data is the element to be appended

Observations:

• dbList is a reference to a list
• data is a value

1. $append(data, dbList)$ pushes the representations of data & dbList into the stack
2. Representations are now accessible by append's implementation

• stack before the call to append

• stack while the called procedure is active

A stub is a piece of code that translates parameters sent between the client and server during a remote procedure call.

The client and server use different address spaces, so parameters used in function calls have to be converted, otherwise the values of those parameters could not be used, because pointers to parameters in one computer's memory would point to different data on the other computer. The client and server may also use different data representations, even for simple parameters (e.g., big-endian versus little-endian for integers).

• Client stubs convert parameters used in function calls and reconvert the result obtained from the server after function execution
• Server stubs reconvert parameters passed by clients and convert results back after function execution

1. Client calls client stub
2. Client stubs builds message
3. Client's OS sends message to remote OS
4. Remote OS gives message to server stub
5. Server stub unpacks message
6. Server performs operation and returns result to the stub
7. Server stub builds message
8. Server OS sends message to client OS
9. Client OS gives message to client stub
10. Client stub unpacks message

Conside the following function:

void foobar(char x, float y, int z[5]){...}

Assuming a word is four bytes:

• char is one by
• float is a whole word
• array is group of words equal to array length

Using these rules, the following message if formed:

Server stub know the format that is being used.

To support situations in which there no result to return to the client

Occurs when reply will be returned but client is not prepared to wait for it and do nothing in the meantime.

1. Client calls servers, waits for acceptance and continues
2. Server gets results
3. Server sends response to client
4. callback in client's side is initiated
5. Client sends acknowledgment to server

• Distributed Systems 3rd edition (2017)
• Socket in Computer Network
• Stub Generation in Distributed System
• What Does Stub Mean?
• Stub (distributed computing)

Client's contact a server to retrieve the time.

Message delays will have outdated the reported time.

1. $j$ sends a timestamped request $T_1$to $i$
2. $i$ records the arrival request $T_2$ time (from local clock)
3. $i$ returns response $T_3$ with a timestamp, as well as the timestamp from $T_2$
4. $j$ records the arrival respone $T_4$ time
5. $j$ calculates offset: $\theta = \frac{(T_2 - T_1) - (T_4 - T_3)}{2}$

Graudally. Changing the time in one go can lead to serious problems such as: an object file compiled just after the clock change having a tim

Server constantly asks nodes what time it is. It then calculates the average time and notifies node whether they should speed up or slow down their local clocks.

Typically to be used in an internal synchronization algorithm.

No, we just need nodes to agree on a time.

1. If two processes do not interact, it is not necessary that their clocks are synchronized.
2. What matters is that processes agree on the order in which events occur, rather than what time it is.

Also displayed as $a \rightarrow b$ It is read as event $a$ happens before $b$.

It means all events agree that a happens firtst, then afterwards b.

1. If $a$ and $b$ are in the same process, then $a \rightarrow b$ is true
2. If $a$ is an event that sends a message,and $b$ is the event of receiving a message then $a \rightarrow b$ is true. (You can't receive a message without sending it!)

Yes. if $a \rightarrow b$ and $b \rightarrow c$

$\Rrightarrow a \rightarrow c$

When they happen in separate processes that do not exchange messages.

$a \rightarrow b$ is not true, nor is $b \rightarrow a$

Pretty much nothing can be said about when the events happened first.

• If $a$ and $b$ are in the same process, and $a$ occurs before $b$ then $a \rightarrow b$ then $C(a) < C(b)$
• If $a$ is a sending event to another process and $b$ is the receiving event, then $C(a)$ and $C(b)$ have to be assigned such that everyone agrees that $C(a) < C(b)$

The clock time, $C$, must always increase. Corrections to time can be made by adding a positive value, not substracting one.

Each process, $P_i$, mantains a local counter, $C_i$

Multicast operation by which all messages are delivered in the same order to each receiver

Nothing. It does not imply $a$ happened before $b$.

Vector clocks

Assign each event a unique name and an incrementing counter: $p_k$ is the $k^{th}$ event that happened at process $P$ Then keep track of the causal histories

Example: Two local events happen at process P, then causal history $H(p_2) = \{ p_1, p_2 \}$

To determine if an event $p$ ocurred before $q$ , we check that $p \in H(q)$ Assumming q is the last local event.

• Representation is inneficient But, there is no need to keep track of all successive events in a process, just the last one!

• Assign an index to each process
• $j^{th}$ entry represents number of events that occurred before $P_j$

We now construct the vector clock by: letting each process $P_i$ mantain a vector $VC_i$ with the following properties:

1. $VC_i[i]$ number of events that have occurred so far at $P_i$
2. If $VC_i[j] = k$ then $P_i$ knows that $k$ events occured at $P_j$

1. Before executing an event, $P_i$ executes: $VC_i[i] = VC_i[i] + d$. Recording an event
2. When $P_i$ sends message $m$ to $P_j$, it sets $ts(m) = V[i]$
3. When $P_j$ receives $m$, it adjust's its own vector by setting $VC_j[k] = max\{VC_j[k], ts(m)[k]\}$

• Cristian’s Algorithm
• Chapter 6 of Distributed Systems 3rd edition (2017)
• Vector Clocks in Distributed Systems

• Token Based Solutions: passing a special message between processes. Whoever holds the token gets to access the shared resource

  • Pros: avoids starvation & deadlocks
  • Cons: if the token is lost, a procedure needs to create a new one

• Permission Based Approach: process needs permission to access a resource

• Select one process as coordinator
• When a certain process wants access to resource, ask the coordinator
• If resource is not being accessed, reply with permission
• If resource is being accessed, either refrain from replying or deny permission. Either way, queue the request
• Once a process is done, notify coordinator
• Coordinator then calls the next item in the queue.

Pros:

• fair
• no starvation
• easy to implement
• 3 messages per resource (ask for permission, grant permission, release resource)

Cons:

• Coordinator is a single point of failure
• In a big system, the coordinator is a performance bottleneck

Permission based algorithm

They are executed in the increasing order of timestamps.

• REQUEST: message sent to all other sites to get their permission to enter CS
• REPLY: message to requesting site that gives its permission to enter CS
• RELEASE: message to all other sites when exiting CS

Each site $S_i$ has a local queue denoted by $request_queue_i$ This queue orders requests requests by their timestamps.

Let $S_i$ be the site t

Critical section request:

• $S_i$ sends request with timestamp to other sites while also putting it in its local queue
• Site $S_j$ puts $S_i$'s request in the local request queue
• $S_j$ replies to $S_i$

Critical section access:

• $S_i$ enters critical section when:
  • $S_i$ is on the top of the local queue
  • $S_i$ receives a reply with a larger timestamp from all sites $S_j$

Critical section release:

• $S_i$ removes its request from local queue
• $S_i$ sends a timestamped RELEASE message to other sites
• All other sites remove $S_i$'s request from their local queues upon recieval from previous message

Image taken from Distributed Mutual Exclusion Using Logical Clocks

Assumptions:

1. $S_i$ and $S_j$ are both in the CS
2. $S_i$'s request timestamp is smaller than $P_j$'s

With the previous assumptions it means $S_i$ and $S_j$ are on top of their respective queues Using FIFO, assumption 2, and the fact that $P_j$ is executing, then the request from $P_i$ is in $P_j$'s queue

This is a contradiction since, $P_i$ should be at the top of the queue since it has a smaller timestamp

So there cannot be two processes executing at the same time.

Permission based algorithm

They are executed in the increasing order of timestamps.

• REQUEST: message sent to all other sites to get their permission to enter CS
• REPLY: message to requesting site that gives its permission to enter CS

Each site $S_i$ has a local queue denoted by $request_queue_i$ This queue orders requests requests by their timestamps.

Let $S_i$ be the site t

Critical section request:

• $S_i$ sends message with timestamp to other sites

• Sites $S_j$ reply immediately to $S_i$ with approval if $S_j$:

  • is not interested in the critical section
  • not executing the CS
  • has a request for critical section with a larger timestamp than incoming request

• The site $S_j$ sends a delayed approval to $S_i$ if it had a request for the critical section with a smaller timestamp than the incoming request; in this case the response is delayed until the critical section is done

Critical section access:

• $S_i$ enters critical section after receiving approval from every other site

Critical section release:

• $S_i$ replies to all the defferred requests

Image taken from Distributed Mutual Exclusion Using Logical Clocks

No. "That’s because each process is personally responsible for granting permission. Even with out of order messages due to transmission delays, the REPLY message will never come thanks to the logical clocks." Distributed Mutual Exclusion Using Logical Clocks

Requests are not made to every other site, only a subset of them.

• REQUEST: message sent to sites in subset to get their permission to enter CS
• REPLY: message to requesting site that gives its permission to enter CS
• RELEASE: message to all other sites in the subset when exiting CS

Summary of critical section request:

$S_i$ sends request to subset of sites Sites $S_j$ sends a reply to $S_i$ if it has not already sent one since the last release If it has sent a reply, it puts the request inside the queue.

**Summary of critical section access: **

$S_i$ enters critical section when after receiving replies from all sites in the subset

Yes.

Solution for the electing a coordinator.

• Consider $N$ processes ${P_0,...,P_{N-1}}$
• $id(P_k)=k$

When the coordinator stops responding, a process $P_k$ initiats election:

1. $P_k$ sends ELECTION messages to all higher processes ($P_{k+1}, ..., P_{n-1}$)
2. If no one responds, $P_k$ is the coordinator
3. If a higher up responds, they take over.
4. Repeat until coordinator gets elected

"Biggest guy in town wins"

• Each process knows its successor When coordinator stops responding

1. Each process sends its ID to the successor
2. If successor node is suspendes, skip it until you find a running one
3. At each node, they add their IDS to nominate themselves
4. After returning the initial node, the node with the highest ID is elected
5. Second loop to inform everyone

• Lamport’s Algorithm for Mutual Exclusion in Distributed System
• Distributed Mutual Exclusion Using Logical Clocks
• Ricart–Agrawala Algorithm in Mutual Exclusion in Distributed System
• Maekawa’s Algorithm for Mutual Exclusion in Distributed System

Collection of shared data that can be accessed by users.

Sequence of multiple operations performed on a database, and all served as a single logical unit of work

• Query: read-only
• Update: modify object/s

They preserve consistency and take finite amount of time

• Atomic
• Consistent: transactions only make changes in predefined ways
• Isolate: transactions don’t interfere with or affect one another
• Durability: changes made by successful transactions will be saved

• BEGIN_TRANSACTION
• END_TRANSACTION
• ABORT_TRANSACTION
• READ
• WRITE

When transactions are constructed as a number of subtransactions

When clients wrap a number of requests, possibly for different servers. The idea is that either all the requests get executed, or none do.

Protocols to mantain consistency

• Transaction Manager: intercepts and executes all the submitted transactions.
• Scheduler: grands or releases locks on data objects as requested by a transaction
• Data Manager: carries out the read-write requests issued by the transaction manager

Yes

If they access the same resource, and at least one of them is a writing operation.

Transaction $b$ executes after transaction $a$ has completed

Transaction $b$ begins execution before $a$ has completed

Order of actions performed by transactions

• All transactions in both logs see the same state in DB
• DB final state is the same

• Serial: when transactions wait for the previous transaction to terminate
• Serializable: When actions are interleaved and the result is the same as the serial execution

Directed graph to test if a log is serializable.

• Transactions serve as nodes
• An edge ei is constructed between node $T_j$ to $T_k$ if one of the operations in $T_j$ appears in the schedule before some conflicting operation in $T_k$ .

• Number of nodes = Number of transactions
• Directed edge $i \rightarrow j$ for each conflicting operation $o_i \rightarrow o_j$

Control the interleaving of conflicting transactions in order to mantain DB consistency

• Transactions lock data before accessing it

• locks data before accessing
• does not lock data more than once
• unlocks data before transaction completion

• once lock is released, it cannot be requested again
• algorithm has a growing phase, then a lock point phase, finally a release phase This means there are no local minimums in the graph

• if they are well formed
• fllow a two-phase scheme

• Deadlocks
• Cascaded rollbacks

Use a transaction's timestamp to decide the order of execution

Lamport's logical clock

• Transaction Manager timestamps each tranaction

• Every transaction has an issued timestamp based on arrival
• Conflicting operations follow transaction order

Notes: W_TS(x): largest timestamp of any transaction that executed write(x) R_TS(x): largest timestamp of any transaction that executed read(x)

• What is a database transaction?
• ACID Transactions
• Concurrency Control in DBMS
• Distributed DBMS model Transactions, Architecture
• Explain serial execution or transaction with an example(DBMS)
• Precedence Graph For Testing Conflict Serializability in DBMS