代做Algorithm | thread代写 | java作业 | 代写assignment | Operating Systems代写 - Basics of Synchronization - 学霸代写 - CS代写, 程序代写, CS作业代写, 代码代写, CS编程代写, java代写, python代写, c++/c代写, R代写, 算法作业代写, web代写, CS assignment代写, MATH代写, 统计代写, 金融代写, business代写, economic, accounting代写等

Basics of Synchronization

代做Algorithm | thread代写 | java作业 | 代写assignment | Operating Systems代写 – 本题是一个利用java进行练习的代做, 对os的Synchronization的流程进行训练解析, 包括了Algorithm/thread/java/Operating Systems等方面, 这个项目是assignment代写的代写题目

Operating System Concepts 10 thEdition Based on Silberschatz, Galvin and Gagne

Lecture 4B:

Basics of Synchronization

This Lecture

Beyond Petersons Algorithm

Synchronization Hardware

Race Condition

Situation when system behavior depends on the timing of uncontrollable events

Example:

Processes P 0 and P 1 are creating child processes using the fork() system call

Race condition on kernel variable next_available_pidwhich represents the next available process identifier (pid)

Unless there is a mechanism to prevent P 0 and P 1 from accessing the variable next_available_pid the same pid could be assigned to two different processes!

Process Code Structure

General structure of process Pi

Image: Petr Kratochvil,
Public Domain

while (true) {

other code

entry section

critical section

exit section

other code

}

Petersons Algorithm

Shared variable turn indicates the next process to enter critical section

Shared variable flag[i] indicates whether intends to enter critical section

Initialize: flag[2] = {false, false};

while (true) {

flag[0] = true; (1)
turn = 1; (2)
while (turn==
&& flag[1]) { }; (3)
critical section (4)
flag[0] = false; (5)

}

P
while (true) {
flag[1] = true; (1)
turn = 0; (2)
while (turn==
&& flag[0]) { }; (3)
critical section (4)
flag[1] = false; (5)
}

Petersons Algorithm

Shared variable turn indicates the next process to enter critical section

Shared variable flag[i] indicates whether intends to enter critical section

Initialize: flag[2] = {false, false};

while (true) {

flag[0] = true; (1)
turn = 1; (2)
while (turn==
&& flag[1]) { }; (3)
critical section (4)
flag[0] = false; (5)

}

P
while (true) {
flag[1] = true; (1)
turn = 0; (2)
while (turn==
&& flag[0]) { }; (3)
critical section (4)
flag[1] = false; (5)
}

Problems with
this approach?

Issues with Peterson s Solution

####### 1. Solution only works for 2 processes

####### 2. Solution requires busy waiting

####### 3. Susceptible to instruction reordering

Lamport’s Bakery algorithm

Initialize: entering[N] = {false, false, false, …}; Initialize: number[N] = {0, 0, 0, …}; j is waiting = number[j] != 0 j is before me = (number[j] < number[i] || (number[j] == number[i] && j < i)) P_i while (true) { entering[i] = true; number[i] = max(number) + 1 entering[i] = false; for (j = 0; j < N; j++) { while (entering[j]) { }; while (j is waiting && j is before me) { }; } critical section number[i] = 0; }

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.

Lamport’s Bakery algorithm

Read from shared memory to registers (on CPU)
Compute max(number) + 1
Write result to number[i] in shared memory

Lamport’s Bakery algorithm

P0 and P1 pick
the same number

Lamport’s Bakery algorithm

P0 hasnt updated
number[0] yet, but P
advanced to condition
checking

Lamport’s Bakery algorithm

P1 sees number of P0 as
zero, and decides that is
not P0 waiting, enters CS

Lamport’s Bakery algorithm

Meantime P0 moves on to
condition checking. Sees same
numbers for P0 and P1 , and
proceeds because 0 < 1.

Lamport’s Bakery algorithm

Both are
now in CS

Lamport’s Bakery algorithm

Both are
now in CS

Lamport’s Bakery algorithm

Both are
now in CS

Image: Alex E. Proimos
Wikimedia Commons, CC

Lamport’s Bakery algorithm

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.

Lamport’s Bakery algorithm

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.

