CS202 Spring 2015 Lab 4: WeensyOS SchedOS

Released Tuesday, March 3, 2015
Due Friday, March 13, 2015, 9:00 PM

Lab4: Software development tools, Debugging, WeensyOS SchedOS

Introduction

This lab is split into three parts (all due on the deadline). In the first part, you will exercise software skills, and gain familiarity with useful tools. The second part will cover debugging. The third part will introduce you to another WeensyOS operating system. (Recall that WeensyOS is a series of coding exercises, written by Eddie Kohler.) This WeensyOS will exhibit scheduling and synchronization.

Getting Started

Please note the following expectations:

Comments. As with the last labs, you are asked to comment every block of code that you write. As a rough guideline, figure that you need a one-sentence comment every four lines or so (but this is rough; feel free to comment larger blocks). In these comments, you must explain the purpose of the code, rather than narrating the instruction that you gave to the computer. Examples of not-good comments are, "assign variable X to variable Y", "dereference pointer P", or "the following code is a for loop that iterates over the foo array." An example of a better comment would be, "We are closing the following file descriptors because [insert reason here]". To be clear: in the real world, it is terrible style to comment code that is obvious or self-documenting. We are departing from that because, this being a class, we want to make sure that you understand and can explain your code.
Coding style. You will have to pay attention to things like indentation and spacing (which need to be consistent), variable names (which need to be clear and consistent), repeated code (which needs to be avoided), spaghetti code (which needs to not happen), etc. Follow this style guide (also due to Eddie Kohler, adapted from here).

We recommend doing this lab inside the development platform that you set up in the previous labs (the virtual devbox or the CIMS machines).

From within the development platform that you have chosen (which, in the recommended cases, will be the virtual devbox or the CIMS machines), change to your lab directory, use Git to commit changes you've made since handing in lab 3 (if any), obtain the latest version of the course repository, and create a local branch called lab4 based on origin/lab4 (which is our lab4 branch). The commands are as follows, but you may not need all of them (for example, if git status indicates that there are no changes to commit):

$ cd ~/cs202
$ git commit -am 'my solution to lab3'
Created commit 254dac5: my solution to lab3
 3 files changed, 31 insertions(+), 6 deletions(-)
$ git pull
Already up-to-date.
$ git checkout -b lab4 origin/lab4
Branch lab4 set up to track remote branch refs/remotes/origin/lab4.
Switched to a new branch "lab4"
$ cd lab4

You are now in the lab4 directory. For the first two parts of the lab, we will not interact much with the source that you have been provided with. However, your answers must go in answers.txt in your ~/cs202/lab4 directory.

Also, note that WeensyOS SchedOS has an artifically introduced bug, which you will address in the second part of the lab. Thus, you should do the lab in order (although the WeensyOS parts themselves can be done in any order).

Part 1: Software development tools and general productivity

This part of the lab will walk through general software development skills as well as some tools to enhance your productivity. You may feel at first that these tools are slowing you down ("how do I enter characters in vi???"), but comfort and fluency with them will pay off in the long term. It's worth slowing down and "learning proper technique."

A good text editor is essential

If you are not doing so already, begin using a powerful text editor. We recommend vi (which in our development environment is an alias for a more powerful version, called vim) or emacs, both of which are installed on your devbox or the Courant machines.

$ vi myfile.txt 

# or

$ emacs myfile.txt

Most of our instructions below will be with reference to vi, so you may wish to use that one.

To get started, work through either this vi tutorial or the emacs tutorial that is built into emacs. (From within emacs, you can pull up the tutorial by typing C-h t. This is read as "press ctrl-h, then let go, then press t").

Spend at least an hour just navigating and editing sample text (perhaps doing HW5, perhaps writing notes to your friends that you later copy into email). You'll find that within a day or so, you'll have the required keystrokes internalized, and within a few days, you'll probably be faster at common editing tasks.

Another critical skill: mapping out code

Our next topic is mapping out code. What we're going to describe here (both the techniques and tools) is the kind of thing that you should be doing when the labs say, "Read and understand the code."

