Post-class 03/04

3 files changed, 348 insertions, 0 deletions

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 <pthread.h>`
+	- Compile using `-lpthread`
+
+- Operations:
+
+```
+#include <pthread.h>
+
+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 <stdio.h>
+#include <pthread.h> //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
+	- `<prompt> 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
+```