代写program编程、代写c++代写程序、C++编程语言调试

日期：2020-11-30 11:16

Answer all the questions below. Once you are finished, print the code of

Question 3 on paper and submit the paper at the start of the lecture on the

due date. Put your name (in English) and student ID number on the paper.

Also add to your paper a picture of your program running.

In addition, upload the C file (only the C file itself, nothing else, no

ZIP file) for Question 3 on iSpace.

Late homework assignments will not be accepted, unless you have a valid

written excuse (medical, etc.). You must do this assignment alone. No

team work or "talking with your friends" will be accepted. No copying from

the Internet. Cheating means zero.

0) The goal of this homework assignment is to use Szymanski’s

synchronization algorithm to prevent race conditions in a multi-threaded

program.

Below is the code of a small C program that creates 26 threads (in addition

to the main thread), where each thread either increases or decreases a

shared variable called sum. Every time a thread modifies the shared sum

variable (up or down) then that thread sleeps for a little while (this is

only necessary to make race conditions move obvious) and then the thread

also prints its name (a single uppercase letter) on the screen. Since the

number 26 of threads is even, the sum variable should be zero at the end of

the program, unless a race condition occurs while the program is running.

The code for Microsoft Windows:

/************************************************************/

#include <stdio.h>

#include <windows.h>

#include <stdlib.h>

#include <time.h>

#define N 26 // Total number of threads (in addition to main thread).

#define M 10 // Number of loop iterations per thread.

int sum = 0; // Data shared by all the threads.

// The function executed by each thread.

DWORD WINAPI runner(LPVOID param) {

int i = *(int *)param; // This thread’s ID number.

int m;

for(m = 0; m < M; m++) {

int s = sum;

// Even threads increase s, odd threads decrease s.

if(i % 2 == 0) {

s++;

} else {

s--;

}

// Sleep a small random amount of time. Do not remove this code.

Sleep(100ULL * rand() / RAND_MAX);

sum = s;

printf("%c", ’A’ + i); // Print this thread’s ID number as a letter.

fflush(stdout);

}

return 0; // Thread dies.

}

int main(void) {

HANDLE tid[N]; // Thread ID numbers.

int param[N]; // One parameter for each thread.

int i;

// Create N threads. Each thread executes the runner function with

// i as argument.

for(i = 0; i < N; i++) {

param[i] = i;

tid[i] = CreateThread(NULL, 0, runner, &param[i], 0, NULL);

}

// Wait for N threads to finish.

for(i = 0; i < N; i++) {

WaitForSingleObject(tid[i], INFINITE);

CloseHandle(tid[i]);

}

printf("\nResult is %d\n", sum);

return 0;

}

/************************************************************/

and the code for Mac OS X or Unix (for this program to work you will need

to tell your C compiler to link your program with the pthread library

available on your computer):

/************************************************************/

#include <stdio.h>

#include <pthread.h>

#include <stdlib.h>

#include <time.h>

#define N 26 // Total number of threads (in addition to main thread).

#define M 10 // Number of loop iterations per thread.

int sum = 0; // Data shared by all the threads.

// The function executed by each thread.

void *runner(void *param) {

int i = *(int *)param; // This thread’s ID number.

int m;

for(m = 0; m < M; m++) {

int s = sum;

// Even threads increase s, odd threads decrease s.

if(i % 2 == 0) {

s++;

} else {

s--;

}

// Sleep a small random amount of time. Do not remove this code.

struct timespec delay;

delay.tv_sec = 0;

delay.tv_nsec = 100000000ULL * rand() / RAND_MAX;

nanosleep(&delay, NULL);

sum = s;

printf("%c", ’A’ + i); // Print this thread’s ID number as a letter.

fflush(stdout);

}

return 0; // Thread dies.

}

int main(void) {

pthread_t tid[N]; // Thread ID numbers.

int param[N]; // One parameter for each thread.

int i;

// Create N threads. Each thread executes the runner function with

// i as argument.

for(i = 0; i < N; i++) {

param[i] = i;

pthread_create(&tid[i], NULL, runner, &param[i]);

}

// Wait for N threads to finish.

for(i = 0; i < N; i++) {

pthread_join(tid[i], NULL);

}

printf("\nResult is %d\n", sum);

return 0;

}

/************************************************************/

Compile this program on your computer and make sure you can execute it. If

you have any problem compiling or executing this program then contact me

immediately for help!

Execute the program multiple times and check that the result of the program

