Simple C programme assignment which requires knowledge of multithreaded programming in C
This assignment involves understanding of basic multithreading in C. POSIX thread and semaphores. You need to complete 2.pdf and also exercise.pdf has 3 exercise at the end. In that you need to complete exercise1 and exercise 2. Exercise needs to be completed by 20/Nov/2020Tutorial 4: Multithread Programming (Part 2) Thread Synchronization and Resource Management Tutor: XU Pengfei(Freeman) Outline Semaphore Basics Binary Semaphore Counting Semaphore Producer Consumer Problem Deadlock Debug multithread program with gdb 2 Recall: Order of Creation vs. Order of Execution • Order of creation ≠ Order of execution • Order of execution depends on how the OS schedules the threads. • Order of execution can be different every time. 3 Thread Synchronizations • Considering the following: Execute sequentially: value of data doesn’t change. If execute concurrently One possible result can be data = -1 Correctness: the result should be the same as if all threads are executed sequentially in order. We as developers should ensure the correctness of our multithreaded program 4 data = 0 initially Synchronization Primitives • For Pthreads • Mutex variables • simple implementation of lock mechanism • Read more here • Condition variables • Read more here • In POSIX standard • Semaphore (Our focus) • It can be also used for processes • Not included in pthread.h 5 Semaphores: A Daily Life Analogy • Init: Set the number of keys • The number of keys that the staff holds • Use: Record the usage status of resources • When a student requests a key • If there are keys left, then the student gets the key and # of keys -1 • After using the restroom, the student returns the key and # of keys +1 • If there’s no key left (# of keys = 0), then the student wait until someone returns a key. … … 6 An OS Example • Init: Set the number of Cores • Use: Record the usage status of resources • When a thread request a core • If there are free cores, then the thread can use a core and # of cores -1 • Right before the thread exit, the thread returns the core and # of cores +1 • If there’s no core left (# of core = 0), then the thread wait until someone release a core. Thread Thread … Thread Thread … Thread Thread … Thread Thread … Thread Thread … 7 What is Semaphore • Invented by Dijkstra • Semaphore is an unsigned integer, with a set of rules applied: • Change of the value is atomic • It can’t be interrupted in the middle of execution • There are only 2 ways to interact with semaphore: • Wait: decrement the value of semaphore by 1 if value > 0. Otherwise, it waits until value > 0. • Post: increment the value by 1 8 An atomic operation is an operation that will always be executed without any other process being able to read or change state that is read or changed during the operation. Semaphore Basic Functions #include 1. Call sem_init(sem_t *sem, int pshared, unsigned int value) • sem_t *sem: pointer to semaphore object • int pshared: 0 if the semaphore shares among threads within a process, always set to 0 for this course. • int value: initial value for the semaphore 2. sem_wait(sem_t *sem) • Decrements (locks) the semaphore pointed to by sem. • If the semaphore’s value is greater than zero, then the decrement proceeds, and the function returns, immediately. • If the semaphore currently has the value zero, then the call blocks until either it becomes possible to perform the decrement (i.e., the semaphore value rises above zero), or a signal handler interrupts the call. 3. sem_post(sem_t *sem) • Increments (unlocks) the semaphore pointed to by sem. • If the semaphore’s value consequently becomes greater than zero, then another process or thread blocked in a sem_wait call will be woken up and proceed to lock the semaphore. 4. sem_destroy(sem_t *sem) • Only a semaphore that has been initialized by sem_init should be destroyed using sem_destroy(). • Destroying a semaphore that other processes or threads are currently blocked on (in sem_wait) produces undefined behavior. • Using a semaphore that has been destroyed produces undefined results, until the semaphore has been reinitialized using sem_init. 9 Binary Semaphore • The value of semaphore can be either 0 or 1 • Can serve as a lock or block mechanism • Sample Code: semaphore_binary.c • Create n threads, each increases the same global variable (initial value is 0) 10000 times • The final value of the global variable should be n*10000 Each thread can change the value of count at any time • Each thread must wait for the semaphore before increase the value of count. • Each thread will post to the semaphore after execute the critical part. • The value of semaphore can be either 0 or 1 à Only one thread can execute the critical part at any time. Critical part 10 Binary Semaphore • Output of semaphore_binary • If increase count without using semaphore • The final value of count ≠ n * number of threads • The final value of count is random • If increase count with semaphore • The final value of count = n * number of threads 11 Thread Safety • Not thread-safe • Change made by one thread can be overwritten by another • Thread safety • A data type or static method is thread-safe if it behaves correctly when used from multiple threads, regardless of how those threads are executed, and without demanding additional coordination from the calling code. • “behaves correctly” means satisfying its specification and preserving its rep invariant; • “regardless of how threads are executed” means threads might be on multiple processors or timesliced on the same processor; • “without additional coordination” means that the data type can’t put preconditions on its caller related to timing” • Semaphore itself is thread safe. (How to test it?) Read more: https://web.mit.edu/6.031/www/fa17/classes/20-thread-safety/ 12 Resource Sharing with Counting Semaphore • The value of semaphore can be any value >= 0 • Semaphore itself is thread-safe à use semaphore as a thread-safe counter. Hence the name “counting semaphore” • Sample Program semaphore_counting.c: • 10 hungry philosophers want to eat food with knives and forks • A bunch of threads need to do some tasks with certain limited resources • A philosopher must acquire a knife and a fork before eat, but the number of knives and forks are less than the number of philosophers. • There are two kinds of resources required to complete certain task • Agreement on picking up knives and forks (to avoid dead lock) • A person must pick up a knife first before pick up a fork • If the person gets a knife but there’s no fork left, the person must put down the knife. Reference: Schivo, S. (2010). Statistical model checking of Web Services (University of Trento). 13 semaphore_counting.c main: sem_trywait() • Won’t block the thread, returns 0 on success • If the decrement cannot be immediately performed, then call returns an error 14 sem_timedwait() int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout); • abs_timeout specifies a limit on the amount of time that the call should block if the decrement cannot be immediately performed. • The abs_timeout argument points to a structure that specifies an absolute timeout in seconds and nanoseconds since the Epoch, 1970-01-01 00:00:00 +0000 (UTC). • If the timeout has already expired by the time of the call, and the semaphore could not be locked immediately, then sem_timedwait() fails with a timeout error • If the operation can be performed immediately, then sem_timedwait() never fails with a timeout error, regardless of the value of abs_timeout. Furthermore, the validity of abs_timeout is not checked in this case. (return 0 immediately if sem value > 0) 15 1970-01-01 00:00:00 +0000 (UTC) time 1. Get current sec and nsec since 1970-01-01: clock_gettime(timespec). 2. Set waiting period: timespec.tv_sec += sec; timespec.tv_nsec += nsec; Wait until tv_sec plus tv_nsec since 1970-01-01… Waiting period Expired semaphore_timedwait.c • int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout); • Set timespec: • Wait until timeout: The boy sets a time limit. The girl waits for the set time. 16 Producer and Consumer Problem • Producer thread: can’t make bread without storage space • Bread + 1 and Storage -1 • Consumer thread: Get bread and release storage space • Bread -1 and Storage +1 Chef Storage space consumer Bread post() wait() wait() post() 17 producer_consumer.c Chef • Wait for consumer. If no consumer shows up in 5 sec, the chef will go home. • If there comes consumer, the chef will start make bread. • First request a storage space for the bread. • Then make the bread. Making a piece of bread takes 2 sec. Consumer • Consumer comes and update the time duty_ts. • Consumer waits for hot bread in 2 + few random sec • If time’s up but no bread is available, the consumer won’t wait and leave. But there’s a problem… 18 producer_consumer.c • Deadlock Problem • Consider the following: • There’s no bread on the shelf and the total storage space is 2. • The chef gets 5 orders and starts to make bread. • The first 2 consumers get their bread, but the other 3 consumers don’t want to wait and leave, but the chef is still making bread. • When the chef start to make the last piece of bread, there’s no space left. • The chef ends up waiting for an empty space, but there’s no consumer to take the bread. The whole process is jammed. 19 A More Complicated Example Background of Assignment 2 • Simulate production of Tesla cars • 7 types of parts need to be produced to assemble one car. • Dependency relationships: • All parts need a storage space, a robot must reserve a space before production • To make a body, 1 skeleton, 1 engine, and 1 chassis are required • To assemble a car, at least 1 body, 1 battery, 4 tires and 7 windows are ready Even easier to create deadlocks. 20 Summary 21 Initialize semaphore • #inlcude • sem_init() How to use semaphore • sem_wait(), sem_trywait(), sem_timedwait() • sem_post() • sem_destroy() after use Access control • Binary semaphore Resource sharing • Counting semaphore • Watch out for deadlocks For the usage of semaphore among processes you can refer to this video: https://youtu.be/ukM_zzrIeXs Debug Multithread Program with gdb • Basics • gdb (GNU Debugger) is a program that runs another program and allows you to track the execution. • When compiling add –g or –ggdb • Preserve identifiers and symbols • Run your program with gdb • gdb ./program • Or gdb, then type file ./program • Customize GDB: make gdb more friendly • You can config your gdb by adding a config file ~/.gdbinit. • E.g.: gdb-dashboard (https://github.com/cyrus-and/gdbdashboard) can automatically print program status with colored highlights. Use gdb 9.2, if you use this gdbinit file. 22 Frequently use GDB cmd bt : backtrace frames(files caller functions) ctl+x+a: switch between TUI/CMD l : list source code k : kill process i thr: show all threads thr + x: go to thread x Ctrl-L : refresh display GDB Cheat sheet: https://gist.github.com/FreemanX/e83e7d2737d82374638ed9cfa37a668b r: run b or : set break point n: step over s: step into c: continue i b: list all break points i watchpoints: list all watch points f : go to frame x f : show current frame d + : delete break/watch point x p : print stuff 23 GDB Example Debug fix_counter.c Expected process: • Create 2 threads, each will receive an offset value. • Both threads will then add the offset to a global variable N times. • Thread th1 gets 1 and th2 gets -1. Both threads loops N times. • The final value of counter should be 0. Where’s the first bug you find? 24 GDB Example • Let’s compile it… • gcc prints out some warnings, but still generates the executable. 25 GDB Example • If we run it anyway ignoring the warnings… • Get segmentation fault. • The compiler warns us about passing the wrong type of argument. • How can that affect the execution? • Key in gdb ./fix_counter * You can find the latest version(9.2) of gdb in /usr/local/DEVTOOL/gdb-9.2/homebrew/bin 26 GDB Example • Type in command run to start execute fix_counter in gdb The execution stops because thread 2 gets segmentation fault. 27 GDB Example • Type bt to check the stacks of the current thread: • Type list to see few more lines before and after line 8: 28 GDB Example • Type info thread to see current running threads: • It tells you which file and which line each thread is currently executing • * means you are looking at this thread in gdb now • If you want to switch to another thread, type thread : “i th” is short for “info thread” 29 GDB Example • You can switch between TUI (Text User Interface) mode and command line mode by pressing Ctrl-X then A 30 GDB Example • Let’s switch back to thread 2 and print some stuff see if we can find anything: The value of the pointer arg is 0x1 Let’s try dereference it but failed. Because arg is a void pointer. Cast the type and try again. We are not allowed to access the memory address 0x1. 31 GDB Example • Back to the source code • We passed the value of offset to pthread_create rather than its pointer. • The value is 1, but if we take 1 as a pointer, we are not allowed to access the address 0x1. à cause of segmentation fault. • We should change the line where we call pthread_create to pthread_create(&th1, NULL, counting_thread, &offset); pthread_create(&th2, NULL, counting_thread, &offset); and 32 If you encounter segmentation faults, it’s likely because your program is trying to access a memory address which doesn’t belong to it. Debug fix_counter.c • However, after we fixed the pointer, the value still isn’t correct. • The final counter value is still random, not 0. • How to fix it? 33 Exercise 1: Make Queue thread safe • Use binary semaphore to make all functions defined in queue.h thread-safe. • DO NOT reuse code from the previous one. • All definitions of functions have changed. • You will use your own implementation of thread safe queue in Assignment 2. 34 Queue Basic Operations • A queue with capacity = 5, size = 3 • Enqueue 3 and 4: • Dequeue(DQ) front twice and DQ rear once: • Enqueue 5, 6 and 7: Check singleThreadTest.c for more sample usage. 35 Queue non-thread safe Thread a Thread b insert 3 insert 4 36 undefined behavior Queue non-thread safe Thread a Thread b insert 3 dequeue rear ? 37 undefined behavior Queue non-thread safe Thread a Thread b insert 3 and 4 queue is full? 38 undefined behavior Exercise 1: Make Queue thread safe • File structure: • queue.h: the header file of Queue. Defines what queue is and functions. • DO NOT change function definitions • queue.c: Implementation of queue related functions • singleThreadTest.c: Provide examples of how to use the queue • multiThreadTest.c: Provide 2 sample tests on thread safety of the queue • Test 1 • Create N threads and each thread enqueues 1. Then check the sum of all elements in queue and see if the sum equals • Then create N threads and each thread dequeues the queue once. After all threads are joined, check if the queue is empty. • Test 2 • Create N threads and each thread enqueues random number of times. Create random number M of threads dequeuing from the front and (q->size – M) threads dequeuing from the rear end. See if the queue is empty after threads are joined. • Makefile: build queue into a static library and link the library to test executables 39 Exercise 1: Make Queue thread safe • Yet another example of using counting semaphore • The admin of workbench has limited the number(300) of processes/threads a user can run concurrently. • Use a counting semaphore to limit the number of concurrent threads in multiThreadTest.c 40 Wait before thread creation Post right before thread exit Exercise 1: Make Queue thread safe • Your task: • 1. Make all functions defined in queue.h thread-safe. • 2. Test all your functions make sure they are thread-safe. • All tests should pass. You may increase the number of runs in multiThreadTest.c • You can design other test cases. Take multiThreadTest.c as a test case example. • Submission: • Create a directory named q1 and put queue.c and queue.h in the directory. 41 Exercise 2: Solve Deadlock • producer_consumer.c will create deadlock. • Your task: • By only making changes to semaphore related functions and related conditional statements, solve the deadlock so that the program can run till the end. • Don’t solve the problem via trying other predefined values • Submission: • Create a directory and name it q2. • Put deadlock free producer_consumer.c in q2 42 Exercise 3: Fix Counter • Your Task 1. Making use of semaphore to fix the problem so that the final counter value is always 0. 2. Run your code many times to verify. 3. If you just change N to a small number like 50 without using semaphore, you may get the final counter value = -100 most of the time instead of random numbers. • Think about the reason and put your explanation in a txt file named explain.txt. • Submission: • Create a directory and name it q3. • Put fix_counter.c and explain.txt in q3. 43 Exercise Submission • Zip all three files in a .zip file and name it _.zip • In Linux use command zip -r _.zip
• Zip only ONCE and it is in .zip format. • Make sure it can be unzipped with Linux cmd unzip on workbench server • Make sure you follow the file structure as shown • Upload the zip file to Moodle. This exercise counts 2.5% of your total assessment of this course. Deadline: Nov. 21, 23:55 44
Are you busy and do not have time to handle your assignment? Are you scared that your paper will not make the grade? Do you have responsibilities that may hinder you from turning in your assignment on time? Are you tired and can barely handle your assignment? Are your grades inconsistent?
Whichever your reason may is, it is valid! You can get professional academic help from our service at affordable rates. We have a team of professional academic writers who can handle all your assignments.
Our essay writers are graduates with diplomas, bachelor, masters, Ph.D., and doctorate degrees in various subjects. The minimum requirement to be an essay writer with our essay writing service is to have a college diploma. When assigning your order, we match the paper subject with the area of specialization of the writer.
We value our customers and so we ensure that what we do is 100% original..
With us you are guaranteed of quality work done by our qualified experts.Your information and everything that you do with us is kept completely confidential.
You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.Read more
The Product ordered is guaranteed to be original. Orders are checked by the most advanced anti-plagiarism software in the market to assure that the Product is 100% original. The Company has a zero tolerance policy for plagiarism.Read more
The Free Revision policy is a courtesy service that the Company provides to help ensure Customer’s total satisfaction with the completed Order. To receive free revision the Company requires that the Customer provide the request within fourteen (14) days from the first completion date and within a period of thirty (30) days for dissertations.Read more
The Company is committed to protect the privacy of the Customer and it will never resell or share any of Customer’s personal information, including credit card data, with any third party. All the online transactions are processed through the secure and reliable online payment systems.Read more
By placing an order with us, you agree to the service we provide. We will endear to do all that it takes to deliver a comprehensive paper as per your requirements. We also count on your cooperation to ensure that we deliver on this mandate.Read more