本次英国代写是C语言数据结构的一个assignment
Exercise 2
This exercise has total 15 points. Each point amounts to one percent of the total module mark. You are not allowed to use any external library in your code. We might ask you to explain your code.
All assessment deadlines in this module are strict. Late submissions will get a mark of 0. All submissions must work on the virtual machine as specified.
This exercise addresses the challenges in concurrent programming. It will use the Binary Search Tree (BST) data structure that you have implemented in Exercise1. Multiple concurrent threads will perform read/write operations on the BST data structure.
Before you start Ubuntu, please set the number of processors to 2 from VM VirtualBox Manager–>Settings–>System–>Processor.
If you are using UTM, right-click on your virtual machine edit->system->show advanced settings and set CPU cores to 2.
After this change, if you run the ‘lscpu’ command from a terminal, it should show the number of CPUs = 2. Part 1:
Use your BST code (bst.c file) from Exercise1 and add the following new functionalities. Please, not that the header file has changed in this assignment, and you may need to adapt your code. You may add helper functions to the bst.c file.
Task 1.1 Node* balanceTree(Node* root);
This function creates a new balanced BST from an input BST. Note that the BST in Exercise1 is unbalanced. See the tips section on how to create a balanced BST in page 5.
Task 1.2 int sumSubtree(Node *N);
This function returns the sum of all the nodes. For example, if you pass the root of a BST, the function will return the sum of all nodes that are present in the tree. The algorithm for this function will be somewhat similar to printSubtree() as both functions perform complete tree traversal; printSubtree() prints the node-values whereas sumSubtree() accumulates the node values.
Inside the main() function in test_bst.c file, sums of an unbalanced BST and its equivalent balanced BST are computed. If the implementation is correct, both sums will be equal.
[Optional: Observe the clock cycle counts for the two sum calculations in main(). In both cases, sumSubtree() visits the same number of nodes. So, in ‘theory’, both sum calculations should roughly consume the same number of cycles. In ‘practice’, do you see any difference
in the cycle counts? If you see a difference, what could be the reason? You do not have to submit your answers for this optional question. (run “make cycle” to do this experiment)]
Part 2:
Assume that a server machine manages a BST data structure. During the day-time, many clients perform operations on the BST. Each client sends its BST-commands in the form of a command- file to the server.
Valid commands that can be executed by the clients are:
(1) insertNode <some unsigned int value>
The server will insert the node with the specified value in the tree. Note that this operation modifies the BST.
The server also prints a log using printf() in the format of
“[ClientName]insertNode <SomeNumber>\n”
(2) deleteNode <some unsigned int value>
The server will delete the node with the specified value from the tree. Note that this operation modifies the BST.
The server also prints a log using printf() in the format of
“[ClientName]deleteNode <SomeNumber>\n”
(3) countNodes
The server will count the current number of nodes in the BST and print the number on the display. Note that this operation does not modify the BST.
The server also prints a log using printf() in the format of
“[ClientName]countNodes = <SomeNumber>\n”
(4) sumSubtree
The server will compute the sum of all the nodes that are present in the BST and print the sum on the display. Note that this operation does not modify the BST.
The server also prints a log using printf() in the format of “[ClientName]sumSubtree = <SomeNumber>\n”
The server executes the commands that are present in a command file one-by-one starting from the first line.
Example: Assume that the server has received a file ‘client1_commands’ from Client1. Let, the file contents be (starting from the beginning of the file):
insertNode 19675 …
…
sumSubtree
Thus, for Client1 the server will first insert a node with value 19675, then perform the following operations, and finally compute the sum of the tree etc.
The server serves multiple clients concurrently. For each client, the server calls void* ServeClient(char *clientCommands) in a concurrent thread and passes the name of the command-file using the string pointer clientCommands.
Every night the server has a downtime. During a downtime, the server transforms its BST into a balanced BST using the balanceTree() function. Note that, different BST modifications during the day-time causes imbalances in the tree. The main() function spawns a thread to perform the downtime operation every night.
The function prototype for executing downtime is as follows
