Homework 4

W4118 Fall 2011

UPDATED: Saturday, 11/05/2011 at 7:35pm EST

DUE: Wednesday, 11/9/2011 at 11:59pm EST

All non-programming, written problems in this assignment are to be done by yourself. Group collaboration is permitted only on the kernel programming problems. All homework submissions (both individual and group) are to be made via Git. Git repository access will use the same public/private key-pair you used for previous homeworks (see these Git instructions).

Individual Written Problems:

The Git repository you will use for the individual, written portion of this assignment can cloned using: git clone gitosis@os1.cs.columbia.edu:UNI/hmwk4.git (replace UNI with your own UNI). This repository will be accessible only by you.

1. Exercise 5.9

2. Exercise 5.11

3. Exercise 5.12

4. Exercise 5.19

5. Exercise 5.20

6. Exercise 5.21

Group Programming Problems:

Group programming problems are to be done in your assigned groups. The Git repository your entire group will use to submit the group programming problems can be cloned using: git clone gitosis@os1.cs.columbia.edu:TEAM/hmwk4.git (Replace TEAM with the name of your team, e.g. team1). This repository will be accessible to all members of your team, and all team members are expected to commit (local) and push (update the server) changes / contributions to the repository equally. You should become familiar with team-based shared repository Git commands such as git-pull, git-merge, git-fetch. One important thing to remember is to pull any changes into your local repository before trying to push any commits to the class server. Some useful screen casts / tutorials can be found on gitcasts.com.

All team members should make at least five commits to the team's Git repository. The point is to make incremental changes and use an iterative development cycle. Please follow the Linux kernel coding style.
Hint(1): use the checkpatch.pl script located in the linux-msm-2.6.32/scripts directory within your repository. Points will be deducted for non-compliance!

All kernel programming assignments in this year's class are done on the Android operating and targeting the ARM architecture. For more information on how to get your development environment configured, please see this page: Development Guide.

The kernel programming for this assignment will be done using a Google Android Developer Phone 1, ADP1, (CVN students may complete this assignments using the emulator). The Android platform can run on many different architectures, but the specific platform we will be targetting is the ARM CPU family. The Google ADP1 phones use an ARMv6 CPU (specifically, ARM1136) which is embedded in a Qualcomm System-On-a-Chip processor called the MSM 7201a (which actually incorporates the cellular baseband processor, and the application processor).

Because the target CPU is (most likely) different from the CPU running in your personal computer, you will have to cross-compile any software, including the linux kernel, to run on the different platform. You should use the same virtual machine you used for Homeworks 2 and 3.

