The new lab about filesystems (2 weeks) is out:
http://www.lst.inf.ethz.ch/teaching/lectures/ss07/2100/filesystem_lab/index.html
Monthly Archive for April, 2007
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