CSCI 401 Operating Systems Instructor: Gedare Bloom Project 3 (100 points) You must do this assignment in collaboration with your team members, if any. You may not use code downloaded from the Internet. Always watch the course website for updates on the assignments. Read all instructions carefully. Start early. Due Sunday, November 20 This project will be completed in teams of 2. Both team members will receive the same grade subject to participation. You are expected to work together, in person, at the same computer. You may choose your own team member. You and your team member must arrange to join the same Project3_Groups on Blackboard prior to submitting. Send the instructor an e-mail if you have trouble and need a manual adjustment of your group. You will need a Linux development environment for this assignment, in particular you need to be able to boot and run the Linux kernel version 3.16.0. See the instructions from Project 2 for more information. The LKD book and supplemental LDD book (available as PDF) will be helpful. Printing a Red-Black Tree using seq_file (100 points) Write a module called tree_traversal that creates a /proc entry file that, when read, displays your module's red-black tree. Much of the implementation has been completed, but some key aspects are missing. Comments labeled with TODO mark locations in the file where code needs to be added; the TODO statements provide additional instruction on what needs to be done. The code that exists will create and initialize the red-black tree, and will also create and destroy the /proc entry. The functionality to display the tree in the proc file is missing. You can add any code, functions, or data structures that you think are necessary to complete the assignment. You should first locate all of the TODO statements, so that you know what must be done. Then, look at the example seq_file implementation: http://lwn.net/Articles/22355/ and a description of how the red-black tree works: http://lwn.net/Articles/184495/ -- similar information can also be found in the Documentation/ directory inside of Linux. Finally, you will be responsible for adding locking – the tree is exported to an in-memory file, which can be read at any time; however, the module could change the data stored inthe tree at any time, so consistency must be ensured. How you choose to lock the critical data is left for you to decide. To test your implementation, you should be able to read the file in /proc using, for example, the less command. Any number of elements in the tree should work. If an error occurs, your module should print a useful message in the log file. To further test your program, use other commands that read from files such as head and tail. Your module will be tested by a combination of such commands, and other methods. Requirements 1. Use make. Your makefile should have a default target to build your modules and a clean target to remove all compiled files. Your modules should have the exact name given in the assignment. 2. COMMENT YOUR CODE. If something doesn't work, you may get partial credit if your comments show that you were on the right track. Remember to put a comment block at the top of every file. Document any places where you received help from anyone else. 3. Remember to use the MODULE_ macros to document your module. 4. Check return values on any function that can possibly fail. Add return values to any function that can fail. 5. Your source code must use UNIX style EOL characters \n not DOS style \n\r. You can write code on Windows, but you must convert it to Unix text files before submitting. The dos2unix command may be useful for this. 6. You must submit a README file (no extension necessary) that explains how to build and run your program, gives a brief description of the pieces of your assignment, and contains any notes from discussions with your peer group partner. 7. Start with filling in bits and pieces of the missing implementation. Incremental development is key! Add locking after you have correctly implemented a solution. 8. When implementing locking, identify the critical data, find where the data is used, and then lock that critical section. You will have to add the lock primitives that you choose to use. 9. Be sure to address all of the TODO statements. BUT do not be afraid to add code that is not explicitly requested. Help Module programming: http://tldp.org/LDP/lkmpg/2.6/html/index.html Linux Kernel API: http://www.gelato.unsw.edu.au/~dsw/public-files/kernel-docs/kernelapi/ Cross-linked Linux source: http://lxr.linux.no/linux/ seq_file: http://lwn.net/Articles/22355/ Red-Black Tree: http://lwn.net/Articles/184495/ Always watch your email for updates on the assignments.Submission Instructions (read carefully) Your submission must consist of your README, module source code and makefiles; do not include compiled output! Your source code must use UNIX style EOL characters \n not DOS style \n\r. You can write code on Windows, but you must convert it to Unix text files before submitting. The dos2unix command may be useful for this. Put all of your files in a single directory with both team members last names as Lastname1Lastname2/. Make a tar and gzip file with both team members last names in the file name. – tar -zcvf Lastname1Lastname2.tgz Lastname1Lastname2/. Where all of your files are in the Lastname1Lastname2 directory. Upload the tgz file to Project 2 on Blackboard. Grading Rubric …