COMP1521 2022T3 Q9 · 并发/线程

COMP1521 2022T3 Q9 · 10 marks · C
知识点: 并发/线程（CONC） · 次: pthread/fseek/均分 · 难度: 进阶
Topic: Concurrency · Source: https://cgi.cse.unsw.edu.au/~cs1521/26T1/resources/practice_exams.html

一句话 / Summary: 5线程均分计算无全局变量无锁

In Sydney, all train carriages have a unique numeric identifier.

A popular game amongst Sydney train commuters is to find some arrangement of the numbers, and
four mathematical operators (+, -, *, /) inserted between them, such that the expression evaluates
to the number 10.

For the purposes of this question, we will assume that there are five digits, and that each operator
is used exactly once. From this, we then have 2880 possible expressions to evaluate. For simplicity,
we will also evaluate the expression left to right , without order of operations.

You have been given 22t3final_q9.c ,
a C program that is supplied with a file containing all 2880 possible expressions (one per line) for a given
five-digit value as a command line argument. At the moment, the program prints out the number of different
expressions that evaluate to 10, but only uses a single thread.

Your task is to modify 22t3final_q9.c so that it creates five new threads to evenly split the work and evaluate the
expressions in parallel. Your modifications must not use any global variables , and must not use any locks or mutexes. You should
instead pass data to the thread, and return data as needed.

Your program must also not load the entire file into memory. Instead, it should read the file line by line.

Each byte of the file should not be read more than once. You may find it useful to have a file descriptor
open for each thread, and to use the fseek library call.

We have provided you with the files 22t3final_q9.h , to provide you with some information about functions you may
find useful, and 22t3final_q9_main.c , which contains a main function to help you test your code, as
well as evaluate expressions. You should not modify these files.

Once complete, the output of your program should look something like this:

make
dcc -pthreads 22t3final_q9.c 22t3final_q9_main.c -o 22t3final_q9
./22t3final_q9 22t3final_q9_examples/15211.txt
Hello from compute thread 0!
Hello from compute thread 1!
Hello from compute thread 2!
Hello from compute thread 3!
Hello from compute thread 4!
288 results found!
Your program created enough threads!
./22t3final_q9 22t3final_q9_examples/54321.txt
Hello from compute thread 0!
Hello from compute thread 1!
Hello from compute thread 2!
Hello from compute thread 3!
Hello from compute thread 4!
32 results found!
Your program created enough threads!
./22t3final_q9 22t3final_q9_examples/69913.txt
Hello from compute thread 0!
Hello from compute thread 1!
Hello from compute thread 2!
Hello from compute thread 3!
Hello from compute thread 4!
62 results found!
Your program created enough threads!

The autotests for this question exist to ensure that your program produces
the correct output, and that it creates five threads. However, they are not
capable of checking whether your program actually evenly splits the work between
the threads.

For this reason, all submissions for this question will be
hand-marked . Solutions that do not evenly split the work between the threads
will be deducted marks .

No error checking is required.

Your program can assume it is always given as argument the name of an existing file.

You may assume that the expressions in the input file are always valid.

You may assume that each line of the input file is 10 characters long, including the newline character.

22t3final_q9_main.c includes a main function to help you test your code.

You may not change the provided 22t3final_q9_main.c file.

You may not change my_main 's prototype.

ie: its return type and its argument types.

Every new thread you create must call the compute_thread_hello function.

You may define and call your own functions if you wish.

Your solution must be in C only.

Your solution must not be in MIPS , C++ , Python , or any other language.

Your program cannot call external programs.

Your program cannot use any of: fork() / exec() , posix_spawn() , system() , or any other similar functions.

Your program may call any functions from the C standard library available by default on CSE Linux systems.

Including but not limited to: stdio.h , stdlib.h , string.h , math.h , assert.h , etc.

🤖 Adapted: write a C program. argv[1] is 5 digits. Of the 2880 arrangements (permute the 5 digits; place a permutation of + - * / between them; evaluate LEFT-TO-RIGHT with real (floating-point) arithmetic; an expression with division by zero does not count), print how many evaluate to 10. (Threading is optional — only the count is judged.)

Verified on the sandbox, cross-checked against an independent oracle, and the oracle reproduces the official examples (15211→288, 54321→32).