is not zero and that the result of the program randomly changes every time

you run the program again. This is a clear sign that this program contains

at least one race condition.

1) Change the value of the N macro (the number of threads) to be 2 and the

value of the M macro (the number of loop iterations) to be 100. Compile

and execute the program again, and check that the result of the program is

still not zero and still randomly changes every time you run the program

again. This means that you still have at least one race condition in the

program even when the program has only two threads (in addition to the main

thread).

Then add the following comment in the program:

// The Critical Section starts right below.

ON A LINE BY ITSELF right BEFORE the start of every critical section for

the variable sum. Also add the following comment in the program:

// The Critical Section ends right above.

ON A LINE BY ITSELF right AFTER the end of every critical section for the

variable sum. (Do not worry about any critical section or any race

condition for the printf function.)

2) Szymanski’s synchronization algorithm works as follows: any process that

wants to enter the critical section must first enter a "waiting room" by

going through an entrance door. If multiple processes want to enter the

critical section at the same time then all these processes can enter the

waiting room, that’s okay.

Once all the processes that want to enter the critical section are inside

the waiting room (no other process wants to go through the entrance door

any more), the entrance door of the waiting room closes automatically. The

processes which are inside the waiting room are then allowed to enter the

critical section one after the other, in order of increasing PID (process

identification number).

After all the processes in the waiting room have gone through the critical

section one by one (so the waiting room is now empty), the entrance door of

the waiting room opens again automatically, which then allows another group

of processes to enter the waiting room by going through the entrance door.

For the case of two processes only (Process 0 and Process 1), the details

of the algorithm are as follows:

- the two processes share an array: int flag[N];

(in addition to the sum variable, which remains shared), where flag[0]

must be initially 0 and is only modified by Process 0 and flag[1] must be

initially 0 too and is only modified by Process 1;

- the two array elements flag[0] and flag[1] can have the following values:

- 0, which means that the corresponding process does not want to enter a

critical section (the process is doing something else);

- 1, which means that the corresponding process wants to go through the

entrance door to enter the waiting room so that it can later enter a

critical section;

- 2, which means that the corresponding process is inside the waiting

room, but is waiting for another process to come inside the waiting

room too, and is also waiting for the entrance door of the waiting room

to close;

- 3, which means that the corresponding process is currently going

through the entrance door to go inside the waiting room;

- 4, which means that the corresponding process is inside the waiting

room, the entrance door of the waiting room is closed, and that the

process is ready to enter the critical section;

- the entrance door of the waiting room automatically closes by itself when

both flag[0] and flag[1] are different from 1;

- the entrance door of the waiting room automatically opens by itself when

both flag[0] and flag[1] are different from 4;

- the code of the algorithm itself is as follows (where i is the PID of the

process running this code and j is the PID of the other process):

// Pi wants to enter the waiting room:

flag[i] = 1;

// Pi waits to go through the entrance door. Pi has to wait either

// because:

// - the door is open but Pj is going through the entrance door right

// now and Pj does not know yet that Pi wants to enter too (flag[j]

// is 3 and not 2);

// - the door is closed because Pj is inside the critical section

// (flag[j] is 4).

while(flag[j] >= 3) // Atomic test.

;

// Pi goes through the entrance door:

flag[i] = 3;

// Check whether Pj wants to enter the waiting room too:

if(flag[j] == 1) {

// then Pi starts waiting inside the waiting room:

flag[i] = 2;

// until Pj comes inside the waiting room too and the entrance

// door closes (then flag[j] becomes 4 and Pi then stops waiting):

while(flag[j] != 4)

;

}

// If Pi and Pj are both inside the waiting room, and Pi entered

// first and was waiting for Pj to enter (flag[i] was 2), and then

// Pj entered too, then Pi stopped waiting and is now ready to enter

// the critical section too (flag[i] changes from 2 to 4).

// If Pi and Pj are both inside the waiting room, and Pj entered

// first and was waiting for Pi to enter (flag[j] is 2), and then Pi

// entered too, then Pi is immediately ready to enter the critical

// section (flag[i] changes from 3 to 4); this in turn will later

// make Pj stop waiting for Pi to enter and will make Pj ready to

// enter the critical section too.

// If Pi and Pj are both inside the waiting room, and Pi and Pj

// entered the waiting room at the same time then flag[i] and

// flag[j] are both 3 and then Pi is immediately ready to enter the

// critical section (flag[i] changes from 3 to 4) and the same thing

// happens with Pj.

