Course 02226, Autumn 2004

Robin Sharp

Report Tasks

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. This Web page describes the rules which you are to follow, and presents the projects which are available.

Projects and project groups

Participants may work on their own or in groups of 2. Each group must choose one of the following five projects:

: A. PERIODIC UPDATE CACHE WRITE POLICIES
: B. AN OS FOR A MULTIMEDIA SYSTEM
: C. FAIR-SHARE ALLOCATIONS IN GRID SYSTEMS
: D. A DAG-BASED TASK SCHEDULER
: E. LOCALITY-AWARE REQUEST DISTRIBUTION

These are described in more detail below. There is no limit to the number of groups which may choose the same project.

Please send an e-mail to me, robin@imm.dtu.dk, when you have made your choice, stating the name(s) and student number(s) of the people in your group and the title (or identification letter) of the project which you have chosen.

Project reports

You are expected to write a report on the project which you have chosen. This report must be handed in by Friday 17 December 2004 at 16.00 at the very latest. Reports must be handed in in a hard-copy edition, and must be signed and dated by all the authors, either on the front page or on the last page of the main report.

Structure

The report is expected to contain a number of sections, typically:

An introduction, explaining the aim and scope of the task.
A number of technical sections, describing your solution.
A conclusion, which summarises the main points and results.
A list of references.

The sections should all be numbered.

If you wish to include extensive program documentation, reference material, test output or program source code, you are recommended to include it as one or more appendices.

Originality

Each group must produce an independent solution to the chosen problem. Although you are encouraged to look on the Internet for relevant information, you must give a clear reference to the source of any material which you have not written yourself, which you actually include in your report.

Breach of the rules on originality will be treated as a breach of the examination regulations, and can have very serious consequences for the persons involved.

Getting advice

I am available to give you advice about the projects at the usual times, and will reserve the period on Thursdays from 13-17 for this purpose. If you want to contact me at other times, it is best to send me an e-mail at robin@imm.dtu.dk

Course 02226: High-Performance Operating Systems
Autumn 2004.
Project A.

PERIODIC UPDATE CACHE WRITE POLICIES

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:

Develop a simple simulation model of the disk system with its cache, making suitable assumptions about the speed of the disk and the distribution of disk transfer sizes and thus of disk service times. Use this model to estimate the average read response times for various intensities of read and write operations, by simulating the execution of a large number of disk transfers.
Use the analytic formulae presented by Carson and Setia and reproduced in the notes to calculate the average response times for various intensities of read and write operations. As in the case of the simulation model, you will need to make suitable assumptions about the disk, and the distribution of disk transfer sizes and disk service times.

In each case, you are required to develop an appropriate computer program which can do the simulation or evaluate the analytic formulae, using data for a real disk, such as the one used as an example in the notes. 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.

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 2004.
Project B.

AN OS FOR A MULTIMEDIA SYSTEM

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:

Audio and video capture require real-time reactions to events in the sound equipment and video camera/capture board.
Presentation of frames of digitised audio and video must be completed before real-time deadlines are reached.
Pre-recorded audio and video must be read from the file system as a continuous stream of frames, which are made available for use by other parts of the system before real-time deadlines are reached.
Data have regularly to be transmitted and received by a network adapter card, in order to pass (possibly compressed) audio and video data between the participants in the multimedia session.

Explain which techniques you would expect to have to implement in the following components of the OS in order to meet these requirements:

The disk scheduling system
The file system
The process scheduler
The thread management system
The IPC system
The device handlers

If you feel that there are no special requirements in any of these systems, so that ``any technique would do'', you should just say so. Otherwise you should give reasons for your choice.

To produce good arguments, you will need to use suitable information about the timing requirements of real multimedia systems. These can be obtained from a number of sources, especially the Internet.

Course 02226: High-Performance Operating Systems
Autumn 2004.
Project C.

FAIR-SHARE ALLOCATIONS IN GRID SYSTEMS

In metacomputers consisting of multiple clusters, it is difficult to ensure that users get the share of the resources which they are entitled to - and not more or less than their entitlement. A typical situation is that a user has been given a grant which covers a certain amount of computer use, including costs for CPU time, disc space used, and so on. This allocation is done on a global basis. The problem is to ensure that the user cannot overrun his allocation (or be cheated) because the individual clusters do not coordinate their way of handling allocation and accounting.

Design and (if possible) implement a system which can offer relatively good guarantees that given allocation limits will be respected. If possible, you should also ensure that a user's allocation can be divided into shares which can be given to sub-users (imagine a case where Professor X has funding for Ph.D. students A, B, C, D,...), in such a way that each sub-user gets his fair share of the resources.

For this task you are encouraged to investigate whether existing tools for allocation in Grid systems can be used as a basis for such a system. A good place to start your investigation is by looking at existing packages such as MAUI and MOAB:

    http://sss.scl.ameslab.gov/maui.shtml
    http://www.clusterresources.com/products/moabgridsuite.shtml

If you would like to implement your system in a real-life practical context, you can do it within the framework of the Danish Center for Grid Computing. Please send me a mail if you are interested in this possibility.

Course 02226: High-Performance Operating Systems
Autumn 2004.
Project D.

A DAG-BASED TASK SCHEDULER

Develop a (simple) software tool which, given a task graph (a DAG whose nodes describe tasks and whose edges describe communication between tasks), can produce an optimum schedule according to a number of possible scheduling principles.

For this project, you should seek inspiration in the system CASCH described in Chapter 23 of Buyya's book. As a minimum, your system should be able to deal with BNP systems, which assume ``zero contention'' communication. For a more challenging task, you could include the possibility of handling APN systems, where communication is dealt with in more detail. If possible, your tool should provide user-friendly output - for example by showing the DAG and the schedule found by your tool on a GUI - so it could for example be used for teaching purposes.

Course 02226: High-Performance Operating Systems
Autumn 2004.
Project E.

LOCALITY-AWARE REQUEST DISTRIBUTION

In the paper ``Locality-aware Request Distribution in Cluster-based Network Servers'' (Proceedings of the 8th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII), ACM SIGPLAN Notices, vol.33(11), pages 205-216, November 1998), Pai et al. describe a system for distributing requests among network servers with a view to achieving load balancing between the servers.

Evaluate their proposal, relating it to other load-balancing principles which you know about. A good starting point for your evaluation would be to implement a simple simulator for their system, based on the simulation model which they describe in their paper, but using more up-to-date data for the networks and disk units used.

File translated from T_EX by T_TH, version 3.11.
On 4 Nov 2004, 10:27.