WeensyOS Minilab 2: Scheduler OS

Introduction

WeensyOS 1 introduced you to threads, and particularly thread creation and thread switching. This lab introduces you to another Weensy operating system that shows off scheduling and synchronization!

Setting up

Download lab2 source, unpack and examine the source for weensyos2 using the following commands:

% tar xvzf weensyos2.tgz
% ls weensyos2
COPYRIGHT    lib.c         schedos-3.c     schedos-kern.h      x86.h
GNUmakefile  lib.h         schedos-4.c     schedos-loader.c    x86struct.h
answers.txt  mergedep.pl   schedos-app.h   schedos-symbols.ld  x86sync.h
bootstart.S  mkbootdisk.c  schedos-boot.c  schedos-x86.c
conf         schedos-1.c   schedos-int.S   schedos.h
elf.h        schedos-2.c   schedos-kern.c  types.h
%

Change into the weensyos2 directory and run gmake run-schedos.

This will build and run the single operating system you'll use in WeensyOS 2, the "scheduler OS" or SchedOS. As before, this will start up Bochs, but not the emulated computer. To start the emulated computer, type "c" at the <bochs:1> prompt. After a moment you should see a window like this:

Part 1: Scheduling

The SchedOS consists of a kernel and four user processes. The processes are extremely simple: the schedos-1 process prints 320 red "1"s, the schedos-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. After printing all 320 characters, each process exits.

The four processes coordinate their printing with a shared variable, cursorpos, located at memory address 0x190000. Note that just like Minilab 1, these mini-processes share data/code segment with each other so the modification of cursorpos in one process will be reflected in another process. 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 schedos-1.c.

Read and understand the comments in schedos-app.h. The basic feeling should be familiar to you from WeensyOS 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 restart the kernel by effectively calling the trap 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.

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 trap()) 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 schedos-kern.c.

Exercise 1. What is the name of the scheduling algorithm schedule() currently implements? (What is scheduling_algorithm 0?)

Exercise 2. Add code to schedule() so that scheduling_algorithm 1 implements strict priority scheduling. Your implementation should give schedos-1 higher priority than schedos-2, which has higher priority than schedos-3, which has higher priority than schedos-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 schedos-1.c so that the schedos processes actually exit via sys_exit(), instead of just yielding forever. Test your code.

Exercise 3. Calculate the average turnaround time and average wait 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.

Exercise 4A. 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.

Exercise 4B. 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 schedos-1 has share 1 and schedos-4 has share 4. Under proportional-share scheduling, schedos-4 will run 4 times as often as schedos-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.)

Part 2: Synchronization

In this section of the problem set, you'll investigate synchronization issues. But 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 schedos-kern.c to interrupt_controller_init(1). This turns on clock interrupts.

After running gmake run-schedos, you should see a window like this:

Note: It is better to do this portion of the lab using bochs. Qemu's interrupt handling is too fast; you may not be able to observe the same interrupt effects on qemu.

Exercise 5. Explain what has happened. Why does this output look different from the output without clock interrupts? Be specific (talk about particular lines of schedos-1.c).

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

The HZ constant in schedos-kern.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 gmake run-schedos, you should see a window like 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 3000 -- but not much higher, since Bochs starts acting weird.)

Exercise 6. Explain what has happened. Why does this output look different from the earlier two? Be specific (talk about particular lines of schedos-1.c, and why the higher clock rate made a difference). Where is the race condition?

Exercise 7. Implement a synchronization mechanism that fixes this race condition. Your code should always print out 320 * 4 characters with no spaces. (The ordering of characters may vary, however, due to clock interrupts.)

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

• 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/schedos-[1-4].sym files, which tells you where each symbol is located. Note that cursorpos has the same address in each process.

This completes the problem set.

Handing in

You will electronically hand in code and a small writeup containing answers to the numbered exercises and extra-credit exercises.

Answer the numbered exercises 1, 3, 5, 6 by editing the file in the weensyos2/ directory named answers.txt. Only ASCII text files are accepted. Please do not hand in Microsoft word documents nor PDF files. For coding exercises, it's OK for answers.txt to just refer to your code (as long as you comment your code).

Run the command make tarball to create a file named weensyos2-yourusername.tar.gz. This tarfile contains the answers.txt file.

Submit the weensyos2-yourusername.tar.gz file here.