Operating Systems

Homework: Processes, Interrupts, Exceptions, Context Switch

Hand-In Procedure

You are to turn in this homework at the beginning of lecture. Please write up your answers to the exercises below and hand them in to a staff member at the beginning of the lecture. Write your CSE login ID at the top of your submission

Assignment Part 1 (Zombies)

In UNIX, a child process may terminate before a parent calls wait(). When the parent calls wait() eventually, it still expects to read the correct exitcode that the child returned. To support this functionality, UNIX does not completely remove the process till it's parent has called wait() on it.

Such processes that have completed execution but still have an entry in the process table are called zombie processes. Usually, the presence of zombie processes in the system for a long time indicates a bug in the program (it is a common error).

Read about Zombie process at this wikipedia article. Also read about the SIGCHLD signal.

Turn in:
In class we discussed that the shell implements "&" functionality by not calling wait() immediately. Should the shell never call wait()? When should it call wait()? Answer by providing short pseudo-code.

Assignment Part 2 (memory and processes in xv6)

Be sure you have read xv6 chapter 2 and familiarized yourself with the xv6 code it refers to before lecture.

Use QEMU with GDB to trace through the free list creation and memory allocation process described in the first part of the chapter. Make sure you understand how the C pointer arithmetic in kfree's for loop works: especially the relationship between the rp, r, and p variables.

Also step through the creation of the first process by allocproc(), and then step through the first context switch into that process via the assembly language swtch() code.

Nothing to turn in for this part.

Assignment Part 3 (traps)

Read: xv6 trapasm.S, trap.c, syscall.c, initcode.S, usys.S. Skim vectors.pl, vectors.S, lapic.c, ioapic.c, picirq.c.

Introduction

Try to understand xv6's trapasm.S, trap.c, syscall.c, initcode.S, usys.S. Skim vectors.S, lapic.c, ioapic.c, picirq.c.

The assigned chapter (chapter 3 of xv6 book) provides a commentary for these files, but you may find it useful to also consult: Chapter 5 of Intel's system programming guide. Be aware that terms such as exceptions, traps, interrupts, faults and aborts have no standard meaning.

Turn in: In xv6, set a breakpoint at the beginning of syscall() to catch the very first system call. What values are on the stack at this point? Turn in the output of x/37x $esp at that breakpoint with each value labeled as to what it is (e.g., saved %ebp for trap, trapframe.eip, scratch space, etc.).

Assignment Part 4 (context switching)

Read: swtch.S and proc.c (focus on the code that switches between processes, specifically scheduler and sched). Also process creation: sys_fork() and copyproc().

In this part of the homework you will investigate how the kernel switches between two processes.

Assignment:

Suppose a process that is running in the kernel calls sched(), which ends up jumping into scheduler().

Turn in: Where is the stack that sched() executes on?

Turn in: Where is the stack that scheduler() executes on?

Turn in: When sched() calls swtch(), does that call to swtch() ever return? If so, when?

Now think back to lecture 2 and the invariants that gcc expects any function, including swtch, to maintain. Compare these invariants with what swtch actually implements, and the state that our kernel maintains in a struct context.

Turn in: Could swtch do less work and still be correct? Could we reduce the size of a struct context? Provide concrete examples if yes, or argue for why not.

Surround the call to swtch() in scheduler() with calls to cprintf() like this: 

  cprintf("a");
  swtch(&cpu->scheduler, &proc->context);
  cprintf("b");

Similarly, surround the call to swtch() in sched() with calls to cprintf() like this: 

  cprintf("c");
  swtch(&proc->context, cpu->scheduler);
  cprintf("d");

Rebuild your kernel and boot it on QEMU. With a few exceptions you should see a regular four-character pattern repeated over and over.

Turn in: What is the four-character pattern?

Turn in: The very first characters are ac. Why does this happen?

Assignment Part 5 (bootsector) : OPTIONAL

This part of the assignment is optional. i.e., this part of the assignment carries no marks. It is just here to give you more insight into the bootsector code. You may choose to skip this part.

A bootsector is only 512 bytes which is a very short space to be able to fit any useful code. So typically a bootsector loads another "program" from disk and jumps to it. For example, the bootsector might load the bootloader code (e.g., GRUB, LILO) and jump to it. The bootloader, in turn, loads the actual OS.

xv6 bootsector contains a very simple IDE disk device driver to read the sectors from disk. An IDE disk has a very simple interface and hence it is possible to fit a device driver inside the bootsector. But what if the boot device (containing the bootloader and the kernel) was a CDROM, SCSI disk, USB disk, etc. All these devices have much more complex interfaces and it will be hard (if not impossible) to fit their device drivers in a bootsector. So how does the OS boot from these devices?

The answer is that BIOS helps in the boot process. BIOS supports certain "BIOS functions" that the bootsector (or bootloader) can call. Some examples of the functionality supported by these functions are: get the physical memory size, read the nth sector of the boot device, etc. This functionality is exposed using the interrupt interface and the int instruction (similar to how system calls are handled on 32-bit linux). Pintos is an OS that is capable of booting through a USB device. You can try booting your personal computer using pintos by using the following command: 

pintos --hardware --
This will create a disk image called os.dsk. You can write this disk image to your USB device using: 
dd if=os.dsk of=/dev/sdb
assuming your USB disk is at /dev/sdb.

Skim through information on "BIOS Interrupt calls" on Wikipedia here, here and here.

Turn in:
Look at Pintos bootsector code and list all the BIOS interrupt calls used by Pintos and their corresponding functionality.

This completes the homework.

Based on MIT 6.828 materials by Frans Kaashoek and others; and Yale OS course materials by Bryan Ford.