Lamport’s Bakery algorithm

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.

Lamport’s Bakery algorithm

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.

Lamport’s Bakery algorithm

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.0

Lamport’s Bakery algorithm

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.0

Lamport’s Bakery algorithm

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.0

Special Case for Two Processes

Initialize: entering[2] = {false, false}; Initialize: number[2] = {0, 0}; j is waiting = number[j] != 0 j is before me = (number[j] < number[i] || (number[j] == number[i] && j < i)) P_i while (true) { entering[i] = true; number[i] = max(number) + 1 entering[i] = false; while (entering[j]) { }; while (j is waiting && j is before me) { }; critical section number[i] = 0; }

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.0

Special Case for Two Processes

Initialize: entering[2] = {false, false}; Initialize: number[2] = {0, 0}; j is waiting = number[j] != 0 j is before me = (number[j] < number[i] || (number[j] == number[i] && j < i)) P_i while (true) { entering[i] = true; number[i] = max(number) + 1 turn = j entering[i] = false; while (entering[j]) { }; while (j is waiting && turn == j) { }; critical section number[i] = 0; }

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.0

Special Case for Two Processes

Initialize: entering[2] = {false, false}; Initialize: number[2] = {0, 0}; j is waiting = number[j] != 0 j is before me = (number[j] < number[i] || (number[j] == number[i] && j < i)) P_i while (true) { entering[i] = true; number[i] = 1 turn = j entering[i] = false; while (entering[j]) { }; while (number[j] != 0 && turn == j) { }; critical section number[i] = 0; }

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.0

Special Case for Two Processes

Initialize: entering[2] = {false, false}; Initialize: number[2] = {0, 0}; j is waiting = number[j] != 0 j is before me = (number[j] < number[i] || (number[j] == number[i] && j < i)) P_i while (true) { entering[i] = true; number[i] = 1 turn = j entering[i] = false; while (entering[j]) { }; while (number[j] != 0 && turn == j) { }; critical section number[i] = 0; }

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.0

Special Case for Two Processes

Initialize: entering[2] = {false, false}; Initialize: flag[2] = {0, 0}; j is waiting = number[j] != 0 j is before me = (number[j] < number[i] || (number[j] == number[i] && j < i)) P_i while (true) { entering[i] = true; flag[i] = 1 turn = j entering[i] = false; while (entering[j]) { }; while (flag[j] != 0 && turn == j) { }; critical section flag[i] = 0; }

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.0

Petersons Algorithm

Initialize: flag[2] = {0, 0};

P_i while (true) { flag[i] = 1 turn = j while (flag[j] != 0 && turn == j) { }; critical section flag[i] = 0; }

Adapted from:
rhk111@flickr
CC BY-NC-SA 2.0

Issues with Peterson s Solution

####### 1. Solution only works for 2 processes

Lamports Bakery Algorithm for N processes

####### 2. Solution requires busy waiting

####### 3. Susceptible to instruction reordering

Implementing Solution

######## 1. Code level: Implement entry and exit sections appropriately

######## 2. Operating Systems provide supporting tools (next week)

######## 3. Needs assumptions about hardware instructions and/or

support in a form of special instructions (next lecture)

######## For algorithmic solutions below, assume atomic load and

store instructions

E.g., if x is a shared variable, 0 executes x=0 and 1 executes x=1 around the same time, x will be either 0 or 1, but not a scramble of bits

Busy Waiting

Wasting CPU
cycles!

Initialize: flag[2] = {0, 0};

P_i while (true) { flag[i] = 1 turn = j while (flag[j] != 0 && turn == j) { }; critical section flag[i] = 0; }

Busy Waiting (Cont.)

Issues with Peterson s Solution

####### 1. Solution only works for 2 processes

Lamports Bakery Algorithm for N processes

####### 2. Solution requires busy waiting

To avoid wasting CPU cycles, need to yield

######## the CPU and request the OS to notify (via

######## interrupt) when the condition is satisfied

####### 3. Susceptible to instruction reordering

Beyond Petersons

Algorithm

Lamports
Bakery
Algorithm

Busy waiting

Instruction
reordering

Synchronization Hardware

