Programming HW2 - Happy Friends Tree

Programming HW2 - Happy Friends Tree === **Deadline:** - **Soft Deadline**: 11/12 (二) 23:59 - **Hard Deadline**: 11/19 (二) 23:59 Github Classroom Link: https://classroom.github.com/a/HBEROTsP (There are updates that need to be changed on your local file, you may download the updated files from this [link](https://drive.google.com/file/d/1oPqE41VsZO8zwQanzdYhwvoION6MPZRy/view?usp=drive_link), Newest update is on 3rd November, 8:11 p.m.) Github Issues Repository: https://github.com/NTU-SP/SP2024_HW2_release ## Credit This Homework is heavily inspired by, and references Programming Homework 2 from SP Class of 2023, designed by previous TA 魏晧融. ## Message from TA Please start this homework ASAP, or atleast read the spec thoroughly to make sure you know how the implementations should be done. And even then, you are not advised to procrastinate at all, the sooner you ask for help, the more we can provide. As the deadline approach, please do not give up, come to TA hour for assistance. If neccessary, please contact TAs by - class 1: ntusp2024.pj@gmail.com - class 2: ntusp.class2@csie.ntu.edu.tw Also, read this hackmd in dark mode thanks. - scroll to top of page, there should be a paintbrush logo, use it to set to dark mode. PS: don't get scared by the length, **A LOT** of this spec is just tips and examples. ## 0. Story (may be skipped entirely) Not_Tako has many friends, but there are too many people that he gets confused on how they met, and how close they are to him. Please make his tree structure and walk him through the relationship status of all his happy friends to find out which Happy Tree Friends he has. **Implementation 1 & 2: Meet & Check** At the beginning, there is only Not_Tako. He then meets people directly as he is very skilled at socializing (社交恐怖分子). Through those friends, he meets even more people, these relationships form a tree, and he may chat with anyone through a chain of communications (pipe). Not_Tako would like to check what friends he has at any time, so he learns to draw the current tree structure whenever he wants to check. **Implementation 3: Adopt** Some people use pay-to-win when making friends, when someone pays for food for other people, they may adopt the other person. We call this act 認義父, where the entire friend group becomes closer to their 義父. For example, if A adopts B, the entire friend group of B becomes closer to A. **Implementation 4: Graduate** All good things come to an end, when Not_Tako graduates, he will move on in life to meet other friends, hence must gracefully say goodbye to all his current friends, and terminate the entire Happy Friends Tree. This is so that there may be new (and old) friends to be met in the future. **Bonus Implementation: Compare** Unfortunately, some people are not truthful to their friends. ~~As the saying goes, 樹大必有枯枝，人多必有白癡,~~ A lot of fake friends pretend to be weak (裝弱), Not_Tako does not want these friends, so he sometimes compares the SP score of his friends. If their answer is greater or equal to what Not_Tako knew, he will feel offended (破防) and stop being friends with them. If they are truthful, they may obtain higher value to Not_Tako. ## 1. Problem Description In this homework, you will be constructing, modifying and inspecting a tree struture. **you are required to implement 4 features by writing 1 program `friend.c`**. These features include: 1. **Meet**: Add a node to the tree structure. 2. **Check**: Output the status of a subtree. 3. **Graduate**: Terminate all processes of a subtree. 4. **Adopt**: Modify the structure by moving a subtree to another node. You are expected to become familiar with various concepts through the implementation of this homework. 1. **Meet**: The use of pipe(), fork(), dup(), exec(), and manipulation of process and/or file descriptor. 2. **Check**: The design of I/O through pipe between parent/child processes 3. **Graduate**: Subtree process elimination and resource clean up. 4. **Adopt**: The combination of above simultaneously, with use case and limitations of FIFO. ## 2. Specs - Please strictly follow the implementation guidelines as follows. - Some details may be omitted on purpose below. Try your best to ensure your program runs smoothly. ![Notes_240921_025221_1](https://hackmd.io/_uploads/ByvMkVhTA.jpg =500x) (A graphical example of friends tree) The picture above serves as an example of a tree structure. The arrangement of relationships may differ based on various test cases, but certain aspects remain constant: **Root** At the topmost level of the tree structure is a node named Not_Tako. It is always the root of the tree and has no `friend_value`, he **reads commands from standard input (fd 0)**. When necessary, it should pass commands downwards. **Node(s)** Each node (excluding root Not_Tako) has a `friend_name` and a `friend_value` stored when created, they only read commands from their parent node and may have multiple child nodes. **Structure Design Overview** You are expected to finish a program named `friend.c`. The program acts as a node in the tree structure to receive commands, fork processes, execute `friend` to create more nodes, etc. Each node is a process and should communicate to each other through the use of pipe (and FIFO if specified/permitted). When passing messages through pipe, I/O multiplexing (select, epoll) is not needed. You can simply use **blocking I/O** for this homework. The message format may be designed freely. **But try to make it easily understandable, you never know if I might read your code manually to give some extra marks :D** In this homework, you need to implement 4+1 commands for the Happy Friends Tree. ## 3.1 Prior Knowledge Before you start, here are some specifications and guides you should know. - Any mention of "Child" in the Spec means direct children of a node. While "Descendants" means all children reachable from all direct child nodes. - All execution should be by format below, where `friend` is the binary executable of your `friend.c`. ``` ./friend <friend_info> ``` - The format of `<friend_info>` is guaranteed to be `<string_number>` - **`string` is always unique, will only contain english alphabets( a-z | A-Z), and consist of at most 8 letters (2 < strlen(string) < 9)** - **`number` is between 00 and 99, represented by a 2 decimal integer**. - **`<friend_info>` will at most have 11 letters (strlen(`<friend_info>`) < 12)** - For example, `<friend_info>` may be `haha_07`, `not_18`, `gura_99`, or `tako_69` - You should extract the `friend_name` from the `string`, and `friend_value` from the `number`, whenever necessary. - If the `<friend_info>` is "Not_Tako", it is the root of the tree, and does not need any further info extraction. - Always run `./friend Not_Tako` first before attempting further commands. As this creates the root of the tree, and is how all the test cases will be. - All 4+1 commands from below will be passed to node `Not_Tako` through stdin (fd 0). - Remember to read [Additional Specifications](#5-Additional-Specifications) carefully before you start implementing anything. - Read about [Traversal Order](#32-Traversal-Order) for a guide to command passing. ## 3.2 Traversal Order Keep in mind that **a service only has information about its parent and its direct child services**. It doesn't and shouldn't have any other information about other services that don't belong to its parent or child services. Therefore to complete a command, a service may need to **recursively** deliver the message to child services and childs of its child services and so on. Given a tree structure, it is recommended that commands are passed in the same order as specified by the Pre-Order Traversal. Here are some explanations: - If a service has only one direct child service, when it needs to relay a command downward, it simply passes it to its sole child service. - If a service has two or more child services, it should relay commands in the order they were created. Essentially, the earlier a child service was created, the earlier it should receive commands from its parent. - The sequence of command forwarding should align with the Pre-Order Traversal. You are advised to have a node read from its child after passing a command, such that when - the entire subtree of the child has received the command, the node knows to pass it to its next child **or** - the command is executed, the node can be informed by the response from the child node, and does not need further command passing. **3.2.1 Tips for Traversal Order** - You are advised to ~~spam~~ insert some print messages (process IDs, names and/or values) during implemental phase to ensure node creation, file descriptor access, and other actions are successful. - Always check return value. - Try to design a response logic for every message (command passing especially), For example: 1. Node_A passed a command to its child (Node_B), and reads from its child (Node_B). 2. B receives command from A, and writes to A the command is received. 3. This way, A may continue to read from its own parent, and B is free to continue passing the command. - Try to order your response logic carefully, For example: 1. Following above, after B receives command from A (and A is performing blocking read from B), it may not always be optimal that B respond first. 2. If B has descendants to further pass the command, or has to execute the command, responding to A before these actions may cause 2 commands to exist in the tree **at the same time**. 3. Instead, similarly to **Pre-Order_Traversal**, a response to parent node should be done **after** the entire subtree of the node has finished its action with the received command. ## 4. Implementation Read the [Story](#0-Story-may-be-skipped-entirely) if you find it hard to grasp the technical concept of what each function does. ### 4.1 Meet **4.1.1 Execution** Given command format: ``` Meet <parent_friend_name> <child_friend_info> ``` You must extract `friend_name` and `friend_value` from `<child_friend_info>`, and create a new node under `parent_node`. Refer to [Prior Knowledge](#3-Prior-Knowledge) for `<friend_info>` format. The newly created node should use pipe fd 3 and 4 to communicate with their parent node (check given template hw2.h for reference). It is possible that `<parent_friend_name>` is Not_Tako. The command format is then: ``` Meet Not_Tako <child_friend_info> ``` - Keep in mind that the order of nodes created should be absolute. - In a graphical sense, nodes first created should be on the lower-left side of the parent, and nodes created later should be to the right of older sibling nodes. - In an implemental sense, information (fd, name, pid, etc) of child nodes should be stored in order of creation by the parent node. **4.1.2 Response** We should check whether a function is successful (same goes with other things in life), hence need a response check. The message is not restricted to be printed by which process. - If a node creation is successful under Not_Tako, print the following message to stdout (fd 1) ``` Not_Tako has met <child_friend_name> by himself ``` - If a node creation is successful under other nodes, print the following message to stdout (fd 1) ``` Not_Tako has met <child_friend_name> through <parent_friend_name> ``` - If a node cannot be created, it is guaranteed the reason is because `parent_friend_name` does not exist, print the following message to stdout (fd 1) ``` Not_Tako does not know <parent_friend_name> to meet <child_friend_name> ``` **4.1.3 Example** 1. `Meet Not_Tako ThisWay_22` should create a node named `ThisWay` with value `22` under node `Not_Tako`. 2. `Meet ThisWay Rwei_20` should create a node named `RWei` with value `20` under node `ThisWay`. 3. Similarly, `Meet Not_Tako Chicken_71` and `Meet Rwei Nugget_17` creates two nodes under `Not_Tako` and `Rwei`, named `Chicken` and `Nugget`, with values `71` and `17` respectively. 4. `Meet Tako Not_18` should fail. ![Notes_240921_025221_2](https://hackmd.io/_uploads/B1d4yEhaC.jpg =500x) Graphical View of Example with final responses: ``` Not_Tako has met ThisWay by himself Not_Tako has met Rwei through ThisWay Not_Tako has met Chicken by himself Not_Tako has met Nugget through Rwei Not_Tako does not know Tako to meet Not ``` **4.1.4 Tips for Meet** 1. Make sure to fully understand pipe(), fork(), dup() and exec() 2. Properly maintain file descriptors, where they read from/write to, and close all unused fd. 3. Use two pairs of pipes for parent child communication. One for the parent to write, the child to read, the other for the parent to read, the child to write. ### 4.2 Check **4.2.1 Execution** Given command format: ``` Check <parent_friend_name> ``` You **must** pass down the command to the necessary node and have them execute the command. Note that `<parent_friend_name>` may be any node, including Not_Tako. **4.2.2 Response** - If `<parent_friend_name>` can be found in the tree, print the entire Tree Structure starting from the `<parent_friend>` and its descendants. - Each node is represented by `<name_value>`, similarly to `<friend_info>`. For example, `ThisWay_22`, `Chicken_71` and `Nugget_17`. - Each sibling/cousin node should be seperated by a single space character " ". - Each level should be printed in a new line. - If `<parent_friend_name>` cannot be found, print the following message to stdout (fd 1) ``` Not_Tako has checked, he doesn't know <parent_child_name> ``` **4.2.3 Example** ![Notes_240921_025221_2](https://hackmd.io/_uploads/B1d4yEhaC.jpg =500x) above structure should print below response for `Check Not_Tako` ``` Not_Tako ThisWay_22 Chicken_71 Rwei_20 Nugget_17 ``` While the same structure would print below response for `Check ThisWay` ``` ThisWay_22 Rwei_20 Nugget_17 ``` And print below response for `Check haha` ``` Not_Tako has checked, he doesn't know haha ``` Note that the response structure only restricts the order of cousin nodes, but not their relative position to their parent nodes. Hence below 2 structures yield the same `Check Not_Tako` response. ![Notes_240921_025221_1](https://hackmd.io/_uploads/ByvMkVhTA.jpg =500x) ![Notes_240921_025221_3](https://hackmd.io/_uploads/SkJ61NhTR.jpg =500x) **4.2.4 Tips for Check** 1. Think thoroughly before you start, as this function is how the test cases check everything else. 2. The process to perform the print(s) is not restricted, it may be multiple. 3. Learn about fflush(), check the template to see if you need it. 4. Remember that you may only print line by line. 5. Don't forget the new line character "\n" for each level. 6. Design your own logic to differentiate node levels (symbols are great for representing different logical cases). 7. You may not save descendant information (name, value, etc.) in the parent node, but you may read from all of them and print them yourself. 8. **Do not use FIFO** in this implementation, refer to [Additional Specifications](#5-Additional-Specifications). ### 4.3 Adopt **4.3.1 Execution** Given command format: ``` Adopt <parent_friend_name> <child_friend_name> ``` You should create a FIFO file **under the current directory** with name `Adopt.fifo` The child node uses this FIFO to write its subtree information to the parent node. If you need additional FIFOs (maybe for error checks or response to avoid deadlock), please remember to clean them. You should obtain the subtree information, and move the subtree below the `parent_friend`, as the newest child. When being adopted, all subtree nodes' `friend_value` must be **modded** by the parent node's `friend_value`. - In an implemental sense, you should recursively perform [Meet](#41-Meet) in the right order on the respective nodes to recreate the `child_friend` subtree while having `child_friend` and all descendant's `friend_value` mod the `parent_friend_value`. **The FIFO file should be deleted after execution.** **4.3.2 Response** The message is not restricted to be printed by which process (root recommended). - If node adoption is successful, print the following message to stdout (fd 1) ``` <parent_friend_name> has adopted <child_friend_name> ``` - If a node cannot be adopted, it is guaranteed the reason is because `child_node` is an ancestor of `parent_node`, print the following message to stdout (fd 1) ``` <parent_friend_name> is a descendant of <child_friend_name> ``` **4.3.3 Example** ![Notes_240921_025221_1](https://hackmd.io/_uploads/ByvMkVhTA.jpg =500x) Calling `Adopt D A` on above structure would only print ``` D is a descendant of A ``` But calling `Adopt B A` on above structure would yield below result, while printing ``` B has adopted A ``` ![Notes_240921_025221_4](https://hackmd.io/_uploads/By-dlEnaR.jpg =500x) **notice the modded values of C and D** **4.3.4 Tips for Adopt** 1. Your design logic from Check may be useful here. 2. FIFO is **mandatory** here. 3. Think about how you want to communicate subtree information through the FIFO, ~~below are some recommendations to choose from~~ below is a recommended step procedure (sorry for the confusing description) 1. in a single string, with a single pass, to the adopting parent 2. command pass (with pipe) one by one, to the respective parent nodes performing the next Meet 4. If each node knows its level in the tree, how can the adopting parent node know where to perform the next Meet? 5. Think about how you can recursively Meet on multiple levels with Pre-Order-Traversal. 6. Remember to mod the values. 7. Remember to terminate the original subtree before executing recursive Meet. Use [Termination Tips](#45-Graduate) from Graduate. 8. If a parent has more than one child and Adopt its own child, the child is moved to the right-most position. 9. If a parent Adopt its only/last child, nothing happens other than the value modding and response print. 10. Please don't try to bypass the requirement, if you don't use FIFO, even if we don't find out, you will most likely timeout. ### 4.4 Graduate **4.4.1 Execution** ``` Graduate <friend_name> ``` You should execute `Check <friend_name>` and terminate the entire subtree. - If `<parent_friend_name>` cannot be found, print the following message to stdout (fd 1) ``` Not_Tako has checked, he doesn't know <parent_child_name> ``` If `<friend_name>` is Not_Tako, print the following message before ending the homework: ``` Congradulations! You've finished Not_Tako's annoying tasks! ``` **4.4.2 Tips for Graduate (same goes for all termination)** 1. Your traversal logic from Check may be useful here. 2. You can use this for Adopt termination. 3. Clean up your file descriptors carefully (close 2 fd pipes to each child). 4. Use wait() or waitpid() properly, leave no zombie processes. 5. Understand the definition of zombie process thoroughly. Not seeing a process in your tree structure does not necessarily mean it is not a zombie process. 6. Please don't flood our workstation due to insufficient understandings. (Atleast check if they're yours) 7. Similar to everything else, Pre-Order-Traversal is recommended. ### Bonus Compare Reminder: If you decide to implement this function, a [Report](#8-Report-Optional-Up-to-1-point) must be handed in explaining your logic or your Compare will not be graded. You will not receive additional marks in your report for Compare. **Bonus.1 Execution** ``` Compare <friend_name> <number> ``` You should create two FIFO files **under the current directory** with names - `number.fifo` - `<friend_name>.fifo` The root node then writes the `<number>` to `number.fifo`, pass down the command with `<friend_name>` to its descendants, and read from `<friend_name>.fifo`. You should implement the order of these 3 actions yourself. When a node receives the comparison request, it should read from `number.fifo` and compare it with its `friend_value`. - If `<number>` > `friend_value` - All descendants (including compared node itself) has their ((`friend_value` * 2) % 99) - write to `<friend_name>.fifo` to tell root node the outcome. - If `<number>` <= `friend_value` - All descendants (including compared node itself) are to be terminated - write to `<friend_name>.fifo` to tell root node the outcome **The root node then deletes the two fifo files when above operation is done.** **Bonus.2 Response** The message is not restricted to be printed by which process (root recommend). - If `<number>` > `friend_value`, print the following message to stdout (fd 1) ``` Not_Tako is still friends with <friend_name> ``` - If `<number>` <= `friend_value`, print the following message to stdout (fd 1) ``` <friend_name> is dead to Not_Tako ``` **Bonus.3 Example** ![Notes_240921_025221_1](https://hackmd.io/_uploads/ByvMkVhTA.jpg =500x) Calling `Compare A 09` on above structure would create `number.fifo` and `A.fifo`, perform communication and delete the FIFO files to yield below result, while printing ``` Not_Tako is still friends with A ``` ![Notes_240921_025221_5](https://hackmd.io/_uploads/Byo6xNnpC.jpg =500x) Calling `Compare B 01` again on above structure would use `number.fifo` and `B.fifo` to yield below result, while printing ``` B is dead to Not_Tako ``` ![Notes_240921_025221_6](https://hackmd.io/_uploads/BJj0lNh6C.jpg =500x) **Bonus.4 Tips for Compare** 1. Your design logic from Check and/or Adopt may be useful here. 2. **FIFO is mandatory here** (must be used), don't try to bypass the use of it. - If you bypass the instructions of this bonus implementation, **you will get 0 for it and your original marks will also get deducted**. 3. There will be no test cases where `friend_name` does not exist or is Not_Tako when calling this function. 4. Use [Termination Tips](#45-Graduate) from Graduate. 6. Root starts to read (next command) from stdin immediately after receiving from `<friend_name>.fifo`, so try to respond to root after performing other actions. 7. Figure out what the root node should do first, then design how other nodes complement it. 8. Remember to **close file descriptors** of your FIFOs and remove the FIFOs. ## 5. Additional Specifications **5.1 General** - There are public testcases that only check output, try to score them. - It is possible that we check additional information for the final judge. - Unless you try to bypass any rules or limitations, the marks from public testcases are guaranteed once you score them. - All commands will be valid and by format (ends with "\n"). - If you have any questions about possible cases, or if your implementation logic is valid, please ask. **No excuses of ambiguity abuse will be accepted.** - kill() and double fork is discouraged. **You will be deducted marks if found.** - No node stores `friend_name` and/or `friend_value` information of non-direct nodes. **You will be deducted marks, possibly to 0 if found.** - There ~~will~~ **should** be no more than **30 nodes** in the tree at any given time. - But it is possible if you create subtree before deleting the original in Adopt - This means the testcase will not purposely make you meet a 31$st$ node, but false implementation may lead to this outcome. - There will be no more than **8 child nodes** for any parent node at any given time. - You do not have to consider cases of accidental process termination. - But it may be used for judging purposes. - We may write scripts with certain commands such as `pstree` or `strace` to perform additional checks when deemed necessary. **5.2 Meet** - There will be no test cases where you Meet the 31$st$ node. - There will be no test cases where you Meet an existing node. - There may be identical `friend_value` from different nodes. - There is one and only one fail case. **5.3 Check** - The subtree to Check will have no more than 7 levels (atmost 6 level of descendants). - Given command `Check <friend_name>`, assume `<friend_name>` as level 0 in subtree, there are atmost 6 more levels under this node. - The subtree to Check will never exceed 30 nodes. - FIFO is **restricted** in the implementation of Check with zero tolerance, **your marks will be 0 if found, allowing NO REGRADE**. - All private test cases will use Check as the primary grading scheme. **5.4 Adopt** - We will not have testcases where you mod by 00 - The subtree to Adopt will have no more than 7 levels. - The subtree to Adopt will never exceed 29 nodes. - Above case is when Not_Tako Adopt his only child. - The command would be `Adopt Not_Tako <child_name>` where `<child_name>` has 29 nodes in its subtree. - There will be no test cases where `parent_node` or `child_node` does not exist when calling Adopt. - FIFO is **mandatory** in the implementation of Adopt, if you try to bypass it, **your marks will be 0 for all test cases with Adopt, allowing NO REGRADE**. **5.5 Graduate** - Simmilar to Check, Graduate will have no more than 7 levels, and will never exceed 30 nodes. - If you have a hard time debugging process termination, print out debugging messages containing process ID. - If a process (with a relatively small PID than your newly created processes) remains on the server even after you call Graduate, it is most likely a zombie process. - You are encouraged to remove zombie processes on the workstation server (and your local machine). - Run `htop -u $(whoami)` or `ps -ux` to check whether there are zombie processes. - Run `pkill -9 friend` to remove zombie processes effortlessly. - Sometimes, ~~砍掉重練不是壞事~~ you need to start from the beginning again to clear your logic. **5.6 Compare** - Second reminder: please write a [Report](#8-Report-Optional-Up-to-1-point) explaining your logic if you do this or your Compare will not be graded. You will not receive additional marks in your report for Compare. - This bonus implementation is independant to Adopt, but you must atleast complete Meet and Check to attempt this. - FIFO is **mandatory** in the implementation of Compare, if you try to bypass it, **your marks will be 0 for all test cases with Compare, and may affect your original marks, allowing NO REGRADE**. - The message **to tell root node the outcome** may be designed freely, the use of FIFO will be checked, but the content itself will not affect grading. ## 6. General Tips - You are advised to figure out how to implement the logic of node creation (Meet), inspection (Check) and deletion (Graduate) first, as Adopt is a combination of them. - Since Graduate calls Check, they can be done similarly (or even as the same function(s)). - Check your Check, it is heavily used for grading. - Check your read/write format and buffer size. - Double check command and response format (especially space " " and newline "\n" characters). - Triple check return value of your function(s), especially read/write. - Quadruple check your file descriptor manipulation. - about 90% of bugs in this homework is IPC getting stuck because of bad file descriptors or buffers. - Following above, help yourself by writing error detection code. - perror() is a good thing, learn how to use it. - Read [Traversal Order](#32-Traversal-Order) for a recommended way of command passing. - If you haven't implemented Graduate, you can always use `htop` to manually close your processes. - You can manually check your input output with `./friend Not_Tako < "path_to_input_file.txt" > "path_to_output_file.txt"` or use `tee` to your advantage - Understand the course materials thoroughly, study manual pages for all possibly needed functions, and read this spec carefully. - Come to TA hour if you need help after performing all three above (or any proof of effort). Otherwise, I will simply ask you to try again. - Eat well and get good sleep ## 7. Code Judging & Grading - If your program doesn't block or sleep (the command is always executing with no indefinite waits), there is no need to worry about the time limit. - We consider certain things fundamental, and will not give partial marks in the code section when completed, e.g. - Command passing mechanism - Correctly open and keep necessary pipes for parent and child nodes - Gracefully terminating a node and all of its descendents - Correctly close unused file descriptors - No zombie process after any termination - Correctly close the file descriptors and remove the FIFOs - Above partial marks is possible with [Report](#8-Report-Optional-Up-to-20). ### **Public (3.2 points)** - Input and output will be provided - Marks of each testcase is equally distributed to all sub-testcases **Public-Test-Case-1: Meet (0.8)** **Public-Test-Case-2: Meet & Check (0.6)** **Public-Test-Case-3: Meet & Graduate (0.6)** **Public-Test-Case-4: Meet, Check & Adopt (0.6)** **Public-Test-Case-5: Everything (0.6)** ### **Private (4.8 points)** - Input will not be provided, additional checks other than output is possible. ### **Bonus Compare (1 point)** - Input will not be provided, additional checks other than output is possible. - Requires Meet & Check, but mutually exclusive with Adopt - This function will be graded seperately, and directly added to total marks, capped at 8 points. ## 8. Report (Optional Up to 1 point) Third time's the charm: If you implement Compare, this report becomes **mandatory**, use it to explain your logic or your Compare will not be graded. You will not receive additional marks in your report for Compare. This report allows for **NO REGRADE** and will only be graded (manually) when: - You did not score full marks with coding - Both code and report are submitted before the **soft** deadline - You are polite to Teachers and TAs :D Provide a **pdf** report of your work, explaining how you implemented this homework, options include: - Node initialization (everything it does after it is created). - Command passing mechanism. - Logic and implementation of any of the 4+1 functions (providing images of code with remarks can make things easier. - Other things you think shows your effort Grading will be based on following: - Late penalty will be applied to the report marks. - Given a part of your code is wrong and you lost marks for it. If your report includes explanation on that section, it will be graded, and you may provide up to 5 sections of answers，each section getting up to 0.2 points. - In each section, the additional marks are divided into 4 equal parts of - Idea: How and why you intended your implementation - Correct Logic: How logically correct is your idea - Explanation: How you put your idea into actual code - Effort: Show an error you fixed and how or show a bug you found but can't fix and why The extra marks for this report are designed such that it is most likely inverse of your coding marks. Hence the higher you score initially, the lesser impact your report, and vice versa. ## 9. Submission ### Code Submission You should use GitHub classroom to submit your homework as before. The folder structure on github classroom should at least be: ``` ├- public-testcases ├- sample-testcases ├- friend.c ├- hw2.h └- Makefile ``` You may not submit other files, except `.gitignore` and README.md. Do not submit files generated by `make` from your `Makefile`. You should call `make clean` from your `Makefile` before you submit. You **will lose 0.25 points as a punishment** if you submit those files. ### Report Submission Your report should be in PDF format and you should upload your report to NTU COOL. ## 10. Reminders - Plagiarism is **STRICTLY** prohibited. - Both copying and being copied result in a score of zero. - Previous or classmates’ work will be considered as plagiarism. - Discussion is allowed, but the code should be entirely self-written. - Avoid letting others view your code. It’s your responsibility to protect your work. - The method of checking goes beyond comparing source code similarity (e.g., changing `for` to `while` or modifying variable names will also be detected). - Late policy (D refers to formal deadline, 11/12 23:59) - If you submit your assignment on **D+1** or **D+2**, your final score will be multiplied by 0.85. - If you submit your assignment between **D+3** and **D+5**, your final score will be multiplied by 0.7. - If you submit your assignment between **D+6** and 11/19, your final score will be multiplied by 0.5. - Late submission after 11/19 23:59 will not be accepted. - Note that we will use your latest submission for grading. Such that if you (accidentally) push your work to your homework repository after the deadlin, it will be considered late submission (even if it is just to clean up logic, add/delete remarks or removing error code). - If you have any questions, we strongly encourage you to: - "Google" or use ChatGPT first to the best of your ability avoiding plagiarism - Evoke issues in [SP2024_HW2_release](https://github.com/NTU-SP/SP2024_HW2_release) - Contact us by email. - Ask during TA hours (**think thoroughly** about what you expect as an answer). Please start your work as soon as possible, I am very confident it is difficult, **DO NOT** leave it to the last day. ## 11. FAQ **-1. Why doesn't the TA reply to my messages?** A: Maybe consider not contacting us through our personal communication methods :) The class email exists for a reason, and you do not deserve any extra privileges compared to other students. **0. Q: How to write error code?** A: By "write error code", I do not only mean code that lets you know where your program stopped, we also need to know WHY. Below is a response from prompting ChatGPT. "Hey there! It looks like you're trying to figure out what might be causing this bug. One thing you can try is using `perror()` in your code. This function prints a message to stderr that includes the latest error message (based on the global errno variable). When you call `perror()`, you’ll get a more specific idea of what's going wrong, like whether a file couldn’t be opened or a network connection failed. Here’s a quick example: ``` #include <stdio.h> #include <errno.h> FILE *file = fopen("somefile.txt", "r"); if (!file) { perror("Error opening file"); } ``` If `fopen()` fails, `perror()` will print something like: ``` Error opening file: No such file or directory ``` This way, you can start diagnosing the issue on your own and get a clearer idea of what's causing the bug. Give it a try and let me know what error message you see!" As mentioned above, please provide TAs something to work with if you want us to help you with debugging (我們不會通靈）. Simply throwing your code at us or just saying what's happening is as useful as saying SP means System Programming. In short, use `perror()` or anything similar to get the REASON a function fails, look up the manual page of the function call and check for yourselves. If you find yourself stuck by then, contact us with descriptions **AND REASON OF FAILURE (atleast error return value)**, we will try our best to help you. **1. Q: Do I have to worry about timeout occuring due to workstation loading?** A: Yes, keep your program as fast as possible. You may use `time ./friend Not_Tako < input.txt > /dev/null` on workstation to check your program runtime. In general, if your output for running `public-input-5-1.txt` and `public-input-5-2.txt` is lesser than one second (0.8 seconds would be better), you don't have to worry about timeout problems. This is about 2.5 to 3 times the runtime of the TA's solution, which the grading will use a similar dynamic time scale (most likely 2). **2. Q: I'm still scared that my program will be affected by other people, what can I do to solidify my grading?** A: You solution will be tested multiple times on CSIE workstation, taking the average of the highest graded few. Depending on the workstation loading, we will dynamically assign a timeout for each grading run. Feel free to reassure yourselves with methods from Q1. You may inspect CSIE workstation workload [here](https://monitor.csie.ntu.edu.tw/). **3. Q: Workstation is too slow, I can't do my homework?** A: This is a common phenomenon during this time of year (because of this homework), a lot of students flood to `ws1` by habit, and they might leave zombie processes. So direct yourself to other workstations to avoid traffic, and remember to clean your own zombie processes (if any occur). **4. Q: my mkfifo() returns error: Operation not supported** A: This is most likely due to running on wsl (it is for me), and your homework directory is not available for this linux command. For your local machine, you may solve this by creating the FIFO at directory `/tmp/<fifo_name.fifo>`, but remember to delete it. If you are on workstatoin, creating a FIFO file on current directory `./<fifo_name.fifo` should be available, hence remember your homework final solution should be in this format (`./`). **5. To what extend is considered not "saving information" of descendants?** Use node Not_Tako as an example. A (descendants): Any node under his direct child node is considered "descendants", refer to [Prior Knowledge](#31-Prior-Knowledge). A (saving): Generally, if information of other nodes exists while Not_Tako is not executing any commands (command passing does not count as execution), it is considered saving. In other words, if an information persists before and/or after the execution of a command, it is considered saving. Short Answer: possessing an information in between commands execution, is considered as saving information. Example 1: read/write fd to communicate with parent/child node must always exist, even when a node is not executing commands, hence it is considered saved (and allowed). Example 2: info (name and/or value) of descendants or siblings is not neccessary when not performing Check, hence buffer content containing descendant node information, persisting after Check is not allowed. List of allowed information to save for each node: 1. read/write fd of parent 2. read/write fd of each child 3. child_name 4. child_value 5. amount of children 6. the command being processed (includes passing and execution) currently 7. if you are not sure of any, you may ask and I will add them here if it is allowed. (Some students are asking about descendants information, so I thought I'd make it clear) List of infomation **NOT** allowed to save for any node: 1. read/write fd of any ancestors 2. read/write fd of any descendants 3. name and/or value of any ancestors 4. name and/or value of any descendants 5. amount of ancestors 6. amount of descendants **6. Q: Why did TA not respond to my issue?** A: Please remember to evoke your issue in the template repository instead of your own private homework repository. **7. Q1: What to do with testcases where it doesn't end with `Graduate Not_Tako`? Alternatively, how to treat EOF? Q2: Why does some testcase not end with Graduate?** A1: In our judge, we will manually terminate your processes, so you don't have to worry about it, just do nothing when you read EOF. But for now, you may treat EOF as `Graduate Not_Tako` or "kill all processes without print" if necessary, but make sure it doesn't get called (maybe use IFDEF?) or to remove it before you submit your code :D A2: This is so that if your implementation for Graduate is wrong, there will still be testcases of other commands where you may get full marks. **8. Q: For Adopt, do we have to consider the case where `<parent>` and `<child>` are the same node?** A: No, as mentioned, there is only one possible fail case. **9. Q: Will there be any `.fifo` files not created by my own program during runtime?** A: No, our judge will guarantee to not create any extra `.fifo` files. If you do create any other than required in the Spec, please remember to clean them. **10. Q: I accepted the assignment after the updates, why is my repository still the initial (wrong) version?** A: Sincere apologies, but this is due to the settings of GitHub classroom, such that changes to templates cannot will not be synced automatically. For this reason, after you accept the assignment (regardless of time), you will need to update the files of your private repository **manually** on your local machine. Sorry for the misleading messages, but to be clear, **accepting the assignment after the updates will still require your manual changes.** You may download the updated files from this [link](https://drive.google.com/file/d/1oPqE41VsZO8zwQanzdYhwvoION6MPZRy/view?usp=drive_link), Newest update is on 3rd November, 8:11 p.m. Again, sincere apologies. **11. Q: Is exec() mandatory for Meet (and Adopt)?** A: A simple yes, only forking a process will have its name also be `./friend Not_Tako`, this will affect grading. You may use `htop` yourselves to test and see the differences with and without calling exec() after fork(). **12. Q1: Can I execute my process with more than one argument (argc != 1)? Q2: can I use `setenv()` and/or `getenv()`?** A1: The answer is **NO**, this will affect our grading as we will check your process name format, which should be and only be `./friend Not_Tako` for root node and `./friend <friend_info>` for every other node. **No additional arguments passing is allowed**. And yes this will affect your grading, BADLY. Refer to Q11 stating exec() is mandatory, and [Prior-Knowledge](#31-Prior-Knowledge) restricting all execution to be in a fixed format. A2: The answer is also **NO**, mainly due to process environment variables are inherited by child processes, and this may be considered ambiguity abuse regarding **"saving information"**, hence marks will be deducted when found. **13. Q: Do I have to write my own Makefile?** A: Yes, as mentioned in [Code Submission](#9-Submission), your `Makefile` should be able to compile your code with `make`, and clean additional files with `make clean`. **14. Q: What counts as "showing my effort" for the Report?** A: Honestly, anything you want, just keep it clear and precise. This is designed to give you as much marks as possible (given you did not score high initially). here are some more suggestions: 0. Helped TA debug testcase problems (I'm sorry QAQ) 1. How you used the pseudo-code given in the template, tips and/or FAQ section in the spec, or online resources. 2. Did you contribute to FAQ? If so which one? How and why did you think of it? 3. What unexpected challenges did you encounter and solve? Here are some I expect you to encounter: - fd problems in Meet - subtree information collection in Check - synchronization problems in Adopt 4. How did you use remarks/error code so that it would be easier to debug or let TA understand in case of looking at your code? 5. Did you try to attempt Compare? Why or why not? 6. What did you learn from this Homework? **15. Q: Is using fd 3 and 4 to communicate with parent process mandatory? how many fd should each process have?** A: Yes it is, considering some students said it was not directly assigned, causing confusion, below will be some clarifications. Given `i` represents the number of children each node has: For Not_Tako, there will be 3 + (2 * `i`) fds - 3 fds (0, 1, 2) represents STDIN, STDOUT, STDERR - 2 * `i` fds are used to read from/write to each chilren For any other process, there will be 5 + (2 * `i`) fds - 3 fds (0, 1, 2) represents STDIN, STDOUT, STDERR - 2 fds (3, 4) are used to read from/write to parent process - 2 * `i` fds are used to read from/write to each chilren We will discuss whether or not to deduct marks for not using fd 3 and 4 for parent communication in the gradings, below are some debate for each stand point, feel free to mail TAs to provide further arguments. - Why it should NOT be deducted: - lack of (direct) clarification in the Spec - It is harder to implement using fd 0 and 1 - Why it should be deducted: - it is clearly defined inside `hw2.h` - mentions of print messages not being restricted to any process implies access to fd 1 (stdout) - direct mention of print(s) may be performed by multiple processes implies multiple access to fd 1 (stdout) Current conclusion: If you used fd 0 and 1 for parent communication, your code may stay as it is **16. Q: I await your question :D**