The top-level point is that most well-designed pieces of software have a particular structure (or architecture); you, as a newcomer to that code, have to figure out what that structure or architecture is, and how the pieces fit together. You figure this out by mapping out the code. In this process, you will learn the high-level structure (for example, the hierarchical relationships among objects) as well as the lower-level details of the code itself (how are objects created? how precisely does the software interact with the rest of the world? etc.)

As with all skills, mapping out code is something that one gets better at over time, with practice. Here are a few techniques that we find helpful. First, when you encounter a new code base, look over the header files; ignore the implementation files at first (that is, look at .h files and ignore .c files). From header files, you learn what the important objects and data structures are, and, crucially, what the interfaces are to the various objects, functions, and modules in the system.

Second, use paper! Draw pictures! Create a box on the page for each struct or class, and label each struct or class with its purpose (and maybe what methods you can call on the class, or functions you can call that take the struct as an argument). Fill in data members that look particularly important. Draw appropriate arrows among these structures. In the shell lab, for example, you could draw a picture of a linked list of command_t structs (perhaps with some of the data members); continuing the example, an important point to have captured is that each command_t potentially points to a linked list "below" it (for a sub-command).

Third, try to figure out the important interfaces. Sometimes these are listed in header files. Write them down too, just so that you have them on the paper. For example, for the shell lab, the important functions include cmd_line_exec (listed in cmdrun.h), and the functions listed in cmdparse.h.

Throughout this process, maintain a list of questions for yourself (you will answer them as you proceed).

The next step is to begin reading the actual code. There are different approaches here. You can go bottom up (try to understand the smaller pieces, and how they are glued into larger ones). Or you can go top down (start with the important interfaces, and examine how they are implemented; or start with a function, and look over all of the functions that it calls). Or you can try to follow the life cycle of an object (class) or struct: where is it created? What functions act on it? Where does it get destroyed, or deleted, or go out of scope?

With experience, you will get faster and faster at the preceding step. It will also go much faster if you use proper navigation tools, of the kind that we turn to now.

Navigating code: `grep`

We now cover grep. Open a terminal and cd to your lab 3 directory. (It's okay if you haven't completed lab 3; you can still do this lab.)

grep can be used to search for a text string or regular expression in files. It is commonly called with the following pattern:

$ grep [flags] [expression-to-search-for] [files-to-search]

To see a concrete example, run the following command:

$ grep "void" sthread.h

grep scans the file sthread.h and prints out each line that contains the term void. You should get the following output:

void smutex_init(smutex_t *mutex);
void smutex_destroy(smutex_t *mutex);
void smutex_lock(smutex_t *mutex);
void smutex_unlock(smutex_t *mutex);
...

Multiple files can be passed into the command:

$ grep "void" sthread.h sthread.cpp
sthread.h:void smutex_init(smutex_t *mutex);
sthread.h:void smutex_destroy(smutex_t *mutex);
sthread.h:void smutex_lock(smutex_t *mutex);
sthread.h:void smutex_unlock(smutex_t *mutex);
sthread.h:void scond_init(scond_t *cond);
sthread.h:void scond_destroy(scond_t *cond);
sthread.h:void scond_signal(scond_t *cond, smutex_t *mutex);
sthread.h:void scond_broadcast(scond_t *cond, smutex_t *mutex);
sthread.h:void scond_wait(scond_t *cond, smutex_t *mutex);
sthread.h:void sthread_create(sthread_t *thrd,
sthread.h:                  void *(start_routine(void*)), 
sthread.h:                  void *argToStartRoutine);
sthread.h:void sthread_exit(void);
sthread.h:void sthread_join(sthread_t thrd);
sthread.h:void sthread_sleep(unsigned int seconds, unsigned int nanoseconds);
sthread.h:long sutil_random(void);
sthread.cpp:void smutex_init(smutex_t *mutex)
sthread.cpp:void smutex_destroy(smutex_t *mutex)
sthread.cpp:void smutex_lock(smutex_t *mutex)
sthread.cpp:void smutex_unlock(smutex_t *mutex)
sthread.cpp:void scond_init(scond_t *cond)
sthread.cpp:void scond_destroy(scond_t *cond)
sthread.cpp:void scond_signal(scond_t *cond, smutex_t *mutex __attribute__((unused)))
sthread.cpp:void scond_broadcast(scond_t *cond, smutex_t *mutex __attribute__((unused)))
sthread.cpp:void scond_wait(scond_t *cond, smutex_t *mutex)
sthread.cpp:void sthread_create(sthread_t *thread,
sthread.cpp:                void (*start_routine(void*)), 
sthread.cpp:                void *argToStartRoutine)
sthread.cpp:void sthread_exit(void)
sthread.cpp:void sthread_join(sthread_t thrd)
sthread.cpp:void sthread_sleep(unsigned int seconds, unsigned int nanoseconds)

