Cs 343 Part 2

Front 1

If you pre-order statements to make sure deadlock doesn't occur, is this deadlock avoidance or prevention?

Back 1

Prevention because it is statically known that the ordering can't deadlock

Front 2

Is graph reduction deadlock avoidance or prevention?

Back 2

Avoidance because graph reduction occurs at execution time.

Front 3

Is using the Banker's algorithm deadlock prevention or avoidance?

Back 3

Avoidance because the algorithm is executed at runtime.

Front 4

What do Linux, OSX, and Windows do about potential deadlock?

Back 4

Nothing!

Front 5

What is the difference between daisy chain and multiple signalling?

Back 5

Daisy chain signalling is when one blocked task unblocks the next blocked task after it is unblocked. Multiple signalling is when blocked tasks are woken by a single task.

Front 6

Why is the implicit signal monitor expensive to use?

Back 6

Because whenever the monitor changes state (block or return), all blocked tasks must be woken so they can check their condition variables.

Front 7

What is a barging task with respect to a mutex object?

Back 7

Barging occurs when a task outside the monitor is implicitly scheduled before a task schedulable inside the monitor.

Front 8

What is a common solution to deal with bargers? What is the problem with this solution?

Back 8

Enclose the wait in a while loop, rechecking the condition when it wakes. However, this is busy-waiting with potential starvation.

Front 9

Why does an administrator always use signalBlock for synchronization?

Back 9

It forces the worker task to execute next so it can exit the mutex object with new work.

Front 10

What are the purpose of tickets in an asynchronous call?

Back 10

To identify a a returning client to a server so the server can return the value it computed for the client

Front 11

What is the difference between explicit-storage-management and implicit-storage-management futures?

Back 11

explicit storage management futures must be allocated and deallocated explicitly by the client, whereas the implicit version is automatically allocated and freed when no longer in use.

Front 12

suppose we have:

_Select( future1);

foo();

What are the conditions for foo to execute?

Back 12

future1 must be available.

Front 13

What needs to be true for execution to continue past:

_Select( f1 || f2) ?

Back 13

Either f1 or f2 must be available.

Front 14

What takes precedence, || or &&?

Back 14

&&

Front 15

Explain what this statement does.

_Select(f1 || f2 && f3)

Back 15

Execution continues only when future f1 is available, or both f2 and f3 are available.

Front 16

When a task accesses a future, an an exception is delivered instead of a value, is the exception synchronous or asynchronous?

Back 16

Synchronous because the task accessing the future triggers the exception on its own stack.

Front 17

What does the type qualifier volatile mean?

Back 17

The variable's value is always fetched from or stored to memory on each access.

Front 18

What is a watchpoint and how is it used for concurrency?

Back 18

A watchpoint is when the hardware is told to watch a memory location for changes. A watchpoint is used in concurrency to know if a copied value is still the same at a later time, indicating if it is safe to change the value.

Front 19

What is the disadvantage of the requeue mechanism to simulate internal scheduling via external scheduling?

Back 19

Dealign with temporary computations and execution location that must be manually remembered as part of the queue.

Front 20

Why is a library approach to concurrency, like pthreads, potentially unsafe?

Back 20

The compiler doesn't know the program is concurrent, so it can perform sequential optimizations, which invalidates the library usage.

Front 21

When creating and joining threads using pthreads, what is the most significant problem?

Back 21

Transferring arguments and returning a result is not statically type-safe.

Front 22

Why is there a tension between concurrent programmers and hardware engineers with respect to the memory model?

Back 22

Concurrent programmers don't want sequential optimizations to invalidate their programs, while hardware engineers want to perform sequential optimizations.

Front 23

Why is transferring data from one computer to another a problem?

Back 23

The data may be in incompatible formats.

Front 24

How do we perform internal scheduling with send/receive/reply?

Back 24

The receiver doesn't have to reply immediately. It can keep the sender blocked and reply at some later time (it has the senders pid)

