The new lab about filesystems (2 weeks) is out:
http://www.lst.inf.ethz.ch/teaching/lectures/ss07/2100/filesystem_lab/index.html
Archive for the 'Labs' Category
Page 2 of 2
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.
mdriver prints the ERROR: mem_sbrk failed. Ran out of memory... error message when the simulated memory heap (20MB) is full. Some of the test traces allocate a total of 37MB (without considering frees). This could therefore happen if:
- your
freeroutine fails to free the released blocks - your
mallocroutine fails to use freed blocks - your allocation algorithm generates too much internal fragmentation
Compilers usually align fields to allow faster access. It is usually possible to tell the compiler to avoid this behavior and generate structs as they are specified. gcc uses the attribute tag. For example the following code
struct test_t {
char b;
long l;
};
struct test_t test = { 'a', 42 };
is compiled (on an Intel architecture) as
.globl _test
.data
.align 2
_test:
.byte 97
.space 3
.long 42
.subsections_via_symbols
where three bytes are used to pad the char to 32 bits. While
struct test_t {
char b;
long l;
} __attribute__ ((packed));
struct test_t test = { 'a', 42 } ;
is compiled as
.globl _test
.data
_test:
.byte 97
.long 42
.subsections_via_symbols
The macros to align the addresses returned by malloc in the given example (in malloc-handout) are wrong since they only deliver 8-byte aligned results.
The results must of course be and-ed with ~(ALIGNMENT-1) and not ~0x7 (which is only OK if ALIGNMENT is 8).
Please patch your mm.c file:
#define ALIGNMENT 8 #define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1)) #define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
A new tarball (malloclab-handout.tar) is available