CISC2005 Lab 06

Starting from:

~~$35~~

$29

1. Prerequisites

1. Successful installation of *nix terminal (e.g., WSL, cygwin) or a *nix operating system (e.g., Linux, Mac).

2. Successful installation of a C compiler, GCC is recommended.

3. Successful installation of a text editor, VIM or Emacs is recommended.

2. Exercises

When multiple threads or processes access shared resources (i.e., critical region or critical section), there is a possibility of race conditions or inconsistent behavior. For example, if two threads simultaneously try to modify a shared variable, the result of the operation may depend on the order in which the threads execute, which may lead to incorrect results.

In this exercise, students are required to complete the following codes to implement several basic operating system synchronization algorithms. For each program, students should capture screenshots of the successful execution, and answer the questions for the program. In the submission file, please attach the added code and execution screenshot in sequence.

Task:

Suppose that a shared resource can be accessed by several threads, please use a global variable “counter” to count the number of accesses to the resource.

Here is the sample code:

1 // Global variables

2 static long counter = 0;

3 void *thread(void *vargp) {

4 // Enter critical region

5 for (long i = 0; i < N_ITERATIONS; i++) {

6 /* Shared resource */

7 counter++;

8 }

9 // Leave critical region

10 return NULL;

11 }

Example 1: Critical region

This example shows what are the race condition and critical region.

12 #include <stdio.h>

13 #include <stdlib.h>

14 #include <pthread.h>

16 #define NUM_THREADS 2

17 #define N_ITERATIONS 10000000 // number of iterations

19 // Global variables

20 static volatile long counter = 0;

22 void *thread(void *vargp) {

24 // Enter critical region

25 for (long i = 0; i < N_ITERATIONS; i++) {

26 /* Shared resource */

27 counter++;

28 }

29 // Leave critical region

31 return NULL;

32 }

34 int main(int argc, char **argv) {

35 pthread_t tid1, tid2;

37 pthread_create(&tid1, NULL, thread, NULL);

38 pthread_create(&tid2, NULL, thread, NULL);

39 pthread_join(tid1, NULL);

40 pthread_join(tid2, NULL);

42 if (counter != (2 * N_ITERATIONS))

43 printf("Wrong! counter=%ld.\n", counter);

44 else

45 printf("Correct! counter=%ld.\n", counter);

47 return 0;

48 }

Code:

1. Download the sample code from UMMoodle (critical_region.c).

2. Compile the above C program and run several times. (Tips: use the following compile command.)

gcc critical_region.c -o critical_region -l pthread.

Question 1:

1.1 Why the counter value is "Wrong"?

1.2 What happens if the number of iterations is reduced?

Requirements:

1. Capture 2 screenshots of different outputs.

2. Answer Question 1.

Example 2: Alternation algorithm

In practice, we will implement mutual exclusion via some algorithms to synchronize access to shared resources, and the Alternation algorithm is the simplest method among them. Complete the code at the blank underline to implement the Alternation algorithm and answer questions.

Code:

1. Download the sample code from UMMoodle (alternation.c).

2. Compile the above C program and run several times. (Tips: use the following compile command.)

gcc alternation.c -o alternation -l pthread.

Incomplete code

1 #include <stdio.h>

2 #include <stdlib.h>

3 #include <pthread.h>

5 #define TRUE 1

6 #define NUM_THREADS 2

7 #define N_ITERATIONS 100000000

9 // Global variables

10 static volatile long counter = 0;

11 static volatile int turn = 1;

14 // Thread 1

15 void *thread_1(void *arg) {

16 while (TRUE) {

while (turn !=

??? ){

18 // Wait

19 }

21 // Enter critical region

22 for (long i = 0; i < N_ITERATIONS; i++)

23 counter++;

25 // Leave critical region

turn =

???

;

28 break;

29 }

31 pthread_exit(NULL);

32 }

34 // Thread 2

