# 2019 工業虛擬機 Concurrency programming: Lab
###### tags: `工業虛擬機`
### Thread & Process
取自[Programming Parallel Machines Spring 2019](https://engineering.purdue.edu/~smidkiff/ece563/)第7周教材
A thread can possess an independent flow of control and be schedulable because it maintains its own:
- Stack pointer
- Registers
- Scheduling properties (such as policy or priority)
- Set of pending and blocked signals
- Thread specific data.
### PThread (POSIX threads)
#### Example
```clike=
#include <stdio.h>
#include <pthread.h>
void printMsg(char* msg) {
int* status = malloc(sizeof(int));
*status=1;
printf("%s\n", msg);
pthread_exit(status);
}
int main(int argc, char** argv) {
pthread_t thrdID;
int* status = (int*)malloc(sizeof(int));
printf("creating a new thread\n");
pthread_create(&thrdID, NULL, (void*)printMsg, argv[1]);
printf("created thread %d\n",thrdID);
pthread_join(thrdID, (void**) &status);
printf("Thread %d exited with status %d\n", thrdID, *status);
return 0;
}
```
執行結果
```bash=
~$ ./a.out "Hello world!"
creating a new threaa
created thread 219465472
Hello world!
Thread 219465472 exited with status 1
```
延伸閱讀:[POSIX Threads Programming](https://computing.llnl.gov/tutorials/pthreads/)
### Synchronizing Threads
3 basic synchronization primitives
- mutex locks
- condition variables
- semaphores
取自Donald Erwin Knuth教授的教材：[Part IVOther Systems: IIIPthreads: A Brief Review](http://pages.mtu.edu/~shene/FORUM/Taiwan-Forum/ComputerScience/004-Concurrency/WWW/SLIDES/15-Pthreads.pdf)
### mutex locks
```clike=
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int pthread_mutex_init(pthread_mutex_t *mutex,pthread_mutexattr_t *attr);
int pthread_mutex_destroy(pthread_mutex_t *mutex);
int pthread_mutex_lock(pthread_mutex_t*mutex);
int pthread_mutex_unlock(pthread_mutex_t*mutex);
int pthread_mutex_trylock(pthread_mutex_t*mutex);
```
- Only the ==owner== can unlock a mutex. Since mutexes cannot be copied, use pointers.
- If `pthread_mutex_trylock()` returns `EBUSY`, the lock is already locked. Otherwise, the calling thread becomes the owner of this lock.
- With `pthread_mutexattr_settype()`, the type of a mutex can be set to allow recursive locking or report deadlock if the owner locks again
```clike=
pthread_mutex_t bufLock;
void producer(char* buf1) {
char* buf = (char*) buf1;
for(;;) {
while(count == MAX_SIZE);
pthread_mutex_lock(&bufLock);
buf[count] = (char) ((int)('a')+count);
count++;
printf("%d ", count);
pthread_mutex_unlock(&bufLock);
}
}
void consumer(void* buf1) {
char* buf = (char*) buf1;
for(;;) {
while(count == 0);
pthread_mutex_lock(&bufLock);
count--;
printf("%d ", count);
pthread_mutex_unlock(&bufLock);
}
}
```
### condition variables
```clike=
int pthread_cond_init(pthread_cond_t *cond,const pthread_condattr_t *attr);
int pthread_cond_destroy(pthread_cond_t *cond);
int pthread_cond_wait(pthread_cond_t *cond,pthread_mutex_t *mutex);
int pthread_cond_signal(pthread_cond_t *cond);
int pthread_cond_broadcast(pthread_cond_t *cond); // all threads waiting on a condition need to be woken up
```
- Condition variables allow a thread to block until a specific condition becomes true
- blocked thread goes to wait queue for condition
- When the condition becomes true, some other thread signals the blocked thread(s)
- Conditions in Pthreads are usually used with a mutex to enforce mutual exclusion.
- the `wait` call should occur under the protection of a mutex
```clike=
pthread_mutex_t lock;
pthread_cond_t notFull, notEmpty;
void consumer(char* buf) {
for(;;) {
pthread_mutex_lock(lock);
while(count == 0)
pthread_cond_wait(notEmpty, lock);
useChar(buf[count-1]);
count--;
pthread_cond_signal(notFull);
pthread_mutex_unlock(lock);
}
}
```
<hide>
> broadcast小實驗
> mutex和block mutex效率小實驗
</hide>
### semaphores
```clike=
sem_t semaphore;
int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_wait(sem_t *sem);
int sem_post(sem_t *sem);
```
- Can do increments and decrements of semaphore value
- Semaphore can be initialized to any value
- Thread blocks if semaphore value is less than or equal to zero when a decrement is attempted
- As soon as semaphore value is greater than zero, one of the blocked threads wakes up and continues
- no guarantees as to which thread this might be
```clike=
sem_t empty, full;
void producer(char* buf) {
int in = 0;
for(;;) {
sem_wait(&empty);
buf[in] = getChar();
in = (in + 1) % MAX_SIZE;
sem_post(&full);
}
}
void consumer(char* buf) {
int out = 0;
for(;;) {
sem_wait(&full);
useChar(buf[out]);
out = (out + 1) % MAX_SIZE;
sem_post(&empty);
}
}
```
#### Comparing primitives
- Using mutual exclusion with CV’s is faster than using semaphores
- Sometimes semaphores are intuitively simpler
延伸閱讀:[Mutex and Semaphore](https://hackmd.io/@nKngvyhpQdGagg1V6GKLwA/Skh9Z2DpX?type=view)
### 執行pThread範例
安裝編譯工具
```bash
~$ sudo apt install build-essential
```
編譯程式連結pthread library
```bash
~$ gcc a.c -lpthread -o a.out
```
執行
```
~$ ./a.out
```
### Homework 1
#### 作業要求
1. 請自行建立一個程式讀取輸入檔案，其功能如下
- 輸出所有點與點之間的距離並按照降序排列，並標注生成的點
- 使用者可指定以N個Thread同時計算距離
輸入檔案每一行為點3軸座標值(x,y,z)，以`,`為間隔，資料型態如下:
| x | y | z |
| --- | --- | --- |
| float | float | float |
#### 範例輸入輸出
輸入檔案`input.txt`
```
0.0 0.0 0.0
1.0 1.0 1.0
2.0 2.0 2.0
```
使用者輸入
```bash
./program input.txt 3 >output.txt
```
輸出檔案`output.txt`
```bash
1.73 (1,2)
1.73 (2,3)
3.46 (1,3)
```
or
```json
{
'd': 1.73,
'p': [1,2]
},{
'd': 1.73,
'p': [2,3]
},{
'd': 1.73,
'p': [1,3]
}
```
#### 注意事項
1. 實作語言C99
2. 輸出格式不限，但須有可讀性。
3. 請繳交專案檔案以及README(描述如何編譯以及執行方式等等)
### Homework 2
#### 作業要求
1. 請自行建立一個程式利用pthread模擬VM Live Migration:
- Assumptions:
- The function Wait() makes a thread wait for an notification, and the function Notify(Thread t) wakes up the thread t
- The remote VM only serves as a memory container. So we do not need to simulate its behavior.
- Preconditions:
- dirtyBitMap is a shared variable in Main Process
- dirtyBitMap only has 20 pages // dirtyBitMap[0...19]
- Migration is a shared variable in Main Process
- Stop is a shared variable in Main Process
#### Pseudocode
Main VM thread
```ruby=
Stop = false
Migration = true
Do a lot of calculation to produce a lot of dirty pages
Print a line of “Producing Dirty Pages”
If (Migration == true)
Critical region begins
Generate a number x, where 0<=x<20
Let dirtyBitMap[x] = 1
Print a line of “Dirtying Pages x” where x is the random number
Critical region ends
End If
If (Stop == true)
Print a line of “Finishing VM Migration”
Call Wait( ) such that the main thread is waiting for the termination of the migration thread
Else If (Migration = true and Migration Thread is null)
Print a line of “Dirtying All”
Set all bits in dirtyBitMap to 1
Create Migration Thread
Start Migration Thread
Go to Step 3
Else
Go to Step 3
End If
```
Migration Thread
```ruby=
While (true)
If (the number of dirty bits of dirtyBitMap > 3 )
Select 3 dirty pages
For each selected dirty page x
Critical region begins
Transmit the dirty page to the remote host
reset the bit in dirtyBitMap to be 0
Print a line of “Cleaning Pages x” where x is the number
Critical region ends
End For
Else
Stop = true
Print a line of “Suspending VM”
While (Main VM Thread is not waiting)
Print a line of “Waiting VM for Suspending”
End While
Critical region begins
For each dirty page x
Transmit the remaining dirty pages to the remote host
Print a line of “Cleaning Pages x” where x is the number
End For
Critical region ends
Notify(Main VM Thread)
Break While
End If
End While
```
#### 注意事項
1. 實作語言不限
2. 請繳交專案檔案以及README(描述如何編譯以及執行方式等等)
Sign in with Wallet
Connect another wallet