7. parallel programming image/svg+xml 7. parallel programming Zidarics Zoltánzamek@vili.pmmf.hu 2016 Parallel programming EmbeddedProgramming 6.complex datastructures 8. Coding Problem initialization Reading input Processing Setting outputs Asynchronous events ? single thread applications have to wait for input polling handling interrupts rounding times asynchronous event in case of pollingprocessing may be delayed Solution operating systems run multiple processes IPC (Inter process Communication) shared memory, pipeline task1 task2 sharedmemory 1. request memory 2. use memory 3. free memory 1. request memory 2. use memory 3. free memory R/W R/W task1 task2 1. open pipe 2. r/w pipe 3. close pipe 1. open pipe 2. r/w pipe 3. close pipe threads   Threads operating system runs it (scheduler) priority can be set advantages disadvantages use a common data area process thread1 thread2 Time fast simple administration common data area management causes problems debugging is harder Thread management int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg); starting thread pthread_t producer; pthread_create(producer, NULL, pizzeria_bake, NULL); thread: A pointer to type p_thread_t. Administer thread-related data to the operating system. attr: thread attributes (priority, scheduling policy, stack size, etc.) start_routine:the function to be run by the thread. arg: parameters to pass to the function return value: thread ID detached state (joinable? default: PTHREAD_CREATE_JOINABLE. Other option: PTHREAD_CREATE_DETACHED) scheduling policy (real-time? PTHREAD_INHERIT_SCHED,PTHREAD_EXPLICIT_SCHED,SCHED_OTHER) scheduling parameter inherited attribute (Default: PTHREAD_EXPLICIT_SCHED Inherit from parent thread: PTHREAD_INHERIT_SCHED) scope (Kernel threads: PTHREAD_SCOPE_SYSTEM User threads: PTHREAD_SCOPE_PROCESS Pick one or the other not both.) guard size stack address (See unistd.h and bits/posix_opt.h _POSIX_THREAD_ATTR_STACKADDR) stack size (default minimum PTHREAD_STACK_SIZE set in pthread.h) thread waiting to finish int pthread_join(pthread_t th, void **thread_return); th: the thread waiting for. End of thread run if pthread_exit () is called or canceled thread_return: the thread can return data to the waiting thread exit from the thread void pthread_exit(void *retval); retval: address of parameters returned by the thread Shared data caching int running=0; void th_func(void *args) { running=1; while(running) { do_something(); } pthread_exit(NULL);}  ...pthread_t thread; pthread_create(thread, NULL, th_func, NULL);sleep(42);running=0;pthread_join(thread, NULL); can be cached (cpu register) volatile keyword need volatile? link link link Atomicity change the value of a variable (++i, i=42) int global_counter=0; void *thread_func1(void *arg) { for (i=0;i<INC_TO;i++) global_counter++;  return (NULL);} void *thread_func2(void *arg) { for (i=0;i<INC_TO;i++) global_counter--;  return (NULL);}   expected result: 0, real result is not 0 memory variable cpu register 1. load from memory 2. change value 3. store to memory built-in functions to access atomic memory type __sync_fetch_and_add (type *ptr, type value, ...)type __sync_fetch_and_sub (type *ptr, type value, ...)type __sync_fetch_and_or (type *ptr, type value, ...)type __sync_fetch_and_and (type *ptr, type value, ...)type __sync_fetch_and_xor (type *ptr, type value, ...)type __sync_fetch_and_nand (type *ptr, type value, ...) { tmp = *ptr; *ptr op= value; return tmp; }{ tmp = *ptr; *ptr = ~(tmp & value); return tmp; } // nand type __sync_add_and_fetch (type *ptr, type value, ...)type __sync_sub_and_fetch (type *ptr, type value, ...)type __sync_or_and_fetch (type *ptr, type value, ...)type __sync_and_and_fetch (type *ptr, type value, ...)type __sync_xor_and_fetch (type *ptr, type value, ...)type __sync_nand_and_fetch (type *ptr, type value, ...) { *ptr op= value; return *ptr; }{ *ptr = ~(*ptr & value); return *ptr; } // nand bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...) can also be used: sig_atomic_t (signal.h) P3_ThreadAtomicity.zip Mutual exclusion code snippets that can only be executed by one thread at a time int counter=0; void* doSomeThing(void *arg) { unsigned long i = 0; counter += 1; printf("Job %d started\n", counter); for (i = 0; i < (0xFFFFF); i++) ; printf("Job %d finished\n", counter); return NULL;} int main(void) { ... while (i < 2) { err = pthread_create(&(tid[i]), NULL, &doSomeThing, NULL); if (err != 0) printf("\ncan't create thread :[%s]\n", strerror(err)); i++; } pthread_join(tid[0], NULL); pthread_join(tid[1], NULL); return (EXIT_SUCCESS);} the other threads that want to execute this snippet,forced to wait 6680 6681 semaphore result: Job 1 startedJob 2 startedJob 2 finishedJob 2 finished  void* doSomeThing(void *arg) { pthread_mutex_lock(&lock); unsigned long i = 0; counter += 1; printf("Job %d started\n", counter); for (i = 0; i < (0xFFFFF); i++) ; printf("Job %d finished\n", counter); pthread_mutex_unlock(&lock); return NULL;} P3_Mutexes.zip c.1 Conditional variables Allows a thread to wait for the resource to be secureddo not book a mutex. The wait is until a condition is true, then you can move on andyou can get the mutext back. Example: Ping pong game. There are two threads running, Ping and Pong. They both have to wait until the other spleen. P3_ConditionalVariable.zip Problems with mutual exclusion solution: one must recognize that there is a deadlock and it must be downmake your own chopsticks the polite philosopher can eat less often, in extreme cases he starves to death.it is starvation if they starve and start eating at the same time, they will all pick it uphis chopsticks and waiting for the other to finish eating and getone more stick: it is deadlock The problem of dining philosophers P3_DeadLock.zip   IPC (Inter process communication) SYSTEM V & POSIX standard Shared memory Semaphore Message queue Demo Shared memory Parent process shm_open(). Open shared memory. ftruncate(). Set the length of shared memory to 0. mmap(). Assign shared memory. execve(). Execution of child process. fork(). Creating a child process. wait(). Waiting for the outcome of a child's process. munmap(). Unmount shared memory. close(). Free shared memory. Child process shm_open(). Open shared memory. mmap(). Assign shared memory. munmap(). Unmount shared memory. close(). Free shared memory. Semaphores Parent process sem_open(). Open semaphore. sem_post(). Send the semaphore value to the child process execve(). Execution of child process. fork(). Creating a child process. wait(). Waiting for the outcome of a child's process. sem_close(). close semaphore sem_unlink(). Delete a named semaphore. Child process sem_open(). Open semaphore. sem_wait(). Waiting for semaphore value sem_close(). semaphore closure Message Queues Parent process mq_open(). Opening MQ mq_send(). sending message to child process execve(). Execute child process fork(). Creating child process wait(). Waiting for the outcome of a child's process. mq_close(). Closing MQ mq_unlink(). Delete named MQ Child process mq_open(). Opening MQ mq_receive(). Reading message mq_close(). Closing MQ Message buffer is created separately by parent and child. Processes vs. threads Each thread runs in the same executable binary app. If child processto be started, it must be started one by one with the exec function. A faulty thread can destroy all threads in the entire process because it is a common data areaused. Processes use separate memory areas. For a new process, generating data memory takes extra processor time.Of course, copying only happens when there is a change, so the "penalty" is less. Threads are needed for applications where fine-tuning of parallelism is required.e.g. if the task can be broken down into many roughly identical tasks. Coarse parallelization for processesmay be required. Data sharing on the threads is not a problem, of course you have to pay attention to the competitive situation. For processes IPC (Inter Process Communication) required Concepts related to multithreaded programming Thread safe: If more than one thread has access to a particular state variableand one of them can overwrite it, we need to coordinate access to all threads.  atomicity: if a variable can be modified from multiple threads, it is providedthe scheduler must not be able to interrupt the thread during the modification race condition: when the result of a calculation depends on the schedulerhow to cross threads. locking: ensuring that the critical code segment is only one thread at a timecan run. reentrancy: a function can be recalled indirectly, or directly. vividness: whether the parallelization actually made the operation really faster, or athere is no significant improvement due to thread handling tasks Task the developer of the Pizzeria project unexpectedly left the company and you became her successor. check if the current code works? create a Makefile to maintain the project! write tests for the project! create documentation for the project! if you had any ideas on the go your suggestions would be in the git repository for a developmentbranch, then make a short presentation in which you present! upload the finished work to your Gitlab repository named pizzeria Pizzéria follow the gitflow method, implement each subtask in a separate branch(Makefile, test, documentation), then merge into the develop branch Useful links Threads in Advanced Linux programming Interprocess Communication in Advanced Linux programming Linux System V and POSIX IPC Examples Threads in Wikipedia
1
  1. Main
  2. Problem
  3. Solution
  4. Threads
  5. Concepts related to multithreaded programming
  6. Thread management
  7. Shared data
  8. Atomicity I.
  9. Atomicity II.
  10. Mutual excusion I.
  11. Mutual excusion II.
  12. Problems with mutual excusion
  13. Conditional variables
  14. IPC
  15. Shared memory
  16. Semaphores
  17. Message Queues
  18. Processes vs. threads
  19. Task
  20. Useful links
  21. next