Reordering Operations

####### Code written in a high-level language, such as C

######## or java undergoes a lot of transformations

Compiler, run time environment, CPU

######## Programmer writes

x = 100;
print(x + 2);

######## Actual instructions could be

print(102);

######## Programmer writes

x = 100;
flag = true;

######## Actual instructions could be

flag = true;
x = 100;

######## Programmer writes

x = 100;
y = sqrt(x);

######## Note that this would be incorrect

y = sqrt(x);
x = 100;

Modern Architecture Example

######## Two threads share the data:

boolean flag = false ;
int x = 0;

######## thread 1 performs

while (!flag) { };
print(x);

######## What is the expected output?

100

######## Thread 2 performs

x = 100;
flag = true;

Modern Architecture Example (Cont.)

######## Two threads share the data:

boolean flag = false ;
int x = 0;

######## Thread 1 performs

while (!flag) { };
print(x);

######## If instructions reordered, result could be

######## Thread 2 performs

flag = true;
x = 100;

Since flag and x are
independent, results
can be reordered:

Petersons Algorithm

Shared variable turn indicates the next process to enter critical section

Shared variable flag[i] indicates whether intends to enter critical section

Initialize: flag[2] = {false, false};

while (true) {

flag[0] = true; (1)
turn = 1; (2)
while (turn==1
&& flag[1]) { }; (3)
critical section (4)
flag[0] = false; (5)

}

P1
while (true) {
flag[1] = true; (1)
turn = 0; (2)
while (turn==0
&& flag[0]) { }; (3)
critical section (4)
flag[1] = false; (5)
}

 0 
flag[2] = {false, false}
turn = 1
turn = 0
flag[1] = true
while (turn==0
&& flag[0]) { };
in critical section
flag[0] = true
while (turn==1
&& flag[1]) { };
in critical section

Initialize: flag[2]

= {false, false};

P_i

while (true) {

flag[i] = true; (1)
turn = j; (2)
while (turn==j
&& flag[j]) { }; (3)
critical section (4)
flag[i] = false; (5)

}

Reordering Breaks the Algorithm

 0 
flag[2] = {false, false}
turn = 1
turn = 0
flag[1] = true
while (turn==0
&& flag[0]) { };
in critical section
flag[0] = true
while (turn==1
&& flag[1]) { };
in critical section

Initialize: flag[2]

= {false, false};

P_i

while (true) {

flag[i] = true; (1)
turn = j; (2)
while (turn==j
&& flag[j]) { }; (3)
critical section (4)
flag[i] = false; (5)

}

Image: Alex E. Proimos
Wikimedia Commons, CC2

######## Petersons Solution and Modern Architecture

####### Although useful for demonstrating an algorithm,

######## Petersons Solution is not guaranteed to work on

######## modern architectures

To improve performance, processors and/or

######## compilers may reorder operations that have

######## no dependencies

####### For single-threaded this is OK as the result will

######## always be the same.

####### For multithreaded the reordering may produce

######## inconsistent or unexpected results!

Synchronization Hardware

######## Many systems provide hardware support for

implementing the critical section code.

######## Uniprocessors could disable interrupts

Currently running code would execute without preemption Is this practical?
Generally, too inefficient on multiprocessor systems Operating systems using this not broadly scalable

######## Hardware support:

Memory Barriers
Test-and-modify instructions

Memory Barrier Instructions

######## A memory barrier instruction is used to ensure that

all loads and stores instructions are completed before
any subsequent load or store operations are
performed

######## Thread 1:

while (!flag) { };
<memory_barrier>
print(x);

######## Thread 2:

x = 100;
<memory_barrier>
flag = true;

Ensure  assignment to
x happens before
assignment to flag

Ensure value of flag is
loaded before value of x

Memory Barrier Instructions (Cont.)

######## Usually not used directly by the programmer, but are

automatically involved when the programmer uses
synchronization tools (next lecture)

######## Memory barriers will not prevent code reordering by

compilers. Might need to use synchronization tools.

Petersons Algorithm

Shared variable turn indicates the next process to enter critical section

Shared variable flag[i] indicates whether intends to enter critical section

Initialize: flag[2] = {false, false};