// If Pi is alone inside the waiting room (Pj is outside) then it is

// immediately ready to enter the critical section (flag[i] changes

// from 3 to 4).

// In all cases, flag[i] becomes 4 (that’s also when the entrance door

// automatically closes).

flag[i] = 4;

// If Pj has a PID lower than the PID of Pi, and Pi and Pj are both

// inside the waiting room, then Pj is allowed to enter the critical

// section first and Pi then waits until Pj is finished with the

// critical section (when flag[j] will again become 0 and then maybe 1

// again, but never 2 or above 2 because the entrance door is still

// closed):

if(j < i) {

while(flag[j] >= 2) // Atomic test.

;

}

/* Code of the Critical Section goes here */

// Pi is finished with the critical section.

// If Pj has a PID higher then the PID of Pi and Pj is still inside

// the waiting room and Pj has not yet noticed that the entrance door

// of the waiting room has closed (flag[j] is still 2 or 3), then Pi

// needs to wait until Pj notices that the door has closed and is

// ready to enter the critical section too (when flag[j] changes to 4).

// This is necessary to ensure that Pj knows that the entrance door is

// closed, which in turn ensures that Pi cannot immediately enter the

// waiting room again before the waiting room becomes empty.

if(j > i) {

while(flag[j] == 3 || flag[j] == 2) // Order matters!

;

}

// Pi goes back to doing something else, and Pj can then enter the

// critical section if Pj was waiting inside the waiting room.

// If the waiting room was empty then this automatically reopens the

// entrance door.

flag[i] = 0;

This algorithm provides mutual exclusion because all the processes inside

the waiting room always enter the critical section one after the other in

the order of increasing PID (this is guaranteed by the "if(j < i)" test).

This algorithm provides progress because, if Pj is doing something else

(flag[j] is always 0), all the tests of the "while" loops are false and Pi

never gets stuck waiting for Pj (the "while(flag[j] != 4)" loop is not

executed at all because it is inside an "if(flag[j] == 1)" test which is

always false).

This algorithm provides bounded waiting because, if Pi is in the waiting

room and Pj is in the critical section, then this means that the entrance

door of the waiting room must be closed. If Pj then leaves the critical

section and immediately tries to re-enter the waiting room, Pj will find

that the entrance door is closed and will have to wait outside in front of

the entrance door (flag[j] is 1 but cannot become 3). This will then

always allow Pi to enter the critical section.

Here is also an explanation of all the different possible combinations of

values for flag[i] and flag[j]:

- flag is {0, 0}: both Pi and Pj are doing something else.

- flag is {0, 1}: Pi is doing something else; Pj wants to enter the waiting

room;

- flag is {0, 2}: Pi is doing something else; Pj is inside the waiting room

waiting for Pi to enter the waiting room. This is impossible because

flag[j] becomes 2 only when flag[i] is 1 (if this case were possible then

the algorithm would not be providing progress).

- flag is {0, 3}: Pi is doing something else; Pj is going through the

entrance door.

- flag is {0, 4}: Pi is doing something else; Pj is ready to enter the

critical section (this is possible because the algorithm provides

progress).

- flag is {1, 0}: Pi wants to enter the waiting room; Pj is doing something

else.

- flag is {1, 1}: Pi and Pj both want to enter the waiting room.

- flag is {1, 2}: Pi wants to enter the waiting room; Pj is waiting inside

the waiting room for Pi to enter the waiting room too (later when Pi

enters the waiting room, flag[i] will become 4 and Pj will then stop

waiting).

- flag is {1, 3}: Pi wants to enter the waiting room; Pj is going through

the entrance door of the waiting room (flag[j] will then become 2 and Pj

will then start waiting for Pi to enter the waiting room too).

- flag is {1, 4}: Pi wants to enter the waiting room; Pj is ready to enter

the critical section (the entrance door is closed and Pi will not be

allowed to enter the waiting room until Pj is finished with the critical

section, otherwise the algorithm would not guarantee bounded waiting for Pj).

- flag is {2, 0}: Pi is inside the waiting room waiting for Pj to enter the

waiting room; Pj is doing something else. This is impossible because

flag[i] becomes 2 only when flag[j] is 1 (if this case were possible then

the algorithm would not be providing progress).

- flag is {2, 1}: Pi is inside the waiting room waiting for Pj to enter the

waiting room; Pj wants to enter the waiting room too (later when Pj

enters the waiting room, flag[j] will become 4 and Pi will then stop

waiting).

