Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Flertrådad programmering > Module 2: Synchronization > Flashcards

Module 2: Synchronization Flashcards

1
Q

Heap and stack memories

A
  • Reference to an object + value type data is saved in the Stack. EX: the object ‘account’
  • Object’s data is saved in the Heap. EX: ‘5000, 0.5, 12’ is saved in ‘account’.
  • Every thread has its own program counter & needs its own calls stack.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How do threads communicate?

A
  1. Through shared variables
  2. Through message passing / method calls
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Shared resources

A
  • EX: Instance variables
  • Multiple threads run the same method, work w/ diff values saved in the same variable & produce wrong results.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Local variables as a shared resource?

A
  • Every thread executing a method remembers the values stored in the local variables.
  • When running the method at the same time = output correct.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Local object reference as a shared resource?

A
  • The reference itself is placed on the stack but object data is on the heap.
  • Method is thread safe; every thread creates own instance of the object, the reference to the local object will be placed on the thread’s local stack.
  • Just don’t make the local object available to another thread.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Context switch

A
  • Process of storing the state of a process or thread, so that it can be restored and resume execution at a later point.
  • Threads may race to update & save the variable.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Interleave

A
  • Operation can consist of multiple steps.
  • EX: k++;
    1. Retrieve current value of k.
    2. Increment value by 1, k = k+1
    3. Store the incremented value back in k
  • Threads can overwrite each other by reading the initial value of k instead of the updated version.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Atomic operation

A
  • Performs completely w/o interleaving (i.e interference)
  • Can’t stop in the middle. Either happens fully or doesn’t at all.
  • k++; done completely by one thread before another accesses k.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Thread Interference

A
  • Condition when more than one thread, executing simultaneously, accesses the same piece of data.
  • Caused by interleaving
  • Data may get corrupted
  • Occurs when the code is not THREAD SAFE.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Thread safe

A
  • Code is safe to call by multiple threads simultaneously.
  • Non-interference: safety property. Guarantees that atomic action in a thread does not alter a shared resource.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Avoiding thread interference

A
  • Locks
  • Const, readonly
  • Thread-local variables
  • Atomic operations (Mutual Exclusion)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Race condition

A
  • Threads race through the critical secion
  • Sharing data & resources => Reading/Writing can occur in the wrong order. Erroneous output & corrupt data.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Synchronization

A
  • Process of making threads work in a way to ensure that shared data and resources are used safely.
  • Possible interleaving is restricted.
  • EX: locks, mutex, semaphores, monitors, condition variables.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Sync Patterns

A
  1. Writer-Reader
  2. Producer-Consumer (bounded buffer)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Mutual Exclusion

A
  • Only one thread is allowed to be in its critical region at a certain time.
  • ME is a mechanism that ensures this.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Condition sync

A
  • Wait, Pulse, PulseAll
  • Signal a condition, process sets a shared variable
  • One thread waits for an event signaled from another thread
  • Wait for a condition to become true (called ‘busy waiting’)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Critical Section

A
  • Sequences of instructions that may get incorrect results if executed simultaneously
  • Usually accesses shared variables
  • Must be protected!!!
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Four Requirements for a solution

A
  1. Mutual Exclusion
  2. Progress
  3. Fairness
  4. No assumption on performance
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Requirement for solution: Mutual Exclusion

A

Only one thread in the critical section at a time.

19
Q

Requirement for solution: Progress

A

No dead/livelock. When no thread is in the CS, any thread that wants to enter should do so without delay.

20
Q

Requirement for solution: Fairness

A

No starvation. A thread shouldn’t wait indefinitely to enter the CS. => Bounded Wait (upper bound on nr of times a thread is allowed to enter its CS while another thread is waiting).

21
Q

Requirement for solution: No assumption on performance

A

Requirements must be met with any nr of CPUs with any relative speed. Overhead of entering & exiting should be small.

22
Q

What is a “lock”?

A

object lockObj = new object();
lock (lockObj)

  • Simple. Ensures Mutual Exclusion but deadlock, livelock, starvation can occur.
  • Lock is aquired by running thread when a statement is executed
  • Automatically released at the end of the lock-block
