Carnegie Mellon
SCS logo
Computer Science Department

15-410 Project 4 Implementation Riddles

This semester Project 4 will consist of three "implementation riddles". We would like you to extend your P3 kernels to address the issues raised by these riddles. It is likely that the requirements changes will require you to redesign and re-implement one or more parts of your code, and fairly likely that you will uncover one or more bugs in your existing implementation.

Implement getchar()

Please implement getchar() to the specification in kspec.pdf. But please spend some time thinking and documenting the hard cases before beginning... getting the interaction between readline() and getchar() right required substantial thought last semester--for the groups who managed to do it.

Implement task_exit()

Please implement task_exit() as follows:

void task_exit (int status)

Causes all threads of a task to exit. The behavior of the system call should be as if the invoking thread ``exits last,'' i.e., the status parameter becomes the exit status of the whole task.

It is important that all threads of a task exit in a timely fashion. You should be able to identify several increasingly-good definitions of "timely", and should strive to implement the most-timely version you can.

What's the matter with remove_pages()?

Some time after we unleashed the remove_pages() specification on the class, one of your dastardly instructors was struck by how potentially-dangerous this system call truly is. Of course, it is possible for a rogue thread to remove memory in use by another thread, such as its stack...ouch! But that's just the beginning of the fun.

Consider what happens if a thread calls readline() and there isn't a line of keyboard input waiting. Now consider what happens if a rogue thread calls remove_pages() specifying the user-space buffer readline() intends to fill.

We decided not to use this problem as a P3 test because we suspected it would cause a great many P3 kernels to crash. We then decided not to publish the test code, because of the strong opinion on the part of the TA's that it would cause widespread demoralization, or at least cause many groups to focus on this problem to the exclusion of others. So, thank your 410 TA at the next available opportunity. But now that you've already written a solid P3 kernel, the gloves are off!

This problem has several possible solutions. We suggest that you think about it until you find at least two solutions before settling on a course of action. Provide a concise but appropriately educational explanation of your ruminations in your P4 README.dox.

By the way, for the curious among you:

  1. The problem is not actually due to remove_pages(); theoretically, the traditional 15-412/15-410 brk() system call could have been used to pose the same riddle. But there's a good practical reason why the thought didn't cross our minds in brk()-land...
  2. Near the end of the P3 period, a group came to us in some excitement, having also discovered this problem. They are entitled to our congratulations--or, at least, they will be once they pass the relevant tests!

Have Fun!

Make sure to have some fun with this project. You've earned it, right?

[Last modified Monday April 12, 2004]