- flag is {2, 2}: Pi is inside the waiting room waiting for Pj to enter the

waiting room; Pj is inside the waiting room waiting for Pi to enter the

waiting room. This is impossible because the last process among Pi and

Pj to start entering the room (the last process to change its flag from 1

to 3) then cannot have the test "if(flag[j] == 1)" be true and thus its

flag then cannot change from 3 to 2.

- flag is {2, 3}: Pi is inside the waiting room waiting for Pj to enter the

waiting room too; Pj is going through the entrance door of the waiting

room (flag[j] will then become 4 and Pi will then stop waiting).

- flag is {2, 4}: Pi is inside the waiting room waiting for Pj to enter the

waiting room too; Pj is ready to enter the critical section (Pi will then

soon stop waiting and become ready to enter the critical section too).

- flag is {3, 0}: Pi is going through the entrance door; Pj is doing

something else.

- flag is {3, 1}: Pi is going through the entrance door; Pj wants to enter

the waiting room (flag[i] will then become 2 and Pi will then start

waiting for Pj to enter the waiting room).

- flag is {3, 2}: Pi is going through the entrance door of the waiting

room; Pj is inside the waiting room waiting for Pi to enter the waiting

room too (flag[i] will then become 4 and Pj will then stop waiting).

- flag is {3, 3}: Pi and Pj both are going through the entrance door of the

waiting room at the same time (flag[i] and flag[j] will then both become 4).

- flag is {3, 4}: Pi is going through the entrance door; Pj is ready to

enter the critical section (flag[i] will then become 4 soon too).

- flag is {4, 0}: Pi is ready to enter the critical section; Pj is doing

something else (this is possible because the algorithm provides

progress).

- flag is {4, 1}: Pi is ready to enter the critical section; Pj wants to

enter the waiting room (the entrance door is closed and Pj will not be

allowed to enter the waiting room until Pi is finished with the critical

section, otherwise the algorithm would not guarantee bounded waiting for Pi).

- flag is {4, 2}: Pi is ready to enter the critical section; Pj is inside

the waiting room waiting for Pi to enter the waiting room too (Pj will then

soon stop waiting and become ready to enter the critical section too).

- flag is {4, 3}: Pi is ready to enter the critical section; Pj is going

through the entrance door (flag[j] will then become 4 too).

- flag is {4, 4}: Pi and Pj are both ready to enter the critical section:

the process with the lowest PID will then enter the critical section

first and then later change its flag back to 0, which will then allow the

other process to enter the critical section.

Add Szymanski’s synchronization algorithm for two processes to the program

of the previous question (this program is using threads, not processes, but

the algorithm is exactly the same).

Note: you are not allowed to change or delete any of the code in the

program. You are only allowed to add to the program the code above for

Szymanski’s synchronization algorithm.

Execute the program multiple times and check that the result of the program

is now always zero. This is then a good sign that the threads in your

program are now correctly synchronized.

3) Change the value of the N macro (the number of threads) to be 26 again

and the value of the M macro (the number of loop iterations) to be 10 again.

Implement Szymanski’s algorithm for more than two processes. Look for

example at https://en.wikipedia.org/wiki/Szyma%C5%84ski%27s_algorithm for

the details.

Warning: be aware that Wikipedia uses "await all" and "await any" loops

instead of "while" loops or "for" loops like in C, so make sure you write

these loops correctly!

Warning: make sure that all the data necessary for Szymanski’s algorithm is

correctly initialized to be 0.

Warning: do not use any "goto" statements anywhere in your code, or you

will lose points.

Use atomic tests like in the code above as much as possible (otherwise you

might get race conditions again).

Execute the program multiple times and check that the result of the program

is still always zero.

After you are finished, you should also notice that the program runs much

more slowly now: that’s because Szymanski’s algorithm uses a lot of

busy-waiting, so it is computationally very intensive. This means that in

practice Szymanski’s algorithm is not a good choice for preventing race

conditions. That’s why microprocessors usually provided atomic hardware

instructions such as test_and_set for synchronization.

Here are a few extra instructions:

- Give meaningful names to your variables so we can easily know what each

variable is used for in your program.

- Put comments in your code (in English!) to explain WHAT your code is

doing and also to explain HOW your program is doing it.

- Make sure all your code is properly indented (formatted). Your code

must be beautiful to read.

- Include a picture of your program running, even if your program is not

completely finished.

Failure to follow these instructions will result in you losing points.

The End!