23
Q

Lock states

A
  1. Held (locked) - lock is in use
  2. Not Held (unlocked) - lock is not in use
24
Q

Lock operations

A
  1. Acquire lock - if lock is not held, mark it Held and thread goes on. Else: wait for lock.
  2. Release lock - mark lock Not Held, and if there is a thread that has called Aquire it gets the lock.

Other threads cannot acquire the same lock when it is used. Can aquire other locks though! Use same lock in CS accessing same data.

25
Q

Reader/Writers problem

A

Many reader and writer threads share the same single resource.

26
Q

Reader/Writer solution

A
  • More than 1 Reader can access the shared resource concurrently
  • The shared resource can be a single object or a buffer
  • More than 1 Writer SHOULD NOT access the shared resource concurrently
  • Threads need to wait for each other when they’re not allowed to enter the code
27
Q

Producer-Consumer (or Bounded-Buffer) Problem

A
  • Thread puts data into the tail of a buffer & another thread reads & empties the data from the head of the buffer (repeatedly).
  • Buffer = shared queue
  • 1 Producer puts work items into buffer. 1 Consumer waits & removes items for processing.
28
Q

Producer-Consumer Rules

A
  1. Producer shouldn’t add an item to the buffer when its full
  2. Consumer shouldn’t remove an item when the buffer is empty
  3. Usually 1 Producer & 1 Consumer, but a solution with more producers & consumers can be programmed.
29
Q

Classic Synchronization Problems

A
  1. Race Condition
  2. Deadlock
  3. Livelock
  4. Starvation
30
Q

Race condition Example

A
  • Imagine multiple light switches connected to a common ceiling light.
  • If two people tried to turn on the light using two different switches at the same time, one instruction might cancel the other or the two actions might trip the circuit breaker.
31
Q

Starvation

A
  • Action in a concurrent programming situation never gets to execute.
  • Never get shared resource / unable to make progress.
  • Happens when: shared resources made unavailable for long periods by “greedy” threads.
32
Q

Starvation Example

A

In the Dining Philosophers problem: A philosopher never gets to pick up a second fork.

33
Q

Deadlock

A

Situation when two or more threads are blocked forever, waiting “deadly” for each other.

34
Q

Deadlock Example

A

Dining philosophers: Everyone picks up one fork and never put it down.

35
Q

Livelock

A

Situation in which a thread is spinning while waiting for a condition that will never become true.
Two or more threads are waiting actively (try to solve the situation by reverting action and retrying)

36
Q

Livelock Example

A

Philosopher tries to give a fork to another. He puts it down. The other philosopher picks it up and tries to give it to the other. Puts it down as well. The cycle continues!

37
Q

Barrier

A
  • Sync method that makes a group of threads stop at a point. Can’t proceed until all other threads reach this point.

Barrier barrier = new Barrier(n);

  • n = number of participants. Each thread signals when it arrives at the barrier.
  • Accounts for the fact that threads have different speeds of execution (some are slower than others).
38
Q

Barrier Example

A

Adding two tables from a database, each table manipulated by a thread.
Both threads must be completed before the next step.

39
Q

Safety

A

Each process/thread must have a safety property, i.e not have a bad state (variables with faulty values)

40
Q

Liveness

A

Each process/thread must have a liveness property, i.e eventually eneter a good state (variables have correct values).

41
Q

Safety Properties

A
  • Class with correct locks is called “thread safe”.
  • Mutual exclusion & absence of deadlock are safety properties
  • Safety Property = nothing bad will happen. Thread will NOT enter bad state.
  • Cars don’t crash on a one-way bridge
  • A safety property must always be true.
42
Q

Achieving Safety Property

A

Mutual exclusion
Condition synchronization

43
Q

Liveness properties

A
  • A class’ ability to execute in a timely manner
  • Requires that something good happens (we don’t know when)
  • Every car can eventually cross a one-way bridge
  • Property is sometimes true
  • EX: absence of dead/livelock and starvation
44
Q

Liveness Property Solution

A
  • No deadlock (some processes can always access a shared resource)
  • No starvation (all processes can eventually access shared resource)

Flertrådad programmering (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions