Robin Sharp
There is no ordinary 4-hour written examination for this course. Instead, you are required to hand in a report on a small project connected with the course, and to present the results of your project orally. This Web page describes the rules which you are to follow, and presents the projects which are available.
Please send an e-mail to me, robin@imm.dtu.dk, when you have made your choice, stating the name(s) of the people in your group and the title (or identification letter) of the project which you have chosen.
Course 02226: High-Performance Operating Systems
Autumn 2001.
Project A.
In the article ``Analysis of the Periodic Update Write Policy for Disk Cache'' ( IEEE Transactions on Software Engineering, pp. 334-344 (1992)), Carson and Setia discuss and analyse several write policies for disk caches, including the simple Write Through (WT) policy, standard Unix Periodic Update (PU), Interval Periodic Update (IPU) and Periodic Update with Read Priority (PURP). These policies are described in Section 7.7.1 of the course notes.
In this project you are to compare at least two of these policies using one or both of the following techniques:
Comment on the results which you achieve, and consider which of the write policies investigated you would select for use in an operating system whose main task is to support (a) an interactive database query system or (b) a continuous media file system.
In this project, it is important that any assumptions which you make about the system and its components are clearly stated. Note also that there are many ways of approaching the project and many sets of results which may be obtained. You should remember that it is at least as valuable to present a carefully explained set of results in which a few parameters are varied as to present a poorly explained set of results where a large number of factors are varied.
Course 02226: High-Performance Operating Systems
Autumn 2001.
Project B.
In chapter 6 of the notes, an approach to analysing interrupt response times based on real-time schedulability analysis is presented. In this project you are to develop techniques which can be used to investigate at run time (``on-line'') whether it is feasible to start a period of activity in which a particular set of devices is active, under the assumption that each event on a device must be dealt with before a given hard deadline.
You should approach this project in two stages. Firstly, you should develop a feasibility checking program which, given a set of periodically submitted interrupt service routines with known priorities, periods, deadlines and computation times, can check whether these routines can be pre-emptively scheduled so that their computations are completed before the corresponding deadlines.
In the second stage, you should extend your solution to take deferred activities set up by the interrupt service routines into account. You should investigate at least one of the following two methods for this purpose:
The programs are to be written in an appropriate modular language such as Java or C++. They should be suitably documented, and the interactions between the various sub-programs should be carefully explained.
Course 02226: High-Performance Operating Systems
Autumn 2001.
Project C.
In the notes, a number of examples are given of two-level systems for management of resources, including:
It might be reasonable to suppose that the systems for page/segment management, disk scheduling and file caching would interact with one another, since they all make use of the disk. Give arguments for whether this is or is not the case:
There are many different features which can be discussed in this project, and a long series of applications for which the management systems can be used can be considered. You must decide for yourself how many features to describe in your solution, bearing in mind that a comparatively detailed description of a few features is as valuable as a more superficial description of many different ones.
Course 02226: High-Performance Operating Systems
Autumn 2001.
Project D.
A system for mixed interactive and non-interactive (pre-recorded) multimedia puts a number of powerful requirements on the operating system on which it is based:
Explain which techniques you would expect to have to implement in the following components of the OS in order to meet these requirements:
To produce good arguments, you will need to use suitable information about the timing requirements of real multimedia systems. You can find a number of these requirements in Chapter 9 of the notes and in the references referred to from this chapter; if you need further information, you should make a search of relevant literature via the Internet.
Course 02226: High-Performance Operating Systems
Autumn 2001.
Project E.
Develop a software analysis tool which can be used to estimate Worst-Case Execution Times (WCETs) for tasks in a system in which I/O devices use DMA with cycle stealing. You are recommended to use the method proposed by Huang, Liu and Hull (in Proceedings of the 17th IEEE Real-Time Systems Symposium, Washington, 1996, pp. 275-285), as described in Section 6.3.1 of the notes. You may assume (as in Huang, Liu and Hull's paper) that the system is based on a bus with a simple bus access protocol, such as the VME bus, and that the DMA controller has a lower priority than the CPU for access to the bus.
You should initially attempt to produce a program which can be used to analyse the behaviour of the system for a simple CPU, such as the Motorola 68020, with the cache not in use. Details of instruction times for this processor can be found in ``MC68020 Microprocessor User's Manual'' which for example can be obtained via the Internet 1. Your program should be able to evaluate the WCET of a task instance in the two cases where (1) there is no DMA transfer running concurrently with the task and (2) a DMA transfer of a length specified by the user is running concurrently with the task.
You are advised to start by analysing some simple tasks, whose programs are given as assembly language programs which just use a small number of different instructions, in order to demonstrate the general principles behind your program. When you feel you have a suitable solution in this case, you may extend your solution to include more instructions or to make allowance for the use of the instruction cache in the MC68020 CPU.
The programs are to be written in an appropriate modular language such as Java or C++. They should be suitably documented, and the interactions between the various sub-programs should be carefully explained. Note that Huang, Liu and Hull's method requires the use of Integer Linear Programming (ILP) to maximise the cost function; if you do not have access to a suitable ILP package, I can give you some suitable links.
1 http://e-www.motorola.com/webapp/sps/site/prod_summary.jsp?code=MC68020