Project 3: Minithreads

---

This is a group assignment. Start early.

Introduction:

This is a difficult assignment. You should read through all of the source files and get a general idea as to what the structure of the system is like and what is expected of you before you start writing code. You have two weeks to do the assignment, which should give you plenty of time, but we recommend that you start right away.

This assignment is broken down into three parts, the second and third of which rely on the first.

1. First, you will implement your own thread management system called minithreads in which you will be able to explore what we've been discussing in class about how non-preemptive thread systems work.
2. In the second part of the assignment, you will write two test applications that demonstrate some classical problems in concurrent programming, as well as stress your thread system.
3. In the third part of the assignment, you will add preemption to your threads package.

The Threads Package:

UNIX gives each process a single thread in a single address space. We want to treat that single UNIX thread as a VIRTUAL PROCESSOR, with which we can schedule multiple threads from the same address space. Each thread represents an independent execution context (private registers, stack, some private scheduling state). The single thread provided by the UNIX operating system is time-multiplexed (by you) across the many minithreads within one address space.

In other words, you deal with the VIRTUAL PROCESSOR given to you by UNIX as UNIX treats the PHYSICAL PROCESSOR on which it runs.

• Debuggability. It's a lot easier to develop and debug programs in user space than it is in the kernel; if you make a mistake, you can fall into the debugger and figure out what happened. (Ask yourselves, fundamentally, why is it easier to develop user-level code than kernel code).
• Cost. If everyone was working on their own kernel, then everyone would need their own computer, and we would need 40+ computers for this class.
• Simplicity. An operating system such as UNIX already provides many auxiliary services that you need for an assignment like this. These services include memory management, a file system, etc. In this assignment, we will be relying on these UNIX services. As the quarter progresses, though, we will be writing our own versions of some of these services.

Getting Started:

tar xvf minithreads.tar

This will extract all the files into the directory minithreads in the current directory.  You could extract the files into the group work directory. (or personal directory if you want your own copy or want

Part 1. Non-Preemptive Threads:

We are providing you with some low level machine dependent functions for stack allocation and deallocation, and context switching. These are defined in include/minithread_public.h, src/minithread_public.c, include/minithread_md.h and src/sys.S.

In addition, a skeleton test program, src/runtester.c, is provided. You can use the routine tester() in this file to implement test programs for your minithreads package. We will provide our own implementation of tester() so that we can test you code when you hand it in, so please leave the references to runtester.c in the Makefile. Because this version of minithreads will be non-preemptive, you will have to include calls to minithread_yield() at arbitrary points in your test program to ensure that interleaved executions work correctly.

You may implement any scheduling policy that you like, although if you implement something other than FIFO, you should explain your motivations which led you to do so.

There will undoubtedly be functions and data structures that you will want to use that are not reflected in the versions of the header files that we have provided. If those functions and data structures need to be made public, then you should declare them in other header files. For convenience, place your own header files in the part1 directory you created (normally, you would place them in the include directory, but turning in two directories is kind of annoying, so put them in part1). If you add new files don't forget to edit your Makefile and/or run make depend to update dependencies.

Part 2. Applications:

Bounded Buffer
Write a solution for the bounded buffer problem. You have one producer thread and one consumer thread. The producer produces random null-terminated character strings and puts them in a buffer pool which can contain at most 10 strings. The consumer takes strings out of the pool and prints them to the screen.

Place your solution to this problem in part2/boundbuf.c. Include a Makefile that produces an executable named boundbuf.

The Cigarette-Smoker's Problem
(From OSC 5th Edition, Exercise 6.8) Consider a system with three smoker processes and one agent process. Each smoker continuously rolls a cigarette and smokes it. But to roll and smoke a cigarette, a smoker needs three ingredients: tobacco, paper, and matches. One of the smoker processes has an infinite supply of paper, another has an infinite supply of tobacco, and the third has an infinite supply of matches (don't ask me why). The agent has an infinite supply of all three materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient then rolls and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats. Write a program to synchronize the agent and the three smokers.

Place your solution to this problem in part2/cigarette.c. Include a Makefile that produces an executable named cigarette.

Part 3. Preemption:

Your solution to this part should be palced in a directory named part3.

In order to protect critical regions of your scheduler from unwanted interrupts, you will need to explicitly enable and disable interrupts at certain points in your scheduler code. However, disabling interrupts too often is not good, and should be avoided. Note that your application programs should not directly request enablement or disablement of interrupts. They should use appropriate blocking synchronization primitives such as semaphores.

Recall that your threads will be running in a single address space. Therefore, you must also use synchronization constructs around any calls to the memory allocator, i.e., malloc and free (why is this so?). The file include/my_malloc.h prototypes wrapper routines called my_malloc and my_free. You should implement these routines in part3/my_malloc.c and add them to your minithreads package. Replace all your calls to malloc and free with my_malloc and my_free. If you are not religious about this, any code that (de)allocates memory will crash at random points, so be careful...

You should test your preemptive implementation initially with a simple program that has several threads in it each of which is counting upwards; ensure that the execution of these threads is interleaved.

You should then rerun the applications from part 2 of the assignment, making sure that you continue to get correct answers with your thread system (note that with preemption, execution ordering can be non-deterministic, so you may not get the same results).

What To Turn In:

• what the code does
• how to build the code
• how to run the executable
• your design and implementation
• your test plan
• anything else noteworthy

Use turnin to submit your solution. From the minithreads directory, use:

turnin -c cse451 -p project-3 part1 part2 part3