develop a program that will have N worker threads created by the main thread the program will have a shared binary search tree

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

CS342 Operating Systems-Fall2019

Project#2Threads, Processes, and Synchronization

1  Assignment

1.1      Part A - Synchronizing Threads

You will now develop a program that will have N worker threads created by the main thread. The program will have a shared binary search tree (pointed by a global variable) with size at most K nodes. The tree is shared among all threads. The tree will be implemented with pointers, not using an array. The tree will keep the K  largest integers seen so far in the input files. Each worker thread will process an input file of integers (one integer per line). There will be N input files. Each such worker thread will read an input file one integer at a time. This time we will read with fscanf (easier). After reading an integer from the input file, the worker thread will insert it into the binary search tree if necessary, otherwise it will discared the integer. Then it will read the next integer from the file. All N worker threads will work like this concurrently. When all worker threads finish, we will have the K largest integers seen in those N files in the binary tree. Then the main thread will print them out in sorted decreasing order to an output file file. You need to implement the tree youself. You can not use a library or an existing code for this purpose.

We will invoke the program as below:

topk_thread_synchron ...

You will use POSIX mutex and conditions variables (if required) to synchronize the threads.

1.2 Part B - Synchronizing Processes

Now you will write a similar program, but this time worker child processes will be used to process the input files. You will also use shared memory to pass information from children to the parent process. That means you will implement your binary search tree to sit in the shared memory. Shared memory should be large enough to hold K binary tree node.

We will invoke the program as below:

topk_process_synchron ... You will use POSIX semaphores to synchronize the processes.

1.3  Part C - Experimentation

 

For both programs, first of all try see what is happening if we don’t synchronize the threads or processes. Do we get wrong results some time?

 

Measure and compare the running of two programs for various values of the following parameters: N, K, integer count in an input file, and try draw conclusions. Write your experimentation experience and results into a report document and convert the document to PDF (report.pdf). The report should include tables or plots and conclusion(s) as well.

 

2 Submission

Put all your files into a directory named with your Student Id. In a README.txt file write your name, ID, etc. The set of files in the directory will include README.txt, Makefile, report.pdf, topk_thread_synchron.c and topk_process_synchron.c. When we type make, all your programs should be compiled and the related executables should be generated. Then tar and gzip the directory. For example a student with ID 21404312 will create a directory named “21404312” and will put the files there. Then he will tar the directory (package the directory) as follows:

tar cvf 21404312.tar 21404312 Then he will gzip the tar file as follows:

gzip 21404312.tar}

In this way he will obtain a file called 21404312.tar.gz. Then he will upload this file in Moodle.

 

Late submission will not be accepted (no exception). A late submission will get 0 automatically (you will not be able to argue it). Make sure you make a submission one day before the deadline. You can then overwrite it.

 

3 Tips and Clarifications

• Work incrementally. Be

• The “man shm_overview” command will give you help information about POSIX shared memory in Linux

• The “man sem_overview” command will give you help information about POSIX semaphores.

• The “man pthreads” command will give you information about POSIX threads and also mutex and condition

• Max value of K is 10000. Min value is

• Max value of N is 10. Min value is

• An input file can contain a very large number of

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme