1. Homepage
  2. Programming
  3. Exercise 2: Binary Search Tree - Challenges in concurrent programming

Exercise 2: Binary Search Tree - Challenges in concurrent programming

Engage in a Conversation
Binary Search TreeConcurrent threadsCBST

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. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

Before you start Ubuntu, please set the number of processors to 2 from VM VirtualBox Manager-->Settings-->System-->Processor. CourseNana.COM

If you are using UTM, right-click on your virtual machine edit->system->show advanced settings and set CPU cores to 2. CourseNana.COM

After this change, if you run the ‘lscpu’ command from a terminal, it should show the number of CPUs = 2. CourseNana.COM

Part 1:

Use your BST code (bst.c file) from Exercise1 or use the model answer code that are attached to this assignment page and add the following new functionalities. Please note 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. CourseNana.COM

Task 1.1 Node balanceTree(Node root);

This function creates a new balanced BST from an input tree of the form made in assignment 1. Note that the BST in Exercise1 is unbalanced and inverted, and the output should be balanced but still inverted. See the tips section on how to create a balanced BST in page 5. CourseNana.COM

Task 1.2 float avgSubtree(Node *N);

This function returns the average of all the nodes. For example, if you pass the root of a BST, the function will return the average of all nodes that are present in the subtree rooted at N. The algorithm for this function will be somewhat similar to printSubtree() as both functions perform complete tree traversal; printSubtree() prints the node-values whereas avgSubtree() accumulates the node values and then finds the average value of them. Inside the main() function in test_bst.c file, averages of an unbalanced BST and its equivalent balanced BST are computed. If the implementation is correct, both averages will be equal (note: the averages may be slightly different due to the implementation of the average as a float. Differences smaller than 0.001 will be fine.) [Optional: Observe the clock cycle counts for the two average calculations in main(). In both cases, avgSubtree() visits the same number of nodes. So, in ‘theory’, both average 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)] CourseNana.COM

Part 2:

Assume that a server machine manages a BST data structure. During the uptime, 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) addNode 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 \n” (2) removeNode 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 \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) avgSubtree The server will compute the average of all the nodes that are present in the BST and print the average 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]avgSubtree =\<SomeNumber>\n” The server executes the commands that are present in a command file one-by-one starting from the first line. CourseNana.COM

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): addNode 19675 .. CourseNana.COM

avgSubtree CourseNana.COM

Thus, for Client1 the server will first insert a node with value 19675, then perform the following operations, and finally compute the average 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. CourseNana.COM

Every 2 seconds the server has a downtime. During a downtime, the server transforms its BST into a balanced BST using the balanceTree() function. The reason for doing this during a downtime is to ensure that no nodes are added while setting up the tree, causing it to become unbalanced again. Note that different BST modifications during uptime causes imbalances in the tree. The main() function spawns a thread to perform the downtime operation every downtime. CourseNana.COM

The function prototype for executing downtime is as follows void downtime(); Task 2.1: Implement the function in serve_client.c void ServeClient(char *clientCommands) that reads the file specified by clientCommands for commands and executes the BST operations one-by-one according to the content of the file. Note that multiple clients will be executing BST operations concurrently. So care must be taken to avoid concurrency issues. CourseNana.COM

Task 2.2: Implement the downtime() function in serve_client.c which calls the balanceTree() function every night. In this exercise, we assume that downtime happens every two seconds. So, balanceTree() is called every two seconds. You can use the function sleep(2) to cause a sleep of 2 seconds between two downtimes. The program ends after three downtimes. CourseNana.COM

Code submission Use the Makefile to compile your code. You are provided with a script called test.sh, that runs test_bst and compares the output with a reference output. Use Valgrind to check memory leaks and errors. The Makefile produces test_bst.o file. The command for checking memory leaks will be valgrind --leak-check=full ./test_bst.o Put bst.c and serve_client.c into a folder named with your student ID and compress the folder to a .zip file. For example: CourseNana.COM

A student with student id of 1234567 should submit 1234567.zip and this file should be able to extracted to a folder with the following structure: 1234567/ ├── bst.c └── serve_client.c Any other form of submission will not be accepted. CourseNana.COM

Marking scheme:

The program must not leak memory and not crash during execution. Any code which does not compile on the virtual machine provided will be awarded 0 marks and not be reviewed. For marking we will use additional, more advanced, test scripts which check whether your program satisfies the specification. If the provided test scripts fail, all the more advanced test scripts are likely to fail as well CourseNana.COM

  • 5 points are given for correctly implementing Task 1.1
  • 1 point is given for correctly implementing Task 1.2
  • 7 points are given for correctly implementing Task 2.1
  • 2 points are given for correctly implementing Task 2.2

We might ask you to explain your code. CourseNana.COM

Get in Touch with Our Experts

WeChat WeChat
Whatsapp WhatsApp
Binary Search Tree代写,Concurrent threads代写,C代写,BST代写,Binary Search Tree代编,Concurrent threads代编,C代编,BST代编,Binary Search Tree代考,Concurrent threads代考,C代考,BST代考,Binary Search Treehelp,Concurrent threadshelp,Chelp,BSThelp,Binary Search Tree作业代写,Concurrent threads作业代写,C作业代写,BST作业代写,Binary Search Tree编程代写,Concurrent threads编程代写,C编程代写,BST编程代写,Binary Search Treeprogramming help,Concurrent threadsprogramming help,Cprogramming help,BSTprogramming help,Binary Search Treeassignment help,Concurrent threadsassignment help,Cassignment help,BSTassignment help,Binary Search Treesolution,Concurrent threadssolution,Csolution,BSTsolution,