|
CO527 Anonymous Questions and Answers Keyword Index |
This page provides a keyword index to questions and answers. Clicking on a keyword will take you to a page containing all questions and answers for that keyword, grouped by year.
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.
Keyword reference for assess4-1112
2011 |
Submission reference: IN2140
Hi, here is my bubble sort algorithm:
public void sortlist (ReadReq thelist[])
{
int i, j;
ReadReg t;
for (i = (readqueue_size - 1); i >= readqueue_tail; i--) {
for (j = readqueue_tail + 1; j <= i; j++) {
// compare and maybe swap thelist[j-1] with thelist[j]
}
}
}
I thinks it's broken in some way but I can't seem to figure out what's wrong.
This looks like a wrap-around related problem: if "readqueue_tail" is not zero, this code will go wrong. See Question 28 (2011) for a description of why. Expressing the bubble sort's loops over the circular buffer (assuming readqueue_head and readqueue_tail are both changing) will not produce pretty looking code, though it should work. It would probably be simpler to ensure readqueue_tail is always zero (i.e. remove it), and swap with the request block at the other (head) end of the array — beware though, the request at the head end of the buffer is at index ((readqueue_head - 1) + readqueue.length) % readqueue.length, ugly because "%" doesn't generally behave nicely with negative numbers).
Keywords: assess4-1112 , bubble-sort
Submission reference: IN2139
Cheeky question - which is likely to get a better mark - a brilliant solution submitted late, with the percentage penalty, or a mediocre solution submitted before the original deadline? :)
Assuming there's not a crazy number of occurances, I'll aim to mark both and provide the best mark. If an excessive number of people do this though, I'll default to the newest submission -- bottom line, don't submit it if you think it's worse than your original submission! (but what is considered "worse" may vary..).
Keywords: assess4-1112
Submission reference: IN2137
I'll try to explain this clearly but it may be difficult.
The idea behind my algorithm was to have to separate request lists; whilst one is being operated on (as in, its requests being found/fulfilled) the other list fills up and then the code swaps over, simply using a boolean switch. However, in readcomplete() I have no idea how to search through the entire list at once. I thought I'd be able to something like:
while (queue size > 0) {
readblock()
didread() //This is on the block just read
// then alter the tail and size accordingly.
}
However this throws up loads of errors of all kinds; bad hashes, busy drive etc. Do I have the right idea, or is just a load of rubbish? I've got a basic improvement already submitted so this is just for extra marks really.
The idea you have is quite sensible, but you cannot implement it quite like this. Specifically, for each call of readcomplete() you can only dispatch at most one request. Dispatching many, as your loop will do, will result in the "drive busy" style errors that you are seeing. This is one of the mild complexities of OS programming — you can't always have the logic for one thing all in one place; sometimes it has to be spread about, both spatially and temporally. That said, having two queues and switching between them shouldn't be impossible!
Keywords: assess4-1112 , disk-scheduling
Submission reference: IN2136
I'm having problems searching through the array of requests. Please can you explain how the circular buffer and the modulo operator work?
Quite a few people have stumbled over this one — the modulo operator ("%" in Java and C) produces, basically, the remainder after division. Its primary use in code is to cause a wrapping-around effect, which is how it is used in the context of the circular buffer. For example, assume we start with an empty buffer:
H +---+---+---+---+---+---+ | | | | | | | (head=0, tail=0, size=0) +---+---+---+---+---+---+ T
Then, the high-level calls blockread a couple of times which causes various things to be added to the buffer, and "head" and "size" updated accordingly:
H
+---+---+---+---+---+---+
| 5 | 10| 2 | | | | (head=3, tail=0, size=3)
+---+---+---+---+---+---+
T
Now lets assume some things get removed from the tail position (as the disk goes idle and is able to service them):
H
+---+---+---+---+---+---+
| | | 2 | | | | (head=3, tail=2, size=1)
+---+---+---+---+---+---+
T
Up to this point, things are looking quite sensible, and it's not hard to see that "size" is just "head" minus "tail". Lets assume some more things get added:
H
+---+---+---+---+---+---+
| | | 2 | 1 | 7 | | (head=5, tail=2, size=3)
+---+---+---+---+---+---+
T
And still everything is sensible, "size" is still "head" minus "tail". However, when the next thing gets added, something different happens:
H
+---+---+---+---+---+---+
| | | 2 | 1 | 7 | 4 | (head=0, tail=2, size=4)
+---+---+---+---+---+---+
T
The "head" pointer has wrapped around back to the beginning of the array, as it clearly should, since this is where the next empty slot is. However, it is no longer the case that "size" is "head" minus "tail" (clearly 4 <> 0-2). To get the wrap-around, there are two ways you can code it:
head++;
if (head == length) {
head = 0;
}
Or:
head++;
head = head % length;
The second of which is a bit more succinct, and could be shortened to just:
head = (head + 1) % length;
which is what the code actually has in places. If something else gets added to the buffer, we'd get:
H
+---+---+---+---+---+---+
| 3 | | 2 | 1 | 7 | 4 | (head=1, tail=2, size=5)
+---+---+---+---+---+---+
T
Whilst the "size" equals "head" minus "tail" idea is broken when "head" is numerically less-than "tail", it is the case that: "size" equals ("head" minus "tail") modulo "length". If some entries then get removed from the buffer, we'd have:
H
+---+---+---+---+---+---+
| 3 | | | | 7 | 4 | (head=1, tail=4, size=3)
+---+---+---+---+---+---+
T
And when "tail" reaches the end, it wraps around in the same way as "head" did.
Having wrap-around like this is convenient for efficiency, instead of shuffling array elements around or reallocating/copying the contents each time. Alternatively a linked-list would have done just as nicely (same ease of adding and removing things) however, a linked-list requires a bit more code to implement.
A particular problem I've seen some people have is iterating over the contents of the array. Given the pictures above, something like:
for (int i=0; i<size; i++) {
...
}
Is going to break, since you'd be accessing:
H
+---+---+---+---+---+---+
|=3=|= =|= =| | 7 | 4 | (head=1, tail=4, size=3)
+---+---+---+---+---+---+
T
So whilst the first element (index 0) is valid, the next two are not! Something else I've seen people code is this:
for (int i=tail; i<size; i++) {
...
}
This won't work either, particular in this case since "tail" is 4 and "size" is 3, so the loop condition is false from the start. Another variation that won't work:
for (int i=tail; i<head; i++) {
...
}
Since, in the above, "tail" is 4 and "head" is 1, so no looping ever occurs. Logically, the number of iterations must be equal to the number of entries in the buffer (which is what "size" tracks), so it's easiest to go from zero and loop over these directly. However, the value used to index the array must be suitable adjusted to wrap-around in the same way. A naive implementation would be something like:
for (int i=tail; i<(tail + size); i++) {
...
}
But this will break in some cases, since you'd be accessing these elements:
H
+---+---+---+---+---+---+
| 3 | | | |=7=|=4=|= = (head=1, tail=4, size=3)
+---+---+---+---+---+---+
T
Where the last one doesn't exist! In Java you'd get an ArrayIndexOutOfBoundsException; in C you'd get a crash and/or undefined behaviour. The correct way to iterate through the contents of the circular buffer is like this:
for (int n=0; n<size; n++) {
int i=(n+tail) % length;
...
}
Or if you prefer:
for (int j=tail; j<(tail + size); j++) {
int i = j % length;
...
}
Or you could be quite nasty and cater explicitly for the case where "head" has wrapped around, but "tail" hasn't yet (but this is not good programming practice!):
if (head < tail) {
// head must have wrapped around!
// deal with back-half of array.
for (int i=tail; i<length; i++) {
...
}
// and then the front-half.
for (int i=0; i<head; i++) {
...
}
} else {
// normal, full or empty
for (int i=tail; i<head; i++) {
...
}
}
Whilst code such as this does work, it's far from pretty and results in large amounts of duplicated code.
Keywords: assess4-1112 , circular-queue
Referrers: Question 28 (2015) , Question 52 (2015) , Question 16 (2012) , Question 31 (2011)
Submission reference: IN2135
I am trying to implement the SSTF algorithm, I have implemented code to work out which block is closest to the last inside the dsched_readcomplete function, however am not sure where to go next as replacing:
disk_readblock (readqueue[readqueue_tail].blk, readqueue[readqueue_tail].req);
with:
disk_readblock (readqueue[closestblk].blk, readqueue[closestblk].req);
gives me an output like this:
disksim: highlevel_didread() read queue 0 got unexpected block 1025 disksim: highlevel_didread() read queue 0 got unexpected block 0 disksim: highlevel_didread() read queue 0 got unexpected block 2048 disksim: highlevel_didread() read queue 0 got unexpected block 1025 disksim: highlevel_didread() read queue 0 got unexpected block 0 disksim: highlevel_didread() read queue 0 got unexpected block 0
So clearly there is more to be done, so was wondering if you could provide any pointers. Thanks.
At a guess, the problem is related to not removing the block from the array correctly. Once you have found closestblk and dispatched it, you need to remove it from the readqueue array. There are two possible approaches:
Keywords: assess4-1112
Submission reference: IN2134
Regarding Question 25 (2011), here is my code for disposing of blocks:
public void disposeblock (int thelocation)
{
boolean done = true;
while(thelocation != readqueue_head)
{
ReadReq nextthing = readqueue[thelocation+ 1];
readqueue[thelocation] = nextthing;
}
}
and here is the code for my read complete method:
public void readcomplete(int blk, BRequest req)
{
// return block to system if (blk >= 0)
if (readqueue_size > 0) {
/* still got requests to service, dispatch the next block request (at tail) */
[snip code]
disposeblock(current);
readqueue_size--;
}
}
Any suggestions as to what's wrong?
I presume there's more in your disposeblock method than the code above, else the loop would never terminate! However, nowhere in your code do you update the readqueue_head index, which is wrong, assuming that the readblock method when called increments it. When something is removed from the array, as well as decrementing readqueue_size, either the head or the tail pointers must move too; presumably the former, since it seems that readqueue_tail is fixed at zero (i.e. the requests are always at the start of the array and don't wrap around in the same way that the FIFO solution does).
Keywords: assess4-1112
Submission reference: IN2133
Hi, this is related to Question 23 (2011). After doing a bit of debugging, I agree that the problem is related to dealing with completed requests. My bubble sort seems to be working ok, as before I implemented it I made a version to sort integers which worked fine, could the problem be with my dispose method, which gets rid of completed requests by moving future blocks one space to the left? I'm a bit confused as to why its not always dealing with requests, as the statements are within an "if" block, that checks if the read queue size is greater then zero, so if there are things to be dealt with, then they should work. I'm just a bit baffled as to why the machine goes idle after a second queue is added, because before it worked perfectly.
More than likely, yes, the problem is with disposing of completed requests. Unfortunately I cannot help much further than this without seeing the code, but if you post the code here, I'll have a look and feedback on the (presumably broken) part of it (but without giving your whole solution away!).
Keywords: assess4-1112
Referrers: Question 26 (2011)
Submission reference: IN2132
I think I'm nearly done with assessment 4, my bubble sort is working and I think I've got my algorithm sorted as it works for the first queue. When a second queue is introduced however, errors start occurring. My system works in the following way:
public void readcomplete(int blk, BRequest req) {
// code for giving the block back to the high level system
if (readqueue_size = 0 {
// set my current block the the read queue tail.
if (the current block = read queue head) {
// the current block is reset to the read queue tail
}
// regardless of this, the block is then read and it is then
// disposed of by moving all the blocks one place to the left,
// the next block is moved into position, the size is decremented
// and the tail incremented.
}
where am I going wrong?
This sounds like some confusion about how the circular buffer works, possibly related to Question 23 (2011). The point of the readqueue_tail variable is to mark the first (oldest) request in the buffer, and readqueue_head the next free slot (where new requests are deposited). If you've moving the buffer contents around (i.e. shuffling left, or more precisely, downwards modulo size) then you probably don't want to be using the readqueue_tail variable anymore — it's ultimately the element at readqueue_head - 1 which is now different, so that (readqueue_head) should be changed. Of course, if readqueue_tail is always zero, then readqueue_head == readqueue_size (invariant) so you can get rid of that too and just use readqueue_size.
The purpose of using a circular buffer (as the basic implementation does) is to avoid having to shuffle the array contents around like this; instead of moving everything down one place in the array, the tail is simply incremented (modulo buffer size).
Keywords: assess4-1112
Submission reference: IN2130
I have an implementation of C-LOOK that isn't quite working right. It finishes with six pending queues and a large number still waiting to be read. It works by using a third worker variable, firstly, the code checks whether this is equal to the head, if it is, then it it sets it to be the same as the tail, as the end of the disk will have been reached, regardless of this, it then accesses the block at the location of the worker variable, and then moves it along in the array by 1. Any suggestions as to what's wrong?
Logically what you're doing sounds sort of right; the problem probably relates to not scheduling the next block to read whenever one is available -- check each path through the code and make sure that if there are more requests to service (i.e. readqueue_size is greater than zero) then one of them is dispatched. Assuming you're sorting the requests too, I'd recommend getting rid of the circular buffer mechanism and just using array elements 0 through (readqueue_size - 1). That would simplify things a bit. The existing implementation removes the oldest request in the queue as it is dispatched; you should make sure that something in your code is dealing with completed requests, given that you're using a different "worker" variable to track the last one dispatched (whereas the existing implementation uses readqueue_tail for this purpose).
Keywords: assess4-1112 , disk-scheduling
Referrers: Question 24 (2011) , Question 25 (2011)
Submission reference: IN2129
I am trying to implement the SSTF algorithm, which was supposed to be the easiest, but I am coming up with errors:
highlevel_didread(): read queue 0 got unexpected block 0 highlevel_didread(): read queue 0 got unexpected block 0 highlevel_didread(): read queue 0 got unexpected block 0 ... finished at time 305 with 13 pending queues disk spent 252 idle, 0 seeking to track, 53 reading 53 blocks *** had 52 logical errors!
Here is the part that I have changed:
[snip code]
for(int i = 0; i < (readqueue_size % DiskSim.MAXREQUESTS); i++)
{
if (readqueue[i].blk ...)
...
}
For my swap methods, I just used a temp variable to swap the two values.
This is a fairly common problem that I'm seeing here. The array's contents aren't indexed from zero; it's a circular buffer — explained in the assessment-related slides (on Moodle). See also Question 13 (2011), which explains the correct way to do this.
In regard to swapping a particular request with the one at 'tail', writing two separate (and fairly specific) methods is not good software engineering! However, given the way that you're calling these methods, I suspect they are broken. Parameters are passed by value in Java, not by reference, so writing something like:
void iswap (int a, b)
{
int t = a;
a = b;
b = t;
}
Is a no-op. 'a' and 'b' won't be changed in the caller. If anything, write just one method that swaps two elements in the array outright:
private void reqswap (int i, j)
{
ReadReq t = readqueue[i];
readqueue[i] = readqueue[j];
readqueue[j] = t;
}
Keywords: assess4-1112
Submission reference: IN2128
Looking at Question 16 (2011) ...
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).
It is my understanding from research that C-SCAN moves in one direction (moving back to 0 or first request in other direction), whilst SCAN moves in both directions.
Wikipedia: One variation of this method ensures all requests are serviced in only one direction, that is, once the head has arrived at the outer edge of the disk, it returns to the beginning and services the new requests in this one direction only (or vice versa). This is known as the "Circular Elevator Algorithm" or C-SCAN.
Is this incorrect?
I'm of a mind to believe that Wikipedia is right and I was wrong. The labelling of a particular algorithm is less important than understanding the mechanics of it though :-).
Keywords: assess4-1112 , disk-scheduling
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
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: 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: 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: 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: 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: 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: 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: 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: 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: 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: IN2115
I have a few questions for assessment 4 (regarding the SSTF algorithm):
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: 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: 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: 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: 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
|
Maintained by Fred Barnes, last modified Wed May 25 15:07:20 2016 |