while (true) {

flag[0] = true; (1)
turn = 1; (2)
while (turn==1
&& flag[1]) { }; (3)
critical section (4)
flag[0] = false; (5)

}

P1
while (true) {
flag[1] = true; (1)
turn = 0; (2)
while (turn==0
&& flag[0]) { }; (3)
critical section (4)
flag[1] = false; (5)
}

Algorithmic Solution 1

Initialize: lock = false;

P_0
while (true) {
while (lock) { }; (1)
lock = true; (2)
critical section (3)
lock = false; (4)
}

P_1
while (true) {
while (lock) { }; (1)
lock = true; (2)
critical section (3)
lock = false; (4)
}

Shared variable lock indicates whether the critical section is occupied

Could Solution 1 Work?

 0 
initialize lock = false
while (lock) { };
lock = true
in critical section
while (lock) { };
in critical section
while (lock) { };
lock = false
while (lock) { };
lock = true
while (lock) { };
in critical section

Initialize: lock = false;

P_i

while (true) {

while (lock) { }; (1)
lock = true; (2)
critical section (3)
lock = false; (4)

}

Solution 1 is Incorrect

 0 
initialize lock = false

Initialize: lock = false;

P_i

while (true) {

while (lock) { }; (1)
lock = true; (2)
critical section (3)
lock = false; (4)

}

Solution 1 is Incorrect

 0 
initialize lock = false
while (lock) { };
while (lock) { };
lock = true
lock = true
in critical section
in critical section

Initialize: lock = false;

P_i

while (true) {

while (lock) { }; (1)
lock = true; (2)
critical section (3)
lock = false; (4)

}

Image: Alex E. Proimos
Wikimedia Commons, CC2

Hardware Instructions

######## Special hardware instructions that allow us to either

test-and-modify the content of a word, or to swap the
contents of two words atomically (uninterruptedly)

Test-and-Set instruction
Compare-and-Swap instruction

The test_and_set Instruction

######## Definition

boolean test_and_set(boolean *target)
{
boolean rv = *target;
*target = true;
return rv:
}

######## Properties

Executed atomically
Returns the original value of passed parameter
Set the new value of passed parameter to true

Solution 1 + test_and_set

Initialize: lock = false;

P_i
while (true) {
while (test_and_set(&lock)) { }; (1)
critical section (2)
lock = false; (3)
}

Shared variable lock indicates whether the critical section is occupied

Solution 1 + test_and_set

 0 
initialize lock = false
while
(test_and_set(&lock)) { };
while
(test_and_set(&lock)) { };
in critical section
while
(test_and_set(&lock)) { };
in critical section
lock = false
while
(test_and_set(&lock)) { };
in critical section

Initialize: lock = false;

P_i while (true) { while (test_and_set(&lock)) { }; critical section lock = false; }

test_and_set(&lock) Returns the value of lock Also sets lock to true

Solution 1 + test_and_set

Initialize: lock = false;

P_i

while (true) {

while (test_and_set(&lock)) { }; (1)
critical section (2)
lock = false; (3)

}

Shared variable lock indicates whether the critical section is occupied

Still based on busy waiting
Does it solve the critical section problem?

The compare_and_swap Instruction

Definition **int compare_and_swap( int value, int expected, int new_value) { int temp = value; if (value == expected) value = new_value; return temp; }

Properties

Executed atomically
Returns the original value of passed parameter value
Set the variable value the value of the passed parameter new_value but only if *value == expected is true. That is, the swap takes place only under this condition.

Solution 1 + compare_and_swap

Initialize: lock = 0;

P_i

while (true) {

while (compare_and_swap(&lock, 0, 1)) { }; (1)
critical section (2)
lock = 0; (3)

}

Shared variable lock indicates whether the critical section is occupied

Still based on busy waiting
Does it solve the critical section problem?

What is the relation between …

memory barriers and a critical section?

busy waiting and Petersons algorithm?

bounded waiting and race condition?

Synchronization Concepts

This Lecture

Beyond Petersons Algorithm

Lamports Bakery Algorithm
Busy waiting
Instruction reordering

Synchronization Hardware

Memory barriers
Test and modify