---
# System prepended metadata

title: '2019 工業虛擬機 Concurrency programming: Lab'
tags: [工業虛擬機]

---

# 2019 工業虛擬機 Concurrency programming: Lab
###### tags: `工業虛擬機`

### Thread & Process
取自[Programming Parallel Machines Spring 2019](https://engineering.purdue.edu/~smidkiff/ece563/)第7周教材
![](https://i.imgur.com/QW1YWsC.png)
![](https://i.imgur.com/gUF3Vz9.png)

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)
![](https://i.imgur.com/0yeKpoT.png)

#### 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);
```

![](https://i.imgur.com/mE4l7n1.png)


- 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)

![](https://i.imgur.com/9gRzRDG.png)

- 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(描述如何編譯以及執行方式等等)