Front 25

There is an administrator who takes requests to getClient or getTaxi. When it receives a call to close, it cleans up and terminates. What does the structure of its while loop look like?

Back 25

Front 26

Tasks A and B call A(), B() in a monitor to exchange values. Write A(), B() using internal scheduling.

Back 26

Front 27

Tasks A and B call A(), B() in a monitor to exchange values. Write A(), B() using external scheduling.

Back 27

Front 28

Tasks A and B call A(), B() in a monitor to exchange values. Write A(), B() using implicit scheduling (waitUntil)

Back 28

Front 29

Suppose we have a list of taxis and a taxi-pointer iterator for that list. How do we get the id of the first taxi in the iterator, then delete that taxi from the list?

Back 29

(*iterator)->id

taxis.delete( iterator )

Front 30

If there are available taxis and waiting clients, we want to satisfy a client by delivering its taxi future (ftaxi). Taxis are waiting on their 'idle' condition variable. When they wake, they examine xclient and yclient to determine where to go. Calling nearestTaxi(LocnClient*, list

Back 30

Front 31

How to we print a message inside a monitor?

Back 31

osacquire(cout) << "message!" << endl;

Front 32

Suppose we have a list of LocnClient with futures ftaxi. How do we mark the futures with a Closed exception and delete the clients?

Back 32

Front 33

Suppose we have a list of Taxi tasks. When they call getClient, they become blocked on a condition variable idle in LocnTaxi. We want to tell all taxis to go home by setting xclient and yclient to -1.

Back 33

Front 34

Suppose we don't want to let bargers pass through the entry code of a method before its their turn. How can we do this?

Back 34

Front 35

We're writing a barrier monitor. Bargers won't process past the entry code unless ticket < serving. Once count reaches N, we release the blocked task. Write the main body of code.

Back 35

Front 36

Write the full code for a barrier with internal scheduling and bargers.

Back 36

Front 37

Write the code for a barrier monitor with implicit scheduling. WAITUNTIL( cond ), RETURN

Back 37

Front 38

When does staleness occur in the readers writers problem?

Back 38

When the arrival time of a reader's task read is newer than the arrival time of a waiting writer task. So, it should really read the value that the writer writes, but the writer hasn't written yet.

Front 39

When does freshness occur in the readers writers problem?

Back 39

When the arrival time of a writer's task write is newer than the arrival time of a waiting reader task. So, the reader will read the new value, when it really shouldn't.

Front 40

What is staleness?

Back 40

Reading an old value, ex:

W1 W2 R1

R1 reads W1 instead of W2.

Front 41

What is freshness?

Back 41

Reading a future value, ex:

W1 R1 W2

R1 reads W2 instead of W1.

Front 42

The following code sequence exists in the entry protocols for readers/writer implemen- tations, where the baton is put down and a thread blocks:

entry.V(); X.P(); // X is some semaphore

Explain, in general, how this code sequence may result in staleness or freshness.

Back 42

Entry is like the baton.

Thread 1 puts down baton, but is time-sliced before X.P().

Thread 2 puts down baton, but is not time-sliced, so it blocks on X.

Thread 1 restarts and blocks on X.

Threads 1 and 2 are now out of order.

Front 43

What are the 3 new kinds of errors introduced by concurrency?

Back 43

1. Deadlock

2. Livelock

3. Race

Front 44

How can nested monitor calls result in deadlock? (i.e. a call from one monitor into another)

Back 44

Task calls into monitor M1, which makes a call to monitor M2. Task waits in M2, which release the lock on M2, but it still holds a lock to M1. Another task can't signal X because it can't get into M2 via M1.

Front 45

What are two scenarios when using a _Nomutex member is useful?

Back 45

1. For read-only routines

2. For combining a multi-step protocol into a single routine, where some of the steps need to release the monitor lock.

Front 46

Why do we not want an abstraction with a thread and no stack?

Back 46

A thread can't execute without a stack.

Front 47

Why might we not want an abstraction with a thread and stack, but no mutual exclusion/synchronization?

Back 47

All synchronization/mutual exclusion would have to be handled explicitly using locks.

Front 48

What is the purpose of a _When clause on an _Accept clause?

Back 48

Provides a condition on acceptance

Front 49

Rewrite the following without using a _When clause:

_When ( a > b ) _Accept( c )

Back 49

if ( a > b ) _Accept( c )

Front 50

What is the difference between direct and indirect communication?

Back 50

Indirect communication occurs through a third party. For example, task <-> monitor <-> task.

Direct communication occurs directly between tasks, i.e. task <-> task

Front 51

Why must we use a flag variable when an administrator needs to return an exception for a client call?

Back 51

The client has to be unblocked so it can raise the exception on its stack, instead of the server's.

Front 52

A future implementation needs the following 3 fields:

uSemaphore resultAvailable;

future *link;

ResultType result;

Explain the purpose of each field.

Back 52

Block client if result not available.

Link futures so server can buffer them for processing.

Result after computed by server.

Front 53

What is disjoint reordering with respect to optimization?

Back 53

Ability to reorder reads and writes on different variables.

Front 54

How do connectionless and connection-oriented communications differ with respect to packet addressing?

Back 54

All connectionless packets carry their dest address, while connection-oriented don't after a connection is established.

Front 55

What are two ways to handle pointers in remote procedure calls?

Back 55

1. Marshal the entire linked data structure (traversing all pointers) and copy the list

2. Use long pointers between address spaces and fetch data only when the long pointer is dereferenced.

Front 56

What execution property are concurrent programmers willing to give up so caching can work efficiently?

Back 56

Reading up to date values (state values may be read)

Front 57

How can disjoint reordering cause a concurrent program to fail? Give an example.

Back 57

me = WantIn // Write

while ( you == WantIn ) { // Read

interchanging would mean that both threads read DontWantIn, set wantIn and proceed (ruins mutual exclusion).

Front 58

C++ 11 threads are implemented by pthreads. What threading model does this use and what is the disadvantage?

Back 58

1:1 model; can't create large numbers of kernel threads

Front 59

Explain the kind of concurrency supported by #pragma

Back 59

concurrent system provides concurrency through implicit constructs, which a programmer uses to build a concurrent program (indirect access to threads)

Front 60

In ADA:

out("blah") writes a tuple to user space

in ("bleh") (blocking) removes a tuple from user space. Build mutual exclusion and synchronization from these constructs.

Back 60

Mutual exclusion:

out("semaphore);

....

in("semaphore")

// CS

out("semaphore")

Synchronization:

Task 1:

in("semaphore)

S2

Task 2:

S1

out("semaphore")

Front 61

A producer and a consumer add and remove from the same shared queue. Should the queue be an array or a linked list? Why?

Back 61

An array. If it's a linked list, they could be manipulating the same data element simultaneously. (Eg. add, blah.next = ..., while blah is being removed)

Front 62

If there is maximum concurrency, what does this say about the critical section?

Back 62

It's as small as possible.

Front 63

What is a split binary semaphore?

Back 63

A collection of semaphores where at most one has the value 1.

Front 64

When are split binary semaphores used?

Back 64

When different kinds of tasks have to block separately.

Front 65

What technique is used with split binary semaphores to solve mutual exclusion problems?

Back 65

Baton passing

Front 66

What are the rules of baton passing?

Back 66

1. There is exactly one baton

2. Nobody moves in the entry/exit code until they have it.

3. Once the baton is released, cannot read/write variables in the entry/exit code

Front 67

In baton passing, who passes the baton and who implicitly picks it up?

Back 67

Signaller implicitly passes it to signalled

Front 68

What are two goals of the readers/writers problem solution?

Back 68

1. Serialize writes

2. As many readers as you want

Front 69

What happens in the following statement?

REGION v DO

AWAIT NOT EMPTY v

Back 69

Lock is acquired, but if the condition in await is false, the lock is released and entry is re-started (busy waiting)

Front 70

What problem is solved by having an atomic counter monitor with increment/decrement functions?

Back 70

Won't suffer from time slicing issue because operations are atomic

Front 71

External scheduling is simple because unblocking is....

Back 71

implicit

Front 72

A task is inside a monitor and calls x.wait(). What 3 things happen?

Back 72

1. Executing task is placed atomically at the back of the condition queue

2. Releases monitor lock

3. Another task can enter

Front 73

what does uCondition.front() return?

Back 73

The integer call stored with the waiting task at the front of the condition queue

Front 74

How is termination synchronization accomplished in java?

Back 74

calling join()

Front 75

How do we retrieve values from a terminated java thread?

Back 75

It becomes an object, so we can call thread.blah

Front 76

What does it mean for a java class member to be synchronized? Why is it incorrectly named?

Back 76

It's mutex; i.e. it's mutually exclusive, not synchronized

Front 77

What is deadlock avoidance?

Back 77

Monitoring all lock blocking and resource allocation to detect any potential formation of deadlock.

Front 78

What is one disadvantage and one advantage of deadlock prevention over deadlock avoidance?

Back 78

Advantage: better resource utilization

Disadvantage: additional overhead/processing to avoid deadlock

Front 79

To run the Banker's algorithm, what must processes state?

Back 79

Their maximum resource needs

Front 80

What are 2 disadvantages of detecting deadlock via resource allocation graphs?

Back 80

1. For lots of processes and resources, detecting cycles is expensive

2. Lots of graphs must be examined; one for each particular allocation state of the system

Front 81

When are allocation graphs constructed?

Back 81

At each moment a resource is allocated

Front 82

What are two requirements for deadlock detection and recovery?

Back 82

1. Ability to discover deadlock

2. Preemption

Front 83

How is deadlock recovery implemented?

Back 83

Preemption of one or more processes in a cycle

Front 84

Are public member of a task implicitly mutex or nomutex?

Back 84

mutex

Front 85

What does external scheduling facilitate in task communication?

Back 85

Allows direct calls to task's mutex members (task blocks during this)

Front 86

Why are accept statements in tasks in the main, not member routines?

Back 86

Because the task's thread starts in main; a monitor doesn't have a thread

Front 87

What can we do to keep public mutex methods as short as possible?

Back 87

do the absolute minimum about of work in the method, and the bookkeeping in the block after the accept statement.

Front 88

If a task accepts its destructor, when is the destructor executed after it's called?

Back 88

After the the caller is popped off the accepted/signalled stack (i.e., after exiting the main)

Front 89

What is the potential problem is _Accept( insert, remove)

Back 89

insert is prioritized, so there is potential starvation for consumer.

Front 90

To maximize concurrency, how should the number of clients and workers relate?

Back 90

1:1

Front 91

What are 3 approaches for asynchronous client/server calls?

Back 91

1. Tickets

2. Callback routines

3. Futures

Front 92

How to tickets work (asynchronous call)?

Back 92

Client makes call to serve specifying work and is returned a ticket immediately. Later, it passes the ticket to retrieve the result and blocks or polls if it's not ready.

Front 93

What are 2 possible problems with using ticket for asynchronous client/server calls?

Back 93

1. Client may use same ticket twice

2. Client could forge ticket and retrieve someone else's work

Front 94

How do call-back routines work?

Back 94

The client passes a routine to be called when the work is done. The routine must not block the server, only store the value and set an indicator. The client must poll the indicator or block until it is set.

Front 95

What are two advantages of call-back routines?

Back 95

1. Server can drop off value immediately, instead of storing it.

2. Client writes the callback routine, so they can decide to block/poll/both.

Front 96

List 2 ways a future is different from a ticket or callback routine.

Back 96

1. No explicit protocol

2. Only one call must be made, not 2.

Front 97

Rewrite the following without or/and:

(_Select(f1)

_or (_Select(f2)

_and(_Select(f3))

Back 97

_Select(f1 || (f2 && f3))

Front 98

Explain LL(load-locked) and SC (store conditional) in MIPS.

Back 98

LL loads value into register and establishes a watch point. SC writes value to memory location, but only if no interrupt, exception, or write has occurred at LL watchpoint (sets register with value to be stores to 0 if so).

Front 99

Write Node *pop(header &h) using LL and SC.

Back 99

Front 100

How does SC differ from CAA?

Back 100

SC detects a change to a value, rather than indirectly checking if value has changed by comparing it.

Front 101

Suppose we have an 'atomic' command that executes a block atomically. Write void push( header &h, node &n).

Back 101

void push(header &h, node &n) {

atomic {

node.next = h.top;

h.top = &n;

}

}

Front 102

What is a drawback of goroutines in go?

Back 102

No direct communication because you can't reference a coroutine object.

Front 103

How do threads communicate/synchronize in Go?

Back 103

Through a channel.

Front 104

What is a limit on the when clause in Ada?

Back 104

It can only contain global variables.

Front 105

How is waiting on a condition variable different than using a require statement in ada?

Back 105

Condition variables automatically save the execution location and any partially computed state, whereas requeing doesn't.

Front 106

How do threads communicate in Linda?

Back 106

Adding, removing, reading data from tuple space.

Front 107

What is an actor?

Back 107

An administrator that accepts messages. It handles them, or sends them to a worker in a fixed open pool.

Front 108

How do clients communicate with Actors?

Back 108

Through a mailbox; an untyped queue of messages. The clients put messages in the queue, the admin reads them and delegates them.

Front 109

List 2 differences between Scala and uC++

Back 109

1. Dynamic(scala) vs static(uC++) communication

2. Scala sends messages asynchronously; uC++ has synchronous calls

Front 110

Open MP has what type of threading model?

Back 110

1:1

Front 111

What is an executor?

Back 111

A server with one or more worker tasks

Front 112

What does a call to submit in an executor return?

Back 112

It returns a future (asynchronous)

Front 113

What does it mean for two programs to be isomorphic?

Back 113

They produce the same result

Front 114

How can we share data among programs?

Back 114

Use a cache

Front 115

What is a problem with multiple caches in a concurrent program?

Back 115

Variable appears in multiple caches. When a thread writes changes to local cache, it invalidates copies in other caches.

Front 116

What are possible methods to type check parameters and arguments in remote calls?

Back 116

1. Dynamic check (additional CPU power, runtime errors)

2. Persistent symbol table that describes called interface

Front 117

Give 2 ways message passing is different from parameter passing.

Back 117

1. Information grouped into a single data area

2. Data passed by value

Front 118

In RPC, why use receive any instead of receive specific?

Back 118

Can have multiple producers

Front 119

What is one advantage and one disadvantage of fixed-sized messages?

Back 119

Advantage: easy implementation

Disadvantage: requires long messages to be broken up

Front 120

What is one advantage and one disadvantage of variable-sized messages?

Back 120

Advantage: easy to use

Disadvantage: more difficult implementation

Front 121

What does typed messaging require?

Back 121

Dynamic type checking

Front 122

What is the two army problem?

Back 122

Two perfect processes with imperfect communication

Front 123

What is the byzantine general problem?

Back 123

Imperfect process that lies about group strength

Front 124

What are the steps in an RPC?

Back 124

1. Local call from client to client stub

2. Stub collects arguments and marshals into a message, passes to local transport entity

3. Transport entity sends message to server transport entity

4. Server transport entity passes message to server stub

5. Server stub unmarshalls message and calls local routine

6. Server performs operation, returns result to stub

7....and back we go.

Front 125

Who is awesome?

Back 125

That's right, you are.