$ grep "void" sthread.*
# (Same output!)

You can also search all files in a directory recursively with the -r flag:

$ grep -r "void" .

(This command searches all files in the current directory; it should return hundreds of lines.)

Exercise 1. Run the following command:

$ grep -r "smutex" .

Answer the following questions

Informally, what does the command above do?
Paste the first few lines of the output into answers.txt

Exercise 2. Answer the following questions in answers.txt:

What command can you use to search the file RequestGenerator.cpp for Task objects?
What command can you use to search all header files for the keyword return?

Grep can also match regular expressions. We will give a simple demo here. To learn more about grep and regular expressions, read the man pages!!

Exercise 3. Run the following command:

$ grep -r "smutex.*(.*);" .

What types of lines are returned by the program? What information does this command give you about your code? Place your answer in answers.txt.

Next, we move to the ctags tool, which also helps with code navigation.

Navigating code: `ctags`

We will investigate ctags with the Linux code base as a running example.

If you're using the devbox, you will need to install exuberant ctags first - the included version of ctags does not have the required functionality. You can do this with the following command:

$ sudo apt-get install exuberant-ctags

Create a new directory (not inside cs202, since we don't need the Linux code to be part of your later submission):

$ mkdir ~/learn-ctags
$ cd ~/learn-ctags

Now download and unpack the Linux source code archive. We are interested in the kernel source and header files:

$ wget https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.19.tar.xz 
# the line above will take a few minutes
$ tar -xf linux-3.19.tar.xz linux-3.19/include linux-3.19/kernel
$ cd linux-3.19
$ ls 
include/ kernel/

Now, you are going to use the ctags program. Type:

$ ctags --recurse=yes * 
# this will also take a few minutes

The ctags utility searches a body of code and creates a tag file, which is an index of programming language objects, such as function and variable definitions. The command above invokes ctags recursively on all items in the entire directory (*) in order to create a single tags file that includes information from all files in the repository.

The rest of this section will use vi to interact with tags. However, emacs also supports tags.

Using vi, open the header file for the linux scheduler:

$ vi include/linux/sched.h

We will now walk through some uses of tags. When we type :something, this refers to a command given in vi's command mode. To get into command mode in vi, you type the escape key (vi by default starts in command mode; the editor enters insert mode when you type i, e, a, etc.). Once in command mode, typing :something does the "something". (For example, try pressing escape and then :q.)

Now, let's get started with tags. Type:

:tag sched_attr

This will take you to the definition of sched_attr. To return to your previous position, press ctrl-t.

The tag file that we created indexed all of Linux's source. We can jump to a tag in another file and it will automatically be opened, as we illustrate in the following exercise.

Exercise 4. Type within vi:

:tag block_device_operations

What file does this open? (You can use the command :ls inside of vi to check this.)

You can use ctrl-] to jump to the definition of the object underneath the cursor. Go to line 129 in sched.h (navigate there with :129, since :<number> in vi takes you to the specified line number). Move your cursor over the token futex_pi_state. Press ctrl+].

Exercise 5. What is futex_pi_state? In what file and line is it defined?

If you look up a tag with multiple definitions, a menu will pop up giving you the choice of which definition to view. Try looking up list_head, and note that the menu will show you all of the files where it is defined.

Tags can also be used with regular expressions. For example, to look up all tags containing proc_sched, enter the following:

:tag /proc_sched

And the following command shows tags that contain proc_sched and task (in that order):

:tag /proc_sched.*task

Exercise 6. How many functions does the linux kernel have that contain proc_sched and task? Where are they defined?

For more information about tags, this resource is good.

