System Programming 2025 HW2 - Hierarchy of FUTURE Kingdom

# System Programming 2025 HW2 - Hierarchy of FUTURE Kingdom :date: Soft deadline: 2025/11/9 23:59 :date: Hard deadline: 2025/11/16 23:59 :warning: This homework is much more complicated than HW1, so TA suggests you to start as soon as possible. [GitHub classroom link](https://classroom.github.com/a/i_F3QjO6) [Slide link](https://docs.google.com/presentation/d/1BIdDX0mCIB3w8-KNK9_uakhKOA0hmyOTokAt8bBFS00/edit?usp=sharing) [Video link](https://youtu.be/zSfsWa2b2Go) [Disscussion Space link](https://github.com/NTU-SP/SP2025_HW2_release/discussions/categories/q-a) [Latest testcases link](https://drive.google.com/file/d/1n0MS4V8wIA5Aq_tqS9b8nKWZ74gCyBfE/view?usp=drive_link) ## Update Message Any updates regarding the assignment will be announced here and simultaneously posted on the NTU COOL platform. 1. **[10/23]** subtree regex updated. 2. **[10/27]** Sample/public testcases update: Please download the updated files from this [link](https://drive.google.com/file/d/1n0MS4V8wIA5Aq_tqS9b8nKWZ74gCyBfE/view?usp=drive_link). 3. **[10/29]** The response for some commands have been updated to align with template code and testcases. 4. **[11/1]** Sample/public testcases update: Please download the updated files from this [link](https://drive.google.com/file/d/1n0MS4V8wIA5Aq_tqS9b8nKWZ74gCyBfE/view?usp=drive_link). 5. **[11/4]** Reminder: `fief_size` of IPC should be passed in the form of char. 6. **[11/5]** `fief_size` and `status` regex updated and allow multiple contents passed in once IPC. 7. **[11/6]** Allow pass other command in recusive command. 8. **[11/6]** Clarify `$` in regex. 9. **[11/6]** `fief_size` ensure greater than zero in `Grant` command. In the Exchange, Conquer, and Visit commands, `lord_A` and `lord_B` must not be the same. 10. **[11/7]** Update hint for conquer, **you can't exchange total `fief_size` through pipe**. 11. **[11/8]** Sample/public testcases update: Please download the updated files from this [link](https://drive.google.com/file/d/1n0MS4V8wIA5Aq_tqS9b8nKWZ74gCyBfE/view?usp=drive_link). 12. **[11/8]** `WHY` can be one of the target nodes in Visit command. ## Message from TA Please start this homework ASAP, or at least read the spec throughly 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 assitance. It is recommended that you use the following TA office hour since the TA at that time is responsible for this homework. - 王裕勳 (Yu-Hsun Wang): Wednesday: 9:30 am to 10:30 am at R404 - 陳竹筠 (Chu-Yun Chen): Tuesday: 11:00 am to 12:00 am at R302 If necessary, please contact TAs by - Class of Prof Cheng: ntusp2025.pj@gmail.com - Class of Prof Li: swnosp@csie.ntu.edu.tw ## 0. Story (may skipped entirely) **WHY** is the king of the FUTURE Kingdom, but ruling the entire kingdom alone proved far too difficult. Therefore, **WHY** established the Kingdom Hierarchy, a tree structured system of governance. Your task is to help WHY construct this tree structure of the kingdom and enable him to understand how each fiefdom (領土) is being governed. #### Implementaion 1 & 2: Grant & Report In the beginning, the entire kingdom was ruled by **WHY** alone. However, the vast fiefdom made it impossible for the king to fully understand the condition of every fiefdom. To resolve this problem, he decided to **grant** portions of the kingdom to his most trusted subjects, making them lords of their fiefdom. Each lord (領主) was also allowed to further **grant** parts of their fiefdom to their own subordinates to govern smaller fiefdom. In this way, the entire kingdom came to be organized as a tree structure. To stay informed, **WHY** could at any time command a lord to **report** on the status of their fiefdom, so that he could better understand how each land was being governed. #### Implementation 3: Exchange As the lands flourished, **WHY** allowed two lords to **exchange** their fiefdoms as an experiment in governance. Through this small change, he sought to test whether different hands could bring new life to the same soil. #### Implementation 4: Revolt Not all lords remained loyal. Some, driven by ambition or discontent, would launch a **revolt** against the crown. Whenever a **revolt** erupted, **WHY** commanded that the rebellious lord’s entire subtree be purged, and the fiefdom restored to its parent lord’s dominion. #### Implementation 5: Conquer To encourage the lords to govern their lands diligently, **WHY** would sometimes command two lords to confront each other in a challenge of strength. Each lord had to present the total resources of their fiefdom. The stronger lord would **conquer** the weaker one, claiming half of their fiefdom, while the remaining half was returned to the weaker lord’s parent. Through these conquests, the kingdom preserved both ambition and balance, ensuring its enduring strength. #### Bonus Implementation: Visit Sometimes, **WHY** goes on secret **visits** to his kingdom. However, each time he can only **visit** two fiefdoms. To make his journey more efficient, he chooses to stay at the residence of their nearest common superior, which corresponds to the Lowest Common Ancestor (LCA) of the two lords. ## 1. Problem Description In this assignment, you will construct, modify, and inspect a tree structure by **implementing five required features in a single program named `monarch.c`**. The features are as follows: 1. **Grant:** Add a new node to the tree structure. 2. **Report:** Output the status of a specified subtree. 3. **Exchange:** Swap the `fief_size` values of two nodes using a FIFO. 4. **Revolt:** Terminate all processes within a subtree. 5. **Conquer:** Compute the total sum of `fief_size` for both subtrees, then terminate all processes in the subtree whose sum is smaller. * In our code template, each node has an integer data field called `fief_size`, which represents the fiefdom size that a lord has. In this specification, we also use `fief_size` to refer to the fiefdom size of a lord. You are expected to become familiar with a variety of system concepts through the implementation of this homework. Specifically: 1. **Grant:** Practice the use of pipe(), fork(), dup(), exec(), and the manipulation of processes and/or file descriptors. 2. **Report:** Design inter-process communication (IPC) using pipes between parent and child processes. 3. **Exchange:** Explore the use of FIFO for data exchange. 4. **Revolt:** Implement subtree process termination and perform resource cleanup. 5. **Conquer:** Integrate the above techniques simultaneously, while understanding the use cases and limitations of FIFO. ## 2. Overall Specification - 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. ### Definition of Kingdom Hierarchy ![kingdom hierarchy](https://hackmd.io/_uploads/B1y_xtJCeg.png) The picture above is an example for management hierarchy under kingdom. The arrangement of lords (node) may differ based on various testcases, but certain aspects remain constant: #### Root The king stands at the topmost level of the kingdom’s hierarchy. It is always the root of the tree structure, named WHY, and has `fief_size = 10000` at the begining. The king **reads commands from the standard input (fd 0)** and passes them downward when necessary. #### Node(s) Each node has a `name` and a integer data field `fief_size`. For all nodes except the WHY, both fields are assigned through the Grant command. Node `names`, except for the WHY, only contains alphabet and are written in **lowercase**. #### Structure Design Overview You are expected to complete a program named `monarch.c`. The main process acts as the root of a tree structure. After receiving several Grant commands from standard input, the process hierarchy will grow into a tree. Each node in this tree receives commands from its parent (or from standard input in the case of the root) and is responsible for either forwarding the commands further down the tree or executing the task if it is the target node specified in the command ([detail specification for behavior of receiving command](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#Pipe-content-regulation)). Every node is implemented as a child process, and communication between nodes should be handled through pipes (and FIFOs if specified or permitted). To avoid you complete this task without really use pipes and FIFOs to pass message, **the content format is [restricted](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#32-IPC-content-regulation)**, we will check the node responsible for performing tasks has received the required command. When passing messages through pipes or FIFOs, I/O multiplexing (such as select or epoll) is not required. You can simply use **blocking I/O** for this homework. ## 3. 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 `monarch` is the binary executable of your `monarch.c`. ``` ./monarch <lord_info> ``` * The format of `<lord_info>` is guaranteed to be `<name_fiefsize>` - `name` is always unique, for all lords (except WHY), will **only contain english alphabets in lower case(a-z)**, and consist of **at most 15 letters (1 <= strlen(name) < 16)** - `fiefsize` is **between 0000 and 9999** for all lords (except WHY), represented by a 4 decimal integer. - `<lord_info>` will **at most have 20 letters (strlen(`<lord_info>`) < 21)** for all lords (except WHY). - For example, `<lord_info>` may be `squirtle_0711`, `gengar_1833`, `cubone_9921`, or `pikachu_0025` - You should extract the `lord_name` from the `name`, and `fief_size` from the `fiefsize`, whenever necessary. - When `<lord_info>` is "WHY", it denotes the root node, whose `lord_name` is fixed as **WHY** and whose `fief_size` is initialized to **10000**. - Always run `./monarch WHY` first before attempting further commands. As this creates the root of the tree, and is how all the test cases will be handled. - All 5+1 commands from below will be passed to node `WHY` through stdin (fd 0). - Remember to read [Additional Specifications](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#5-Additional-Specifications) carefully before you start implementing anything. - Read about [Traversal Order](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#31-Traversal-Order) for a guide to command passing. - Read about [IPC content regulation](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#32-IPC-content-regulation) for correctly passsing message in our requirement. ### 3.1 Traversal Order Keep in mind that **each node can keep any data (e.g., lord_name, fief_size, PID, pipe fd, etc.) about its parent and direct children, but it cannot store information about any other nodes**. It doesn’t and shouldn’t have any other information about unrelated nodes. To complete certain commands, a node may need to **recursively** deliver messages to child nodes and childs of its child nodes 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 node has only one direct child node, when it needs to relay a command downward, it simply passes it to its sole child node. * If a node has two or more child nodes, it should relay commands in the order they were created. Essentially, the earlier a child node 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 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. ### 3.2 IPC content regulation To make sure you pass the data through the pipes and FIFOs, and following the instrument in [implementation section](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#4-Implementation) to complete this assignment, we regulate the format of passing message. #### Pipe content regulation ##### a. Parent to Child For messages passed from a parent to a child, the message must be a valid command from one of the two tables below. You are also required to implement the expected behavior for each node upon receiving a command. We will verify that, for each command, the final commands received by each node and their order correctly complete the task. This will be checked by rerunning your command passing records in our implementation. ###### 1. Normal Command These are the valid 5 + 1 command formats. Only the target node and the root perform actions upon receiving a command. All other nodes are only expected to forward the command (if necessary) and should not perform any additional behavior. | Format | Target node Expected Actions | Root node Expected Actions | | ------ | -------- | -------- | | Grant `<lord_name>` `<lord_info>` | `Fork` a child process | None | | Report `<lord_name>` | Collect subtree information | None| | Exchange `<lord_name>` `<lord_name>` | Write `fief_size` to the exchange partner | Make / control FIFO | | Revolt `<lord_name>` | Collect subtree information and pass `fief_size` to parent then kill subtree| None | | Conquer `<lord_name>` `<lord_name>` | Collect subtree total `fief_size`, write / read total `fief_size` to / from conquer opponent and update, kill subtree and pass `fief_size` to parent if needed | Make / control FIFO | | Visit `<lord_name>` `<lord_name>` | Unrestricted | Unrestricted | - You can print the response in the target nodes or root when they receive above commands as you like. - We don't restrict how you implement command `Visit`, please describe details in the written part. ###### 2. Recursive Command For `Report`, `Revolt` and `Conquer` command, the node in subtree of target node also need to involve the recusive task, you can add following two types of prefix to original command (or other valid command) to recusively collecting information or kill node on the subtree node. | Format | Expected Actions in Subtree Node| | ------ | ------ | | r-Rep-`<Valid command>` | Collect subtree information and pass to parent | | r-Rev-`<Valid command>` | Collect subtree information and pass to parent then kill subtree | ###### Prefix Status We allow you to include a status indicator that the parent node wants to convey to its child through command passing. Please use **one alphabetic character** followed by a hyphen (-) as a prefix to the original command (from 'a'–'z' or 'A'–'Z'). For example, you can ``` Use 'a-Exchange <lord_A_name> <lord_B_name>' to tell child "We have found the target 0 <lord_A_name>." when passing Exchange command. ``` or ``` Use 'b-Exchange <lord_A_name> <lord_B_name>' to tell child "We have found the target 1 <lord_B_name>." when passing Exchange command. ``` ##### b. Child to Parent For the message pass from child to parent, we allow following three types of message. ###### 1. Fief size You can pass the `fief_size` to parent. ###### 2. Subtree You can pass the subtree information collecting from childrens, we also regulate the format of string to represent a subtree. When a node recieve `Report`, `Revolt` and recursive command, we will check every child really pass their own subtree information to parent. To use a string to represent a tree, please **use `' '` (one space)** to seperate the `lord_info`, and **use `'*'` to seperate the layer**. For the below example: ![Subtree example](https://hackmd.io/_uploads/H1J4cmG6xe.png) when `WHY` recieve `Report` command, `pikachu` should pass this string to `WHY`: ``` pikachu_0300*pichu_0200*ditto_0100 ``` `eevee` should pass this string to `WHY`: ``` eevee_0200*cubone_0100 celebi_0100*plusle_0030 minun_0060 ``` ###### 3. Status You can design your own message to response parent after complete require behavior, it can be used to report the executed result or existence status. However, you can **only use one alphabet** ('a' to 'z' and 'A' to 'Z') to represent the status you want to tell parent. For example, you can ``` Use 'a' to tell parent "Command is successful executed." ``` or ``` Use 'b' to tell "The first target is exist in my subtree." ``` Once a node recieve a response (or after integrating all childrens response), you can decide what to do next base on the reported status. For example: 1. Stop or Resume the command passing. 2. Print command response in terminal. 3. Make new response to parent. #### FIFO content regulation We will check the FIFOs content in those command need FIFOs, you can only pass [Fief size](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#1-Fief-size) and [Status](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#3-Status) in FIFO file. Please also follows the format. ### 3.3 Constant We list all variables that has fix value in this assignment, we also use these constants to regulate your IPC content. | Variable | Constant | Value | | --- | --- | --- | | Max string length of `lord_name`| `MAX_LORD_NAME_LEN` | 16 | | Max string length of command name | `MAX_CMD_NAME_LEN` | 15 | | Max string length of command | `MAX_FULL_CMD_LEN` | 49 | | Max string length of `lord_info` | `MAX_LORD_INFO_LEN` | 21 | | Max string lenght of status | `MAX_STATUS_LEN` | 2 | | String length of `fief_size` | `FIEF_SIZE_LEN` | 5 | | Max string length of `subtree` | `MAX_SUBTREE_LEN` | 630 | | Max string length of PIPE content | `MAX_PIPE_INFO_LEN` | 630 | | Max string length of FIFO content | `MAX_FIFO_INFO_LEN` | 5 | | Max number of subtree layer | `MAX_SUBTREE_LAYER` | 7 | | Max number of child node | `MAX_CHILDREN_NUM` | 8 | | Max number of subtree node | `MAX_SUBTREE_NODE` | 30 | * All the string length has considered the null character '\0' * Command name refers to the first word in command, e.g., `Grant`, `Exchange`, `r-Rep-Conquer`..., max valid value is `r-Rep-Exchange`. * Max valid value for `MAX_FULL_CMD_LEN` can be `r-Rep-Grant bbbbbbbbbbbbbbb aaaaaaaaaaaaaaa_0003` * `MAX_SUBTREE_LEN = MAX_SUBTREE_NODE * (MAX_LORD_INFO_LEN - 1) + (MAX_SUBTREE_NODE - 1) + 1 = 630` ### 3.4 Content Format Regular Expression To define the content format more clearly, we provide a regular expression for each valid format. The buffer size (the count parameter in the read/write functions) of the IPC content may exceed the actual string length you passed, but please ensure that a null terminator ('\0') is added at the end of the string. Pipe content for parent to child: | Valid Format | Regular Expression | | --- | --- | | Grant `<lord_name>` `<lord_info>` | `^(?:[A-Za-z]-)?Grant ([A-Za-z]{1,15}) ([a-z]{1,15}_[0-9]{4})$` | | Report `<lord_name>` | `^(?:[A-Za-z]-)?Report ([A-Za-z_]{1,15})$` | | Exchange `<lord_name>` `<lord_name>` | `^(?:[A-Za-z]-)?Exchange ([a-z]{1,15}) ([a-z]{1,15})$` | | Revolt `<lord_name>` | `^(?:[A-Za-z]-)?Revolt ([A-Za-z_]{1,15})$` | | Conquer `<lord_name>` `<lord_name>` | `^(?:[A-Za-z]-)?Conquer ([a-z]{1,15}) ([a-z]{1,15})$` | | Visit `<lord_name>` `<lord_name>` | `^(?:[A-Za-z]-)?Visit ([a-z]{1,15}) ([a-z]{1,15})$`| | r-Rep-`<Original command>` | We will check the 5 charecters prefix (or 7 charecters for status prefix) then apply the above regex on remaining part | | r-Rev-`<Original command>` | Same as above | - `(?:[A-Za-z]-)?` is for the prefix status. Pipe content for child to parent and FIFOs: | Valid Format | Regular Expression | | --- | --- | | `fief_size` | `^[0-9]{4}$` | | `subtree` | `^[A-Za-z]{1,15}_[0-9]{4}(?:[ *][A-Za-z]{1,15}_[0-9]{4}){0,29}$` | | `status`| `^[A-Za-z]{1}$`| The `$` in regex usually matches the position before a newline (\n), but in this assignment, we want it to match the position before a null terminator (\0). The expected content should be like "9999\0" or "a\0". ## 4. Implementation Read the [Story](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#0-Story-may-skipped-entirely) if you find it hard to grasp the technical concept of what each function does. The `fief_size` of WHY (root) is initialized to **10000**. ### 4.1 Grant #### 4.1.1 Execution Given command format: ``` Grant <parent_lord_name> <child_lord_info> ``` You **must extract** `lord_name` and `fief_size` from `<child_lord_info>`, and create a new node under `parent_node`. Refer to [Prior knowledge](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#3-Prior-Knowledge) for `<lord_info>` format. The newly created node should **use pipe fd 3 and 4** to communicate with its parent node (check the provided template `hw2.h` for reference). It is possible that `<parent_lord_name>` is WHY. The command format is then: ``` Grant WHY <child_lord_info> ``` - Keep in mind that the order of nodes created should be absolute. - When a new node is granted, the parent’s available `fief_size` **must be reduced** by the corresponding amount. - The parent node’s remaining `fief_size` **must always be greater than 0**; if this condition is violated, the creation of the new node should fail. - We ensure that `fief_size` in `Grant` command would greater than zero. #### 4.1.2 Response We should verify whether a function has executed successfully; therefore, a response check is required. The response message is not restricted to be printed by any specific process. - If a node creation is successful under WHY, print the following message to stdout (fd 1). ``` WHY has granted <lord_name> by himself. ``` - If a node creation is successful under other nodes, print the following message to stdout (fd 1). ``` <parent_lord_name> has granted <child_lord_name>. ``` If a node fails to be created, there are two possible reasons: - The `<parent_lord_name>` does not exist. In this case, print the following message to stdout (fd 1). ``` <parent_lord_name> does not exist in the kingdom. ``` - The `<parent_lord_name>` does not have enough fiefdom to grant to `child_lord`. In this case, print the following message to stdout (fd 1). ``` <parent_lord_name> does not have enough fiefdom to grant <child_lord_name>. ``` #### 4.1.3 Example 1. `Grant WHY pikachu_0600` should create a node named `pikachu` with `fief_size` `600` under the node `WHY`. After the grant, the `fief_size` of `WHY` should be reduced by `600`. 2. `Grant pikachu pichu_0300` should create a node named `pichu` with `fief_size` `300` under the node `pikachu`. After the grant, the `fief_size` of `pikachu` should be reduced by `300`. 3. Similarly, `Grant WHY eevee_0400` and `Grant pichu ditto_0100` creates two nodes under `WHY` and `pichu`, named `eevee` and `ditto`, with `fief_size` `400` and `100` respectively. 4. `Grant mewtwo mew_0020` and `Grant pichu raichu_0250` should fail. ![Grant](https://hackmd.io/_uploads/HkvaCWfagl.png) ``` WHY has granted pikachu by himself. pikachu has granted pichu. WHY has granted eevee by himself. pichu has granted ditto. mewtwo does not exist in the kingdom. pichu does not have enough fiefdom to grant raichu. ``` #### 4.1.4 Hint 1. Ensure you have a solid understanding of pipe(), fork(), dup(), and exec(). 2. Properly manage file descriptors, where they read from/write to, and close all unused fd. 3. Use two pairs of pipes for communication between the parent and child processes: - One pipe for the parent to write and the child to read. - The other pipe for the child to write and the parent to read. 4. In the tree diagram, nodes created earlier should be placed on the lower-left of their parent, while nodes created later should appear to the right of their older siblings. 5. In an implemental sense, information (fd, name, pid, etc) of child nodes should be stored in order of creation by the parent node. ### 4.2 Report #### 4.2.1 Execution Given commanf format: ``` Report <parent_lord_name> ``` You **must** pass down the command to the necessary node and have them execute the command. Note that `<parent_lord_name>` may be any node, including WHY. #### 4.2.2 Response The message is not restricted to be printed by which process. - If `<parent_lord_name>` can be found in the tree, print the entire tree structure starting from the `<parent_lord>` and its descendants. Then, print the total sum of the subtree’s `fief_size`. - Each node is represented by `<lord_info>`, similarly to `<lord_info>`. For example, `WHY_30`, `pikachu_30` and `eevee_40`. - Each sibling/cousin node should be seperated by a single space character `" "`. - Each level should be printed in a **new line**. - If `<parent_lord_name>` cannot be found, print the following message to stdout (fd 1). ``` WHY does not get any report from <parent_lord_name>. ``` #### 4.2.3 Example ![Report](https://hackmd.io/_uploads/SkjByfGple.png) Above structure should orint below response for `Report WHY` ``` WHY_9000 pikachu_0300 eevee_0300 pichu_0200 cubone_0100 ditto_0100 10000 ``` While the same structure would print below response for `Report pikachu` ``` pikachu_0300 pichu_0200 ditto_0100 600 ``` And print below response for `Report mew` ``` WHY does not get any report from mew. ``` #### 4.2.4 Hint 1. Think thoroughly before you start, as this function is how the testcases 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](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#5-Additional-Specifications). ### 4.3 Exchange #### 4.3.1 Execution Given command format: ``` Exchange <lord_A_name> <lord_B_name> ``` You should pass down the command to two target node, then exchange the `fief_size` of two nodes through FIFO. We guarantee that `<lord_A_name>` and `<lord_B_name>` will never be WHY, and would be different lords. You need to create two FIFO files in the current directory: 1. `<lord_A_name>2<lord_B_name>.fifo` for `lord_A` transfer data to `lord_B` 2. `<lord_B_name>2<lord_A_name>.fifo` for `lord_B` transfer data to `lord_A` We also allow the root (WHY) to create a FIFO and act as the reader to receive responses from two target nodes. This command can complete with above two FIFO file and pipe, but if you use this additional FIFO, the FIFO file should named: 3. `Exchange.fifo` for root receive data from two target nodes. The direction of the FIFO is fixed. In the case where one of the target nodes does not exist, the root can take over the missing node’s job. **Make sure to delete all FIFO files after this command finishes execution.** #### 4.3.2 Response The message is not restricted to be printed by which process. - If the exchange of `fief_size` is completed successfully, print the following message to stdout (fd 1). ``` <lord_A_name> and <lord_B_name> has exchanged their fief. ``` If exchange cannot be executed, there are three possible reasons: - The `<lord_A_name>` does not exist. In this case, print the following message to stdout (fd 1). ``` First lord <lord_A_name> does not exist in the kingdom. ``` - The `<lord_B_name>` does not exist. In this case, print the following message to stdout (fd 1). ``` Second lord <lord_B_name> does not exist in the kingdom. ``` - Both of `<lord_A_name>` and `<lord_B_name>` do not exist. In this case, print the following message to stdout (fd 1). ``` Both lords do not exist in the kingdom. ``` #### 4.3.3 Example ![Exchange before](https://hackmd.io/_uploads/SkjByfGple.png) Calling `Exchange pikachu cubone` on above structure yield below result, ![Exchange after](https://hackmd.io/_uploads/SJfgEzf6ex.png) and would print the response: ``` pikachu and cubone has exchanged their fief. ``` Calling `Exchange mew pikachu`, `Exchange pikachu mewtwo`, `Exchange mew mewtwo` on above structure will print the response: ``` First lord mew does not exist in the kingdom. Second lord mewtwo does not exist in the kingdom. Both lords do not exist in the kingdom. ``` #### 4.3.4 Hint 1. FIFO is **mandatory** here, and the `fief_size` information should only be passed through the FIFO. 2. Collecting node existence status using response passed in pipe or the root FIFO. 3. You can use the [prefix status](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#Prefix-Status) to pass status information that helps determining the order of FIFO writes. 4. Design an extendable response rules in pipe (or cooperate with root FIFO if you used it) to collecting status in this command would be beneficial to Conquer and Visit. 5. The additional FIFO is **optional**. It only provides an alternative way to design the status passing. Note that this FIFO will be **written multiple times**; carefully consider the write/read order and synchronization to avoid blocking. 6. For the additional FIFO, don't worry about data interleaving, the POSIX standard specified that when write less than `PIPE_BUF` bytes (usually 4k) to pipe or FIFO are granted [atomic](https://pubs.opengroup.org/onlinepubs/9699919799/functions/write.html). 7. 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 Revolt #### 4.4.1 Execution Given command format: ``` Revolt <parent_lord_name> ``` You should execute `Report <parent_lord_name>` first and terminate the entire subtree. The parent of the revolting node should increase its `fief_size` by the total fief size of that subtree. #### 4.4.2 Response The message is not restricted to be printed by which process. - If `<lord_name>` is found, the program should only output the result of the Report command, no additional messages or text should be printed. * If `<parent_lord_name>` cannot be found, print the following message to stdout (fd 1) ``` <parent_lord_name> does not exist in the kingdom. ``` * If `<parent_lord_name>` is WHY, print the following message before ending this homework: ``` Congradulations! You've finished these tasks! ``` #### 4.4.3 Hint 1. Your traversal logic from Report may be useful here. 2. You can use this for Conquer termination. 3. Make sure to properly close the two pipe file descriptors for each child process. 4. Use `wait()` or `waitpid()` properly to ensure that no zombie processes are left. 5. Make sure to thoroughly understand the definition of a zombie process. Not seeing a process in your tree structure does not necessarily mean that it is not a zombie process. 6. Please don’t flood the workstation because of a lack of understanding. At least make sure the processes you create are yours. 7. Similar to other cases, Pre-Order Traversal is recommended. ### 4.5 Conquer #### 4.5.1 Execution Given command format: ``` Conquer <lord_A_name> <lord_B_name> ``` You should compare the total `fief_size` of the subtrees of both lords. The subtree with the smaller total `fief_size` will be terminated. The total fief_size of the terminated subtree is then divided ***equally*** between ***the winning lord*** and ***the parent of the losing lord***. If the total `fief_size` is an ***odd number***, ***the parent of the losing lord*** receives the remaining one unit. If the two subtrees have the **same** total `fief size`, then both subtrees will be terminated, and their `fief_size` will be returned to their respective parents. We guarantee that `<lord_A_name>` and `<lord_B_name>` will never be WHY, and would be different lords. You need to create two FIFO files in the current directory: 1. `<lord_A_name>2<lord_B_name>.fifo` for `lord_A` transfer data to `lord_B` 2. `<lord_B_name>2<lord_A_name>.fifo` for `lord_B` transfer data to `lord_A`. We also allow the root (WHY) to create a FIFO and act as the reader to receive responses from two target nodes. This command can complete with above two FIFO file and pipe, but if you use this additional FIFO, the FIFO file should named: 3. `Conquer.fifo` for root receive data from two target nodes. The direction of the FIFO is fixed. In the case where one of the target nodes does not exist, the root can take over the missing node’s job. **Make sure to delete all FIFO files after this command finishes execution.** #### 4.5.2 Response The message is not restricted to be printed by which process. - If the conquer command is executed successfully, print the following message to stdout (fd 1). ``` <lord_winner> conquers <lord_loser>, grabbing <half_fief_size_of_loser_subtree> land. ``` - If the conquer command is executed successfully but they have same total `fief_size`, print the following message to stdout (fd 1). ``` Both side suffer, all lords died in the war. ``` If conquer cannot be executed, there are three possible reasons: - The `<lord_A_name>` does not exist. In this case, print the following message to stdout (fd 1). ``` First lord <lord_A_name> does not exist in the kingdom. ``` - The `<lord_B_name>` does not exist. In this case, print the following message to stdout (fd 1). ``` Second lord <lord_B_name> does not exist in the kingdom. ``` - Both of `<lord_A_name>` and `<lord_B_name>` do not exist. In this case, print the following message to stdout (fd 1). ``` Both lords do not exist in the kingdom. ``` #### 4.5.3 Example ![Conquer before](https://hackmd.io/_uploads/H1J4cmG6xe.png) Calling `Conquer pichu celebi` on above structure yield below result, ![Conquer after](https://hackmd.io/_uploads/Hk1-H6NTll.png) and print the response: ``` pichu conquers celebi, grabbing 50 land. ``` Calling `Conquer mew pikachu`, `Conquer pikachu mewtwo`, `Conquer mew mewtwo` on above structure will print the response: ``` First lord mew does not exist in the kingdom. Second lord mewtwo does not exist in the kingdom. Both lords do not exist in the kingdom. ``` #### 4.5.4 Hint 1. FIFO is **mandatory** here, and the total `fief_size` for both subtree should only be pass through the FIFO (the `fief_size` pass to parent is also valid, but you can exchange total `fief_size` through pipe). 2. Your design logic from Report and/or Exchange may be useful here. 3. Noticed that we don't guarantee the existence of the target nodes, please read the hint in Exchange command said. 4. Please try your best to skip unnecessary process communication and perform tasks concurrently. 5. If you want to pass and execute command in two subtree concurrently, please note the case where the two nodes are in an ancestor–descendant relationship. 6. The parent of loser node should call waitpid() (or wait()). We recommand that the parent of both target nodes always keep waiting for the child reporting the status of conquer result, because you can't know which target node would terminate in advance. 7. Remember to terminate the loser subtree. Use [Hint](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#44-Revolt) from Revolt. 8. 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. ### Bouns Visit **Reminder:** If you decide to implement this part, please explain your logic in the written part of your submission; otherwise, Visit will not be graded. Note that no additional points will be awarded for Visit in the written part. #### Bouns.1 Execution Given command format: ``` Visit <lord_A_name> <lord_B_name> ``` You should find the **lowset common ancestor, LCA**, for `<lord_A_name>` and `<lord_B_name>` in the tree structure, `<lord_A_name>` and `<lord_B_name>` would be different lords. Using a FIFO is **optional**, but if you use one, it must be created as `Visit.fifo` in the current directory. `WHY` can be one of the target nodes, the two target nodes would be two different nodes. #### Bouns.2 Response The message is not restricted to be printed by which process. When find the LCA for `<lord_A_name>` and `<lord_B_name>`, print the following message to stdout. ``` <lord_LCA_name> is the LCA for <lord_A_name> and <lord_B_name>. ``` If we cannot find the LCA, there are three possible reasons: - The `<lord_A_name>` does not exist. In this case, print the following message to stdout (fd 1). ``` First lord <lord_A_name> does not exist in the kingdom. ``` - The `<lord_B_name>` does not exist. In this case, print the following message to stdout (fd 1). ``` Second lord <lord_B_name> does not exist in the kingdom. ``` - Both of `<lord_A_name>` and `<lord_B_name>` do not exist. In this case, print the following message to stdout (fd 1). ``` Both lords do not exist in the kingdom. ``` #### 4.6.3 Example ![Visit](https://hackmd.io/_uploads/H1J4cmG6xe.png) Calling `Visit cubone minun` on above structure should print: ``` eevee is the LCA for cubone and minun. ``` Calling `Visit ditto plusle` on above structure should print: ``` WHY is the LCA for ditto and plusle. ``` #### Bouns.4 Hint 1. Your design logic from Exchange may be useful. ## 5. Additional Specifications ### 5.1 General - All commands will be valid and by format (ends with "\n"). - If you have any questions about possible cases or whether your implementation logic is valid, please ask. **No excuses due to ambiguity or unclear instructions will be accepted.** - `kill()` and `double fork()` is discouraged. **You will be deducted points if found**. - There should be no more than **30 nodes** in the tree at any given time. - There should be no more than **8 child nodes** for any parent node at any given time. - You do not need to handle cases of accidental process termination. - However, it may be used for judging purposes. - We may use scripts containing certain commands, such as `pstree` or `strace`, to perform additional checks when necessary. ### 5.2 Grant - There will be no testcases where you Grant the **31st** node. - There will be no testcases where you Grant an existing node. - There are two and only two fail cases. ### 5.3 Report - The subtree to Report will have **no more 7 levels** (at most 6 level of descendants). - For the command `Report <parent_lord_name>`, consider `<parent_lord_name>` as level 0 of the subtree. There are at most six additional levels beneath this node. - The subtree to Report will **never exceed 30 nodes**. - FIFO is **restricted** in the implementation of Report with zero tolerance, your **points will be 0 if founded**, allowing **NO REGRAGE**. - All private testcases will use Report as the primary grading scheme. ### 5.4 Exchange - There will be no testcases in which the **root** is `<lord_A_name>` or `<lord_B_name>`. - FIFO is **mandatory** in the implementation of Exchange, if you try to bypass it, your **points will be 0 for all testcases with Exchange**, allowing **NO REGRADE**. ### 5.5 Revolt - Similar to Report, Revolt will have **no more than 7 levels**, and will **never exceed 30 nodes**. - If you have difficulty debugging process termination, print debugging messages that include the process ID. - 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 monarch` to remove zombie processes effortlessly. - Sometimes, you need to start from the beginning again to clear your logic. ### 5.6 Conquer - As in Exchange, Conquer will have no testcases the **root** (WHY) as `<lord_A_name>` or `<lord_B_name>`. - FIFO is **mandatory** in the implementation of Conquer, if you try to bypass it, your **points will be 0 for all testcases with Conquer**, allowing **NO REGRADE**. ### 5.7 Visit - **Second reminder:** Please explain your logic in the written part if you choose to implement Visit; otherwise, your Visit will not be graded. No additional points will be given for Visit in the written part. ## 6. General Hints - You are advised to figure out how to implement the logic of nodes inspection (Report), swap (Exchange), deletion (Revolt) first, as Conquer is a combination of them. - Since Revolt calls Report, they can be done similarly (or even as the same function(s)). - In command Exchange, Conquer and Visit, different existence statuses require different handling methods. It would be ideal to design a shared mechanism to collect and pass the existence status with the pipe or FIFOs. - Check your Report, 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.) - **Double check** return value of your function(s), especially read/write. - **Double 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](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#31-Traversal-Order) for a recommended way of command passing. - If you haven't implemented Revolt, you can always use `htop` to manually close your processes. - Two methods are recommended for manually checking your input and output: - `./monarch WHY < "path_to_input_file.txt" > "path_to_output_file.txt"` - `tee` - Review the course materials thoroughly, read the manual pages for any functions you may need, and go through this specification carefully. - Come to the TA hour if you still need help after completing all double check above (or can provide proof of effort). Otherwise, the TAs will simply ask you to think again. - Eat well, sleep well, and pay attention in every class. ## 7. Written Part (Optional) In this part, you need to explain how you implemented this assignment, including but not limited to the following aspects: - Node initialization. - Command passing mechanism. - Explain the logic and implementation of any of the 5 + 1 functions (including screenshots or annotated code can make your explanation clearer). - Other things you think shows your effort. **Third reminder:** If you implement Visit, this part becomes **mandatory**, use it to explain your logic or your Visit will not be graded. You will not receice additional points in your written part for Visit. ## 8. Code Judging & Grading - We will run your code on ws1. Please ensure that your program can execute properly in ws1. - When working on your assignment, we recommend that you run your code on other workstations. You can check the workstation loading [here](https://monitor.csie.ntu.edu.tw). - Please strictly follows the [IPC content regulation](https://hackmd.io/qZ1vOegwSrKXpVK6_Chepw?view#32-IPC-content-regulation). If we find any invalid content, you will got zero point. - We have a soft time limitation for this assignment, your execution time in `ws1` can't be more than 15 seconds, otherwise you will got zero point for this test case. - We complete all commands except `Conquer` in one times full tree traversal in pipe. The test case `public-input-3-5.txt` has 1,000 commands only with `Exchange` and runs in `7` seconds on `ws1`. It's the biggest one — no test case has more than 1,000 commands. - We complete `Conquer` in one times full tree traversal in pipe and at most two times subtree traversal in pipe. The test case `public-input-5-3.txt` has 1,000 commands only with `Conquer` and `Grant` also runs in `7` seconds on `ws1`. It's the biggest one — no test case has more than 1,000 commands. - We consider certain aspects to be fundamental and will not award partial points for them in the code section once completed, for example: - 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. - If you violate the rules or use any dirty tricks (e.g., building a tree data structure), you will loss the points for the affected part. - Above partial points is possible with written part. ### Public (3.2 points) - Input and output will be provided. - Points of each testcase is equally distributed to all sub-testcases. - Only check output, try to score them. #### Public-Test-Case-1: Grant (0.6) #### Public-Test-Case-2: Grant + Report (0.6) #### Public-Test-Case-3: Grant + Exchange (0.8) #### Public-Test-Case-4: Grant + Revolt (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. - We will check additional information during the final judging phase (e.g., whether the FIFO files are deleted after the command is executed). ### Bouns Visit (1 point) - Input will not be provided, additional checks other than output is possible. - This function will be graded seperately, and directly added to total points, **capped at 8 points**. ### Written part (optional up to 1 point) This part allows for **NO REGRADE** and will only be **manually graded** when: - You did not score full points with coding. - Both code and report are submitted **before the soft deadline**. The points for this part are designed to be **inversely related to your coding points**. Hence, the higher you score in the coding section, the smaller the impact of your written report, and vice versa. You may submit up to 5 + 1 sections of answers, each worth **up to 0.2 points**, for a **maximum total of 1 point**. In each section, the points are divided equally into four parts: - Idea: How and why you designed your implementation. - Correct logic: How logically sound your idea is. - Explanation: How you turned your idea into working code. - Effort: Show a fixed error and how you resolved it, or a bug you couldn’t fix and why. **Late penalty** will be applied to the written part points. ## 9. Submission ### Code Submission You should use GitHub classromm to submit your assignment as before. The folder structure on GitHUb classroom should at least be: ``` ├- public-testcases ├- sample-testcases ├- monarch.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. We will use `make` to build and run your code during grading. You **will lose 0.25 points as a punishment** if you submit those files. ### Written Part Submission ``` <student_id>_report.pdf (e.g. r12345678_report.pdf) ``` Your written part should be submitted in **PDF** format, and you must 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 implementation must be completely your own work. - 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/9 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/16**, your final score will be multiplied by 0.5. - Late submission **after 11/16 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 deadline, 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 do the following things first: - **Google** or use **ChatGPT** first to the best of your ability avoiding plagiarism. - Check the Issues section of SP2025_HW2_release or the NTU COOL discussion to see if other students have encountered the same problem. - If the above doesn’t help, try one of the following: - Post your question on the Issues section of SP2025_HW2_release or the NTU COOL discussion. - Contact TAs by email. - Ask during TA hours (think thoroughly about what you expect as an answer). Please start your work ASAP, I am very confident it is difficult, **DO NOT** leave it to the last day. ## 11. FAQ We will post frequently asked questions here. Before asking, we recommend that you check this section first to see if your question has already been answered. 1. If I cloned the repository after October 27, would the test cases be the most up-to-date ones? **ANS:** We haven’t updated the test cases in the repository, so you’ll need to manually download the new test cases and update them in your local folder. 2. `fief_size` of IPC should it be passed as an int type or as a char type? **ANS:** It should be passed as a char type. 3. This assignment is relatively complex, is it allowed to split the code into multiple files to improve readability? **ANS:** No, please write all of your code in the designated monarch.c file for this assignment. 4. Do `r-Rep-<Valid command>` a `r-Rev-<Valid command>` need to include `<parent_lord_name`? **ANS:** Yes, according to the spec, you only need to add a prefix to the original command. 5. When the input receives EOF, does the program terminate? But since it hasn’t received `Revolt` it shouldn’t enter `print_finish`, right? **ANS:** Only the program that receives the Revolt command will be terminated. Receiving EOF does not mean that the program should terminate. 6. If the test case does not include the `Revolt` command, will the judge automatically kill all processes? **ANS:** Yes, our judge program will automatically terminate the process once the output has finished. 7. Is it allowed to pass a `fief_size` value such as 0 or a negative number into the FIFO to indicate that the target node does not exist? **ANS:** Negative number is invalid format for `fief_size`. However, any IPC content that matched the format in regex is valid. Example: you can pass `0000` to indicate that the target node does not exist. 8. For every question about whether your implementation logic is valid or not. **ANS:** The general answer is: for this assignment, as long as you (1) fulfill each command’s requirements describe in SPEC 4\* and SPEC 8\*, (2) do not record or retain information about nodes other than the node’s parent and direct children, and (3) only forward information that follows the specified format, you will not lose points. 9. Is `Grant WHY pikachu_1000\n\0` is valid? **ANS:** No, you should replace the last newline character with a null character ('\0') after receive command from stdin.   感覺 ok 我加一下我回答過的問題