On the lab page you can find a sample solution to the scheduler lab.
To test changes on a disk image (performed with the fs_creat and fs_write calls) you should check the modified image file with a filesystem checker.
Example on Linux:
$ fsck.vfat -lnv single.img
dosfsck 2.11 (12 Mar 2005)
dosfsck 2.11, 12 Mar 2005, FAT32, LFN
Checking we can access the last sector of the filesystem
Boot sector contents:
System ID "mkdosfs"
Media byte 0xf8 (hard disk)
512 bytes per logical sector
2048 bytes per cluster
1 reserved sector
First FAT starts at byte 512 (sector 1)
2 FATs, 12 bit entries
1024 bytes per FAT (= 2 sectors)
Root directory starts at byte 2560 (sector 5)
512 root directory entries
Data area starts at byte 18944 (sector 37)
502 data clusters (1028096 bytes)
32 sectors/track, 64 heads
0 hidden sectors
2048 sectors total
Checking file /single
Checking file /FILE.TXT
Checking for unused clusters.
single.img.orig: 2 files, 1/502 clusters
Options:
-l: list path names of files being processed-n: no-operation mode: non-interactively check for errors, but don’t write anything to the filesystem-v: verbose
The points computed by mdriver are not absolute but depend on the machine where the test is run as they depend on an evaluation of the installed libc performance. You might therefore notice different results for your lab. All the labs are tested on the same machine and evaluated using the same libc performance values.
Some sample solutions and examples for the malloc lab are availble.
| mm-naive.c | The simplest solution: malloc simply sbrk’s and writes a size header. free does nothing. realloc is implemented directly with malloc and free. This solution has great throughput but terrible space utilization, and thus fails on many traces because it exhausts memory. |
| mm-implicit.c | Solution based on coalescing implicit free lists with boundary tag. This is the simplest reasonable package. |
| mm-explicit.c | Solution based on explicit free list with boundary tag coalescing and first fit placement. |
| mm-tree.c | Highly optimized solution based on red-black trees. |
| mm-test.c | A buggy malloc that produces overlapping blocks. Used for testing the driver. |
The new lab about filesystems (2 weeks) is out:
http://www.lst.inf.ethz.ch/teaching/lectures/ss07/2100/filesystem_lab/index.html
Currently there is a vivid discussion about a new scheduler that should replace the current O(1) scheduler of the linux kernel.
Two different approaches are in the queue:
Rotating Staircase Deadline cpu scheduler policy [RSDL]
http://thread.gmane.org/gmane.linux.kernel.ck/6462
Modular Scheduler Core and Completely Fair Scheduler [CFS]
http://thread.gmane.org/gmane.linux.kernel/515644
Both of these schedulers try to be fairer and cleaner than its predecessor (as usual). The idea seems nice and I’m looking forward to meet them ‘in the wild’ ;)
traces.tar.gz contains some scheduling traces with some example results that you can use to test your scheduler.
Traces:
| Trace number | File name | Comment |
|---|---|---|
| 1 | deadlock | deadlock: simulation should not finish |
| 2 | priority-1 | process 1 should run first |
| 3 | priority-2 | process 0 should run until process 1 starts |
| 4 | priority-3 | process 0 should run until process 1 starts and after 1 renices (after 2 slots) |
| 5 | inversion |
|
| 6 | random-1 | random trace 10 processes |
| 7 | random-2 | random trace 100 processes |
| 8 | random-3 | random trace 1000 processes |
| 9 | random-4 | random tracd 10 short processes |
| 10 | length | 1 long process 9 short processes |
| 11 | idle | idle CPU |
Example results:
| Trace | Total time | Average response time | Average turnaround time | Average waiting time | CPU utilization |
|---|---|---|---|---|---|
| 1 | - | - | - | - | 100% |
| 2 | 20 | 5.0 | 15.0 | 0.0 | 100% |
| 3 | 13 | 0.0 | 8.0 | 0.0 | 100% |
| 4 | 15 | 0.0 | 13.0 | 0.0 | 100% |
| 5 | 30 | 5.7 | 22.3 | 5.7 | 100% |
| 6 | 534 | 26.4 | 204.4 | 44.5 | 99% |
| 7 | 5949 | 3.3 | 2875.2 | 2614.5 | 100% |
| 8 | 59072 | 6928.0 | 19072.7 | 11509.8 | 100% |
| 9 | 134 | 9.1 | 40.2 | 6.2 | 90% |
| 10 | 1009 | 4.5 | 105.4 | 0.0 | 100% |
| 11 | 3100 | 0.0 | 55.0 | 0.0 | 4% |
I just wanted to add some notes about the handin of the scheduler lab:
- Hand in only the scheduler.c file with your solution by email to mathias.payer@inf.ethz.ch
- Include documentation about your scheduler.
- What are your design desicions?
- How does your scheduler algorithm decide which process is next?
- What kind of data structure do you use to manage the processes?
- How do you manage locks?
- Deadline is (still) April, 29 at 24:00 MET
I just uploaded a new handout and a patch to generate.pl against a possible bug in generate.pl. If your scheduler does not clean up closed locks after a process finishes you could run into an endless loop. The problem is that generate.pl could generate traces with locks that hold longer than the process’s length.
I just uploaded a new handout, which should handle the renice-permissions correctly (finally…). There was another small issue in the generate.pl where the renice-event could happen at relative time “-1″, so before the process was even started. This is now corrected as well. Get the patch or the new handout.
Mathias updated the simulator with a bug fix. Please download a new handout or patch your working copy
The simulator has problems on the cygwin platform because of an apparent wrong handling of the z modifier in the fscanf format string.
As a workaround you can substitute
while((ret = fscanf(fd, "%i %s %zi %i %i\n", &time, event, &id, &duration, &arg)) != EOF) {
with
while((ret = fscanf(fd, "%i %s %i %i %i\n", &time, event, &id, &duration, &arg)) != EOF) {
You can follow the bug report on the cygwin mailing list.
A new version of the handout is available: Mathias corrected the computation of the response time.
There is an additional small patch for simulator.h to surpress two warnings. Just use this patch, if you applied the patch below and did not use the new handout!
The arrays containing the events in the process simulator were not properly initialized causing an error while freeing memory at the end of the simulation.
A patch and an updated handout are available.
As you may have seen most of the malloc labs have been corrected. I sent emails with the points to all people of each team (some handins have not yet been graded – they will follow in a day or so). If there are any questions, step by at my office or drop me an email.
A new version of the scheduler lab handout which includes the missing trace generator is available
The C99 standard defines that a malloc(0) is legal:
If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.
If a non-zero value is returned it should be not used but it is legal to pass it to a subsequent call of free (note that free(NULL)is also legal).
It follows that
void * p = malloc(0); free(p);
is legal and should be accepted by your allocator.
- The books and papers references are now online
- The course schedule was updated with the first two labs deadlines
Both pages will be regularly updated