L1-User Threads Lab Project PDF 2024

Operating Systems Lab Project: User-level threads Index 1. Objectives................................................................................................................................................. 2 2. Introduction..................................

Operating Systems Lab Project: User-level threads Index 1. Objectives................................................................................................................................................. 2 2. Introduction............................................................................................................................................... 2 3. The execution context...............................................................................................................................4 3.1 Digression: stack management (on x86) during execution................................................................4 3.1.1 A little bit of x86 assembler (GNU / AT&T syntax).....................................................................5 3.1.2 Function calls (x86).................................................................................................................... 6 3.1.3 Call conventions........................................................................................................................ 7 3.2 Back on route: toward user threads...................................................................................................9 3.2.1 Example...................................................................................................................................10 Exercise..................................................................................................... 11 3.2.2 Almost there............................................................................................................................. 11 Exercise..................................................................................................... 13 4. Cooperative threads................................................................................................................................ 13 Exercise..................................................................................................... 14 4.1 Implementing a cooperative threads library..................................................................................... 15 Exercise..................................................................................................... 16 4.1.1 Thread queue.......................................................................................................................... 16 Exercise..................................................................................................... 17 4.1.2 Scheduler prototype................................................................................................................. 17 4.2 Come and join the scheduling loop.................................................................................................. 18 Exercise..................................................................................................... 19 4.3 Yield to the scheduler...................................................................................................................... 20 4.4 Thread sleep.................................................................................................................................... 20 Exercise..................................................................................................... 20 4.5 Cancellation points.......................................................................................................................... 20 Exercise..................................................................................................... 21 4.6 Preemption using a timer................................................................................................................. 21 Exercise..................................................................................................... 22 5. Synchronization primitives......................................................................................................................22 Exercise................................................................................................... 24 Exercise................................................................................................... 25 6. Classic synchronization problems...........................................................................................................25 6.1 Dining philosophers......................................................................................................................... 25 6.2 Producer consumer.......................................................................................................................... 27 6.3 Producer consumer with condition variable.....................................................................................28 6.4 Sleeping barber............................................................................................................................... 29 6.5 Readers and writers (solution favorable to readers)........................................................................31 6.6 Readers and writers (solution favorable to writers).......................................................................... 32 6.7 Readers and writers (fair solution)...................................................................................................34 Lab Project: User-level threads (Operating Systems, Amos Brocco) V8 31/07/24  2/36 1. Objectives Modern operating systems are “complex beasts” made of millions of lines of code. Understanding the inner- workings of an operating system by studying the source code is a daunting task. Experimenting with a real kernel is also a time consuming activity. The main problem is that kernel code is typically not developed for teaching purposes, changes are complicated, and debugging at such a low-level is not easy. Since we have (unfortunately) very little time to try to apply the concepts we see in the class in a “real” situation, working inside an existing kernel is not an option. Accordingly, we will approach the problem from a higher level of abstraction: instead of working at the kernel level, we will work on top of an existing kernel. Can we study and experiment with the main concepts of an operating system by working outside the kernel? Yes, if we limit ourselves to just some of the topics found in the course. In this regard, we will focus on task/thread management, scheduling algorithms, and synchronization mechanisms (IPC) with the goal of implementing a thread library. As we saw during the class processes and threads are important abstractions which enable multiple programs to execute concurrently on our computers. Processes represent instances of running programs, and can be viewed as containers which keep track of the resources needed and used by the program. Inside processes, the execution of machine code might simultaneously take different paths, called threads. Each thread is thus an active entity whose execution state is managed by a scheduler. As we saw in the class there exist two ways for implementing threads: either at kernel level, or at user level. Modern operating systems like GNU/Linux or Windows already implement threads, thread scheduling, and thread synchronization primitives at kernel level. Hence, to make things a little bit easier (and perhaps more interesting), the goal of this tutorial is to implement such functionality at the user-level, by developing a simple user-level thread library in C (complete with a scheduler, preemptive behavior, and synchronization mechanisms). This piece of software will behave very similar to a kernel, but will spare us from dealing with the hardware and similar low level concerns: we will learn how to represent the execution context of a thread, how to save and restore that information, how to execute multiple threads “at the same time” (using pseudo-parallelism and preemption), how to design our own scheduler, and how to implement synchronization primitives. As a prerequisite you need to install a C compiler (typically gcc, which is also available on Windows through Cygwin) and a text (code) editor of your choice. The code presented here is targeted to a GNU/Linux system, however it should compile with no issues on POSIX compatible systems (for example, Apple OSX) too. Because technical discussions on specific machine instructions refer to Intel x86 and AMD64, it is preferable (but not mandatory) to work on such architectures. In order to compile your code you will have to specify the compiler options -std=gnu11 and the linker option -lm. In this tutorial, the symbol indicates some practical exercise / problem that you need to solve before continuing to the next step. The estimated time to complete an exercise is indicated next to the symbol. To complete the whole tutorial (reading and completing the exercises), which will take approximately 35 class hours (~26 effective hours), you might need some additional information, such as man pages or online references: feel free to use all the information you need, as the goal of this exercise is to really get a good grasp of some fundamental aspects of an operating system. Do not forget to implement tests for your code (even assert fulfills this purpose!), and if you have any doubt or question ask your lecturer! 2. Introduction Now that we set our goal (that is, implement a user-level thread library)... where do we start? At first glance, we might think of each thread as being some kind of procedure that executes in parallel with other procedures. Consider for example the following code: 1.void thread1() { Lab Project: User-level threads (Operating Systems, Amos Brocco) V8 31/07/24  3/36 2. process(take()); 3.} 4. 5.void thread2() { 6. show_progress(); 7.} 8. 9.void main() { 10. while(1) { 11. thread1(); 12. thread2(); 13. } 14. } We assume that take returns a data unit to be processes (from a global pool), process does something on this data, and show_progress shows a message to the user indicating the overall progress of the program. The main procedure acts as a scheduler, allowing each thread to be executed. Is it a general and valid solution? It could be, apparently. Execution “bounces” back and forth between thread1 and thread2 like in a pseudo-parallel system, but what if the body of the thread1 procedure contains a loop such as: 1.void thread1() { 2. for(int i=0; icurrent_item); 11. } while (tp->state != __BTHREAD_READY); 12. // Restore context or setup stack and perform first call 13. if (tp->stack) { 14. restore_context(tp->context); 15. } else { 16. tp->stack = (uintptr_t) malloc(sizeof(char) * STACK_SIZE); 17. uintptr_t target = tp->stack + STACK_SIZE - 1; 18. #if __APPLE__ || __arm__ || __aarch64__ 19. // Align the stack at 16 bytes 20. target -= (target % 16); 21. #endif 22. #if __aarch64__ 23. // We need to store the value of tp in a register, and then restore it after 24. // changing the stack pointer 25. asm __volatile__("mov x1, %0" :: "r"(tp) : "x1"); 26. asm __volatile__("mov sp, %0" :: "r"((uintptr_t) target) : "x1"); 27. asm __volatile__("mov %0, x1" : "=r"(tp) ); 28. #elif __arm__ 29. asm __volatile__("mov %%sp, %0" :: "r"((uintptr_t) target)); 30. #elif __x86_64__ 31. asm __volatile__("movq %0, %%rsp" :: "r"((uintptr_t) target)); 32. #else 33. asm __volatile__("movl %0, %%esp" :: "r"((uintptr_t) target)); 34. #endif 35. bthread_exit(tp->body(tp->arg)); 36. } 37. 38. } First, the current_item pointer is reset to point to the start of the queue: this step is important as we need to ensure that we always point to a valid element. Next, the scheduler's context is saved: this allows for returning to the scheduler by simply restoring its context. The scheduling loop cycles through all threads until one in the __BTHREAD_READY state is found. Please note that each time the loop is repeated we move the current_item pointer one position forward. Once a suitable thread has been found we check if its stack has already been initialized, if so we restore the thread's context. Otherwise we setup a new stack (allocating memory on the heap!) and, using a little bit of assembler, we change the stack pointer register. Finally, we call the thread's routing (wrapping it inside bthread_exit to ensure that the thread cannot escape). Did you notice that there is no cushion, in contrast to the "hard-coded" example? The answer is simple: our first idea for creating separate stacks was more of a "hack" than a proper solution, and would prevent us from dynamically create and destroy a large number of threads (since we would not be able to recover already allocated stack space). Exercise: Implement the aforementioned scheduler methods (the prototypes for “public” methods go into bthread.h, whereas all private prototypes and the implementation goes into bthread_private.h and bthread.c). Add code to handle zombie threads in bthread_join ( 180 min ) Lab Project: User-level threads (Operating Systems, Amos Brocco) V8 31/07/24  20/36 4.3 Yield to the scheduler In our current implementation threads must explicitly yield to the scheduler (because preemption is not yet available): a good way to ensure periodical yields is to implement and use a yielding printf variant using this simple macro: 1.#define bthread_printf(...) \ 2. printf(__VA_ARGS__); \ 3. bthread_yield(); 4.4 Thread sleep Threads might decide to sleep for a while using the following procedure: 1.void bthread_sleep(double ms); The ms parameter specifies the number of milliseconds the thread must sleep. To implement sleeping we must add a new field in the thread structure: 1.double wake_up_time; When calling bthread_sleep the state of the thread is set to __BTHREAD_SLEEPING and then the thread must yield to the scheduler. The wake up time is computed from the current time, obtained using: 1.double get_current_time_millis() 2.{ 3. struct timeval tv; 4. gettimeofday(&tv, NULL); 5. return (tv.tv_sec) * 1000 + (tv.tv_usec) / 1000 ; 6.} Each time the thread is considered for execution the scheduler must first check if it's sleeping: in that situation the scheduler compares the current time with the wake up time and if necessary changes the state to __BTHREAD_READY to enable execution. Exercise: Implement and test bthread_sleep. ( 45 min ) 4.5 Cancellation points As we saw in the class, a thread can also request cancellation of another thread: cancellation happens as soon as the thread receiving the request calls testcancel. To implement cancellation points in our library we need to keep track of cancellation requests by adding a flag to the thread structure which will be initialized to 0 and set to 1 when someone ask for cancellation: 1. int cancel_req; Cancellation (through bthread_exit) happens when the recipient thread executes bthread_testcancel. The return value of a cancelled thread is -1. The prototypes of these methods are: 1.int bthread_cancel(bthread_t bthread); 2. 3.void bthread_testcancel(void); Lab Project: User-level threads (Operating Systems, Amos Brocco) V8 31/07/24  21/36 Exercise: Implement and test bthread_cancel and bthread_testcancel. ( 45 min ) 4.6 Preemption using a timer Preemption prevents a thread from never releasing control to the scheduler (through bthread_yield), and can be implemented by means of a timer signal that periodically interrupts the executing thread and returns control to the scheduler. To set such a timer we employ setitimer: 1.static void bthread_setup_timer() 2.{ 3. static bool initialized = false; 4. 5. if (!initialized) { 6. signal(SIGVTALRM, (void (*)()) bthread_yield); 7. struct itimerval time; 8. time.it_interval.tv_sec = 0; 9. time.it_interval.tv_usec = QUANTUM_USEC; 10. time.it_value.tv_sec = 0; 11. time.it_value.tv_usec = QUANTUM_USEC; 12. initialized = true; 13. setitimer(ITIMER_VIRTUAL, &time, NULL); 14. } 15. } The length of the quantum (in microseconds, a millionth of a second) is defined by the macro QUANTUM_USEC. Each time the alarm fires a SIGVTALRM is sent to the process and the bthread_yield procedure is called. Note: if the above solution does not work on your system replace ITIMER_VIRTUAL with ITIMER_REAL. The signal handler executes on the current thread's stack, hence bthread__yield will save the correct execution context. Preemption can also cause some issues in our library. For example, if the scheduler is preempted we might generate a race condition. To avoid this problem we to define two “private” procedures to temporarily block/unblock the timer signal (using sigprocmask): 1.void bthread_begin_atomic_execution(); 2.void bthread_end_atomic_execution(); Timer signals must be enabled when thread execution is started/resumed but must be blocked prior to any context save (sigsetjmp), for example during bthread__yield. These procedures can be called from threads (which could be dangerous) but can also provide some initial low-level atomicity (useful for implementing synchronization primitives). Finally, to ensure that access to the console does not end up in a deadlock (since we are using signals), an async-safe printf function must be implemented (replacing the previous definition of the same-name macro). Here instead of a variadic macro we use a variadic function: 3.void bthread_printf(const char* format, …) 4.{ 5. bthread_begin_atomic_execution(); 6. va_list args; 7. va_start(args, format); 8. vprintf(format, args); 9. va_end(args); 10. bthread_end_atomic_execution(); 11. } Lab Project: User-level threads (Operating Systems, Amos Brocco) V8 31/07/24  22/36 Exercise: Complete the library by implementing preemption. You might want to try different quantums lengths to determine the best value. Pay attention to functions that should remain “private” within your library. Also, ensure that variables declared in preemptable regions of code that need to be preserved across context switches are declared in the global scope and as volatile to prevent the compiler from caching the value in a CPU register ( 90 min ) 5. Synchronization primitives Among the last pieces of the thread library are synchronization primitives, namely mutexes, semaphores, barriers, and condition variables. Their implementation will enable us to run the “classical problems” we saw (or will see) during the class. We start with the mutex (tmutex.h), and leave other primitives as an exercise: 1.#ifndef __TMUTEX_H__ 2.#define __TMUTEX_H__ 3. 4.#include "tqueue.h" 5. 6.typedef struct { 7. void* owner; 8. TQueue waiting_list; 9.} bthread_mutex_t; 10. 11. // Defined only for "compatibility" with pthread 12. typedef struct { char nop; } bthread_mutexattr_t; 13. 14. // attr is ignored 15. int bthread_mutex_init(bthread_mutex_t* m, const bthread_mutexattr_t *attr); 16. 17. int bthread_mutex_destroy(bthread_mutex_t* m); 18. 19. int bthread_mutex_lock(bthread_mutex_t* m); 20. 21. int bthread_mutex_trylock(bthread_mutex_t* m); 22. 23. int bthread_mutex_unlock(bthread_mutex_t* m); 24. 25. #endif And here is the implementation of the mutex (tmutex.c): 1.#include 2.#include "tmutex.h" 3.#include "bthread_private.h" 4. 5.int bthread_mutex_init(bthread_mutex_t* m, const bthread_mutexattr_t *attr) 6.{ 7. assert(m != NULL); 8. m->owner = NULL; 9. m->waiting_list = NULL; 10. return 0; 11. } 12. 13. int bthread_mutex_destroy(bthread_mutex_t* m) 14. { 15. assert(m->owner == NULL); 16. assert(tqueue_size(m->waiting_list) == 0); 17. return 0; Lab Project: User-level threads (Operating Systems, Amos Brocco) V8 31/07/24  23/36 18. } 19. 20. int bthread_mutex_lock(bthread_mutex_t* m) 21. { 22. bthread_begin_atomic_execution(); 23. __bthread_scheduler_private* scheduler = bthread_get_scheduler(); 24. volatile __bthread_private* bthread = (__bthread_private*) tqueue_get_data(scheduler->current_item); 25. if (m->owner == NULL) { 26. m->owner = bthread; 27. bthread_end_atomic_execution(); 28. } else { 29. bthread->state = __BTHREAD_BLOCKED; 30. tqueue_enqueue(&m->waiting_list, bthread); 31. while(bthread->state != __BTHREAD_READY) { 32. bthread_yield(); 33. }; 34. } 35. return 0; 36. } 37. 38. int bthread_mutex_trylock(bthread_mutex_t* m) 39. { 40. bthread_begin_atomic_execution(); 41. __bthread_scheduler_private* scheduler = bthread_get_scheduler(); 42. __bthread_private* bthread = (__bthread_private*) tqueue_get_data(scheduler- >current_item); 43. if (m->owner == NULL) { 44. m->owner = bthread; 45. bthread_end_atomic_execution(); 46. } else { 47. bthread_end_atomic_execution(); 48. return -1; 49. } 50. return 0; 51. } 52. 53. int bthread_mutex_unlock(bthread_mutex_t* m) 54. { 55. bthread_begin_atomic_execution(); 56. assert(m->owner != NULL); 57. assert(m->owner == tqueue_get_data(scheduler->current_item)); 58. __bthread_private* unlock = tqueue_pop(&m->waiting_list); 59. if (unlock != NULL) { 60. m->owner = unlock; 61. unlock->state = __BTHREAD_READY; 62. bthread_yield(); 63. return 0; 64. } else { 65. m->owner = NULL; 66. } 67. bthread_end_atomic_execution(); 68. return 0; 69. } When a thread tries to lock the mutex we check if it's available. If not, we put the thread in the __BTHREAD_BLOCKED state. To avoid race-conditions we must execute mutex procedures atomically with the timer signal disabled. As you can see we re-use our queue to store the list of threads that are currently waiting for the mutex. When the mutex is released we pick the first thread from the queue and resume its execution. Lab Project: User-level threads (Operating Systems, Amos Brocco) V8 31/07/24  24/36 Exercise: copy-paste the mutex implementation in your code and verify that mutual exclusion works correctly. ( 30 min ) The interface of other synchronization primitives is as follows, starting with the semaphore: 1.#ifndef __TSEMAPHORE_H__ 2.#define __TSEMAPHORE_H__ 3. 4.#include "tqueue.h" 5. 6.typedef struct { 7. int value; 8. TQueue waiting_list; 9.} bthread_sem_t; 10. 11. // pshared is ignored, defined for compatibility with pthread 12. int bthread_sem_init(bthread_sem_t* m, int pshared, int value); 13. 14. int bthread_sem_destroy(bthread_sem_t* m); 15. 16. int bthread_sem_wait(bthread_sem_t* m); 17. 18. int bthread_sem_post(bthread_sem_t* m); 19. 20. #define bthread_sem_up(s) \ 21. bthread_sem_post(s); 22. 23. #define bthread_sem_down(s) \ 24. bthread_sem_wait(s); 25. #endif Barrier: 1.#ifndef __TBARRIER_H__ 2.#define __TBARRIER_H__ 3. 4.#include "tqueue.h" 5. 6.typedef struct { 7. TQueue waiting_list; 8. unsigned count; 9. unsigned barrier_size; 10. } bthread_barrier_t; 11. 12. // Defined only for "compatibility" with pthread 13. typedef struct {} bthread_barrierattr_t; 14. 15. // attr is ignored 16. int bthread_barrier_init(bthread_barrier_t* b, 17. const bthread_barrierattr_t* attr, 18. unsigned count); 19. 20. int bthread_barrier_destroy(bthread_barrier_t* b); 21. 22. int bthread_barrier_wait(bthread_barrier_t* b); 23. 24. #endif Condition variable: Lab Project: User-level threads (Operating Systems, Amos Brocco) V8 31/07/24  25/36 1.#ifndef __TCONDITION_H__ 2.#define __TCONDITION_H__ 3. 4.#include "tqueue.h" 5.#include "tmutex.h" 6. 7.typedef struct { 8. TQueue waiting_list; 9.} bthread_cond_t; 10. 11. // Defined only for "compatibility" with pthread 12. typedef struct {} bthread_condattr_t; 13. 14. // attr is ignored 15. int bthread_cond_init(bthread_cond_t* c, const bthread_condattr_t *attr); 16. 17. int bthread_cond_destroy(bthread_cond_t* c); 18. 19. int bthread_cond_wait(bthread_cond_t* c, bthread_mutex_t* mutex); 20. 21. int bthread_cond_signal(bthread_cond_t* c); 22. 23. int bthread_cond_broadcast(bthread_cond_t* c); 24. 25. 26. #define bthread_cond_notify(s) \ 27. bthread_cond_signal(s); 28. 29. #define bthread_cond_notifyall(s) \ 30. bthread_cond_broadcast(s); 31. 32. #endif Exercise: Implement the remaining synchronization primitives (semaphore, barrier, and condition variable). Test and verify that mutual exclusion works correctly. ( 360 min ) 6. Classic synchronization problems In this last part of the laboratory we report the source code of classic synchronization problems, which can be studied and used to verify the user-level thread library. 6.1 Dining philosophers 1.#include 2.#include 3.#include 4.#include "bthread.h" 5.#include "tmutex.h" 6.#include "tsemaphore.h" 7. 8.#define N 5 9.#define LEFT(i) (i+N-1) % N 10. #define RIGHT(i) (i+1) % N 11. #define THINKING 0 12. #define HUNGRY 1 13. #define EATING 2 14. 15. int state[N]; Lab Project: User-level threads (Operating Systems, Amos Brocco) V8 31/07/24  26/36 16. bthread_mutex_t mutex; 17. bthread_sem_t philosopher_semaphore[N]; 18. 19. void* philosopher (void* arg); 20. void take_forks(int i); 21. void put_forks(int i); 22. void test(int i); 23. void think(int i); 24. void eat(int i); 25. 26. void think(int i) 27. { 28. bthread_printf("Philosopher %d is thinking...\n", i); 29. bthread_sleep(200); 30. } 31. 32. void eat(int i) 33. { 34. bthread_printf("Philosopher %d is eating...\n", i); 35. bthread_sleep(300); 36. } 37. 38. void* philosopher (void* arg) 39. { 40. volatile int i; 41. i = (intptr_t) arg; 42. while(1) { 43. think(i); 44. take_forks(i); 45. eat(i); 46. put_forks(i); 47. } 48. bthread_printf("\tPhilosopher %d dead\n", i); 49. } 50. 51. void take_forks(int i) 52. { 53. bthread_mutex_lock(&mutex); 54. state[i] = HUNGRY; 55. bthread_printf("\tPhilosopher %d is hungry\n", i); 56. test(i); 57. bthread_mutex_unlock(&mutex); 58. bthread_sem_wait(&philosopher_semaphore[i]); 59. } 60. 61. void put_forks(int i) 62. { 63. bthread_mutex_lock(&mutex); 64. state[i] = THINKING; 65. test(LEFT(i)); 66. test(RIGHT(i)); 67. bthread_mutex_unlock(&mutex); 68. } 69. 70. void test(int i) 71. { 72. if (state[i] == HUNGRY 73. && state[LEFT(i)] != EATING 74. && state[RIGHT(i)] != EATING) { 75. state[i] = EATING; 76. bthread_printf("\tPhilosopher %d got forks\n", i); 77. bthread_sem_post(&philosopher_semaphore[i]); 78. } 79. } Lab Project: User-level threads (Operating Systems, Amos Brocco) V8 31/07/24  27/36 80. 81. int main(int argc, char *argv[]) 82. { 83. int j; 84. for (j=0; j