General productivity: `find`

We now cover a very powerful Unix tool: find.

At a high level, find by default recurses through directories, "looking" at files, to see which files match a provided predicate. Here is the pattern for its use:

$ find [flags] [path...] [expression]

Now cd to the root directory of the linux kernel that you downloaded earlier. Type this command:

$ find .

This recursively prints all files in the current directory (it will print the names of tens of thousands of files).

You can also search on file name patterns:

$ find . -name "sched.h"
./include/asm-generic/bitops/sched.h
./include/linux/sched.h
./include/linux/sunrpc/sched.h
./include/xen/interface/sched.h
./include/uapi/linux/sched.h
./include/trace/events/sched.h
./kernel/sched/sched.h

And you can limit the search to particular directories:

$ find include/linux include/asm-generic -name "sched.h"
include/linux/sched.h
include/linux/sunrpc/sched.h
include/asm-generic/bitops/sched.h

As with most Unix commands, wildcards can be used:

$ find . -name "sched.*"
./include/asm-generic/bitops/sched.h
./include/linux/sched.h
./include/linux/sunrpc/sched.h
./include/xen/interface/sched.h
./include/uapi/linux/sched.h
./include/trace/events/sched.h
./kernel/sched/sched.h

This returns all files named "sched" with any extension.

Where find really starts to be powerful is that you can execute commands on the files that are returned. For example:

$ find . -name "sched.h" -exec grep foobar {} \;

This says, "return all file names that match sched.h and grep each of them for the string foobar."

Exercise 7. How many header files are there in the linux source code?

Hint: The unix program wc can be used to count words or lines from a file or standard input. How can we get the output from find to wc?

More information on find can be found here.

Part 2: Debugging

This part of the lab will give you practice debugging. We will work with two code bases: Ye Ji's demo (from the March 5 class), and WeensyOS SchedOS (which you cloned at the beginning of the lab).

Navigating to syntax errors

Clone Ye's code:

$ git clone https://github.com/cs202/cs202-gdb-tutorial.git
$ cd cs202-gdb-tutorial
$ make

The code has a syntax error; thus, it cannot be compiled.

Fix the syntax error.

Use the compiler's error message to determine what's wrong. Also, recall that in vi you can navigate to a given line of code :<number>. You can also launch vi with its cursor in place:

$ vi +<number> <filename>

to begin directly on a given line number. For example, vi +5 foo.c begins with the cursor at line 5.

After you fix the syntax error, the code will compile. Use make to see this:

$ make

Now, try testing the code itself, using the small test_linked_list utility:

$ ./test_linked_list
Segmentation fault (core dumped)

Aha! Our code compiled, but it was not correct (core dumps are bad). Specifically, the segmentation fault means that our program issued an illegal memory reference, and the operating system ended our process. Making matters worse, we have no idea what the problem in the code is. In the following section, you will learn how to use gdb to debug this kind of problem.

The debugger (`gdb`) in user space

Run gdb: Use the GNU debugger, or gdb to run the program:

$ gdb test_linked_list
(gdb)

Set breakpoints: One thing that you might want to do is to set a breakpoint before the program begins executing. Breakpoints are a way of telling gdb that you want it to execute your program and then stop, or break, at a place that you define. Use the following command to set a breakpoint at the main function:

(gdb) b main
Breakpoint 1 at 0x400963: file test_linked_list.c, line 43.

Then use gdb's command run to actually start the program (this is the general pattern in gdb: one invokes the debugger, perhaps sets a breakpoint, and then starts the program with run):

(gdb) run

The program will be stopped when it reaches the breakpoint (advanced topic: how does gdb conspire with the hardware to make this work??). At this point, you will be presented with gdb's command prompt again. To make the program continue running after a breakpoint, use continue, or c for short:

(gdb) c

Step through code: Of course, if you just c every time you hit a breakpoint, then you will lose control of the program. You often want the command next, or n:

(gdb) n

This "executes" the next line of code, for example executing an entire function. (The command step executes a single line of C code. There is little difference between step and next unless you are about to enter a function. step steps into the function; next "steps over" the function.)

Inspect the values of variables: In gdb's command prompt, the program is stalled. You can query the program's current global and local variables with the print command, or p for short.