1.   (70 pts.) The Display-Boosted Multilevel Container Scheduler
   Write a new Linux kernel scheduling class, and demonstrate correct behavior by modifying all Android Java programs to use the new schduling class.
   
   The Linux scheduler repeatedly switches between all running tasks in the system attempting to give a fair amount of CPU time to each task. On an embedded device in which only one or two applications at a time (e.g. the top-most application in Android's display stack, and the phone's status bar) are visible to the user, it can be beneficial to give those applications visible on the display more CPU time. Scheduling these "interactive" applications more often than background tasks should make the system appear more responsive to the user, and increase their productivity. Let's call this type of scheduling, display-boosted.
   
   We can use this display-boosting concept together with a multilevel feedback scheduler. A multilevel feedback scheduler provides an approximation to shortest job first scheduling for improving interactive performance. Applications that are using the display receive higher priority and shorter time slices. As an application consumes more CPU and does not use the display, its priority is reduced and its time slice is increased. If an application uses the display again, its priority is boosted back to the top again with a shorter time slice. The result is that applications that frequently use the display will run with higher priority, and gradually lose that priority the longer they run without accessing the display.
   
   As we learned in previous homeworks, each Android Java application uses several threads for performing various functions. Because we want the application as a whole to be more responsive, we will need some notion of a container which represents a group of processes/threads. This is straight-forward on the Android system because each application runs under a unique user ID (which is set/created when the application is installed). If any one of the process in a container draws on the display then the entire container should get an increased amount of CPU time.
   
   In the scheduling algorithm you write, each process/thread in a container will receive the same CPU time slice, and should be scheduled in a first-come-first-serve manner until either all processes in a container use up their time slices, or there are no more runnable tasks in the container. When either of these conditions occur, the container should be moved to the end of the next-lowest priority queue, and the time quanta for each contained process/thread should be refreshed to the value which corresponds to the queue in which the container was placed (see scheduling algorithm below for details).
   
   Objectives:
   • Add a new scheduling policy to the Linux kernel to support display-boosted multilevel container scheduling. Call this policy DBMC. The algorithm should run in constant time and work as follows:
     1. There should be 5 prioritized scheduling queues, each of which correspond to an increasing CPU time slice (quantum): 10ms, 20ms, 40ms, 80ms, 160ms.
     2. Each queue should be a collection of containers, and each container should comprise the set of processes/threads which belong to a particular user ID (On the Android platform, each application runs under a unique user ID which is set/created when the application is installed).
     3. Containers on queues with shorter time quanta should be scheduled before containers on queues with longer time quanta i.e. in order for a container on the 40ms queue to be scheduled, the 20ms and 10ms queues must be empty (contain no runnable processes).
     4. The time quantum assigned to each process/task in a container should be equal to the time quantum associated with the queue on which its container resides. For example, if a container has 1 process and 5 threads, and is currently on the 80ms queue, then each of the 6 contained tasks should be given an 80ms time quantum.
     5. Each task within a container should be scheduled in a first-come-first-serve manner until it has used up its allotted time quantum.
     6. When there are no runnable tasks within a container that have not used up their time slices, the container should be moved to the end of the next lower-priority queue, and all tasks in the container should be run with the new time quantum value. For example, if a container currently on the 10ms queue no longer contains any task which is runnable, it should be placed at the end of the 20ms queue and each contained runnable task should receive a "refreshed" time quantum of 20ms.
     7. If a task within a container still has time left in its time quantum, but was sleeping when its container was moved to a different queue, then that task should receive the refreshed time quantum of the new queue when it runs.
     8. If any process/thread within a container draws on the display, then that container should be moved immediately to the front of the 10ms queue (refreshing time quanta as necessary).
     9. If a container which has no currently runnable tasks has a task become runnable, that container should go the back of the 10ms queue (i.e. it should be the last container to get a turn on that queue).
   • The Linux scheduler implements individual scheduling classes corresponding to different scheduling policies. For this assignment, you need to create a new scheduling class, sched_dbmc_class, for the DBMC policy, and implement the necessary functions in kernel/sched_dbmc.c. You can find some good examples of how to create a scheduling class in kernel/sched_rt.c and kernel/sched_fair.c. Other interesting files that will help you understand how the Linux scheduler works are kernel/sched.c and include/linux/sched.h. While there is a fair amount of code in these files, a key goal of this assignment is for you to understand how to abstract the scheduler code so that you learn in detail the parts of the scheduler that are crucial for this assignment and ignore the parts that are not.
   • Implement a container abstraction which uses the user ID of the contained tasks as its identifier. Only processes from the associated user ID may be added to the container. Not all processes which belong to a particular user ID must be contained, however all threads which belong to a process which is a container member must also be contained and scheduled by the DBMC.
   • Your scheduler should operate along side the existing Linux scheduler. Therefore, you should add a new scheduling policy, SCHED_DBMC. The value of SCHED_DBMC should be 6. Only tasks whose policy is set to SCHED_DBMC (normally done via the system call sched_setscheduler()) should be considered for selection by your new scheduler.
   • Tasks using the SCHED_DBMC policy should take priority over tasks using the SCHED_NORMAL policy, but not over tasks using the SCHED_RR or SCHED_FIFO policies.
   • The SCHED_DBMC scheduling flag should be inherited by the child of any forking task. However, you should handle any changes in user credentials which may occur so that the new task is scheduled in the correct container (creating one as needed).
   • Your scheduler should be designed to work with any number of containers (UIDs) and should not assume a fixed number of containers.
   • All Android Java processes (and threads) should use the SCHED_DBMC scheduling policy automatically!
     
     Hint(2): The app_process binary is renamed to zygote after being run.
     
     Hint(3): You will probably want to test the scheduler out on both a subset of Android processes, and a couple of simple test programs you write. The test directory in your homework repository contains a simple command-line program template for this use.
   • The SCHED_DBMC scheduler only needs to work on a uniprocessor system, however it should fail gracefully on a multiprocessor system by not allowing any tasks to be assigned to that scheduling class if the system is a multiprocessor.
   
   
   Display notification:
   
   You may have been wondering how you will know that a given process is drawing or using the display. Fortunately this part has been done for you. The display_mod directory in your homework repository contains a modified version of the libsurfaceflinger.so library, and a Makefile which will install the new library onto your phone/emulator. Simply run make install_emu or make install_dev and follow the instructions. This modified library makes a special (custom) system call every time a rectangle is rendered on the screen. This system call is named set_display_owner and is implemented in the kernel/sys.c file in the Linux kernel directory in your homework repository. Take a look at the implementation, and customize as necessary!

Additional Hints/Tips

Kernel / Scheduler Hacking:

• Remember that you must configure your kernel before building, and whenever you switch between the emulator and the ADP1 device. The command to configure the kernel for the device is: make ARCH=arm CROSS_COMPILE=arm-none-linux-gnueabi- adp1_defconfig and similarly for the emulator: make ARCH=arm CROSS_COMPILE=arm-none-linux-gnueabi- goldfish_defconfig
• For this homework the default kernel configurations for both the emulator and the device have been updated to include the debugfs, and some basic scheduler debugging. These tools can be of great value as you work on this assignment. Debugfs documentation can be found here: here, and scheduler debugging information can be found in /proc/sched_debug and /proc/schedstat respectively. You can also search through the code for SCHED_DEBUG and SCHEDSTATS - you may want to add something while you debug!
• As an initial starting point, there is a file in the debugfs which will output the current UID of the process which most recently wrote something to the display. This file is: /sys/kernel/debug/msm_fb on the ADP1 device, and /sys/kernel/debug/goldfish_fb on the emulator. (assuming that debugfs was mounted with mount -t debugfs none /sys/kernel/debug). This is also a good way to verify that the libsurfaceflinger.so update process described above succeeded.

1. Download the Android SDK from here
2. Extract it to ~/android-sdk-os.f2011
3. Inside the platforms subdirectory, extract the file android-os.f2011.tar.bz2
4. Download the code-sourcery cross-compiler from here
5. Extract this tar somewhere (e.g. ~/tools)
6. Add the arm-2011.03/bin directory to your path in for example ~/.bashrc
7. Set the CROSS_COMPILE variable to arm-none-linux-gnueabi-