# 作業系統lab
## lab2
:::spoiler
### OS Lab2 Process and Socket
###### 了解Process的運作
###### 理解Socket的原理並且實作socket通訊
----
#### Process
----
#### Process lab2-1
----
#### 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
----
#### 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
----
#### Simplified diagram of socket communication
----
#### 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），前面的變數什麼的都會完整被複製過去，然後父子進程在分裂的地方同時進行。
但就算是全域變數，父子進程也不是共用的。
```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!
```
### 第二題
因為父進程跟子進程是同時的，並且沒有誰的權重比較高。
所以輸出可能是亂的
```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");
}
```
### 第三題
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
----
這些函式都屬於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
----
#### 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
通常主執行緒 (此例為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;
}
```
### 第二題
```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;
}
```
## 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`
Sign in with Wallet
Connect another wallet