|
CO527 Anonymous Questions and Answers |
This page lists the various questions and answers. To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.
We have taken the liberty of making some minor typographical corrections to some of the questions as originally put. Although most of the questions here will have been submitted anonymously, this page also serves to answer some questions of general interest to those on the course.
Submission reference: IN1862
What is the average air-speed velocity of an unladen student?
About 145 m/s.
Submission reference: IN2106
With regards to the second assignment, technical essay. Titles and content of the essay including references count towards the 450 word limit. Does the bibliography at the bottom also count towards the word limit?
Bibliography and references are the same thing, so yes, they count towards the word limit.
Keywords: essay
Submission reference: IN2108
What software should we be compiling this in? I tried Visual Studio 2010 to compile the C sources but with dsched.c am getting the following errors:
disksim.h(24): error C2054: expected '(' to follow 'inline'
disksim.h(25): error C2085: 'block_to_track' : not in formal parameter list
disksim.h(25): error C2143: syntax error : missing ';' before '{'
disksim.h(30): error C2054: expected '(' to follow 'inline'
disksim.h(31): error C2085: 'block_to_sector' : not in formal parameter list
disksim.h(31): error C2143: syntax error : missing ';' before '{'
and with disksim.c:
disksim.c(12): fatal error C1083: Cannot open include file: 'sys/mman.h': No such file or directory
For whatever reason, Visual Studio doesn't seem to like the inline declarations, and the Windows platform doesn't have the sys/mman.h include file (which I'm not surprised about). However, any reasonably modern Unix platform should be able to cope with it. You can compile and run the software on 'raptor', and edit the file on your Windows machine (just mount the raptor filestore, via the VPN if off-campus probably). Or install a Linux distribution in VMWare, VirtualBox or QEmu.
The Java version should work fine on Windows though (with the Sun/Oracle JVM). If you know C pretty well, Java should be somewhat simpler by comparison. For the task I'm asking you to complete, the difference between the C and Java code is pretty minimal — this is about low-level OS coding, not about using APIs provided by Java, POSIX or Windows.
Keywords: disk-scheduling , assess4-1112
Submission reference: IN2109
Hi, I'm having trouble understanding exactly how branching offsets are used. In my example below (hopefully the formatting didn't break) when trying to jump forward 8 instructions, it appears that we end up 9 instructions along. Is there something I am missing?
Instruction | Instruction offset | ================================ 0 | ? 4 | ? 8 | BEQ 1 1 8 12 | (1st) 16 | (2nd) 20 | (3rd) 24 | (4th) 28 | (5th) 32 | (6th) 36 | (7th) 40 | (8th) <-- This is where I would expect to be, 8 instructions along. 44 | (9th) <-- This is where (8+4) + (8<<2) ends up.
It also means that branching with an offset of 0 would jump to the next instruction when to me it should be the current instruction.
If you look at the MIPS definition for the branch instructions, the offset (when branching) is applied to the instruction pointer, which will already have been updated to point at the next instruction, so will always be 1 word ahead of the current instruction. That gives the results you see; the bit of information you were missing is that the instruction-pointer has already been updated at the point the branch is processed (in practice anyway — logical diagrams may show this more explicitly as a +4 embedded into the branch path somewhere, depending on where the control signal for the branch is wired).
Keywords: architecture
Submission reference: IN2110
For assessment 4 are we allowed to use Vectors in Java?
Nope, as it is essentially one of the collection classes. It's reasonable to assume that an operating-system will not have this sort of high-level functionality at its disposal — such things would need to be implemented separately (and probably specifically for efficiency).
Keywords: assess4-1112
Submission reference: IN2112
For the Systems Programming, I have tried to implement C-LOOK, but the results coming out are basically identical to the programs original output. Is perhaps using C-LOOK a bad idea, or maybe I have just implemented it that badly?
I realise this is not the most efficient way to do it (although I still expected it to be faster than FIFO), my (not so good) implementation of C-LOOK just, on each "readcomplete" where there are still requests in the queue, calls another method to find the next block. In pseudo-code this looks something like:
current_blk = ? // Stores current block
if (still requests to service) then
clear lowest, highest and next block numbers.
for (each request still to process) do
if (this request lower than lowest block seen so far) then
lowest = this request
endif
if (this request higher than highest block seen so far) then
highest = this request
endif
if (this request higher than current, but less than next) then
next = this request
endif
done
// Should now have lowest, highest and next block numbers.
if (next not set) then
service lowest request
else if (current greater than highest) then
service lowest request
else
service next request
endif
Any ideas/suggestions?
The logic of this looks pretty sensible and it should give better performance than the default FIFO implementation. If you can't see anything obviously wrong with the implementation, I'd suggest putting in some debugging statements in the "readcomplete()" call to print out what the contents of the request queue are and, the current/last block, then which block your implementation cbooses. You should be able to see at a glance if something is going wrong or not.
Keywords: assess4-1112 , disk-scheduling
Submission reference: IN2113
Using Java to do the A4 assessment, can we use null (set an object as null, compare it against null, etc.)?
Yes, that's fine — null is part of the core language pretty much (as it is in C).
Keywords: assess4-1112
Submission reference: IN2114
Can we use the Java library class Math?
Short answer no. But why would you need to? Its methods like "abs", "min" and "max" are easy (and short enough) to code yourself in local methods/functions (or inline). An OS may have such things, but probably implemented as pre-processor macros.
Keywords: assess4-1112
Submission reference: IN2115
I have a few questions for assessment 4 (regarding the SSTF algorithm):
Keywords: assess4-1112
Submission reference: IN2116
Can you post on Moodle the results your SSTF gives for requests-big?
The Moodle page is getting a bit cluttered, so I'll post them here: (also Moodle's CSS is sufficiently broken that it destroys all preformatted blocks, making putting such things there a pain at the best of times):
finished at time 36526 with 0 pending queues disk spent 36 idle, 35029 seeking to track, 1460 reading 1000 blocks time for request in queue (min, max, avg): 0 , 35711, 1201.2 +/- 4776.5 time for request in read (min, max, avg): 1 , 252 , 36.5 +/- 54.3 time for request total (min, max, avg): 1 , 35712, 1237.7 +/- 4781.3
Bear in mind that this was only a very quick implementation, so the results are hardly the best that they could be!
Keywords: assess4-1112
Submission reference: IN2117
I was also wondering, can an SSTF implementation still receive the same marks as the other algorithms? (I know marks will depend on other factors but I just mean in the main).
Implementing SSTF won't attract as many marks as better algorithms. Partly because the implementation of SSTF is pretty trivial, plus I've told you how to do it on the assessment web-page! However, it's also technically not the best algorithm in terms of fairness, which is important. You can start with SSTF and improve it in various ways, without it becoming some of the more complex algorithms such as elevator and similar.
Keywords: assess4-1112
Submission reference: IN2118
Before implementing any sort of reading is the read request queue already filled up? E.g.: when the first read is sent from the scheduler is the queue already full with all requests and so FIFO does them one by one until its empty or is the queue partially full and FIFO waits until another request is made before continuing?
Short answer: see the assessment 4 slides. Long answer: neither and both — it's non-deterministic. At the point the read request is made (by calling "readblock()") the FIFO queue may be nearly empty or nearly full. However, each time "readcomplete()" is called (to indicate that a read has finished or the disk is idle) the existing FIFO code simply dispatches the next read (if there are any left). It might be the case that the queue gets completely emptied sometimes, but not necessarily.
Keywords: assess4-1112
Submission reference: IN2119
I'm trying to implement the SSTF disk-scheduling algorithm in Java and I keep getting an ArrayIndexOutOfBoundsException. Here's the basic structure of my code so far:
1 readcomplete
2 {
3 if block number greater or equal to 0 {
4 give block read back
5 }
6
7 loop through array {
8 calculate difference between last block number and current block number
9 if difference is smaller than current best {
10 update current best and store current block number
11 }
12 }
13
14 set tail to current block number and current block number request
15
16 if still requests to service {
17 dispatch next block request
18 store block number
19 increment tail pointer
20 reduce tail size
21 }
22 }
Any hints on where I am going wrong would be appreciated!
The exception will tell you whereabouts in the code the problem lies (or, rather, at least where the array is indexed out-of-bounds). That'll either be on line 7 (or lines 8-11 as a result of how the array is looped over), line 14 (assuming it accesses the request array), or line 17. There may be some cause-effect chasm going on though, so a run-time error at a particular point doesn't always mean the problem lies there.
At a guess, the problem is probably the way you're looping through the elements in the array. The array is organised as a circular buffer (as explained in these slides) which means that loops that look like:
for (int idx=0; idx<readqueue_size; idx++)
..or..
for (int idx=readqueue_tail; idx<readqueue_size; idx++)
..or..
for (int idx=readqueue_tail; idx<(readqueue_tail + readqueue_size); idx++)
and various other combinations are potentially broken (assuming the code therein tries to access readqueue[idx]). If the buffer is not empty (i.e. "readqueue_size > 0"), then the first valid request is "readqueue[readqueue_tail]" and the last valid request is "readqueue[(readqueue_tail + readqueue_size - 1) % readqueue.length];". The modulo operator ensures that things wrap-around right (as is already present when incrementing the tail pointer). Constructing a loop that iterates over each array element individually isn't too hard, if indeed the problem lies there:
for (int i=0; i<readqueue_size; i++) {
int idx = (readqueue_tail + i) % readqueue.length;
// do stuff with readqueue[idx]
}
Bear in mind that the tail pointer ("readqueue_tail") and size ("readqueue_size") should only ever be modified by lines 19 and 20 in "readcomplete". And the tail pointer only incremented by one each time — because the disk can only deal with one request at a time. On that logic, line 14 looks a bit dubious.
Keywords: assess4-1112
Referrers: Question 14 (2011) , Question 22 (2011)
Submission reference: IN2121
After establishing an error with my for() loop, using the answer from Question 13 (2011), I have come across results that do not fall in line with that of which I was hoping to achieve. In particular I am attempting to implement C-SCAN (elevator) which sorts the blocks into ascending order before processing them, thus not leaving any block missed. However.. My code looks like the below:
for (int i=0; i < readqueue_size; i++) {
int idx = (readqueue_tail + i) % readqueue.length;
if (the block at readqueue idx is greater than the block of idx+1,
AND neither block is -1) {
swap the read request at idx with the one at idx+1.
}
}
Which is a small implementation of bubble sort, but produces the following results:
finished at time 2546 with 0 pending queues disk spent 36 idle, 2382 seeking to track, 127 reading 97 blocks time for request in queue (min, max, avg): 0 , 2243 , 375.7 +/- 519.6 time for request in read (min, max, avg): 1 , 188 , 25.9 +/- 53.7 time for request total (min, max, avg): 1 , 2297 , 401.5 +/- 539.5
which I am sure are slower than the original results. Can you point out where I am going wrong here?
The pseudo-code you give for the bubble-sort isn't right. What you have there will incrementally move a block along the queue until the loop condition returns false -- it assumes, in particular, that the list is already sorted. If it's not, this won't work right! Normally a bubble-sort has two nested loops. Because new blocks get added to the end of the array, rather than the start, a newly added request will be moved at most one space, so most of the time I'd expect this bubble-sort to be doing nothing useful! This is why you're seeing the bad results. If you turned the bubble sort around to go from (head-1) rather than (tail), it should produce better results, but I'd suspect it'd still be a bit broken.
A good idea would be to write a method that prints out the contents of the request queue, and see what it looks like before and after you try and sort it. That should point you in the general direction of where things are going wrong.
Keywords: assess4-1112 , disk-scheduling
Referrers: Question 15 (2011)
Submission reference: IN2122
My output for my program currently looks like this:
highlevel_didread(): read queue 0 got unexpected block 2049 highlevel_didread(): read queue 0 got unexpected block 2049 highlevel_didread(): read queue 0 got unexpected block 2049 highlevel_didread(): read queue 11 got unexpected block 2217500 highlevel_didread(): read queue 11 got unexpected block 2217000 highlevel_didread(): read queue 11 got unexpected block 2216500 highlevel_didread(): read queue 11 got unexpected block 2216000 highlevel_didread(): read queue 11 got unexpected block 2215500 (This particular one happens about 31 times) finished at time 1163 with 13 pending queues disk spent 35 idle, 1066 seeking to track, 62 reading 54 blocks *** had 38 logical errors! time for request in queue (min, max, avg): 0 , 197 , 44.6 +/- 77.1 time for request in read (min, max, avg): 1 , 198 , 68.1 +/- 81.1 time for request total (min, max, avg): 1 , 394 , 112.7 +/- 151.7
What does this error mean? I'm pretty sure I'm not changing any of the block information (blk or req).
The errors mean that the [virtual] system is getting back blocks which it didn't ask for (or which had previously been returned, more likely in this case). That probably means that your code is injuring the contents of the request queue in some way, probably by adding or removing entries incorrectly.
A good approach to debugging would be to create a small request file (with fewer requests), see if that breaks in a similar way, then run the program with the verbose flag ("-v") — that will let you see what's going on in terms of which blocks are being requested from the disk and when. As suggested in the previous question (Question 14 (2011)) you might find it useful to print out the contents of the request queue before and after, and see if this matches up with what you think is happening!
Keywords: assess4-1112
Submission reference: IN2123
Before I progress too far down my current path I wanted to clarify exactly how you would like an implementation C-SCAN to behave. My current attempt involves having all the read requests dumped into the readqueue and once there ordered from smallest to largest and then actually read. This will provide a very swift solution I am sure but I don't know whether it is representative of the algorithms usage in real life (it requires having all the read requests at the beginning so they can all be ordered).
The alternate approach I considered was simply dumping all the requests into the readqueue and then as they are read have the readcomplete method compare the current readrequest with the last, if it is larger have it read, if it is smaller, skip it and move on. Once the highest request is reached have it jump back to 0 and start increasing again. This method would be slower since this process would potentially need to be repeated many times.
I wanted to check this because the current method I am attempting is throwing up a peculiar error and before I spend too long trying to fix it I want know if it would even result in a correct solution.
If all blocks were available at the start then your first thought would be right. However, the blocks are requested at different (effectively arbitrary) times, so at no point are all blocks to be read known. This is one of the issues of non-determinism, which you code needs to be able to cope with. Sorting then processing will deal with all the requests that are currently outstanding, but more may arrive whilst those are being processed — which have to be handled appropriately (there are many different ways you can deal with this bit!).
Your second suggestion is basically SCAN (or one-way elevator), but it should work. You can improve though by alternating the SCAN direction (which makes it C-SCAN or a proper elevator algorithm).
Keywords: assess4-1112 , disk-scheduling
Referrers: Question 21 (2011)
Submission reference: IN2124
In my attempt at provising an algorithm I thought I had finished it with much better results. However, I seem to be reciving only 5 logical errors within requests.txt file. I have not yet tested my algorithm on anything else until I am sure I can solve the cause of these errors. The problem itself lies within the following:
if readqueue is greater than zero {
initialise a for loop with condition less than readqueue_size {
int idx = (readqueue_tail + i) % readqueue.length;
if the current block at readqueue[idx] is not equal to lastRead &&
the current block is greater than the block of lastRead {
/* still got requests to service, dispatch the next block request (at tail) */
DiskSim.disk_readblock (readqueue[idx].blk, readqueue[idx].req);
lastRead = readqueue[idx];
/* increment tail pointer, modulo buffer size */
readqueue_tail = (readqueue_tail + 1) % DiskSim.MAXREQUESTS;
readqueue_size--;
}
}
}
otherwise loop until it is.
This works but gives the following results:
drive busy, cannot read block 1025 at this time! drive busy, cannot read block 2457602 at this time! drive busy, cannot read block 2600102 at this time! drive busy, cannot read block 10219000 at this time! drive busy, cannot read block 10230000 at this time! finished at time 431 with 13 pending queues disk spent 163 idle, 251 seeking to track, 17 reading 15 blocks *** had 5 logical errors! time for request in queue (min, max, avg): 0 , 188 , 17.1 +/- 49.9 time for request in read (min, max, avg): 1 , 188 , 17.9 +/- 49.6 time for request total (min, max, avg): 1 , 190 , 34.9 +/- 66.0
I can't see where in the loop this is happening and I've been over it with a debugger.
You say your code works, but it doesn't! (hence the errors). Debugging with a debugger probably won't help -- the most useful way of debugging would be to run with the "-v" (verbose) option which causes the framework to print out what it's doing (more "-v" options give more verbosity, as is the case with many programs out there).
The specific problem you're seeing is that the disk is being sent requests when it's already busy, which it doesn't support (one block at a time!). That probably happens because the loop you have can dispatch multiple block reads, instead of stopping once it's dispatched the request at 'idx'.
Another problem which would become apparent is that you dispatch the block at "idx", then trash the one at "readqueue_tail", leaving the one at "idx" still there for next time! As suggested in the slides, swap this with the one at tail before dispatching, so you're not throwing away other read requests. Alternatively, shuffle-up the array, but that's more hastle in the code.
Keywords: assess4-1112
Submission reference: IN2125
When we edit the code on our preferred IDE how do we upload it back to the raptor folder?
It's not clear what you're trying to do here -- why do you need to upload it back to raptor? If you're compiling and running on raptor, either use scp or map your raptor filestore on the Windows desktop via Samba/CIFS ("\\raptor\files"). Submission of your modified DSched.java or dsched.c should be done via Moodle though.
Keywords: assess4-1112
Submission reference: IN2126
After implementing an algorithm without errors I have received the following results:
finished at time 434 with 11 pending queues disk spent 157 idle, 252 seeking to track, 24 reading 22 blocks time for request in queue (min, max, avg): 0 , 188 , 24.8 +/- 49.2 time for request in read (min, max, avg): 1 , 188 , 12.5 +/- 41.3 time for request total (min, max, avg): 1 , 190 , 37.3 +/- 59.6
Is this acceptable? (I'm particularly concerned with the pending queues)
The fact that there are pending queues means that this is broken in some way. Basically that the system went idle after only 22 blocks were read (there are more blocks than this in the request file!). At a guess, your code isn't dispatching the next read request when a previous one has completed, but not all of the time (22 of the blocks got read okay).
Keywords: assess4-1112
Submission reference: IN2127
I was wondering if the efficiency of our algorithm matters (the code rather than the head movement) in terms of marking. I've used a bubble-sort to order my queues and obviously in a real system the time it takes to sort the queues matters, in the simulation it doesn't appear to. Would it be worth changing this to something like quicksort?
Grossly inefficient code will probably lose marks compared with its more efficient equivalent, but there's probably not a huge amount in it. However, when a particular algorithm is used, I'm looking for a demonstration of understanding, not just mindless plug-and-play coding! Don't assume quicksort is faster than other sorting algorithms for every situation though — it isn't.
Keywords: assess4-1112
|
Maintained by Fred Barnes, last modified Wed May 25 15:07:20 2016 |