35 void *thread_2(void *arg) {

37 while (TRUE) {

while (turn !=

??? ){

39 // Wait

40 }

42 // Enter critical region

43 for (long i = 0; i < N_ITERATIONS; i++)

44 counter++;

turn =

???

;

46 // Leave critical region

48 break;

49 }

51 return NULL;

52 }

54 int main() {

55 pthread_t tid1, tid2;

57 pthread_create(&tid1, NULL, thread_1, NULL);

58 pthread_create(&tid2, NULL, thread_2, NULL);

59 pthread_join(tid1, NULL);

60 pthread_join(tid2, NULL);

62 printf("counter=%ld.\n", counter);

64 return 0;

65 }

Question 2:

2.1 Please complete the code for the alternation algorithm.

2.2 Why does it satisfy the mutual exclusion?

2.3 What are the drawbacks of the alternation algorithm?

Requirements:

1. Capture 1 screenshots of the successful execution.

2. Answer Question 2.

Example 3: Peterson’s algorithm

Peterson’s algorithm is a more flexible method. Complete the code at the blank underline to implement the Peterson’s algorithm and answer questions.

Code:

1. Download the sample code from UMMoodle (peterson.c).

2. Compile the above C program and run several times. (Tips: use the following compile command.)

gcc peterson.c -o peterson -l pthread.

Incomplete code

1 #include <stdio.h>

2 #include <stdlib.h>

3 #include <pthread.h>

5 #define ENTER 1

6 #define LEAVE 0

7 #define NUM_THREADS 2

8 #define N_ITERATIONS 10000000

10 // Global variables

11 static volatile long counter = 0;

12 static volatile int turn = 0;

13 static volatile int flag[NUM_THREADS] = {0, 0};

15 // Increment function

16 void *increment(void *arg) {

17 int thread_id = *(int*)arg;

19 flag[thread_id] = ENTER;

turn =

???

;

while (flag[

???

] && turn ==

??? ){

22 // Wait

23 }

25 // Enter critical region

26 for (long i = 0; i < N_ITERATIONS; i++) {

27 counter++;

28 }

30 // Leave critical section

31 flag[thread_id] = LEAVE;

33 return NULL;

34 }

36 int main() {

37 pthread_t threads[NUM_THREADS];

38 int thread_ids[NUM_THREADS];

40 // Create threads

41 for (int i = 0; i < NUM_THREADS; i++) {

42 thread_ids[i] = i;

43 pthread_create(&threads[i], NULL, increment, &thread_ids[i]);

44 }

46 // Wait for threads to finish

47 for (int i = 0; i < NUM_THREADS; i++) {

48 pthread_join(threads[i], NULL);

49 }

51 printf("counter=%ld.\n", counter);

53 return 0;

54 }

Question 3:

3.1 Please complete the code for the Peterson’s algorithm.

3.2 Why does it satisfy the mutual exclusion?

Requirements:

1. Capture 1 screenshots of the successful execution.

2. Answer Question 3.

Example 4: Lock

Locks allow threads or processes to acquire exclusive access to shared resources, ensuring that only one thread or process can access the shared resource at a time. This prevents race conditions and ensures the correctness of the program. This example shows how to implement a spinlock.

Code:

1. Download the sample code from UMMoodle (lock.c).

2. Test 2 lock algorithms. Do they both work?

1 /***********1st algorithm*******/

2 while (*lock) {

3 // Wait

4 }

5 *lock = TRUE;

6 /*******************************/

8 /*********2nd algorithm*********/

9 while (test_and_set(lock, TRUE) == TRUE) {

10 // Wait

11 }

12 /*******************************/

3. Compile the above C program and run several times. (Tips: use the following compile command.)

gcc lock.c -o lock -l pthread.

Question 4:

4.1 What's the difference between the 2 lock algorithms in the "acquire" function?

4.2 Does the 1st algorithm work? Why?

4.3 Does the 2nd algorithm work? How does the "test and set" operation work?

Requirements:

1. Capture 2 screenshots of the 2 lock algorithms.

2. Answer Question 4.