CSC 469F | Assignment 2 | Fall 2006

Due: 6:00 p.m., November 17, 2006.

1. Introduction
2. Starting Points
3. Submission Instructions

GOAL: To study support for multiprocessor scheduling in desktop and workstation operating systems.

You may again work in teams of 2 for this assignment.

Small-scale multiprocessors (2-8 CPUs) are becomming commonplace, with even some laptops containing dual-core hyperthreaded hardware today. For these systems, the primary concern is support for multiprogramming -- running several mostly-independent processes simultaneously -- rather than support for parallel programming. It is therefore rare to find support for parallel jobs such as gang scheduling in these operating systems, but concerns of how to organize run queues, together with load balancing and processor affinity still must be handled.

In this assignment, you will research (using source code and other resources) the multiprocessor scheduling support provided by FreeBSD (version 6.1-RELEASE), Linux (version 2.6.9) and Darwin (version 8.6 XNU).

Your investigations should focus on the following points:

• the run queue organization (illustrate this with a diagram)
• how new tasks (or threads) are initially assigned to run queues
• how load balancing is handled
• how processor affinity is supported, including how the POSIX sched_getaffinity and sched_setaffinity system calls are handled.

Discuss your findings in an 8-12 page report (use 12 point fonts, 1.5 line spacing, and 1 inch margins). Include an introduction and a conclusion.

Make specific references to the source code (file name, functions, line numbers) in your discussion. You may use any non-live-human resources in addition to the code, provided they are properly cited and referenced in the bibliography of your report. For example, books, wikipedia, Linux Journal online articles, etc. are ok, while asking a question about multiprocessor scheduling on the Linux Kernel mailing list is not. You must, however, describe the schedulers in your own words.

Do not discuss other scheduling issues such as priority adjustments or real-time scheduling, unless these are specifically related to multiprocessor scheduling.

Browsable, searchable, cross-referenced source code for all of these systems (and more) is available online at http://fxr.watson.org. The indexing is provided by the LXR (Linux Cross Reference) tool.

• FreeBSD 6.1:
  FreeBSD provides two schedulers in the source code, the "old" scheduler based on BSD 4.3, and the "new" ULE scheduler. You should focus on the ULE scheduler, found in kern/sched_ule.c. Both schedulers define many of the same symbols, structures and functions (only one is compiled into a particular kernel), so be careful when you are browsing the code to make sure you are looking at the ULE versions, rather than the BSD versions. In looking for non-source code resources, you will find it helpful to look for information on the FreeBSD ULE scheduler specifically.
  The main FreeBSD project pages are at http://www.freebsd.org.
  
• Linux 2.6.9:
  The Linux scheduler, like most other parts of the Linux kernel, is constantly evolving. Be careful to verify claims made in online or print articles that say "the Linux scheduler does X" against the source code for 2.6.9. Earlier versions of the Linux scheduler (pre-2.6.8?) treated each logical processor on an SMT system as a full physical processor, but the 2.6.9 scheduler is SMT-aware.
  The main scheduler code can be found in kernel/sched.c.
  
• Darwin 8.6 XNU:
  Darwin is the open-source core of the Mac OSX operating system, and inherits much code from BSD Unix and Mach. The scheduler in particular is based on Mach, which provided multiprocessor support from the beginning.
  The main starting point for the scheduler code is osfmk/kern/sched_prim.c.

To understand what happens when new threads are created, you will probably want to look at how fork() interacts with the scheduler, and to see how the POSIX affinity-related system calls are dealt with, you should look at the system call handling code for each system.

Submit hardcopy of your report using the assignment drop box in BA 2220 (The box is labelled CSC469, and is located on the lower right side of the array of boxes).

Submit a softcopy of your report (postscript or pdf format) using 'submit -c csc469h -a A2 a2.pdf' on CDF. (file name a2.ps is also accepted).