From afb09551d41f2c0ac666c68dc50c14b243e2784d Mon Sep 17 00:00:00 2001 From: loshprung Date: Wed, 4 Mar 2020 11:36:12 -0800 Subject: Post-class 03/04 --- 02-21.md | 4 ++ 02-26.md | 172 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 03-04.md | 172 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 348 insertions(+) create mode 100644 02-26.md create mode 100644 03-04.md diff --git a/02-21.md b/02-21.md index 52cccc2..045fdff 100644 --- a/02-21.md +++ b/02-21.md @@ -72,3 +72,7 @@ void loop(int n){ - Lock - Conditional Variables - Semaphores + +--- + +[-> Notes 02/26](02-26.md) diff --git a/02-26.md b/02-26.md new file mode 100644 index 0000000..ef1c0a5 --- /dev/null +++ b/02-26.md @@ -0,0 +1,172 @@ +[\<- Notes 02/21](02-21.md) + +--- + +# Threading Continued + +## Locking + +- Sharing Variables + - Requires mutual exclusion + - Lock/unlock to avoid a race condition +- Have one lock for each independent critical region + +- Bad Example (no synchronization): + +``` +int count = 0; + +void *update(){ //returns a pointer with no given data type + int i; + + for(i = 0; i < 1000; i++){ + count++; + } +} +``` + +- Good Example (using lock): + +``` +int count = 0; + +void *update(){ //returns a pointer with no given data type + int i; + + for(i = 0; i < 1000; i++){ + //lock + count++; + //unlock + } +} +``` + +- More real world example: + +``` +int balance = 100; //$100 + +//process 1: withdraw $20 + //read balance (i.e $100) + //write new balance (i.e $80) + +//process 2: withdraw $30 + //read balance (i.e $80) + //write new balance (i.e $50) +``` + +- In the above example, you need to use lock to avoid one process reading the balance before the other process finishes writing + +## pthread library + +- We will use the Linux pthread library + - Main information + - `man pthread` + - There are man pages for specific functions + - Include ".h" file as shown in the man page: `#include ` + - Compile using `-lpthread` + +- Operations: + +``` +#include + +pthread_t thread; + +int pthread_create( + pthread_t *restrict thread, //thread id + const pthread_attr_t *restrict attr, //attributes + void *(*start_routine)(void *), //function + void *restrict arg); //argument +``` + +- More operations: + - `void pthread_exit(void *value_ptr);` + - `int pthread_join(pthread_t thread, void **value_ptr);` + +- Example using pthreads + - Alternating threads + - Creates 3 threads + - Let the system execute them in a round-robin fashion + - Wait for them to finish at main + +``` +#include +#include //this is the library that allows for threading + +void *loopThread(void *arg); + +int main(){ + int i; + pthread_t thr[3]; + + for(i = 0; i < 3; i++){ + pthread_create(&thr[i], NULL, loopThread, (void *)i); + } + for(i = 0; i < 3; i++){ + pthread_join(thr[i], NULL); + } +} + +void *loopThread(void *arg){ + int i, j; + int threadNo = (int)arg; //cast the void pointer + + for(i = 0; i < 20; i++){ + printf("Thread %d\n", threadNo); + sleep(1); + } +} +``` + +- Functions: + +``` +pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER + +//INIT +int pthread_mutex_init(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrict attr); + +//LOCK +int pthread_mutex_lock(pthread_mutex_t *mutex); + +//UNLOCK +int pthread_mutex_unlock(pthread_mutex_t *mutex); +``` + +- Example using mutex lock: + +``` +//Using mutex lock +//pthread_mutex_init called in main + +int count = 0; +pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; + +void *update(){ + int i; + + while(i = 0; i < 1000; i++){ + pthread_mutex_lock(&mutex); + count++; + pthread_mutex_unlock(&mutex); + } +} +``` + +- Danger! + - When one or more threads are waiting for one another and no thread can proceed +- Example: + - One thread is waiting for itself + - Two threads are waiting for each other + - Several threads are waiting for one another in a cycle + +## Performance Considerations + +- Thread creation is expensive +- Each thread has its own stack +- Lock contention requires skills to keep many threads as possible running + +--- + +[-> Notes 03/04](03-04.md) diff --git a/03-04.md b/03-04.md new file mode 100644 index 0000000..dfd1de5 --- /dev/null +++ b/03-04.md @@ -0,0 +1,172 @@ +[-> Notes 02/26](02-26.md) + +--- + +# Large Programs + +- When programs are long + - Need to split the file into several files + - Need to compile them together + - Example: + - We have files: main.c, list.c, file.c + - To compile: `gcc -o proj main.c list.c file.c` + +- Sharing global variables + - Define types in a `.h` file + - Declare global variables (do not initialize!) + - extern in a .h file + - Declare and initialize global variables + - in one of the .c file (e.g., the main one) + - Include the .h file in all the .c files which use any of the global variables: `#include "proj.h"` + +- Example: + - in `link.h`, declare (do not initialize!) global variables + - `extern NODE *head;` + - In main.c, include link.h, and declare and initialize global variables + +``` +#include "link.h" +NODE *head = (NODE *)NULL; +``` + +- In all the other .c files, just include link.h + - `#include "link.h"` + +- Use `makefile` to automate the compilation process +- Create a "makefile" file with instructions +- Command `make` will parse the makefile file and execute the appropraite command + - ` make proj1` + +- Example 1: + +``` +proj1: main1.c list1.c io1.c + gcc -o proj1 main1.c list1.c io1.c + ./proj1 filename +``` + +- Example 2: + +``` +proj2: main2.c list2.c thr2.c + gcc -o proj2 main2.c list2.c thr2.c -lpthread + ./proj2 filename1 filename2 +``` + +- The tab is important! (its the syntax) + +## Development Tools + +- Unix/Linux + - Environment and commands + - Tools - learn to use these!! + - vi + - grep + - gdb + - makefile + - shell script + +- Libraries + - Math + - String + - Memory + - Threads + +--- + +# Special Operators + +## Condtional Operator + +- The conditional operator `?:` takes three operands + - c ? r1 : r2 + - The value of the expression using the conditional operator is the value of either its second or third operand, depending on the value of the first operand + - Shorthand for: + +``` +if(c){ + //result value is r1 +} +else{ + //result value is r2 +} +``` + +- Examples + - In assignment: `x = (a < b) ? a : b;` + - x will be assigned the smallest value between a and b + +- Very useful for macros +- Examples: + - `#define MAX(a,b) (((a) > (b)) ? (a) : (b))` + - returns the max between the paramaters assigned to a and b + - `define ISLETTER(c) (((c) >= 'A' && (c) <= 'z') ? 1 : 0)` + - returns 1 if the value of assigned to c is a letter and returns 0 if not + +## Sequential Evaluation + +- The comma operator + - Evaluates its two operands in sequence, yeilding the value of the second operand as the value of the expression + - The value of the first is discarded + +- Example: + - In assignments: `x = (i += 2, a[i]);` -> `i += 2; x = a[i];` + - Parenthesis are important because precedence + +## Bitwise Operators + +- Positive integers are represented in the computer by standard binary numbers + - Examples: + +``` +short n = 13; +//in memory - 0000 0000 0000 1101 +//2^0 + 2^2 + 2^3 = 13 + +char c = 5; +//in memory - 0000 0101 +//2^0 + 2^2 = 5 +``` + +- Bitwise operators + - take operands of any integer type + - char, short, int, long + - but treat an operand as a collection of bits rather than a single number + +### Bitwise Negation + +- Bitwise negation + - Operand: `~` + - Application of `~` to an integer produces a value in which each bit of the operand has been replaced by its negation + - 0 -> 1 + - 1 -> 0 + - Example: + - ` n = 0000 0000 0000 1101` + - `~n = 1111 1111 1111 0010` + +### Bitwise Shift + +- Shift operators + - shift left: `<<` + - shift right: `>>` + - Take two integers operands + - The value on the left is the number to be shifted + - Viewed as a collection of bits that can move + - To avoid implementation problems, avoid negative numbers when shifting right + - The value on the right is a nonnegative number telling how far to move the bits + +- Operand + - `<<` shifts bits left + - `>>` shifts bits right +- The bits that "fall off the end" are lost +- The "emptied" positions are filled with zeros + +- Examples: + +``` +int n; // n is 0000 0000 0000 1101 +n << 1 //now n is 0000 0000 0001 1010 +n << 4 //now n is 0000 0000 1101 0000 +n >> 3 //now n is 0000 0000 0000 0001 +n << 4 //now n is 0000 0000 1101 0000 +``` -- cgit