$29
CISC2005 Lab 07
1. Prerequisites
• Successful installation of *nix terminal (e.g., WSL, cygwin) or a *nix operating system (e.g., Linux, Mac).
• Successful installation of a C compiler, GCC is recommended.
You can also use an online c compiler: https://www.onlinegdb.com/online_c_compiler
• Successful installation of a text editor, VIM or Emacs is recommended.
2. Exercises
Semaphore is a synchronization tool that is used to control access to a shared resource in a concurrent system. There are two types of semaphores: mutex semaphore and counting semaphore. A binary semaphore can only take on two values, 0 and 1, and is typically used for mutual exclusion. A counting semaphore, on the other hand, can take on a range of non-negative values and is typically used to control access to a finite pool of resources.
In a *nix operating system (e.g., Linux, Mac), the <semaphore.h> header defines the sem_t type, used in performing semaphore operations. Here are some important functions about semaphore operations.
In this exercise, students are required to complete missing codes ( ??? ) to implement several basic synchronization algorithms using semaphore. 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.
Example 1: Mutex semaphore
In this example, we use a global variable “counter” and a semaphore variable “s” to count the number of accesses to a shared resource. Please use sem_init, sem_wait, and sem_post to complete the following code to correctly count accesses.
1. // Global variables
2. static volatile long counter = 0;
3. sem_t s; // Semaphore variable
4.
5. void *increment(void *vargp) {
6. // Enter critical region
7. for (long i = 0; i < N_ITERATIONS; i++) {
8. // Block on a semaphore count
9. ??? ; // P(S)
10. // Shared resource
11. counter++;
12. // Increment a semaphore
13. ??? ; // V(S)
14. }
15. // Leave critical region
16. return NULL;
17. }
18.
19. int main(int argc, char **argv) {
20. // Initialize the semaphore
21. sem_init(&s, 0, ??? );
22. // Create threads
23. pthread_t threads[NUM_THREADS];
24. // Create threads
25. for (int i = 0; i < NUM_THREADS; i++) {
26. pthread_create(&threads[i], NULL, increment, NULL);
27. }
28. printf("Create %d threads.\n", NUM_THREADS);
29. // Wait for threads to finish
30. for (int i = 0; i < NUM_THREADS; i++) {
31. pthread_join(threads[i], NULL);
32. }
33. printf("counter=%ld.\n", counter);
34. // Destroy the semaphore
35. sem_destroy(&s);
36. return 0;
37. }
Code:
1. Download the sample code from UMMoodle (example1.c).
2. Compile the above C program and execute. (Tips: use the following compile command.)
Question 1:
1.1 Please complete the code in example1.c.
1.2 How does the semaphore “s” change as the program runs?
Requirements:
1. Capture 1 screenshots of the successful execution.
2. Answer Question 1.
Example 2: Counting semaphore
Imagine the following scenario: there are two workers serving 5 customers, and each worker can only serve one customer at a time. Complete the code in example 2 to simulate this scenario.
1. // Number of customers
2. int NUM_CUSTOMERS = 5;
3.
4. sem_t s; // Semaphore variable
5.
6. // Simulate the process of service
7. void *get_service(void *arg)
8. {
9. int id = *((int*)arg);
10. // Block on a semaphore count
11. ??? ; // P(S)
12. // Enter critical region
13. printf("Customer [%d] is getting service.\n", id);
14. sleep(2);
15. printf("Customer [%d] has left.\n", id);
16. // Leave critical region
17. // Increment a semaphore
18. ??? ; // V(S)
19. return 0;
20. }
21.
22. int main()
23. {
24. // Initialize the semaphore
25. sem_init(&s, 0, ??? );
26. // Create threads
27. pthread_t threads[NUM_CUSTOMERS];
28. int thread_ids[NUM_CUSTOMERS];
29. printf("Create %d threads.\n", NUM_CUSTOMERS);
30. for (int i = 0; i < NUM_CUSTOMERS; i++) {
31. thread_ids[i] = i + 1;
32. pthread_create(&threads[i], NULL, get_service, &thread_ids[i]);
33. }
34. // Wait for threads to finish
35. for (int i = 0; i < NUM_CUSTOMERS; i++) {
36. pthread_join(threads[i], NULL);
37. }
38. // Destroy the semaphore
39. sem_destroy(&s);
40. return 0;
41. }
Code:
1. Download the sample code from UMMoodle (example2.c).
2. Compile the above C program and execute. (Tips: use the following compile command.)
Question 2:
2.1 Please complete the code in example2.c.
2.2 How does the semaphore “s” change as the program runs?
Requirements:
1. Capture 1 screenshots of the successful execution.
2. Answer Question 2.
Example 3: Possible deadlocks with semaphores
Deadlock is the permanent and unresolvable blocking of two or more threads that results from each waiting on the other. The following code in example3.c provides a simple illustration of how deadlock can happen. There are two threads, running the first and second functions. The code for first tries to acquire semaphore “A” before “B”, while second acquires them in the opposite order. Figure 1 shows the state model for this example. Please execute example3 and explain why the deadlock occurs.
Figure 1. State model for example 3.
Example3 code:
1. /* struct contains shared semaphores */
2. typedef struct {
3. sem_t A;
4. sem_t B;
5. } SEMAPHORE;
6.
7. void *first (void * args)
8. {
9. SEMAPHORE *sem = (SEMAPHORE *) args;
10. /* Acquire "A" before "B" */
11. printf("Job started in the first thread.\n");
12. sem_wait(&sem->A);
13. sleep(1);
14. while (-1 == sem_trywait(&sem->B))
15. {
16. printf("The first thread has acquired 'A' and waits for 'B'.\n");
17. sleep(1);
18. }
19. /* other code here */
20. return NULL;
21. }
22.
23. void *second (void * args)
24. {
25. SEMAPHORE *sem = (SEMAPHORE *) args;
26. /* Acquire "B" before "A" */
27. printf("Job started in the second thread.\n");
28. sem_wait(&sem->B);
29. sleep(1);
30. while (-1 == sem_trywait(&sem->A))
31. {
32. printf("The second thread has acquired 'B' and waits for 'A'.\n");
33. sleep(1);
34. }
35. /* other code here */
36. return NULL;
37. }
Code:
1. Download the sample code from UMMoodle (example3.c).
2. Compile the above C program and execute. (Tips: use the following compile command.)
Question 3:
Why does the deadlock occur in example 3?
Requirements:
1. Capture 1 screenshots of the successful execution.
2. Answer Question 3.
Example 4: Bounded Buffer with semaphores
This example provides an implementation of Bounded Buffer with semaphores.
1. // Global variables
2. buffer_item START_NUMBER = 0;
3. buffer_item buffer[BUFFER_SIZE];
4. sem_t mutex;
5. sem_t empty;
6. sem_t full;
7.
8. void initialization(){
9. sem_init(&mutex, 0, 1);
10. sem_init(&full, 0, BUFFER_SIZE);
11. sem_init(&empty, 0, 0);
12. }
13.
14. void *producer(void *arg)
15. {
16. int thread_id = *(int*)arg;
17. buffer_item item;
18.
19. while(TRUE) {
20. sleep(1);
21. sem_wait(&full);
22. sem_wait(&mutex);
23.
24. item = START_NUMBER++;
25. insert_item(item);
26.
27. printf("Producer %d produced %d \n", thread_id, item);
28.
29. sem_post(&mutex);
30. sem_post(&empty);
31. }
32.
33. return NULL;
34. }
35.
36. void *consumer(void *arg)
37. {
38. int thread_id = *(int*)arg;
39. buffer_item item;
40.
41. while(TRUE){
42. sleep(1);
43. sem_wait(&empty);
44. sem_wait(&mutex);
45.
46. remove_item(&item);
47. printf("Consumer %d consumed %d \n", thread_id, item);
48.
49. sem_post(&mutex);
50. sem_post(&full);
51. }
52.
53. return NULL;
54. }
Code:
1. Download the sample code from UMMoodle (example4.c).
2. Compile the above C program and execute. (Tips: use the following compile command.)
Requirements:
1. Capture 1 screenshots of the successful execution.