Run gdb on test_linked_list. Set a breakpoint at the function list_delete.

At this breakpoint, determine the value of the integer id:

(gdb) print id
$1 = 1

This means that variable id holds the integer 1.

Aside: you can check local variables' names using:

(gdb) info local

Core dump: If a program terminated abnormally (for example, test_linked_list), the state of the program will be recorded by the OS and (if core dumps are enabled) saved in a so-called core dump. gdb can use a core dump to inspect a crash situation.

To debug using core dumps, you must first enable core dumps, and then point gdb at the relevant file. We'll do this in several steps; they will vary depending on which development platform you're using.

On the CIMS machines:

# enable core dumps
$ ulimit -c unlimited 
# in the next command, replace /path/to with the path to.
# also, the parentheses should be included
$ (cd ~ && /path/to/cs202-gdb-tutorial/test_linked_list)
$ ls -l ~/core.*
# below, core.num should correspond to a file in your home directory
$ gdb ./test_linked_list ~/core.[num]

On the devbox:

# enable core dumps
$ ulimit -c unlimited 
$ ./test_linked_list
$ ls -l core
$ gdb ./test_linked_list core

The idea here is that the core file gives gdb enough information to recover the memory and CPU state of the program at the moment of the crash. This will allow you to determine which instructions experienced the error.

Exercise 9. Fix the bug in the code. Recompile and rerun to make sure it is fixed. State the line of code and the fix in answers.txt.

The debugger (`gdb`) applied to WeensyOS

We can also use gdb to debug a kernel running on QEMU:

$ cd ~/cs202/lab4
$ make run-gdb
....
(gdb)

At this point, you can continue execution:

(gdb) c

Uh oh! The dreaded triple fault!!! Another bug; you will fix this below, after gaining a bit more experience with the debugger. For now, quit out of the debugger (using q), start it up again (with make run-gdb), and work through the exercises below.

What is the value of %eax when the kernel first enters the function interrupt()? Place your answer in answers.txt.

To do this, you will need to set a breakpoint. You will also find handy gdb's info command. For example:

(gdb) info registers

outputs the state of the registers.

What is the value of the p_state member in proc_array[0] when the kernel first enters the function interrupt()?

(Hint: use the command discussed earlier.)

The function interrupt() contains a large switch/case statement. The basis of the switch is reg->reg_intno. Which case does the kernel execute the first time that it executes interrupt()?

(Hint: you probably want to use some or all of the gdb commands b, p, and n.)

Now it's time to debug the triple fault. We added two lines of buggy code to the kernel, which are causing the fault; your job is to find and eliminate these lines.

Use gdb to find the bugs that we added to WeensyOS. Delete these bugs. Note: you can find these lines by inspection, but we're not really asking where the errors are; the point of this exercise is to build the skill of using gdb to track down the sources of error.

