Description
Objectives
1. Compile the Android kernel.
2. Familiarize Android scheduler
3. Implement a weighted round robin scheduler.
4. Get experience with software engineering techniques.
Operating Systems 2
CS356 Operating System Projects
Preliminary
3
Enviroment
• Implementation
◦ AVD(Android Virtual Devices)
▪ SDK version r24.4.1
• Development
◦ Linux （64-bits）
▪ Ubuntu (recommended)
▪ Debian
▪ Fedora
◦ VMware
Operating Systems 4
What to Submit
• A“tar” file of your DIRECTORY, containing:
◦ All *.c, *.h files you have changed in Linux kernel.
◦ Any “readme” or “.pdf” files asked for in the project
◦ Screen captures of the scheduler test
▪ If you cannot get your program to work, submit a run of whatever you can get to work as you can get partial credit
• DO NOT SUBMIT your object or executable files, REMOVE them before you pack your directory.
Operating Systems 5
How to Submit
• Pack your code in a project directory
tar –cvf Prj2+StudentID.tar project1
• Send your Prj2+StudentID.tar file on Canvas.
Operating Systems 6
For Help?
• Teaching Assistant
◦ Menghan Guo
▪ Email: 15667083571@163.com
◦ Jiafeng Xu
▪ Email: xujiafenga3@163.com
Operating Systems 7
CS356 Operating System Projects
Recompile the Kernel
8
Compile the Linux Kernel
• Make sure that your environment variables are correct.
Operating Systems 9
Compile the Linux Kernel (cont.)
• Modify Makefile in the kernel
• Change
ARCH ?= $(SUBARCH)
◦ CROSS_COMPILE ?=
• To
Operating Systems 10
Compile the Linux Kernel (cont.)
• Execute the following command:
Operating Systems 11
Compile the Linux Kernel (cont.)
• Then you can see a GUI configuration dialog:
Operating Systems 12
Compile the Linux Kernel (cont.)
• Open the Compile the kernel with debug info in Kernel hacking:
Operating Systems 13
Compile the Linux Kernel (cont.)
• Enable loadable module support with Forced module loading, Module unloading and Forced module unloading in it:
Operating Systems 14
Compile the Linux Kernel (cont.)
• Enable loadable module support with Forced module loading, Module unloading and Forced module unloading in it:
Operating Systems 15
Compile the Linux Kernel (cont.)
• Compile it
◦ The number of -j* depends on the number of cores of your system.
Operating Systems 16
CS356 Operating System Projects
Introduction to Project 2
17
Problem
• Android supports three built-in scheduling policies: Normal, FIFO and RR.
• In this problem, you are required to implement a new scheduling policy:
◦ Weighted Round Robin.
• The blog relevant to linux kernel scheduler could be helpful to you：
◦ https://helix979.github.io/jkoo/post/os-scheduler/
Operating Systems 18
Problem
• Weighted Round Robin (WRR)
◦ Round-robin scheduling treats all tasks equally, but there are times when it is desirable to give some tasks preference over the others.
◦ Android Tasks can be classified into foreground groups and background groups.
◦ WRR assigned more milliseconds as a time slice for foreground groups. (In our problem, 100ms for fore and 10ms for back)
Operating Systems 19
Problem
• Foreground and Background Groups
◦ From user level, you can run ps -P on the device or emulator to check the assigned groups for each task.
◦ At the kernel level, a task’s group information can be found using a task pointer. Refer to the line 96 in
kernel/sched/debug.c and use that function appropriately.
◦ The return value will be “/” for a foreground (and system group in earlier versions) group, “/bg_non_interactive” for a background group.
Operating Systems 20
Implementation Details
• Files MAY NEED Modification
◦ /arch/arm/configs/goldfish_armv7_defconfig
◦ /include/linux/sched.h
◦ /kernel/sched/core.c
◦ /kernel/sched/sched.h
• To implement WRR scheduler, you need to create a new class in the directory /kernel/sched/, that is
◦ /kernel/sched/wrr.c
IMPORTANT: If you feel confused on what to do in wrr.c, read /kernel/sched/rt.c carefully. In rt.c, RR and FIFO are well implemented.
Operating Systems 21
Implementation Details
/arch/arm/configs/goldfish_armv7_defconfig
• In this file, you need to add a new line as follows:
Operating Systems 22
Implementation Details
/include/linux/sched.h
In this file, you need to:
• Define SCHED_WRR (Refer to SCHED_RR, about Line 42). The value of SCHED_WRR should be 6.
• Define sched_wrr_entity (Refer to sched_rt_entity, about Line 1250)
• Define time slice for foreground and background groups. (Refer to RR_TIMESLICE, about Line 1280)
• Add a sched_wrr_entity varaible to task_struct (About Line 1310).
• Declare a wrr_rq struct. (Refer to struct cfs_rq, about Line 150)
• Maybe a little more to be revised. It depends on your implementation.
Operating Systems 23
Implementation Details
/kernel/sched/sched.h （path is different from last page）
In this file, you need to:
• Declare a wrr_rq struct. (Refer to struct rt_rq, about Line 90)
• Define a new struct wrr_rq (Refer to rt_rq, about Line 300).
• Add a wrr_rq variable to struct rq (About line 400) and similarly add a list_head variable as the figure shows.
• Declare some extern variables and functions（*）. (You can refer to extern var/func of rt in the same file, About Line 190-210, Line 880, Line 900, Line 1170-1180). E.g.
• Maybe a little more to be revised. It depends on your implementation.
Operating Systems 24
Implementation Details
/kernel/sched/core.c
In this file, you need to:
• Revise function: static void __sched_fork(struct task_struct *p)
• Revise function: static void __setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
• Revise function: static void __sched_setscheduler(struct task_struct *p, int policy, const struct sched_param *param, bool user)
• Add init_wrr_rq(&rq->wrr). (Refer to init_rt_rq(), about Line 7230)
• Revise function: static void free_sched_group(struct task_group *tg) and struct task__group *sched_create_group(struct task_group *parent) (about Line 7500-7600)
• Maybe a little more to be revised. It depends on your implementation.
Operating Systems 25
Implementation Details
/kernel/sched/core.c
• To know what to revise, you have to read the code carefully and know what are they implemented for.
• For example, when revising __sched_setscheduler, we meet the following code segment:
Since we have one more policy WRR now, we should change it to:
Operating Systems 26
Implementation Details
/kernel/sched/wrr.c
• This is the major file in which you write codes. You can refer to rt.c in the same directory to learn how to write wrr.c
• Here, we give a framework of wrr_sched_class
Operating Systems 27
Implementation Details
/kernel/sched/wrr.c
For funtions labeled “Required”, you need to implement it in wrr.c
For functions labeled “Never need impl”, you can just put them dummy
Operating Systems 28
Implementation Details
/kernel/sched/wrr.c
• Remember that in wrr.c, when you want to allocate time slice to a task with WRR as its policy, you should judge whether it is a foreground task or background task, and allocate corresponding time slice to it.
• The blog relevant to linux kernel scheduler could be helpful to you：
◦ https://helix979.github.io/jkoo/post/os-scheduler/
Operating Systems 29
Implementation Details
To put your /kernel/sched/wrr.c into effect:
• You need to revise the Makefile in /kernel/sched like this:
Operating Systems 30
CS356 Operating System Projects
For Your Work
31
What to show
Basic
• We will provide an apk processtest.apk.
• Add some printk(“”) in wrr.c or some other places which proves there is a task using WRR as a policy.
• Write a test file, which can change the scheduler in user space.
◦ Change the apk’s scheduler to WRR when the apk is in foreground groups, and give out some information (pid, name, timeslice, and some others you like).
◦ Change the apk’s scheduler to WRR when the apk is in background groups, and give out some information (pid, name, timeslice, and some others you like).
• To check the pid of processtest.apk in Android shell, you may use:
Operating Systems 32
What to show
Basic
Print information when app is in foreground:
Print information when app is in background:
Operating Systems 33
What to show
Bonus (10 points in Final Score):
• Any extended ideas can be considered into the bonus!
• Here are some of the ideas we provide, I hope you won’t be limited to these:
◦ Can you come up with a method to compare the performance of RR, FIFIO, NORMAL and WRR?
◦ Can you build WRR in a multi-cpu architecture and implement load balance?
Operating Systems 34
Hints
• To change the scheduler, study several functions with SYSCALL in their names. For example, SYSCALL_DEFINE3 (sched_setscheduler…….). Try to use these system calls in user space.
• You can firstly change scheduler to RR or FIFO to see if your testing file is logically correct.
• You can take full use of printk and the functions defined in /kernel/sched/debug.c for debugging.
• Helpful files:
◦ /kernel/sched/core.c and /kernel/sched/sched.h tells you how the Linux scheduler works.
◦ /kernel/sched/rt.c tells you how to create a scheduler.
◦ /include/linux/sched.h concerns run-state processes.
Be patient enough to read them carefully!
Operating Systems 35
Hints
To install the processtest.apk to your AVD:
• Initiate your Android Virtual Device
• Type the command in Ubuntu Shell:
◦ adb install [the path of apk in Ubuntu (not in Android)]
• Launch your apk by clicking the icon in Android AppList
Operating Systems 36
Report
• Explain how your wrr.c work.
• Explain what have you done in all the other files except wrr.c.
• Any further analysis is welcome.
Operating Systems 37
Something to Specify
• To give you an overview of this project:
◦ You need to write 500 lines (more or less) of codes in:
▪ /kernel/sched/wrr.c
◦ You need to revise the following files to put wrr.c into effect:
▪ /arch/arm/configs/goldfish_armv7_defconfig
▪ /include/linux/sched.h
▪ /kernel/sched/sched.h
▪ /kernel/sched/core.c
▪ /kernel/sched/Makefile
◦ You need to write a test script to print the Scheduling Information of processtest.apk in foreground and background.
Operating Systems 38
Deadline
Operating Systems 1.39
Demo & Presentation
• Demo:
◦ Demo slots will be posted in the WeChat group. Please sign your name in one of the available slots.
• Presentation:
◦ You are encouraged to present your design of the project optionally. The presentation will be in the afternoon of June 6, .
Operating Systems 1.40
Operating Systems 1.41
