---
# System prepended metadata

title: 'OS Homework 3: Multithread Programming'
tags: [OS]

---

---
tags: OS
---

# OS Homework 3: Multithread Programming
105042015 沈冠妤 外語20

## :memo: Code Explain

### Main program():
* Include libraries
* Self defined type "data", indicating the array to be sorted, and the indexes of left, mid, right.
![](https://i.imgur.com/DxVmcN4.png)
* Open files (input testcases and output .txt)
* Define threads, time variables, and input
* Define a buffer to save the numbers collected by while-loop (next step)
![](https://i.imgur.com/LYC4DvE.png)
* Use a while-loop to collect every character (number)
* If it collects a white-space, save the numbers in the buffer, and clear the buffer.
* Keep track of the number of numbers in each line (index_of_num).
![](https://i.imgur.com/xhDDRcf.png)
* If it collects a '\n', we start the merge sort because we had received all numbers in a line.
* Get the initial index of left, mid, and right.
    * Left index will be 0
    * Mid index will be (length of array)/2
    * Right index will be length of array
* Start the clock
* Create two threads for sorting (sort the left and right array)
* Join the threads
* Create a thread for merging (merge the segmented arrays)
* Join the thread
* Get time from the clock
* Output results and time
![](https://i.imgur.com/GnP74zr.png)

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

* Close files (input testcases and output .txt)
![](https://i.imgur.com/ysS0xVA.png)


### Merge sort():
Implemented **recursively**:
* Calculate mid index to separate an array into two.
* Left array and right array do merge sort.
* Merge the two arrays.
![](https://i.imgur.com/SS8fIDj.png)

Merging:
* Retrieve the left array and the right array by input indexes.
* Merge the two arrays by comparing the first elements of the two arrays. Stop until one of the array is empty
    * If left array's first element is smaller, input left array's first element.
    * If right array's first element is smaller, input right array's first element.
    
![](https://i.imgur.com/VX99RmL.png)
* One of the array might be empty first. Keep output the non-empty array's element, until both array are empty
![](https://i.imgur.com/whwkIBn.png)


## :memo: Result Screen Shot
(Last output is testcase written by myself)
![](https://i.imgur.com/rMuSZBP.png)

## :memo: Reference
[Initialize an array in C/C++ - hemingwaylee](https://coherence0815.wordpress.com/2016/07/11/initialize-an-array-in-cc/)

[atoi()用法](http://tw.gitbook.net/c_standard_library/c_function_atoi.html)

[Segmentation fault](https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/560380/)