(Hint: you may want to set two breakpoints: one at the function start() and one at the function interrupt(). Use the debugger's ability to execute a line of code at a time to determine which instruction is causing the fault.)

Part 3: WeensyOS SchedOS

Please note that you can do Parts 3.1 and 3.2 in either order.

Part 3.1: Scheduling

Change into the lab4 directory and run

$ cd lab4
$ make run

This builds and runs the WeensyOS SchedOS. As before, this will start up QEMU. After a moment you should see a window like this:

The SchedOS consists of a kernel and four simple user processes. The p-schedos-app-1 process prints 320 red "1"s, the p-schedos-app-2 process prints 320 green "2"s, and so forth. Each process yields control to the kernel after each character, so that the kernel can choose another process to run. Each process exits after printing its 320 characters. The four processes coordinate their printing with a shared variable, cursorpos, located at memory address 0x198000. The kernel initializes cursorpos to point at address 0xB8000, the start of CGA console memory. Processes write their characters into *cursorpos, and then increment cursorpos to the next position.

Read and understand the SchedOS process code. Specifically, read and understand p-schedos-app-1.c.

Read and understand the comments in process.h. The basic feeling should be familiar to you from Lab 1.

The kernel's job is very simple. At boot time, it initializes the hardware, initializes a process descriptor for each process, and runs the first process. At that point it loses control of the machine until a system call or interrupt occurs. System calls and interrupts effectively call the kernel's interrupt function. Note that this simple kernel has no persistent stack: every time a system call occurs, the kernel stack starts over again from the very top, and any previous stack information is thrown away. Thus, all persistent kernel data must be stored in global variables.

Read and understand the following pieces of kernel code. To do so, use the tools and skills that were exercised in the first part of the lab. Don't worry about every last detail; just get a feeling for the high-level structure and purpose of each function:

The process descriptor structure process_t defined in kernel.h. This is a lot like the process descriptor structure from Lab 1.
The comments at the top of kernel.c.
The start function from kernel.c, which initializes the kernel.
The interrupt function from kernel.c, which handles all interrupts and system call traps.

SchedOS supports two system calls, sys_yield and sys_exit. The sys_yield call yields control to another process, and sys_exit exits the current process, marking it as nonrunnable. The kernel implementations of these system calls (in interrupt()) both call the schedule function. This function is SchedOS's scheduler: it chooses a process from the current set of runnable processes, then runs it. In the first part of this problem set, you'll focus on this function, and SchedOS's scheduling algorithms.

Read and understand the schedule() function from kernel.c. What is the name of the scheduling algorithm schedule() currently implements? (What is scheduling_algorithm 0?)

Exercise 15. Add code to schedule() so that scheduling_algorithm 1 implements strict priority scheduling. Your implementation should give p-schedos-app-1 higher priority than p-schedos-app-2, which has higher priority than p-schedos-app-3, which has higher priority than p-schedos-app-4. Thus, process IDs correspond to priority levels (assuming that numeric priority levels are defined as usual, where smaller priority levels indicate higher priority). You will also need to change p-schedos-app-1.c so that the schedos processes actually exit via sys_exit(), instead of just yielding forever. Test your code.

Please note although SchedOS's current processes never block, your scheduler must work correctly even if processes blocked and later became runnable again.

Exercise 16. Calculate the average turnaround time and average response time across all four jobs for scheduling_algorithms 0 and 1. Assume that printing 1 character takes 1 millisecond and that everything else, including a context switch, is free. (Use the definition of response time given in the book and our class notes.)

Now complete at least one of Exercises 17A and 17B.

Exercise 17A. Add another scheduling algorithm, scheduling_algorithm 2, that acts like scheduling_algorithm 1 except that priority levels are defined by a separate p_priority field of the process descriptor. Also implement a system call that lets processes set their own priority level. If more than one process has the same priority level, your scheduler should alternate among them. You must support at least 1000 different priority levels, and your scheduling algorithm should not be too slow—it should take, say, O(N) time to choose which of N processes to run, rather than O(N²) or O(NP) where P is the number of priority levels.

Exercise 17B. Add another scheduling algorithm, scheduling_algorithm 3, that implements proportional-share scheduling. In proportional-share scheduling, each process is allocated an amount of CPU time proportional to its share. For example, say p-schedos-app-1 has share 1 and p-schedos-app-4 has share 4. Under proportional-share scheduling, p-schedos-app-4 will run 4 times as often as p-schedos-app-1 (at least until it exits); so we might expect to see output like "441444414444144...". (Note that this is a form of priority scheduling, but the priority levels are defined differently: larger shares indicate higher priority.) Also implement a system call that lets processes set their share.

Part 3.2: Synchronization

In this section, you'll see synchronization issues. You will deal with atomic hardware instructions and synchronization primitives that are lower-level than mutexes. This is a good match to our present setting. (As noted in class, mutexes and condition variables are good primitives for application-level concurrent programming; within a kernel, mutexes and condition variables are still appropriate, but one sometimes wants to use lower-level locks as well.)

As you know, synchronization isn't interesting without concurrency, and right now, our operating system is cooperatively multithreaded: each application decides when to give up control. We introduce concurrency by turning on clock interrupts and introducing preemptive multithreading. When a clock interrupt happens, the CPU will stop the currently-running process -- no matter where it is -- and transfer control to the kernel. This indicates that the current process's time quantum has expired, so the kernel will switch to another process. However, note that clock interrupts will never affect the kernel: this simple kernel runs with interrupts entirely disabled. Interrupts can only happen in user level processes.

Change scheduling_algorithm back to 0. Then change the interrupt_controller_init(0) call in kernel.c to interrupt_controller_init(1). This turns on clock interrupts.

After running make run, you should see a window like this:

Clock interrupts are occasionally preempting SchedOS processes, breaking up the steady round-robin order.

Refer to the picture above (not your own SchedOS, which may differ). During the execution of which process does the first known timer interrupt occur? Explain your answer.

But we're not done! Let's cause clock interrupts to happen a little bit more frequently.

The HZ constant in kernel.h equals the number of times per second that the clock interrupts the processor. It is set to 100 by default, meaning the clock interrupts the processor once every 10 milliseconds. Set this constant to 1000, so that the clock interrupts the processor every milliscond.

After running make run, you should see a window similar to this:

Note that the output has less than 320*4 characters! Clearly there is a race condition somewhere! (Your particular output may differ. You may actually see 320*4 characters with occasional gaps, which demonstrates a related race condition. If you still see 320*4 characters with no gaps, try raising HZ to 2000 or even higher.)

Exercise 19. Implement a synchronization mechanism that fixes this race condition. Your code should always print out 320 * 4 characters with no spaces. (However, it is OK for the ordering of characters to vary. For instance, you might end with a string of the same character, depending on precisely how timer interrupts arrive.)

There are lots of ways to implement the synchronization mechanism; here are a few.

Implement a new system call that atomically prints a character to the console.
Use the atomic operations in x86sync.h directly.
Use the atomic operations in x86sync.h to build a lock data type, then use lock_acquire and lock_release operations. Note that all four processes must share the same lock! It does no good to implement a different lock object per process.
Implement new system calls that provide lock_acquire and lock_release operations.

However, you must not turn off clock interrupts. That would be cheating. Some hints:

You may need to use typecasts to get the x86sync.h atomic operations to work.
Note that cursorpos points to a 16-bit integer, so the C statement cursorpos++; actually increments the address stored in cursorpos by 2 bytes, not one.
If you create a lock object, make sure that all four processes share a single lock object. (There's no critical section if each process uses a private lock!) You can tell each lock's address by looking in the obj/p-schedos-app-[1-4].sym files, which tells you where each symbol is located. Note that cursorpos has the same address in each process.

Honors supplement. Honors students (section 001) should choose ONE of the two exercises below; students in section 002 are free (even encouraged) to do the exercises, but there will be no credit given.

Exercise 20 (Honors). Implement another interesting scheduling algorithm—for example, lottery scheduling or multilevel queue scheduling (Google for more information). Explain how your scheduling algorithm is supposed to work, describe any new system calls you supplied, and code the algorithm with a new scheduling_algorithm value.

Exercise 21 (Honors). Implement more than one synchronization mechanism for printing characters. Use preprocessor symbols so that your code can be compiled with either mechanism.

Handing in the lab

If you have not done so yet, commit your code.

$ git status  # see what files you changed
$ git diff    # examine your changes
$ git commit -am "My solutions to lab4"

Then, follow these steps:

Make sure that you are on the lab4 branch (and that the commit above went to the lab4 branch!), and inside your lab4 directory.
Make sure that you have filled out answers.txt.
Make sure you have answered all code exercises in the files, and that your code is consistent with the expectations described in the introduction.
Create a file called slack.txt noting how many slack hours you have used for this assignment. (This is to help us agree on the number that you have used.) Include this file even if you didn't use any slack hours.
Then do:
```
  $ make handin
```
This command removes binaries from your directory, archives your directory in a tarball called lab4-handin.tgz, and invokes a script that submits this tarball to our submission server. Assuming that you performed the submission setup step in lab1, you should see something like this:
```
  CLEAN
  CREATE lab4-handin.tgz
  SUBMITTING ... 
  ... progress ...
  Submission successful
```

After a successful submission, you should receive email confirmation (at your NYU email address).

If you submit multiple times, we will take the latest submission and count slack hours accordingly.

This completes the lab.

Last updated: Mon May 04 11:24:46 -0400 2015 [validate xhtml]