---
# System prepended metadata

title: 作業系統
tags: [Coding]

---

# 作業系統lab
## lab2
:::spoiler
### OS Lab2 Process and Socket
###### 了解Process的運作
###### 理解Socket的原理並且實作socket通訊

----

#### Process
![image](https://hackmd.io/_uploads/BJ2STUSBkl.png=46%x)
![image](https://hackmd.io/_uploads/BJu8TLBHyx.png=50%x)

----

#### Process lab2-1

![image](https://hackmd.io/_uploads/HJep6IrSJl.png)

----

#### Process lab2-1 example code
```c 
#include <stdio.h> /* printf */
#include <sys/types.h> /* pid_t */
#include <unistd.h> /* fork(), getpid() */
#include <sys/wait.h> /* wait() */

int main() {
	pid_t pid;
    
    /* Write your code here */
    
    
    /* Wait for a child process to stop or terminate */
    wait(NULL);
    printf("[%d] Hello world!\n", getpid());
  	
    return 0;
}
```

----

#### Process lab2-2
![image](https://hackmd.io/_uploads/HJCEzOk-ke.png)

----

#### Process lab2-2 example code
前置作業: 先在當前目錄下創立一個.C檔(範例檔名為programA)，功能為印出"execlp success"，並且將它轉為可執行檔。
```c
#include <stdio.h> /* printf */
#include <sys/types.h> /* pid_t */
#include <unistd.h> /* fork(), getpid() */
#include <stdlib.h> /* exit() */
#include <sys/wait.h> /* wait() */
//execlp(const char *file, const char *arg, ..., NULL);
//execlp(尋找程式路徑, 傳遞給程式的第一個引數(通常為程式名稱), ..., NULL);
//該程式可利用argv[0]取得程式名稱

int main() {
    pid_t pid;
    
    for(int i = 0; i < 3; i++)
    {
        /* Write your code here */
    }
    while(wait(NULL) > 0); /*父親等待兒子完成。當沒有子進程可等待，則返回-1*/
    
    if(pid > 0)
    {
        /* Write your code here */
    }
    else if(pid == 0)
    {
        if(/* Write your code here */)  /*利用execlp使process跳到別的程式執行*/
        {                               /*若execlp執行失敗，回傳-1*/
            perror("execlp failed"); /*印出錯誤資訊*/
            exit(1);   
        }
    }
    else
    {
        perror("fork failed");
        exit(1);
    }
    return 0;
}
```
----

#### lab2-3 Socket

![image](https://hackmd.io/_uploads/B1WCTISrJl.png)

----

#### Simplified diagram of socket communication
![image](https://hackmd.io/_uploads/S1RCaIBBke.png)

----

#### TCP server example code
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#define PORT 4444
#define IP_ADDRESS "127.0.0.1"

int main()
{

	int serversocket; // sockfd => socket file descriptor, socket()
	struct sockaddr_in serverAddr;
	
	int newSocket; // sockfd, accept()
	struct sockaddr_in newAddr;

	socklen_t addr_size;				   // accept()
	int checkbind, checklisten, checkRecv; // bind(), listen(), recv()

	char buffer[1024]; // recv(), send()
	pid_t childpid;	   // fork()

	/* replace this line with socket() */
	if (/* check error */)
	{
		printf("[-]Error in creating Server Socket.\n");
		exit(1);
	}
	printf("[+]Server Socket is created.\n");

	memset(&serverAddr, '\0', sizeof(serverAddr));
	serverAddr.sin_family = AF_INET;
	serverAddr.sin_port = htons(PORT); //host to net short
	serverAddr.sin_addr.s_addr = inet_addr(IP_ADDRESS);

	/* replace this line with bind() */
	if (/* check error */)
	{
		printf("[-]Error in binding.\n");
		exit(1);
	}
	printf("[+]Bind to port %d\n", PORT);

	/* replace this line with listen() */
	if (/* check success */)
	{
		printf("[+]Listening....\n");
	}
	else
	{
		printf("[-]Error in binding.\n");
	}

	while (1)
	{
		/* replace this line with accept() */
		if (/* check error */)
		{
			exit(1);
		}
		printf("Connection accepted from %s:%d\n", inet_ntoa(newAddr.sin_addr), ntohs(newAddr.sin_port));

		/* replace this line with fork() */
		if (/* check if it's a child process */)
		{
			close(serversocket);

			while (1)
			{
				/* replace this line with recv() */
				if (/* check error */)
				{
					break;
				}

				if (strcmp(buffer, ":exit") == 0)
				{
					printf("Disconnected from %s:%d\n", inet_ntoa(newAddr.sin_addr), ntohs(newAddr.sin_port)); //network to ascii
					break;
				}
				else
				{
					printf("Client : %s\n", buffer);
					/* replace this line with send() */
					bzero(buffer, sizeof(buffer));
				}
			}
		}
	}

	close(newSocket);

	return 0;
}
```

----

#### TCP client example code
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#define PORT 4444
#define IP_ADDRESS "127.0.0.1"

int main()
{

	int clientSocket;
	struct sockaddr_in serverAddr;
	int checkConnect, checkRecv;
	char buffer[1024];

	/* replace this line with socket() */
	if (/* check error */)
	{
		printf("[-]Error in creating Client Socket.\n");
		exit(1);
	}
	printf("[+]Client Socket is created.\n");

	memset(&serverAddr, '\0', sizeof(serverAddr));
	serverAddr.sin_family = AF_INET;
	serverAddr.sin_port = htons(PORT);
	serverAddr.sin_addr.s_addr = inet_addr(IP_ADDRESS);

	/* replace this line with connect() */
	if (/* check error */)
	{
		printf("[-]Error in connection.\n");
		exit(1);
	}
	printf("[+]Connected to Server.\n");

	while (1)
	{
		printf("Client : ");
		scanf("%s", &buffer[0]);
		/* replace this line with send() */

		if (strcmp(buffer, ":exit") == 0)
		{
			close(clientSocket);
			printf("[-]Disconnected from server.\n");
			exit(1);
		}

		/* replace this line with recv() */
		if (/* check error */)
		{
			printf("[-]Error in receiving data.\n");
		}
		else
		{
			printf("Server : %s\n", buffer);
		}
	}

	return 0;
}
```
----
:::
### 第一題
fork的作用會返回一個值並且在程式碼的地方分裂出另一個一模一樣的程式（process），前面的變數什麼的都會完整被複製過去，然後父子進程在分裂的地方同時進行。
但就算是全域變數，父子進程也不是共用的。
![6_MCU_LCD_20241017](https://hackmd.io/_uploads/B1YFN_DGke.jpg)
```cpp=
#include <stdio.h> /* printf */
#include <sys/types.h> /* pid_t */
#include <unistd.h> /* fork(), getpid() */
#include <sys/wait.h> /* wait() */
int a=1;
int main() {
    pid_t pid;
    /* Fork to create processes */
    for (int i = 0; i < 7; i++) { // Fork three times to create 8 processes
        a+=1;
        pid = fork();
        printf("[%d] [%d]\n", getpid(),i);
        printf("%d\n",a);//確認前面變數有複製到
        if (pid < 0) { // If fork fails
            perror("Fork failed");
            return 1;
        } else if (pid == 0) { // Child process
            printf("i am child  [%d] [%d]\n", getpid(),i);
            continue; // Go to next iteration of fork loop
        } else { // Parent process
            printf("i am father [%d] [%d]\n", getpid(),i);
            break; // Parent process does not continue forking
        }
    }

    /* Wait for a child process to stop or terminate */
    wait(NULL);
    printf("[%d] Hello world!\n", getpid());

    return 0;
}



輸出：

[6903] [0]
2
i am father [6903] [0]
[6904] [0]
2
i am child  [6904] [0]
[6904] [1]
3
i am father [6904] [1]
[6905] [1]
3
i am child  [6905] [1]
[6905] [2]
4
i am father [6905] [2]
[6906] [2]
4
i am child  [6906] [2]
[6906] [3]
5
i am father [6906] [3]
[6907] [3]
5
i am child  [6907] [3]
[6907] [4]
6
i am father [6907] [4]
[6908] [4]
6
i am child  [6908] [4]
[6908] [5]
7
i am father [6908] [5]
[6909] [5]
7
i am child  [6909] [5]
[6909] [6]
8
i am father [6909] [6]
[6910] [6]
8
i am child  [6910] [6]
[6910] Hello world!
[6909] Hello world!
[6908] Hello world!
[6907] Hello world!
[6906] Hello world!
[6905] Hello world!
[6904] Hello world!
[6903] Hello world!


```
### 第二題
因為父進程跟子進程是同時的，並且沒有誰的權重比較高。
所以輸出可能是亂的
![IMG_1533](https://hackmd.io/_uploads/ryZf7avM1g.jpg)
![113_編譯器期中考ans](https://hackmd.io/_uploads/rJh9Iavfye.jpg)
```cpp=
#include <stdio.h> /* printf */
#include <sys/types.h> /* pid_t */
#include <unistd.h> /* fork(), getpid() */
#include <stdlib.h> /* exit() */
#include <sys/wait.h> /* wait() */
int main() {
    pid_t pid;
    
    for(int i = 0; i < 3; i++)
    {
        pid = fork(); 
    }
    while(wait(NULL) > 0); 
    if(pid > 0)
    {
        printf("[%d]I'm parent\n",getpid());
    }
    else if(pid == 0)
    {
        if(execlp("./b_A" , "b_A", NULL) == -1)  
        {
            printf("[%d]execlp failed",getpid()); 
            exit(1);   
        }
    }
    else
    {
        printf("fork failed");
        exit(1);
    }
    return 0;
}
```
programA.c
```cpp=
#include <stdio.h>
int main() {
    printf("execlp success\n");
}
```

![image](https://hackmd.io/_uploads/HynE1_PMyx.png)

### 第三題
client.c
```cpp=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#define PORT 4444
#define IP_ADDRESS "127.0.0.1"

int main()
{
    int clientSocket;
    struct sockaddr_in serverAddr;
    int checkConnect, checkRecv;
    char buffer[1024];

    // Create socket
    clientSocket = socket(AF_INET, SOCK_STREAM, 0);
    if (clientSocket < 0)
    {
        perror("[-]Error in creating Client Socket.");
        exit(1);
    }
    printf("[+]Client Socket is created.\n");

    memset(&serverAddr, '\0', sizeof(serverAddr));
    serverAddr.sin_family = AF_INET;
    serverAddr.sin_port = htons(PORT); // Server port
    serverAddr.sin_addr.s_addr = inet_addr(IP_ADDRESS); // Server IP address

    // Connect to server
    checkConnect = connect(clientSocket, (struct sockaddr*)&serverAddr, sizeof(serverAddr));
    if (checkConnect < 0)
    {
        perror("[-]Error in connection.");
        exit(1);
    }
    printf("[+]Connected to Server.\n");

    while (1)
    {
        // Get message from user
        printf("Client : ");
        fgets(buffer, sizeof(buffer), stdin); // Use fgets to handle spaces
        buffer[strcspn(buffer, "\n")] = 0; // Remove trailing newline character

        // Send message to server
        int checkSend = send(clientSocket, buffer, strlen(buffer), 0);
        if (checkSend < 0)
        {
            perror("[-]Error in sending data.");
            break;
        }

        // Check for exit condition
        if (strcmp(buffer, ":exit") == 0)
        {
            close(clientSocket);
            printf("[-]Disconnected from server.\n");
            exit(1);
        }

        // Receive message from server
        memset(buffer, 0, sizeof(buffer)); // Clear buffer before receiving
        checkRecv = recv(clientSocket, buffer, sizeof(buffer), 0);
        if (checkRecv < 0)
        {
            printf("[-]Error in receiving data.\n");
        }
        else
        {
            printf("Server : %s\n", buffer); // Display received message from server
        }
    }

    return 0;
}
```
server.c
```cpp=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#define PORT 4444
#define IP_ADDRESS "127.0.0.1"

int main()
{
    int serversocket; // sockfd => socket()
    struct sockaddr_in serverAddr;
   
    int newSocket; // sockfd, accept()
    struct sockaddr_in newAddr;

    socklen_t addr_size; // accept()
    int checkbind, checklisten, checkRecv; // bind(), listen(), recv()

    char buffer[1024]; // recv(), send()
    pid_t childpid; // fork()

    // Create server socket
    serversocket = socket(AF_INET, SOCK_STREAM, 0);
    if (serversocket < 0) {
        perror("[-]Error in creating Server Socket.");
        exit(1);
    }
    printf("[+]Server Socket is created.\n");

    // Prepare the sockaddr_in structure
    memset(&serverAddr, '\0', sizeof(serverAddr));
    serverAddr.sin_family = AF_INET;
    serverAddr.sin_port = htons(PORT); // host to net short
    serverAddr.sin_addr.s_addr = inet_addr(IP_ADDRESS);

    // Bind the server socket
    checkbind = bind(serversocket, (struct sockaddr*)&serverAddr, sizeof(serverAddr));
    if (checkbind < 0) {
        perror("[-]Error in binding.");
        exit(1);
    }
    printf("[+]Bind to port %d\n", PORT);

    // Listen for incoming connections
    checklisten = listen(serversocket, 10); // backlog of 10 clients
    if (checklisten == 0) {
        printf("[+]Listening....\n");
    } else {
        perror("[-]Error in listen.");
        exit(1);
    }

    while (1)
    {
        addr_size = sizeof(newAddr);
        // Accept an incoming connection
        newSocket = accept(serversocket, (struct sockaddr*)&newAddr, &addr_size);
        if (newSocket < 0) {
            perror("[-]Error in accepting connection.");
            exit(1);
        }
        printf("Connection accepted from %s:%d\n", inet_ntoa(newAddr.sin_addr), ntohs(newAddr.sin_port));

        // Fork a child process to handle the client
        childpid = fork();
        if (childpid == 0) {
            // Close server socket in the child process
            close(serversocket);

            while (1)
            {
                // Receive message from client
                memset(buffer, 0, sizeof(buffer)); // Clear the buffer
                int checkRecv = recv(newSocket, buffer, sizeof(buffer), 0);
                if (checkRecv <= 0) {
                    break;
                }

                if (strcmp(buffer, ":exit") == 0) {
                    printf("Disconnected from %s:%d\n", inet_ntoa(newAddr.sin_addr), ntohs(newAddr.sin_port));
                    break;
                } else {
                    printf("Client : %s\n", buffer);
                    // Send message back to client
                    send(newSocket, buffer, strlen(buffer), 0);
                }
            }
            // Close the client socket
            close(newSocket);
            exit(0);
        }
    }

    // Close the server socket (this point is never reached unless the server is terminated)
    close(serversocket);

    return 0;
}
```
## lab3
:::spoiler
### OS Lab3 Multithreading
1. 建立1個thread進行矩陣相乘&利用system call分配thread給最後一個core
2. 透過4個threads加速矩陣相乘

----

#### Example
![image](https://hackmd.io/_uploads/H11Z0UBHJg.png =57%x)


----
這些函式都屬於pthreads函式庫，它們並不屬於 GCC 編譯器的部分，而是獨立於標準函式庫之外的額外函式庫。因此，在編譯時，必須告知編譯器連結該函式庫。
* [pthread_creat](https://man7.org/linux/man-pages/man3/pthread_create.3.html)
* [pthread_join](https://man7.org/linux/man-pages/man3/pthread_join.3.html)
* [pthread_exit](https://man7.org/linux/man-pages/man3/pthread_exit.3.html)
* ```gcc -o <execute> <C_filename> -lpthread```

---

#### lab3-1
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/syscall.h>
#define SIZE 80

int arr[SIZE][SIZE];
int result[SIZE][SIZE] = {0};
bool isStart = false;
typedef struct my_pid
{
    int pid;
} my_pid;

/* don't change */
void readMatrix()
{
    FILE *fp;
    fp = fopen("number.txt", "r");
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            fscanf(fp, "%d", &arr[i][j]);
        }
    }
    fclose(fp);
}

/* don't change */
void multipfy()
{
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            for (int k = 0; k < SIZE; k++)
            {
                result[i][j] += arr[i][k] * arr[k][j];
            }
        }
    }
}

/* don't change */
long sum()
{
    long ret = 0;
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            ret += result[i][j];
        }
    }
    return ret;
}

/* don't change */
void diff(struct timespec start, struct timespec end)
{
    struct timespec temp;
    if ((end.tv_nsec - start.tv_nsec) < 0)
    {
        temp.tv_sec = end.tv_sec - start.tv_sec - 1;
        temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
    }
    else
    {
        temp.tv_sec = end.tv_sec - start.tv_sec;
        temp.tv_nsec = end.tv_nsec - start.tv_nsec;
    }
    printf("Time = %ld seconds and %ld nanoseconds\n", temp.tv_sec, temp.tv_nsec);
}

int getLastCore()
{
    /* code */
}

void setTaskToCore(my_pid *pid) /*將Thread綁定到指定core*/
{
    int core = getLastCore(); /*獲得最後一個core編號*/
    while (pid->pid == 0);    /*等待Thread取得PID*/
    /* code */
}

void *child(void *arg) /*子執行緒*/
{
    long *ret = calloc(1, sizeof(long));
    my_pid *pid = (my_pid *)arg;
    // pid->pid = // tid

    // printf(); // pid
    // printf(); // tid

    /* don't change */
    while (!isStart);
    multipfy();
    *ret = sum();
    /* ------------ */

    // pthread_exit();
}

int main()
{
    pthread_t thread;
    void *ret;
    my_pid pid;
    struct timespec timeStart, timeEnd;

    // printf(); // pid
    // printf(); // tid

    readMatrix();

    // pthread_create();

    setTaskToCore(&pid);

    sleep(1);

    isStart = true;
    clock_gettime(CLOCK_REALTIME, &timeStart);

    // pthread_join();

    clock_gettime(CLOCK_REALTIME, &timeEnd);

    // printf(); // verify the answer
    diff(timeStart, timeEnd); // time spent

    return 0;
}
```

----

#### 3-1 result

![image](https://hackmd.io/_uploads/B1e7CISB1l.png =70%x)


----
#### Hint
```
getLastCore function
   system(“grep -m1 \”cpu cores\” /proc/cpuinfo > CPUINFO”);
   //讀取CPUIFO，取得CPU核心數量
   
tmp-48-1 : 將ASCII碼轉換成整數並減去 1（因核心編號從 0 開始）

setTaskToCore function
   sprintf(tmp, “taskset -cp %d %d”, core, pid->pid);
   system(tmp);

child funtion
   syscall(SYS_getpid); // process id
   syscall(SYS_gettid); // thread id
```
---

#### thread lab2
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/syscall.h>
#define SIZE 80
#define THREAD 4

int arr[SIZE][SIZE];
int result[SIZE][SIZE] = {0};
bool isStart = false;

/* don't change */
void readMatrix()
{
    FILE *fp;
    fp = fopen("number.txt", "r");
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            fscanf(fp, "%d", &arr[i][j]);
        }
    }
    fclose(fp);
}

/* don't change */
long sum()
{
    long ret = 0;
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            ret += result[i][j];
        }
    }
    return ret;
}

/* don't change */
void diff(struct timespec start, struct timespec end)
{
    struct timespec temp;
    if ((end.tv_nsec - start.tv_nsec) < 0)
    {
        temp.tv_sec = end.tv_sec - start.tv_sec - 1;
        temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
    }
    else
    {
        temp.tv_sec = end.tv_sec - start.tv_sec;
        temp.tv_nsec = end.tv_nsec - start.tv_nsec;
    }
    printf("Time = %ld seconds and %ld nanoseconds\n", temp.tv_sec, temp.tv_nsec);
}

void multipfy(int startIndex, int endIndex)
{
    /* code */
}

void *child(void *arg)
{
    // printf(); // pid
    // printf(); // tid

    while (!isStart);
    // multipfy();
}

int main()
{
    pthread_t *threads;
    struct timespec timeStart, timeEnd;

    // printf(); // pid
    // printf(); // tid

    readMatrix();

    threads = (pthread_t *)malloc(THREAD * sizeof(pthread_t));
    for (int i = 0; i < THREAD; i++)
    {
        // pthread_create()
    }

    sleep(1);
    isStart = true;
    clock_gettime(CLOCK_REALTIME, &timeStart);

    for (int i = 0; i < THREAD; i++)
    {
        // pthread_join();
    }
    clock_gettime(CLOCK_REALTIME, &timeEnd);

    printf("Sum = %ld\n", sum()); // verify the answer
    diff(timeStart, timeEnd);     // time spent

    return 0;
}
```
---

關於Thread分配工作 (child函式) :
SIZE = 80, THREAD = 4
1. 執行緒平分列數 : SIZE/THREAD = 80/4 = 20
2. ==0~19列==
第0個執行緒(threadIndex = 0) :
startIndex = 0x20 = 0, endIndex = (0+1)x20 = 20
==20~39列==
第1個執行緒(threadIndex = 1) :
startIndex = 1x20 = 20, endIndex = (1+1)x20 = 40
==40~59列==
第2個執行緒(threadIndex = 2) :
startIndex = 2x20 = 40, endIndex = (2+1)x20 = 60
==60~79列==
第3個執行緒(threadIndex = 2) :
startIndex = 3x20 = 60, endIndex = (3+1)x20 = 80

---

#### 2 result

![image](https://hackmd.io/_uploads/SJDuAISHye.png =70%x)

通常主執行緒 (此例為TID : 4848)，會做一些初始化工作（例如讀取矩陣），然後創建子執行緒來執行矩陣的計算工作

----
:::

:::spoiler number.txt
 93   8  73  64  29  11  85  69  72  19  24  74   8  97  57  48  51  53  73   9  61  91  17  48  90  31  15  30  34  10  86  26  69  11  42  97  21  78  18  45  97  93  70  56  89  26   4  91  31  28 100  91  18  68  39  59  98   5  40  83  66  25  61  34  35  54  83   8  31  52  52  27  44  73  35  32  99  90  23  29  17  74  19  86  41   9  44  38  65  83  21  82  59  81  16  46  86  50   5  16   1   8  95  96  80  29  27  78  18   1  58  86  26  77  23  66  37  66  56  54 100  28  35  58  60  50  55  45  51  59  60   3  66  54  98  46  34  25  75  51  77  33  88   3   9  10  20  97  27  75  50  26   2  85  36  61  86  90   5  89  49  65  91  14  70  89  11   4  65  86   6  93  18  94  47  78  55  67  74  82  41  76  59  95  12  94   7  49  84  12  37  84  28  28  49  49  16  60  52  32  97  58  24  14   3  71  43  57  37  68  90  29  43  49  75   6  42  82  55  77  45  43  60  72  70   9  72  37  20  24  68  16  81  44  81  35  14  75  43   2  42  33  82  37  33  57  42  74  90  48   3  34  91  14  57  12  74  28  49  93  51  68  60  83  11  92  69  76  66  12  29  60  44  11  96  76  67  89   1  56  37  55  41  27  69  97  38  42  24  38  87  27  58  98  61  20  90  30  96   7  41  76  18  36  86  13  11   4  54  63  11  90  18  51  68  86  99  57  27  75  47  65   1   4  63  61  23   4  42  70  62  82  46  80  17  83  44  79  87  97  42  97  86  11 100   5  96  98  62  74  72   8  91  24  63  53  37  37   8  78   7  69  12   4 100  80  86  44  11  24  40   4  73  78  14  72  82  61  21  95  34  93  54  24  68  16  28   4  53  35  34  11  56  45  66  55  76  51  50  86  27  90  89  99  19   2  22  52  62  42  47  48  86  52  23  54  68  51   9  72  37  42  82  44  86  99  99  62   1 100  47  27  41  88  77  59  41  98  11   3  92   9   2  77  60  24  82  79  26  91   2  63  32  35   6  70  33  56  83  34   8  81  60  48  68  89   7   9  86  69  63  77  29  64   6  40  39  87  19  65  29  20  79  13  55  36  82  39  44  64  72  51  44  84  98  64  72  56  24  57  76  86  86   4   1  91  44  91  29  14  55  10  85  85  22  91  73  55  30  16  18   1  18  13  36  67  28   7  23  51  16  50  88   1  54  88  43  49  79  23  14  85  32  50  22   5  41  94  59  22  61  28  74  78  41  10  96  20  16  70  71  83  20  58  35  25  98  77  25  28  52  38  64  35  87  85  92  79  30  50 100  90  78  74  19  70  35  67  89  50  36  11  85  55  21  19  31  18  48  55  97  51  44  60  85  83  45  76  61  26  78  13  68   7  38  86  76  72  52  16  73  40  79  57  94  99  76  77  68  23  31  64  73  27  23   9   9  19  37  21  97  14  85  64  20  22   1  47  93   5  14  66  44  92  22  89  42  49  65   9  23  48  24  47  74  99  56  34  17  44   6  65  57  91  28  28  12  29  74   5  85  39  22  28  31  43  16  72  44  33  33  66  80  56  13  53  54  20  38  23  63  43  87  71  33  67  98  97  95  23  53  79  61  74  58  43  68  73  15  11   5  99  77  36  54  41  40   8  60  77  30  22  20  16  44   4  34  41 100  28  15   4  58  27  77  67  70  45  92  36   7  48  34  35  84  87  75  23  46  86 100  75  59  71  43   2  26  76  94  78  56   8  81  65  87  58  32  56  54  23  43  12  70  76  47   5  14  73  28  60  11  79  34  69  49  28  23  74  56  16  51  11  76  84  27  62  41  58  69  46  32  11  57  54  38  55  58  51  80  37  10  90  15  96  58  15  75  32  89  30  48  91  92  75  26  19  36  66  28  56  63  60  66  20  65  55  26  74   5   5  11  67  94  25  14   4  40  88  87  80  70  34  22  61   8  48  31  95  65  59   2  28  70  67  99  34  21  24  59  78  81  69  96  26  46   9  81  37  48  68  68  69  53  41  30  13  40  60   7  57  70   9  84  39  27  34  24 100   9  83  29  41   3  24  67 100  84  47  36  83  66  55  52  19  96  33  31  87  44  89  43  14  49  78  52  76  63  76  27  72  10   7  12  12  30  30  12  65  29  99  47  94  54  98  12   1  30  42  87  74  31  82  87  79  59  90   6  22  17  84  45  26  90   8  90  71  38  53  35  66  51  82  59  56  31  71   8  13  64  47  86  94  28  24  25  38  65  82  59  82  66  55  59   7  63  48  30 100  52  64  17   3  97  75  10  80  97  18  92  61  64  29   6  91   4  82  28  68  64  39   1  81  45  12  39   7  11  68  58  63  84  26  65  80   1  74  11  49  43   2  61   6  82  19  48  85 100  28   5  63  66   5  95  62  68  34  69  79   1  78  41  84   4  57  16  56  82  26  56  25  80  17  30  61  35  78  98  34   5   2  49  22  58  95  83  26  28   3   4  81  33  96  16  88  52  83  43  33   9  50  57  40  66  39 100  52  68  49  38  72  50  38  45  60  32  79  37  12  34  92  44  66  87  59  53  38  42  47  22   2  96  79  41  14  69  92  65  36  41   2  59  42  91   3  53  23  33  41  34  66  32  77  31  70  87  35   7  80  33  81  81  81  59  73  94  27  17  10  14   9  64  72   2  54  74  55  76   6  95  61  24  79  89   6  48  28  41   7   7  25  87  40   5  97  12  98  75  80   8  88  88  71  59  90  24  84  96  52  41  90  64  64  20  53  70  68  80  62  74  38  86  12  77  91   8  41  40  82  20  47  21   8  69  79  49  45  62  44  48  54  85  11  18   5  63  39  72  94 100  97  84  85   8  60  27  67  52  67 100  72  65  20  31  34  98  79  30  11  74  77  64  58  87  33  62   2  71  85  47  70  33  30   7  92  42  33  58  93  51  57  64  16  76  46   1  25  76  82  35  49  58  51  59  96  83  72  97  54   9  96  75  41  25  81  85  18  66  42  11  16  51  26  83  78  72  83   3  99  64  89 100  73  91  58  69  74  81  17  27  89  12  53  82  89  34  66   6  99  59  68  66   9  94  49  39  17  83  93  67  99  81  66  71  24  75  91  97  56  60  75  96  71  27  77  11  60  94  69  10  53  36  76  13  81  76  51  49  58  43  16  56  76  81  79  99  56  21  47  63  80  21  58  51  99  35  13  11  28  81  20  80  69  47  45   1  22  95  50  80  90  65  87  17  97  17  67   4  38  13  66  17  85  24  19  83  58  32  93  37  64  65  69  84  11  13  85  33  59  86  64  48  50   2  16  98  19  82   2  56  94  67  24  78  90  43  13  99  26   5  36  41  69   4  25  32  68  61  64  26  46  79  26  47  80  41  96  50  23  97  57  16  16  81  46   5  75  58  56  52  14  91  92  35  46  68  66  65  80  81  90  77  59  15  23  90  56  19  92  78  67  48  45  82  80  42  39  54  51  94   5  65  36  49  99  33  68  64  97  48  96  86  24  54   1  99  95   8  69  86  37  35  86  33  69  65  75   7  71  77 100  27  93  35  75  43  67  43   6  15  42  53 100  65   6  52  63  53  59  83  38  47  18  23  80  86  40   6  92  10  82  43  36  27  29  11  69  47   5  27  61  46  79  60  62  85  64  77  89  22  59  26  69  28   1 100  13  40   5  56   1  38  98  36  64  78  46  33  24   2  59  84  99  37  96  13  73  59  89  61  32  99  39 100  27  91  51  39  82   7  47  82  45  96  17  60  74  15  44  97  68  54  81  67  91  28  79  15  86  19  28  17  17  18  69  43  60  19  34  41  26  80  74  22  75  90  33 100  56  77  97  24  30  29  42  72  56  72  39  41  42  66   9  58  83  77  53  94  48  86  34  25  17   7  98  43  48  30  43   4  58  39  79  88  19  72  11  74  95  49  66  36  66  26  93 100   3  97  93   2  82  26  26  50  84  23  93  32  52  35  87  10  25  17  49  95  88  11  20  82  60  37  17  25  62  61  25  16  58  17  17  91  95  42  41  78  16  85  61  68  71  47  29  47  63  29  41   2  39  60  35  50  96  51  27   9  64  51  25  73  19  41  63  13  35  55  43  50  91   3  69  61  50  49  59  64  29  99  18  20  10  52  69  57   3  95  66  18  97  42  90  16  82   4  80  68  11  22  18   1  25  38  14  26  87  72  89  15  71  58  34  32  10  55  89  64  49   6  81  98  47  70  13  80  25  44 100  35  66  17  36  90  54  49  67  92  20   7   7  42  65  92  74  74  46  14  37  47  71  17  44  69  38   8 100  14  51  99  49  16  15  36  57  21  84  23  12  55  30  70  97  94  14  22  19  59  87  55  57   9  23 100  77  12   7  76  25  10  75  25  77  41  60  34  61  95   8  25  50  89  94  98  34   7  71  52  18   9  58  74  17  80  26  93  43  84  68  20  93  94  44  70  35   4  55  47  50  62  71  99  51  17  48  84  75  18  36  92  26  93  18  94  25  95  86  67  78   6  38  23  51  82  44  85  37  98  32  86  59  54  37  61  70  84  97  97  54  84  40  31  28  57  25   4   3  62  23  81  67  60   3  70  41  46  54  29  95  37  67   5  43   3  66  64  38  14  60  91  97 100  22  76   8  98  80  11  59   2  43  78  61  97  47  54  94  52  82  88  41  48  92  83   2   9  98  40  74  10  30  70  61   3  98  68  52  77  30  11  78  24  40  38  20  38  91  13  89  25  52  81  72  96  15  26   4  13  65  30  22  46  51  82   1  48   1  52  24  83  14   1   6  53  91  78  90  33  90  31  57  94  11  81  89  26   6  44  38  70  73  11  67  24  44  67  71  96  71  95  78  84  47  36  89  37  13  78  70  54  60  78  99  71  58  87  96  15  31  85  36   3  47   3  78  42  69  49  37  39  95  67  75  41   2  63  30  66  92  51  71  52  28  70  22  38   8  69  52  38   5  88  93  51  90  70  92  10  70  80   1  64  46  75  57  99  37  86  16  28  36  87  31  15   8  52  52  15  20   4   5  76  43  97  26  32  18  69  93  88  49  93   3  46  19  11  45  55  48  60  35  35  46  65  50   5  69  53  20  40   8  24  16  50  72  93  33  89  62  26  28  62  70  83   7  89  93  51  95  41  63  81  27  60  46  76  65  66  81  84   5  88  59  72  38  30  65  22  70  78  47  98  39  17  32  97  57  24 100  51  16  62  32  43  21  29  70  85  94  50  20  50  90  78  22  27  59  86  48  29  63  47  78  53  15   9   1  71  84 100  73  52  61   4  46  34  32  15  18  77  17  90  27   6  19 100  84  78  85  83  58  99  81  87   3  95  95   3  17  78   3  42  81  15  45  26  48  29  93  18  57  61  59  35  66  77  34   1   6  18  35  63  68  16  49  70  62  95  73  31  25  27  72   5  41  68  31  41  96  75  10   5  35  68  39  52  96  73  52   2  42  38  16  10  53  17  79  67  11   3  97  35  29  68  92  22  35  74  14  83  48  75  87  82  94  77  85  89  49  88  90  91  25  58 100  78  74  30  44  84  33  92  71  13  59  14  86  45  87  51  79  86  25  17  19  70  94   3  59  94  90 100  84  14  57  35  43  30  65  38  66  49  29  88  13  39   1  51  36  39  53  14  24  30  83  94  99  28  96  57  21  37  57   5   2  65  91  45  47   7  82  12  55  11  51  20   1   3  22  36  41  74   2  16   3  84   9   2  11  56  10  31  44  18  87  45  83  30  89  81  36  23  44  43  85  94  62  85  96  35  21  88   8  22   3  63  57  63  16  67  70  25  49  13  95  88  57  29  17  98   9   4  72  52  46  56  97  59  92  92  93  12  31  53  85  33  15  41  47  30  59  16   6  60  28  52  99  36  80  67  33  40  70   4  91  16  11  39  74   3  82  19  66  12  71  51  96  85  43  42  66   2  57  23  13  84  75  11  20  54  77   4  94  98  60  36  13  70  27  39  72   8  57  38  20  79  40  15  63  82  57  80  35  65   2  47   1  76   9  20  82  37  75  27  35  34  14  99   4  40  37  27  48  45  16  19  23  55  33  37  89  41  68  23   6  70  22   6  97  82  77  78  19   3   4  53  37  70   3  92   9  92  70   8  36  86  26  11  92  11  99  80  51  67  55   8  88  28  65  84   9  93  14  27  96  69  31  32  38  34  75  47  25  44  54  12  81  80  74  25  42  73   4  92  91  10  52  78  37  16  61  46  61  26  24  56  95  55  39  32  40  13  30  64   8  84  75  41  15  49  65  56  73  20  99  63  30  50  92  18  18   4  15  78  30  39  85  24  93  23   7  84  87  37  47  46  72  73  38  86  73   2  93  97  74  43  59  55  45   2  72  14   6  39  43  35  77  27  10  21  49  16   4  87  52   2  32  75  74  22  12  99  23   4  95  48  99   6   2  43   7  26  56  64  64  98  98  92  24  59  12  24  75  15  62  78  68  45  53  41  66  64  91  41  20  38  88  18  43  42  12   1  19  67  65  82  16  14  73  91  73  36  66  99   2  27  76  69  71  80  61  89  96  52  29  15  89  68  84  83   9  95  35  27  13  99  60  28  65  84  70  37  19  35  87  72  61  14  40  83  94  53  23  41  56  51  55  96  19  90  78  79  84  64  58  48  15  17  75  79  53  96  67  23  30  53  95  42  66  86  76  11  38  99  51  45   1  57  40  71  46  69  50  81  33   7  28  47  75  54  77  27   1  43  50  30  47  96  23  12  81  99  75  71  49  77  15  49  34   7  20  31  75  21  64  59  79  43  57  53  49  33  32  49  75  33  31  21  28  53  85  60  51  11  82  99  87  49 100  72  55  19   3  81  91  18  92  69  60  48  73  60  81  56   9  55  88  39  28  67  91  12  79  94  22  12  44  60  60  43  32  66  13  86  99   3  55  90  23  14  37  48  26  17   3  34  24  43  24   3  61  66  14  91  59  87   3   3  98  14  97  29  80  10  66  30  12  20  19  87  86   7  34  11  76  88  96  51  82  19  53  43  84  18  33  95   4  87  49  53   1  45  34  80  54  99  61  18  19  79   4  56  37  89  66  12  76  61  62  58  31  66  52  66  83  36  60  38  23   8  91  23   5  24  54  58  22  14  27  92  44  30  47  80  70  64  44  46  76  57  55   6  23   6  72  57  41  83  95  15  43  85  37  47   8  42  56  81  55  83  25  50  64  23  82  34  87  25  31  14  33  85  20   7  90  43  64  82  77  58  97  19  42  85  17   1  27  73  33  33   7  57  35  22  32  16  55  70  92  85  83  24  21  54  31  62  48  94  44  25   3  92  95  96  76  12  96  54  36  80  39  42  89  73  15  20  40  70  89  31   6  71   6  27  77  36  88  24  81  83  48  35  74  43  30   2   6  77   7  41  57  97  34  45  69  48  64  60  69   4  90  75  26  96  53   2  83  92  78  16  27  77  50 100  71  80  53  76   8  12  68  64   8   1  60  29   1  75  88  69  78  78  95  56  25  99  57   7  91  86  74  17  63  24  68  85  55  73  61  62  84  80  78  91  33  37  19  33  12  59  53  41  36 100  96  12  98   5  18  40  90  44  56   4  19  76  89  25  48   1  38  83  32  15  25  64   4  96  48  15  54   1  55  41 100   3  52  49   7  21  89  48  64  44  52  82  71  92   6  70  44  96  52  75  10  77  39  13  24  86  79  77  38  86  17  37  88  20  86  46  40  74  93   4  69  96  37  40  87  95  61  30  90  13   5  51  41  95  64  64  80  94  40  70  79   8   6  18  27  43  63  66  68  56  21  89   3  10  80  90  56  40  71  45  52  27  95  44  21  10   7  53   4  98  22  34  57  79  52  83  74  14   1  93  21  73  81  24  34  12  65  89  52  35  33  55  14  80  99  86  41  57  38  96  55  11  30  63  42  81  98  15  46  98  59  67  22  40  42  56   3   6  44  54  40  29  61  53  60  59  91  52  67  28  48  73  91  29  36  32  61  33  98  58  82  56  24  55  47  65  10  50  70   6  55  62  86  15  66  97  25  56  48  92  36  47  64  78  27  99   9  87  83  58  45  64  65  20  19  64  37  80  13  58  37  19  19  22  34  37  18  58  92  18   1  79  64  65  56  91  15  16  29  98  25  25  13  90  45  83  53  33  63  17  90  99  35   9  73  68  97  42  78  40  59  78  19  75  42  26  65   9  42  45  58  66  70  70   7  66  53  59  98  67  27  87  17  62  47  41  81  43  83  58  83  41  36  53  15  29  78  31  37  71  28  94  89  49  16  95  14  20   6  63  38  32  49  54  93  48  47  74  90  29  31  24  21  18  76  36  99  54  18  87  76  45  33  64  93  48  59  58  19  64  20  56  95  21  61  88  68   7  13   9  35  95  33  56  13  60  43  11  65  12  97  41  57  29   4   1  28  14  59  46  77  30   1  24  50  14  63  69  20  75  78   7  69  62  62  33  73  56  95  38  67  92  30  75  72  33  28  52  47  86  97  75  67  50  98  69  63  60  37  34  86  66  40   7  79  53  39  52   8  86  89  27  29  18   1 100   2  28   3 100  65 100  75  84   1  24  52  63  36  88  96  73  54  88  79  32  40  70  35  48  55  23  26  83  92  78  34  46  58  37  45  22  88  71  57  88  95   8   2  82  96  49  54   1  36  33  84  76   2  19  75   8  93 100  90  37  77  23  82  34  59  26   8  46  97  16  85  43  24  86  24  71  35  77  23  70   9   6  97  62  76  71  69  21  70  58  57  99  33  38  84  43  63  43  41  11  59  25  53  82  63  76   4  97  53  26  18  13  31  15  75  59  85  43  79   7  53  35  57  37  72  92  31  86  35  71  97  45  48  49  78  10  77  81  58  29   6  27  41  88  41  67  98  78  62  76  36  66  10  44   2  33  35  32  19  21  55  67  17  54  67  94  15  43  26  24  71  83  50  64  23  43  30  20  72  91  96  59  56  57   2   9  42  88  93  12  61  47  78  29  52  44  23  66  87 100  89   9  83  90  72   5  32  54  76   3  44  71  13 100  80  14  60  21  54  52  32  66  50  61  94   1   4  68  18  42  68  58  51   2  48  74  58  79  27  33  34  23  56  46  22  35  12  33   7  17  85  38  82  34  98  27  87  53  95   4  95  14  62  97  15   9  22  72  39  49  56  24  71  11  22  44  45  33  76   3   1  12  40  34  46  89  60  32  94   6  87  40  19  48  88  33   8   9  56  99   9  12  22  31  22  43  26  19  27   2  21  27  65  13  60  10  53  72  93  46  77  32  37  48  31  24  80  39  33  88  89  93  51  10  24  24   5  49  42  31   2  15  58  67  79  69  28  31  92  73  29  21  56  17  68  86  41  99  76  25  86  64  17  36  26  92  60  30  41  53  60  94  19  69  12  97  90  92  80  81  64  60   1  71  76  20  56  16  19  32  40   4  47   9  92  72 100   3  53  92  55  13  38  74  33  49  22  22  92   1  55  55  60   7  77  36  27  33   3  45  16  95 100  14   3  43  38  54  45  90  98  52   2  87  25  87  35  46   8  27  99  14  33  58  21  10  45  47  94  48  43  61  42  94  74  96  37  11   1  81   1  50  32  54  36   8  40  23   6 100   1   4  13  33  13  33  94  10  31  39   9  25  99   2  19  25  97  55  35  49  35  35  99  19  41  34  26  80  56  83  31  56  38  44  41  51  28  86  12  11  77  20  35  75  21  53  51  69   7  86  17  94  72  15  64  12   1  89  44  56  24  74  64  61  69  56  11  49  41  74  59  69  93  93  96  13  46  46  81   4  31  50  97   3  64  60  66  16   1  61  24  24  87  87  84  55  42  47   3  34  20  61   3  65   6  50  29  51  95  62  54  26  11   3  80  26  62  97  42  14  58  65  89  44   3  73  50  96  71   5  81  42  17  35  58  22  84  87  72  79 100  78   4  10  80  35  87  93  31  80   7  88  96  47  83  98  71  33  93  41  89  26  35   5  60  92  27  44  30  98  22  29  75  77  90   6  11  29  99  93   8  57  81   4   3  15  53  74  47  98  66  35  23  52  92  82  96  18  25  25  67  98   6  94  74  95  99  36  75  49  29  83  57  61  38  60  75  90  85  74  87   2  60  61  54  51  43  49  68  19  25  87  69  30  80  94  77  78  82  51  27  10  85  35  22  22  46  48  64  30  21   2  84  33  63  89  35  57  89  55  27  13  41  95  95  20  89  71  97  70  73  75  31  58  62   4  79   7  51  42  37  72  44  72  56  58  60  90  14 100  44  40  12  84  87   6  55  27  28   4  48   1  78  78  58  39  33  88  46  83  30  34   6  25  57  61  82  68   3  95  67  46  86  30  82  72  88  36  98  15  39  97  67  69  26  24  59  58  12  56  41  93  41  46  17  97  59  50  16  61  44  82  58  81  12  39   5  99  27  54  65  65  51  32  85  76   7  44  34  18  51  26  62  92  23  30  40  81  79  56  93  22  37  51  55 100  41  59  98  67  12  63  84  14  46  68  90  52  63  75  22  14 100  83   5  22  13  96  55  91  51  47  65  40  97  71  39  38  29  89  56  92   3  39  58  48   7  47  51  21  73  72  34  24   7  90  97  71  86  51  13  88  50  29  27  46  99  66  35  79   6  91  23   8  81  80  55  39  78   5  60  50  29  93  25  35  35  21   5  20  24  17  59  73  46  86  70  96   3  57  75   8  99  97  15  79  28  21  18   5  77  29   6   5  73  30  91   7   2  47  78  25  16  37  49  13  22  19   8  76  75  34  83  25  30  49  55   9  69  72  13  45  52  18   2  25  99  44  31   1  91  61  25   6  97  74  18  70  44  25  45  70  59  27  94  40  75  48   1  95  72  13  91  75  83  44  99  81  88  82  33  78  42  58  35  90  83  52  59  78  28   3  47  38  81  92  30   7  91  30  53  14  94  43  89  76  39  87   9  26  20  41  55  61  50  89   2  84  92  60  61  71  14  59   9  46   2  90  52  93  71   4   6  64  99  94  40  37  33 100  14   4  92  68  17  42   8  18  77  99  78  38  69  43  48  29  89  50  70  40  42  40  96  99   4  46  45  95  34  29  94  47  32  85  14  48  78  73  66  55  71  95  44  91  37  43  72  25  92  41  17  85  33  64  36  36   9  80  82  42  60  27  40  91  63  53  91  41  25   8  47  47  54  42  89  90  84  60  67  28  53  35  12  85  50  47  72  10  78   5  51  37  31  42  28  45  94  70  37  70  77  83  68  30  76  56  71  60  68  89  87  72  75  50   8  24  97  31  33  26  35  35  63  17  76  42  61  21  11  98  42  39  32  61  20   8  69  90  67  36  31   5  59  57  54  66  33   2  96  65  28  82  52  90  98  79  31  58  52  93  55  45  31  87   6  50  94  74  91  12  61  73  68  19  30  21  84  62  75  31  78   2  12  81  91   9  60  73  18  11  17  25  55  47  63  12  48   8  85  38  19  45  11  86  63  92  58  98  53  32  28  82  33  91  63  75  51  74  99  69  36  15  45  42  13   7  54  60  14  38  50  32  35  60  69  97   3  78  47   7  10  26  88  94  17   2  21  19  75  71  87  10  38  31  52  50  37   5  10   2  94  59  33  28  70  53  77  72  83  23  30  44 100  69  89  16  71   9  35  45  32  73   7  69  56  58  18  44  62  27  46   7  37  30  35   6  35  11  29  17  85  10  60  84  79  48  52  49   9  38  45  40  62  51  60  69   8  77  13  21  56  10  28  92  91  14  50  77  76  30  93  60  92   4  95  70   4  46  70  12  35  66   3  97  17  62  65  76  90  29  49  45  90  28  89  81  41  90  57  16  71   2  27  62  57  21  31  60  19  52  71  53  18  25   1  86  38  18  13  28  98  61  72  88  88  60  20  28   1  28  95  72  81  21  33  38  42  16  97  12  19  20  16  36  44  17  73  34  86  86  61  83  46  32  22  86  44  41  65  44  21  60  67   1  80 100  90  73  67  87  36  85  58  52  73  53  68  45  86  53  82  46  87  28  30   9  13  73   1  29  68  21  88  87  74  20  38  63  44   4   1  80  40  58  31  12  11  50   9  48  54  90  94  40  69  23  48  33  47   1  62  66  21   1  52  46  20  89  61  16  44  61  95  84  71  77  47  33  26   7  80  31  49  73  70  17  47  70   2  93  70  63  11  42  15  62  88  35   3 100   2  98  60  48  81  82  24  80  14   1  86  46  31  86  18  52   3  17  21  56  61  42  70  71  84  84  85  23  70  39  22  71  36  33  18  69  67  41  48  80  93  85  25  75  71  95  27  25  63  99  80  23  41  49  46  76  32  30  50  54  20  71  24  55  55  42  23  21  34  22  53  27   7  29   1  29  75  79   5  37  78  36  12  70  84  57  97  67  38  46  20  57  68  96  11  22  37  86  95  22   7  47  48  65  27   1  45   2  31  49  90   8  84   1  29  19  57  77  38  94  22   9  50  89   4  13  63  92  98   9  14  56   7  13  21  33  13  65  86  44  66  76   3   1  76  84  20  85  60   9  30  34  69  32  74  73  44  88  16  93  96  29  48   2  94  20  87  58  37  24  53   2  99  56   2  27  91  73  63   2  33  92  35   2  23   9  74  18  48  41  62  44  22  62  97  15  81  35  72  17  59  25  70  57  32  24  35  74  48  97  75  81  41  62  82  15  22   7  33  69  47  46  12  20   7  61  34  40  95  58  56  53  34  78  62  17   1  48  90  48  45  16  28  85  77  61  51  98  67  35  67  66  81  30  85  87  90  71  26  37  28  34  89  13  63   2  29  63  50  70  62  46  85  42  82  14   2  32  63  21  67  81  86  47  11  22  85  52  92  63  88  71  48  29  83  10  30  63  72  31  32  85  76  69  26  57  82  80  89  96  52  55  77  89  53  87  10  37  90   2  51  30  24  98  58   7   7  39  21  30  70  53  15  97  73  92   6   6  23  94   1  74 100  77  62   4  15  24  92  57  77  43  86 100  40  43  58  99  33  79  28  54  83  94  51  55  38  56  60  60   1  60  86  52  89  99  55  55  22  46  11  98  88  48  98  80  90  55  78  75  85  57  28  67   3  30  21  40  85  32  99  37  44  36  88  32  35  42  38  56  40   1  54  79  48   3  58  90   9  87  64  94  44  91  12  46  21  33  37  57  64  87  94  59  23  33  90  57  27  80  64  66  80  69  44  27  71  54  16  32  40  31  25  35  22  88  32  94  20  68  50  36  55  95  94  77  28  36  85  54  67  48  19  98  69  14  24  39  67  92  70   7  22  46  41  95  86  73  88   5  92  90  92  46  84  38  74  11  25  10  64  43  10  34  40  78  48  15  16  14  58  38  72  80  35  65  26  20  89  66  77  80  55  20  26  38   9  51   1  85  61  16  27  70  50  66  47  49  33  14  14  90   3  38  21  38   2  47   9  90  12  37  69  18   9  46   7  17  97   7  54  57  23  80  26  24  98  24  72  30  37  37  19  40  74  40  29  27  38  89  16   1  78  37  18  86  82  24  54  30  83   7  38   5  39  15  80  36  38  51  17  27  39  87  18  65  26  46  91  15  86   7  15  63  95  84 100  76  60   6  58  42  12  95  46   2  10  25  37  99  27   5  25  17  92  42  81  69  39  72  84  25  30  50  39  24  34  91  99  93  96   8  34   7   3  31   9  64   7  97  62  85  54  39  53  45  80  34  65  19  57  48  95  86  50  33   9  83  23  59  27  70  67  12  29  21  94  37  84  52  85  97  36  38  35  88  34  15  73  99  85  29  98  79  14  47  63  22  81  38  81  59   7  99  70  35  19  63  23  54  14  60  50   1  49  37  41  83  51  65  33  87  94  30  65  59  29  79  33   9  16  65  68  23  63  89   9  81   4  32  86  17  43  35  70  91  23  62  25  73  26  57  11  71  39  75  30  67  54  62  27  21  26  46  95  88  35   4  20  38  87  57   6  29  43  75  71  66  88  96  90  14  52   1  84  42  27  13   8  80  26  87  53  51  32  47  90  66  50  61   3  88  17  61  68  60  87  39  77  75  34  66  88  37  66  23  79  93  88  38  24  13  24  76  16  56  75  57  73  24  70  28  64  38  88  31  49  74  69  25 100   2  91  39  91   8  62  21  52  49  58  28  13  34   3  80  41  77  37  65  53   6  92  16  43  31  46  44  57  67  68  56  20  10  95  10  18   8  30  69   8  40  96  20  25  51 100  65  79  88  29  83  45  73  98  39   3  96  82  59  62  50  67  81  59  13  43  28  20  24  97  27  15  44  46  39  46  97   3  77  84  84  59  80  56   9  19  10  56 100  21  17  49  87  49  60  99  43  87  70  67  35  96  81  31  93  20  76  42  74  52  77   9  11  57  16  71  75  26  26  74  46  94  75  84  42  86  82  37  72  51   3  59  98  35  89  90   6  16  83  32  68  60  40  30  16  56 100  90  33  77  15  78 
:::

### 第一題
```cpp=
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <pthread.h>
#include <unistd.h>
#include <sched.h>
#include <sys/syscall.h>
#include <errno.h>

#define SIZE 80 // 矩陣的大小

int arr[SIZE][SIZE]; // 用於儲存讀取的矩陣
int result[SIZE][SIZE] = {0}; // 用於儲存矩陣相乘的結果
bool isStart = false; // 用於控制子執行緒是否開始計算

typedef struct my_pid {
    int pid; // 儲存子執行緒的 PID
} my_pid;

/*
 * 讀取矩陣資料，從檔案 "number.txt" 中讀取。
 * 檔案格式必須是每行包含矩陣的數值，
 * 各數值以空格分隔。
 */
void readMatrix() {
    FILE *fp;
    fp = fopen("number.txt", "r");
    if (!fp) {
        perror("Failed to open file");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            fscanf(fp, "%d", &arr[i][j]);
        }
    }
    fclose(fp);
}

/*
 * 計算矩陣相乘的結果，將結果存入 result 陣列。
 */
void multipfy() {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            for (int k = 0; k < SIZE; k++) {
                result[i][j] += arr[i][k] * arr[k][j];
            }
        }
    }
}

/*
 * 計算 result 矩陣的所有元素總和。
 * 回傳結果作為 long 型別。
 */
long sum() {
    long ret = 0;
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            ret += result[i][j];
        }
    }
    return ret;
}

/*
 * 計算兩個時間點之間的差異，
 * 並輸出差異時間（秒與奈秒）。
 */
void diff(struct timespec start, struct timespec end) {
    struct timespec temp;
    if ((end.tv_nsec - start.tv_nsec) < 0) {
        temp.tv_sec = end.tv_sec - start.tv_sec - 1;
        temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
    } else {
        temp.tv_sec = end.tv_sec - start.tv_sec;
        temp.tv_nsec = end.tv_nsec - start.tv_nsec;
    }
    printf("Time = %ld seconds and %ld nanoseconds\n", temp.tv_sec, temp.tv_nsec);
}

/*
 * 獲取要綁定的 CPU 核心編號，
 * 此處固定返回核心編號為 1（第 7 核心）。
 */
int getLastCore() {
    return 1; // 綁定到第 7 核心
}

/*
 * 將指定的執行緒綁定到指定核心，
 * 利用 sched_setaffinity 設定。
 */
void setTaskToCore(my_pid *pid) {
    int core = getLastCore(); // 獲得最後一個核心的編號
    while (pid->pid == 0);    // 等待執行緒獲得 PID

    cpu_set_t cpuset;
    CPU_ZERO(&cpuset);
    CPU_SET(core, &cpuset);

    printf("pid %d's current affinity list: 0-15\n", pid->pid);

    if (sched_setaffinity(pid->pid, sizeof(cpu_set_t), &cpuset) != 0) {
        perror("sched_setaffinity");
        exit(EXIT_FAILURE);
    }

    printf("pid %d's new affinity list: %d\n", pid->pid, core);
}

/*
 * 子執行緒的主體函數，負責進行矩陣相乘和總和計算。
 */
void *child(void *arg) {
    long *ret = calloc(1, sizeof(long)); // 用於儲存總和的記憶體
    if (!ret) {
        perror("calloc failed");
        pthread_exit(NULL);
    }

    my_pid *pid = (my_pid *)arg;
    pid->pid = syscall(SYS_gettid); // 獲取子執行緒的 TID

    printf("Process Id: %d\n", getpid());
    printf("Thread Id: %d\n", pid->pid);

    // 等待主執行緒啟動
    while (!isStart);

    multipfy(); // 矩陣相乘
    *ret = sum(); // 計算總和

    pthread_exit(ret);
}

/*
 * 主函數：負責創建子執行緒、設置核心綁定、
 * 啟動計算並計算執行時間。
 */
int main() {
    pthread_t thread; // 儲存子執行緒 ID
    void *ret = NULL; // 用於儲存子執行緒的返回值
    my_pid pid = {0}; // 儲存子執行緒的 PID
    struct timespec timeStart, timeEnd; // 記錄開始和結束時間

    printf("Process Id: %d\n", getpid());
    printf("Thread Id: %ld\n", syscall(SYS_gettid));

    readMatrix(); // 讀取矩陣資料

    // 創建子執行緒
    if (pthread_create(&thread, NULL, child, &pid) != 0) {
        perror("pthread_create failed");
        exit(EXIT_FAILURE);
    }

    setTaskToCore(&pid); // 設置子執行緒綁定的核心

    sleep(1); // 等待子執行緒初始化完成

    isStart = true; // 通知子執行緒開始工作
    clock_gettime(CLOCK_REALTIME, &timeStart); // 記錄開始時間

    // 等待子執行緒完成
    if (pthread_join(thread, &ret) != 0) {
        perror("pthread_join failed");
        exit(EXIT_FAILURE);
    }

    clock_gettime(CLOCK_REALTIME, &timeEnd); // 記錄結束時間

    if (ret) {
        printf("Sum = %ld\n", *(long *)ret); // 輸出矩陣總和
        free(ret); // 釋放記憶體
    } else {
        printf("Error: No result from thread\n");
    }

    diff(timeStart, timeEnd); // 輸出執行所花費的時間

    return 0;
}
```
![image](https://hackmd.io/_uploads/SJ7C_Bu4kx.png)

### 第二題
```cpp=
#include <stdio.h>  // 用於輸入和輸出
#include <stdlib.h> // 提供內存分配和程序退出的函數
#include <stdbool.h> // 定義布林值類型
#include <pthread.h> // 提供多執行緒的函數
#include <unistd.h>  // 提供POSIX操作系統API
#include <sys/syscall.h> // 提供系統調用的接口
#define SIZE 80  // 矩陣大小為 80x80
#define THREAD 4 // 執行緒數量為 4

// 全域變數：儲存矩陣和計算結果
int arr[SIZE][SIZE];
int result[SIZE][SIZE] = {0};
bool isStart = false; // 用於通知執行緒開始計算

/*
 * 讀取矩陣資料到全域變數 `arr` 中
 * 矩陣資料來自檔案 "number.txt"
 */
void readMatrix()
{
    FILE *fp = fopen("number.txt", "r");
    if (!fp)
    {
        perror("Failed to open number.txt");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            fscanf(fp, "%d", &arr[i][j]);
        }
    }
    fclose(fp);
}

/*
 * 計算結果矩陣的所有元素總和
 * 回傳總和
 */
long sum()
{
    long ret = 0;
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            ret += result[i][j];
        }
    }
    return ret;
}

/*
 * 計算兩個時間點之間的差距，並輸出結果
 */
void diff(struct timespec start, struct timespec end)
{
    struct timespec temp;
    if ((end.tv_nsec - start.tv_nsec) < 0)
    {
        temp.tv_sec = end.tv_sec - start.tv_sec - 1;
        temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
    }
    else
    {
        temp.tv_sec = end.tv_sec - start.tv_sec;
        temp.tv_nsec = end.tv_nsec - start.tv_nsec;
    }
    printf("Time = %ld seconds and %ld nanoseconds\n", temp.tv_sec, temp.tv_nsec);
}

/*
 * 矩陣相乘的一部分，計算指定行範圍內的結果
 */
void multipfy(int startIndex, int endIndex)
{
    for (int i = startIndex; i < endIndex; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            for (int k = 0; k < SIZE; k++)
            {
                result[i][j] += arr[i][k] * arr[k][j];
            }
        }
    }
}

/*
 * 子執行緒的函數，用於計算其負責的行範圍內的矩陣乘法
 */
void *child(void *arg)
{
    int threadIndex = *(int *)arg; // 獲取執行緒索引
    int startIndex = threadIndex * (SIZE / THREAD); // 計算開始行索引
    int endIndex = (threadIndex + 1) * (SIZE / THREAD); // 計算結束行索引

    printf("Process Id: %d\n", getpid());
    printf("Thread Id: %ld\n", syscall(SYS_gettid));

    // 等待主執行緒通知開始計算
    while (!isStart);

    // 執行矩陣相乘的部分計算
    multipfy(startIndex, endIndex);

    free(arg); // 釋放動態分配的記憶體
    pthread_exit(NULL); // 結束執行緒
}

int main()
{
    pthread_t *threads; // 儲存執行緒的陣列
    struct timespec timeStart, timeEnd; // 用於記錄開始和結束時間

    printf("Main Process Id: %d\n", getpid());
    printf("Main Thread Id: %ld\n", syscall(SYS_gettid));

    readMatrix(); // 讀取矩陣資料

    // 分配記憶體以儲存執行緒資訊
    threads = (pthread_t *)malloc(THREAD * sizeof(pthread_t));
    if (!threads)
    {
        perror("Failed to allocate memory for threads");
        exit(EXIT_FAILURE);
    }

    // 建立執行緒
    for (int i = 0; i < THREAD; i++)
    {
        int *threadIndex = malloc(sizeof(int)); // 動態分配執行緒索引的記憶體
        if (!threadIndex)
        {
            perror("Failed to allocate memory for thread index");
            exit(EXIT_FAILURE);
        }
        *threadIndex = i;
        if (pthread_create(&threads[i], NULL, child, threadIndex) != 0)
        {
            perror("Failed to create thread");
            exit(EXIT_FAILURE);
        }
    }

    sleep(1); // 確保所有執行緒已準備好
    isStart = true; // 通知執行緒開始計算
    clock_gettime(CLOCK_REALTIME, &timeStart); // 記錄開始時間

    // 等待所有執行緒完成
    for (int i = 0; i < THREAD; i++)
    {
        if (pthread_join(threads[i], NULL) != 0)
        {
            perror("Failed to join thread");
            exit(EXIT_FAILURE);
        }
    }
    clock_gettime(CLOCK_REALTIME, &timeEnd); // 記錄結束時間

    // 驗證結果並輸出
    printf("Sum = %ld\n", sum());
    diff(timeStart, timeEnd);

    free(threads); // 釋放執行緒陣列的記憶體
    return 0;
}
```
![image](https://hackmd.io/_uploads/SJ6R_S_Vke.png)

## lab4
:::spoiler
### OS Lab4 Race condition
* peterson algorithm
* semaphore

----

使用兩個thread分別對一個global variable做100000次的加法與減法運算


----

#### Peterson
```C
#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>

int data = 0;

atomic_int turn = 0;
atomic_int flag[2] = {0};

void *subchild()
{
}

void *addchild()
{
}

int main()
{
    return 0;
}

```

----

#### Semaphor
```C
#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>

typedef struct global_data
{
	int data;
	int count;
	atomic_flag m;
} global_data;
global_data gdata;

void semwait()
{
	while (atomic_flag_test_and_set(&gdata.m))
	{
	};
	// P

	/* --- */
	atomic_flag_clear(&gdata.m);
}

void semsignal()
{
	// V
}

void *subchild()
{
}

void *addchild()
{
}

int main()
{
	return 0;
}
```
:::

### 第一題peterson
```cpp=
#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>

int data = 0; // 全域變數

atomic_int turn = 0; // 用於表示輪到哪個執行緒
atomic_int flag[2] = {0}; // 用於表示執行緒是否希望進入臨界區

void *subchild(void *arg)
{
    for (int i = 0; i < 100000; i++)
    {
        flag[1] = 1;         // 表示執行緒 1 想進入臨界區
        turn = 0;            // 將控制權讓給執行緒 0
        while (flag[0] && turn == 0)
            ; // 等待執行緒 0 結束

        // 臨界區
        data--;

        flag[1] = 0; // 離開臨界區
    }
    return NULL;
}

void *addchild(void *arg)
{
    for (int i = 0; i < 100000; i++)
    {
        flag[0] = 1;         // 表示執行緒 0 想進入臨界區
        turn = 1;            // 將控制權讓給執行緒 1
        while (flag[1] && turn == 1)
            ; // 等待執行緒 1 結束

        // 臨界區
        data++;

        flag[0] = 0; // 離開臨界區
    }
    return NULL;
}

int main()
{
    pthread_t t1, t2;

    // 建立執行緒
    pthread_create(&t1, NULL, addchild, NULL);
    pthread_create(&t2, NULL, subchild, NULL);

    // 等待執行緒結束
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("Final data value: %d\n", data);
    return 0;
}
```
答案 `Final data value: 0`

### 第二題 semaphore
```cpp=
#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>

typedef struct global_data
{
    int data;               // 全域變數
    atomic_flag m;          // 信號量鎖
} global_data;

global_data gdata = {0, ATOMIC_FLAG_INIT}; // 初始化

void semwait()
{
    while (atomic_flag_test_and_set(&gdata.m))
        ; // P 操作：嘗試獲取鎖
}

void semsignal()
{
    atomic_flag_clear(&gdata.m); // V 操作：釋放鎖
}

void *subchild(void *arg)
{
    for (int i = 0; i < 100000; i++)
    {
        semwait(); // 獲取鎖

        // 臨界區
        gdata.data--;

        semsignal(); // 釋放鎖
    }
    return NULL;
}

void *addchild(void *arg)
{
    for (int i = 0; i < 100000; i++)
    {
        semwait(); // 獲取鎖

        // 臨界區
        gdata.data++;

        semsignal(); // 釋放鎖
    }
    return NULL;
}

int main()
{
    pthread_t t1, t2;

    // 建立執行緒
    pthread_create(&t1, NULL, addchild, NULL);
    pthread_create(&t2, NULL, subchild, NULL);

    // 等待執行緒結束
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("Final data value: %d\n", gdata.data);
    return 0;
}
```
答案 `Final data value: 0`