On the lab page you can find a sample solution to the scheduler lab.
Archive for the 'scheduler' Category
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
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.
A new version of the scheduler lab handout which includes the missing trace generator is available