|
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 assess5-1314
2013 |
Submission reference: IN2982
My C-Look implementation scores 773 for the small file, and 2397 for the large file. "-d 32" runs score between 2500 and 3000. Is this reasonable?
Please see various other anonymous questions on this: there's enough information on the pages now for you to make an informed judgement on your own work!
Keywords: assess5-1314
Submission reference: IN2981
I noticed that after the initial idle call (-1 blk value for readcomplete), there isn't any other idle phase, with these files at least. Do we have to take this into consideration? Or will you just be using our scores from these two (requests and requests-big) for marking?
From the assessment description: "Your submission will be tested on an unseen request data file, so you should focus on an appropriate generalised algorithm, not one that is targeted to the provided data-sets.". Technically, you need to handle the idle case at any time, not just at the beginning. Whether or not your solution encounters this will depend mostly on how fast your solution processes the requests it's got (i.e. if there is idle time before subsequent requests are made by the system).
Keywords: assess5-1314
Submission reference: IN2980
Will 703 and 2937 for the small and large request files get me a good mark?
That will probably score somewhere between 50% and 60%, so reasonable. It's comparable with various SSTF implementations, at least for those two request files.
Keywords: assess5-1314
Submission reference: IN2979
In regards to the disk scheduling assignment for CO527 I first implemented LOOK and then C-LOOK, but LOOK scores better for me (even on files I made myself, with the exception of the largest one). However, C-LOOK scores better using the dynamic option. My concern is that if the assessment is marked based on the score of some file(s) LOOK may end up scoring better despite its bias. What option would be best to go with?
Your call! See Question 99 (2013) perhaps — dynamic mode is basically overload, but that may be detectable and as a result you could use a different strategy in scheduling. Such things are going to be complicated, but if you can get it to work, it'll likely score well overall. Bear in mind that the best student submission will score 100%, so scoring is relative to your peers in that sense.
Keywords: assess5-1314
Submission reference: IN2978
Probably a bit late to ask this but thought I'd try...when writing a C-SCAN implementation, will the simulator take the shortest (circular) route from a high sector to a low sector or not? If not will I have to get it to "move" to the very last sector before it will make the jump to the first one again?
The simulator will work as it's programmed to do :-). There is only one way the active sector changes, and that's as the disk spins. So in terms of longest or shortest route, there isn't a choice: disks spin one way only.
Keywords: assess5-1314
Submission reference: IN2975
I have written a loop:
for (int i=readqueue_tail; i < (readqueue_tail+readqueue_size); i++)
...
like that, but I am getting an ArrayIndexOutOfBoundsException?
As I've said elsewhere, you cannot iterate over a circular queue like this: in fact, what you get by adding the queue tail pointer to the queue head pointer doesn't necessarily make sense. In short, don't try and do this, unless you understand fully what's going on: draw a diagram and work through it by hand! Instead, start with the LIFO version of the code. It's performance as LIFO is extremely bad, but the code is perhaps a simpler starting point for other algorithms (where whether it's implemented as a stack or queue is irrelevant, since it's not treated as either necessarily).
Keywords: assess5-1314
Submission reference: IN2976
Is there any reason I would get a NullPointerException at "req.time_read = timenow;" in DiskSim.java?
Most likely your code is calling disk_readblock() with a NULL parameter: the second parameter should be the BRequest structure (object) that accompanied the request originally.
Keywords: assess5-1314
Submission reference: IN2974
How would I find the top track?
Look at the code! Near the start of DiskSim.java is a constant that specifies this; it's publically visible name so you can use it in your own code if you must. But note that strictly speaking your code doesn't need to know this outright: the top track is the biggest one in the request queue as far as it needs to be (or should be) concerned.
Keywords: assess5-1314
Submission reference: IN2973
What value should I expect to get for a C-look implementation on requests-big.txt? I'm currently getting:
[snip]
Score value: 2936
and for requests.txt:
[snip]
Score value: 1762
For the large request file, the score looks sensible: better than SSTF anyway. But for the smaller request file, 1762 seems slow: FIFO manages a score of around 1400. I've not looked hard at what is precisely meant by "c-look" (and it may depend on whose definition you use) but my own C-SCAN implementation (not sophisticated by any means) gets a score value of around 670 on the small request file, and around 2340 on the big request file. On that basis, I'd query whether your algorithm is implemented correctly: based on the fact it's worse than FIFO in one instance.
Keywords: assess5-1314
Submission reference: IN2971
I'm confused as to what we are actually trying to compare. I'm using linked lists to implement the C-Scan. I start at the head and move down towards the end of the disk, as I'm moving down the disk, I'm going to be servicing requests as it goes down. But in this instance what is a "request", am I meant to be looking for blocks or tracks?
The system (high-level) requests blocks — as you previously learned, some sort of logical numbering applied to "block devices" (starts from 0 and goes up to the size of the device divided by the size of a block, minus one). These blocks reside on particular tracks, the mapping from the former to the latter computed by DiskSim.block_to_track(). When a request is given to the disk, it is given as a block number (and returned as such) but the disk must first move the heads to the correct track for that particular block (i.e. some code in there, that in reality would probably the disk's firmware, also calls this to find out which track needs to be selected). The scheduling algorithm, whose job is (partly) to minimise track-to-track seek times, thus should be comparing tracks of those particular blocks. Note that it wouldn't make sense to define a request as a "track", since any particular track contains a whole bunch of blocks (in all sectors on that track and across all heads).
Keywords: assess5-1314
Submission reference: IN2970
Is it recommended to periodically take requests from the request queue/stack and place them in another temporary queue/stack to be serviced? It seems like taking requests in waves is the only way to ensure no starvation happens.
That's probably a sensible way of dealing with starvation, in cases where you know it's happening.
Keywords: assess5-1314
Submission reference: IN2969
Are we allowed to use the block-to-track methods in DiskSim?
Yes! Else I would not have explicitly said about it in the assessment description :-).
Keywords: assess5-1314
Submission reference: IN2968
Regarding the requests file you will be using to test each implementation, will it contain enough requests to simulate -dynamic to a high amount of accuracy while still being consistent over each implementation so that it is fair?
I won't be testing implementations on just one request file. The dynamic mode is pathological: disk overload basically, so it may be representative of one of the tests. Ideally your implementation should perform well under whatever conditions (such would be expected in any normal OS) but it's reasonable to settle for something which is "pretty good" in all cases (i.e. SSTF does pretty well except for high-load, where it ends up starving requests, and can starve in other cases too).
Keywords: assess5-1314
Referrers: Question 108 (2013)
Submission reference: IN2966
Is "time for request in queue" just how long it took to start reading a block from when it was requested? Because in my SSTF implementation the average is 22848. Does this mean starvation is occurring?
Yes, and possibly. But the standard deviation will tell you more about starvation than the average.
Keywords: assess5-1314
Submission reference: IN2965
For assessment 5, what exactly does the visualisation mean? It moves too quickly and there's too much info for me to process any of it.
It shows the read/write head's position on the disk in tracks (i.e. track 0 at one end horizontally). The head will flash 'R' when it reads, which won't necessarily stay on the screen long. You can slow it down if needed by hacking the appropriate bit of code in DiskSim.java (around line 1020) by just changing the wait for delay to delay * 100 or something. But the point of the visulisation is that you can see if your algorithm is doing the right thing, e.g. for SSTF, it should move slowly across the disk doing lots of reads as it goes. For C-SCAN, the head should sweep forwards and backwards processing requests as it goes. SCAN is similar.
Keywords: assess5-1314
Submission reference: IN2964
Hi, I was wondering if you could explain the conversion from FIFO to SSTF in a little more detail. I am struggling to understand slide 28 of your helpful slides that you have included. More specifically, is there anyway you could explain the 3 points in a little more depth please? Thanks.
I'm afraid that if I go into any more detail here, I'm effectively doing it for you! Thus, you won't really learn anything useful from the assessment. Obviously you need to understand what the code there is doing, but given that you've been programming for 2 or more [academic] years, this ought not to be a problem..
Keywords: assess5-1314
Submission reference: IN2963
I'm having the same problem as Question 84 (2013). I have no idea why this is happening and nothing seems to make any difference — my code looks likes it should work. Is there any reason that it may work well for small inputs but not large ones? Is there any guidance you can give to help me fix this problem?
Usually because something is broken, either subtly or seriously. The way to diagnose this is to create a request file, perhaps with two queues starting at the same time, where the track numbers in each are strictly increasing. The formula to construct block numbers is given in the slides. But simply:
0 8 0 64 128 192 256 320 384 448 512 0 8 1 65 129 193 257 321 385 449 513
If you run with verbose on, you should see the requests processed in the block order: 0, 1, 64, 65, 128, 129, etc. I.e. shortest seek time first. With FIFO, this would be more like: 0, 64, 128, 256, 1, 65, 129, ... (haven't actually tried this, so may be different). As mentioned elsewhere, shortest seek time first is not nearest block number first.
Keywords: assess5-1314
Submission reference: IN2961
my SSTF implementation gives around 3200 for requests-big.txt but around 2800 for requests.txt. Is this fine?
The value for requests-big.txt looks sensible, the for requests.txt seems quite high (I'd have expected something around 720).
Keywords: assess5-1314
Submission reference: IN2959
I'm trying to run this in Eclipse by choice, but nothing happens when I go to DiskSim.java -> "run as" -> "Java application". Is there a reason why this wouldn't work?
Not that I'm aware of — but as I've said elsewhere, Eclipse is too heavyweight and not the right tool for the job. Using Eclipse to edit is fine, but I'd stick with compiling and running from the command-line (if you're forced to use Windows). Sensible suggestion: compile and run on raptor, edit on Windows (you'll need raptor's filestore mounted, of course, which off-campus means abusing SSH tunnels or using the VPN).
Keywords: assess5-1314
Submission reference: IN2957
This is very basic, but how do you read a block to tell what value it is? I'm totally lost.
Your question doesn't make sense I'm afraid. A block's "value" is irrelevant (and for the most part unknown). But to read a block you call "DiskSim.disk_readblock(...)" — at some point later on, your "readcomplete()" method will be called to indicate that this block has been read, which it can then give back to the high-level code by calling "DiskSim.highlevel_didread(...)".
Keywords: assess5-1314
Referrers: Question 90 (2013)
Submission reference: IN2956
For a C-SCAN implementation should we be concentrating on reading blocks that are on the same track as the block being currently serviced?
That should probably apply to most things, including SSTF, SCAN and C-SCAN; i.e. (for SSTF) if there are requests on the same (current/last) track, these must be closer than all others (zero track seek time), so should get serviced in preference.
Keywords: assess5-1314
Submission reference: IN2955
In SCAN/C-SCAN do you sort the requests in what track they're in, or by the number of the request?
What do you mean by "number of the request"? But see Question 80 (2013) — the track is what you should be primarily interested in, as moving between tracks is what takes (comparatively) a lot of time.
Keywords: assess5-1314
Submission reference: IN2954
How do you find out where the current head position is?
You can't: you have to keep track of this yourself. In many cases, it will be the track associated with the block seen by readcomplete, but not always (e.g. if the disk had been idle).
Keywords: assess5-1314
Submission reference: IN2953
In the LIFO implementation why does it start reading the 3rd line of requests before all of the 2nd line of requests are finished? For example: read request for block 2457603, then the next read request is for read request for block 1048500. But there are still blocks in the second queue to read such as 2434000?
The requests are not read linearly: each line of block numbers is a set of requests that starts at a specific time. So blocks from the 3rd line will start being requested a little while after blocks from the 2nd and 1st lines are requested (start times being 30, 40, 50, etc.). Each request queue will try and keep a fixed number of block requests pending (4 at the moment). Thus the disk scheduler code will see the first 4 blocks of each request before seeing more blocks from the same request queue. How this works isn't important though: your disk scheduler just gets requests for particular blocks and has to deal with these.
Keywords: assess5-1314
Submission reference: IN2952
My SSTF implementation scores 704 for requests.txt, but 8291 for requests-big.txt. There are no logical errors, and it seems to process all the requests. Is there anything that could be causing such a bad score for requests-big.txt when the score for requests.txt is reasonable?
Although it's not broken, something clearly isn't right. You should be getting a score of around 3000-3200 for SSTF, give or take. Look at the raw stats though, i.e. average and the deviation, as this might help a bit. Also run with visualisation on and check that the read/write heads are doing what you might expect (i.e. shortest seek between reads). As to likely causes, there could be many, some of which are eluded to in other anonymous question answers.
Keywords: assess5-1314
Referrers: Question 94 (2013)
Submission reference: IN2951
If the SCAN algorithm starts from the outside and works inwards, and the read/write head starts at track 0 in the middle, doesn't initially moving the head to the start position for SCAN slow the whole process down?
Not sure why you think track 0 is in the middle..! Are there negative track numbers on one side and positive on the other? Track 0 is either the outermost or innermost on the disk (doesn't matter which).
Keywords: assess5-1314
Submission reference: IN2950
Is my interpretation of C-Scan correct?
Thanks.
No, I'm afraid! If you swap head and track in your description what you have is SCAN in effect. Head numbers are mostly irrelevant: the disk has multiple read/write heads (as per diagram) so can service multiple requests from the same track/sector at different heads simultaneously.
Keywords: assess5-1314
Submission reference: IN2948
Is that I should compare between the track number rather than the block number when I try to sort the queue?
As I've said in Question 77 (2013), don't try and sort a queue. This is just hard. Much easier if you start with the stack version (LIFO implementation). But yes, things like SSTF and others are (should be) concerned with the track number foremost, since changing tracks takes time.
Keywords: assess5-1314
Referrers: Question 87 (2013)
Submission reference: IN2947
I'm getting a lot of "logical errors". Stderr is full of lots of "highlevel_didread(): read queue foo got unexpected block bar". What does this mean? Is my implementation useless as a result?
See Question 30 (2013). But yes, unfortunately, it means your implementation is broken and won't score anything in effect. At this point you need to start writing your own request files (starting with just a few blocks perhaps) and debug — running with "--verbose" or putting in your own "System.err.println(...)" statements.
Keywords: assess5-1314
Submission reference: IN2946
I am using the SCAN method and when I test it in --dynamic 32 mode, I get an average score around 6000 and is it a reasonable score? As I think I am doing correctly but the score seems a little bit high...
My SCAN implementation in this mode came out at around 2500, so I'd suspect something isn't entirely right here. Double-check: run with --vis and a static request file and look to see if the SCAN is working in the way it ought to be. You can always construct your own request file (I'd suggest writing a script to do this if more than a handful of lines) so you know what behaviour to expect.
Keywords: assess5-1314
Submission reference: IN2945
Hi, I don't have a clue where to start on assessment 5. I have read through all the material on Moodle and have conducted my own research online, but still cannot comprehend how to undergo the task. I have spoken to a large number of people and they all seem to be really struggling. Any more help would be very much appreciated!
There are a few things that you need first (before attacking the code) in terms of understanding:
Hopefully you understand the problem, but understanding the code may be more of a challenge. If the whole head/tail thing in the FIFO implementation is causing confusion, start with the LIFO implementation instead (DSched-lifo.java) — this has a fixed-size array that acts as a stack. The way the simulated OS interacts with the disk scheduler code is not straightforward. Logically there are two fairly independent things going on: OS generating read requests at some arbitrary rate; and the disk processing requests one at a time. These things interact through the DSched code: new requests are added to a stack (or queue), and when the disk is able to accept another request, this is taken off the stack (or queue).
The code isn't deliberately intended to be complex, but that is the nature of such things in an OS. As we said early on in the module, part of the OS's job is to manage lots of things going on at once — this is part of that. If anything, this is much simpler than a real OS, that also has to deal with concurrency issues, such as protecting shared data structures. The simulator is completely single-threaded, whereas a real OS has things happening inside interrupt handlers (disk read complete perhaps) and the like.
That aside, a sensible first step in coding is to try and implement something like SSTF. I.e. rather than the bit of code in readcomplete() that picks the last thing on the stack (the entry at index readstack_size - 1), pick the request whose track is closest to the last one serviced. The code deals with block numbers — to get the corresponding track (which is most relevant for disk scheduling) you need to call DiskSim.block_to_track(int blk). Once you've identified which request you want to give to the disk next, you need to send it to the disk (calling disk_readblock()) and remove it from the stack/queue — the simplest approach is not to try and shuffle up the array contents or other complex things, but just swap with the request at the end (which is easy to remove as the existing code already does). The key bit of the SSTF algorithm here is "pick the request whose track is closest to the last one serviced". I.e. you need to search through the queue/stack of pending requests. An alternative is to keep the array contents sorted (and I'd only ever suggest you do this to the LIFO code, not try and mangle a quicksort over a circular buffer — what you end up with is hard). But observe that it's not actually needed: searching the array for the next best request is fine, since it's O(n). In a real OS, this would be an issue for efficiency of the OS code itself, as we would like things to be O(1) or O(log2(n)) preferably.
More complex algorithms such as SCAN, C-SCAN, elevator, etc. (some overlap here depending on whose definitions you read) require more complex implementations. In any case, I'd suggest you start by implementing SSTF — it should perform much better than FIFO or LIFO in general. Once you've got that (and have saved a copy in version-control, as an initial Moodle submission, or as a different file locally so you haven't lost it if you need to go back), then attempt the more complex things. Trying to jump from zero into C-SCAN for instance may be too much for many.
Keywords: assess5-1314
Referrers: Question 80 (2013)
Submission reference: IN2944
I am getting the same error as in Question 23 (2013). Should entries be removed from the data structure once they have be completed? I have tried this by setting the blk in the data structure for a just read block equal -1, but then my program just stops and doesn't return anythings.
Just setting the block number to -1 would work, but breaks its use as a queue — since now it will have "holes" for blocks that have already been dealt with. The slide-deck explains one way of handling this, which is swap that block (no longer of interest since it's been read) with the last one in the queue, and reduce the size of the queue by 1 (safe since the last item is now the done one). Again though, try a small request file and add debugging; something must be going wrong somewhere! When you say your program stops though, check to see if it's just eating 100% CPU (not stopped, but livelocked) that would suggest a non-terminating loop somewhere in your code.
Keywords: assess5-1314
Submission reference: IN2943
Will all of the requests be submitted immediately or spaced over random time periods in assessment 5?
Neither.. But it shouldn't matter. If you really want to find out, put together your own request files, run with verbose on and observe.
Keywords: assess5-1314
Submission reference: IN2942
Where in the array should the C-SCAN add to?
This is too specific a question, and unsuitable for anonymous Q+A pages! (as it only applies to people who have done C-SCAN using an array that is perhaps sorted somehow).
Keywords: assess5-1314
Submission reference: IN2941
I'm a little unsure as to how the scoring system works for assignment 5. Is lower better? Or higher? The supplied FIFO gets a score of 8701 on requests-big.txt. My SCAN implementation gets a score of 12944, I was under the assumption that lower was better as when I run requests.txt my score is lower than the FIFO implementation. Below is the output from requests-big.txt for my implementation.
finished at time 104787 with 0 pending queues disk spent 21 idle, 92257 seeking to track, 12508 reading 2105 blocks time for request in queue (min, max, avg): 0 , 103159, 2679.5 +/- 10210.2 time for request in read (min, max, avg): 1 , 259 , 49.8 +/- 64.1 time for request total (min, max, avg): 14 , 103176, 2729.2 +/- 10214.8 Score value: 12944
Lower is better — it represents a time value: average plus deviation. I think your implementation is broken. My SCAN implementation (which is nothing special) reports around 2400 for requests-big.txt.
As explained elsewhere, just because a particular algorithm works well on one dataset, doesn't mean it'll work well on all.
Keywords: assess5-1314
Submission reference: IN2939
I would like to use the C-SCAN approach, so I tried to build an array of queues, one to hold current requests, sorted, and th eother (idle queue) to store new requests. After the active queue is emptied, the two queues will be swapped around. However, at the end of operation there are still "pending queues" and the score value isn't reduced very much. What would cause the "pending queues" problem and is there any problem with my method? Is that some blocks are missed during the swap of active and idle queues?
If you have pending queues, this is an error, and the score value means nothing (but in most cases it's better to try and continue rather than just stop hard). It sounds like blocks are being lost from either queue, so double-check the code. Even better, print out the contents of both queues at various places and see if they're as they should be — you'll probably want to create your own small request files to check for correctness, of course. I would hazard a guess that it's the sorting that's broken, as this is usually where errors creep in. Swapping queues should not involve anything other than pointer manipulation (or equivalent; it depends on what you mean by "array of queues" precisely).
Keywords: assess5-1314
Referrers: Question 93 (2013)
Submission reference: IN2938
I am currently trying to set up the 5th Assignment so that i can easily work on it. Due to being at home (and the kent VPN is not working for me at the moment) I can't access my raptor files directly. I have used PuTTY to follow the raptor quick start and everything compiles and runs fine, I just now can't easily modify the DSched.java there. I tried importing a version into eclipse but the DiskSim doesn't have a main() to run (I feel I am missing something obvious here).
Would it be possible to explain how to get everything to work in an IDE like Eclipse or how I could possibly modify easily the DSched that is already on my raptor space without the VPN.
Obviously there is a main() method in DiskSim, else the command-line way of launching it would fail. I wouldn't recommend using any IDE though — too cumbersome and not needed (wrong tool for the job I feel). But people have not reported problems in the past, so maybe your Eclipse is broken.. Not using Eclipse I can't help you I'm afraid. But there should be no problem editing the file on raptor, or transferring it to/from raptor between local edits. Editors like vim and pico will be available on raptor, but it might be easier to edit locally (Notepad++) for instance and then use WinSCP (SCP/SFTP) to copy the files to raptor. Or even better, edit the files locally, and run the simulation locally — just from the command-line, no need for fancy IDEs! Because the Windows environment sucks for programming (frankly) you might want to consider installing something like cygwin to give you a command-line that won't drive you insane. Or fix the VPN issue.
Keywords: assess5-1314
Submission reference: IN2937
In the readcomplete() method, is the blk parameter the last block read?
Assuming that it is >= 0, then yes, but not always: if the disk was idle at some point (i.e. no more requests for some period of time) then this will be called with an invalid block to say that the disk is idle and is ready for more.
Keywords: assess5-1314
Submission reference: IN2935
Are we allowed to add extra methods? Such as for building new data structures?
Yes, that's fine (extra methods). If you needed extra classes, make them inner ones: submission is just the DSched.java file, nothing else. (any extra classes you create should just be wrappers for structured data, like the one already there). This is not, and should not, end up looking overly object-oriented.
Keywords: assess5-1314
Submission reference: IN2934
I have been looking a multiple versions of C code on Google. I have noticed one thing in common that they all have a head starting track. I can't seem to find this in the code provided (unless I'm not seeing it). Can we assume that there is no head starting track and therefore set it to whatever we deem appropriate.
See Question 27 (2013). But don't just convert someone else's C code to Java for this, that's potentially plagiarism if you don't acknowledge the source! The point of the assessment is to understand and implement a disk scheduling algorithm, and you don't need to look at [real] code for that!
Keywords: assess5-1314
Submission reference: IN2933
Is there any reason why I would only get:
finished at time 295 with 4 pending queues
disk spent 31 idle, 253 seeking to track, 11 reading 15 blocks
and no more information?
Because there's no more information to give. What's happening here is that your implementation is losing requests — 4 of the request queues had outstanding blocks. I'd suggest you make a much smaller requests file (just a handful of blocks, or maybe just two initially) and then run with the "-v" flag (verbose) to try and figure out what's going wrong. As always, your own debugging printouts are probably useful too (just so long as these are removed/commented before submitting!). This is a bit different from errors such as in Question 57 (2013) and Question 23 (2013) — rather than returning wrong blocks, your code isn't returning any (or all).
Keywords: assess5-1314
Submission reference: IN2932
Can you please provide some useful links that can help us with the assignment. I have found nothing that explains an algorithm in enough depth that I can then attempt to turn into code and it's really starting to annoy!
I assume you've read the slide-deck (?) but am slightly concerned that you cannot find anything useful online. I just Google'd for "SSTF and FIFO" and all the hits look relevant. Also I'd expect most OS textbooks in the library to have some coverage of this and there are a lot of them. But these are not complicated algorithms (or at least they shouldn't be!) — not compared with algorithms like general graph algorithms, AVL trees or quicksort/mergesort. As a last resort, email me and arrange a time where I can go through this with you.
Keywords: assess5-1314
Submission reference: IN2931
For the assessment, when does the simulator know (or thinks it knows) when all requests have been serviced?
The simulator is what produces the requests in the first place (from a file or dynamically and continuously generated). The simulator terminates when it has got nothing left to do, at which point hopefully all blocks have been serviced! Technically, the simulator terminates once it runs out of events (around line 1115 in DiskSim.java).
Keywords: assess5-1314
Submission reference: IN2930
I don't understand how block requests are being given to the lower level code. I understand that it is to do the with private class at the top but I don't understand how the private class knows which block to process/pass. How does it do this?
It doesn't — only the DSched class knows which block to pass next. Although this code necessarily uses classes and objects, it's not object-oriented as such (operating systems [broadly speaking] are not object-oriented either). So don't think of ReadReq (the private class) as being some meaningful object-oriented object, rather it's just a convenient way of storing information about a request that needs to be serviced at some point.
See also Question 56 (2013).
Keywords: assess5-1314
Submission reference: IN2922
For the submission does our implementation have to be FIFO? OR is the objective to achieve the most efficient method using LIFO OR FIFO?
Both FIFO and LIFO are poor implementations, and what I've given you already — submitting either would clearly get you zero..! A working SSTF solution is the minimum standard, and will probably score in the range 40%-60%. There are better algorithms than SSTF for disk scheduling — speaking generally, rather than for specific workload types — and these will score higher (e.g. C-SCAN, elevator, hybrid). The best student submission(s) will score 100% and others will be scaled based on performance as appropriate (how it happens in practice will depend on the submissions plus common sense).
Keywords: assess5-1314
Submission reference: IN2919
Can you please explain how the following error occurs:
highlevel_didread(): read queue x got unexpected block XYZ
I tried looking in the "requests" text file to ensure my sorting algorithm wasn't manipulating any blocks. But I can clearly see that XYZ appears in the file.
See the answers to Question 30 (2013) and Question 23 (2013) — probably the same cause.
Keywords: assess5-1314
Referrers: Question 66 (2013)
Submission reference: IN2914
In assignment 5 there is this code:
private class ReadReq
{
int blk; /* block number */
BRequest req; /* request info */
}
Do we need to keep the BRequest or can we remove it?
Given that you need to pass it to DiskSim.disk_readblock to perform an actual read, you need to keep it! There's nothing to stop you keeping this somewhere else though; the ReadReq class here is just convenience (I would have used a struct in C, tuple in Erlang, etc. but this is Java).
Keywords: assess5-1314
Referrers: Question 63 (2013)
Submission reference: IN2913
Step one to changing the code to SSTF. Could you please explain a little more on how to achieve this? For example, do I need to use the "int DiskSim.block_to_track (int blk)" method to find the track number and so on?
The algorithm you need to implement is one that finds the block that has the shortest seek-time. As explained in various places (and as should well be common knowledge!) seek time is mostly a function of track-to-track distance. I.e. the further the read/write heads have to travel, the longer the request will take. In code, this amounts to finding the block (and request) with the closest track number to the one that was done just previously (initially zero, see Question 27 (2013)). That involves turning the block number into a track number, which block_to_track does.
Keywords: assess5-1314
Submission reference: IN2912
In the assessment how do you access block 10219000 when there are only 8388608 blocks?
You can't clearly (i.e. it's not there). However what happens here is what would typically happen in a real system: it wraps around (so you end up accessing block (10219000 modulo 8388608), give or take — the real issue is what DiskSim.block_to_track returns, which is bounded). The particular reason this is still here is because I forgot to remove those requests from the test file (or at least truncate them) when the size of the disk got changed at some point. But they shouldn't cause any harm.
Keywords: assess5-1314
Submission reference: IN2911
For the assessment how many blocks are there on the disk?
There are DiskSim.NBLOCKS blocks on the disk.
Keywords: assess5-1314
Submission reference: IN2908
In the assessment for disk scheduling, we're told not to use for-each loops yet one is already coded in? Do we specifically need to remove that and find out a different way of approaching it? Or is it just to be left?
Also, why is the modulo used when incrementing the queue head?
There is no for-each loop in the existing code! By for-each I mean things that looks like:
for (Thing i : things) {
...
}
But there's nothing wrong with using a regular for-loop, i.e. things that look like:
for (start; test; iterate) {
...
}
Keywords: assess5-1314
Submission reference: IN2905
Are you allowed to use threads in the assignment?
Nope — that would probably make things behave very strangely! (and altogether much more complex). But moreover, it's not necessary, and extremely unlikely that a real OS would use threads in such a thing (it might be sensible to have one thread per disk queue in a real OS, but as there's only one disk being considered in the assessment, threads wouldn't make sense here).
Keywords: assess5-1314
Submission reference: IN2902
For the implementation of the SSTF I have used the Math.abs function is this allowed?
No — but you can achieve the same in a single expression, e.g.: ((i < 0) ? -i : i). If you really want an abs function, just write one into the DSched class.
Keywords: assess5-1314
Submission reference: IN2895
Is the only difference between the FIFO algorithm and the SSTF algorithm the way the the next block will be selected? Can the rest be left as it is — such as readcomplete()?
Yes, but in a sense, that is the only difference between all scheduling algorithms: which block is selected next. In FIFO, it's the oldest one (so will always be at the far end of the queue). In SSTF, it's the one closest to the last. But this will need modifications to readcomplete() since it's that method which selects the "next" block for the disk to read. That is effectively ordering as you remove things from the queue, but you could order them as you put them into the queue, which would be in blockread(). One of these has to change in any event! The LIFO code represents a simpler starting point perhaps, since it doesn't need the queue (just a stack, which is a bit simpler to code).
Keywords: assess5-1314
Submission reference: IN2890
Can we assume for() loops are acceptable in the assessment?
Yes, as are while() loops, and the use of continue and break as necessary. foreach() loops are not allowed, however.
Keywords: assess5-1314
Submission reference: IN2888
For the disk scheduling assessment, can we use exceptions?
No: on the grounds that normal OS languages do not have these (i.e. C and assembler). Whilst it can make programming a bit more interesting (error checking and handling needs a bit more thought perhaps) it is realistic.
Keywords: assess5-1314
Submission reference: IN2886
Looking at the code for assignment 5, does this line:
readqueue = new ReadReq[DiskSim.MAXREQUESTS];
add all of the blocks to read to the queue?
Also, if I am to implement a Shortest Seek Time First (SSTF) algorithm, does a queue have to be used?
Not quite. This line just allocates a fixed-size array of 'ReadReq' object references, enough to hold the maximum number of requests that the system might ask for (in real systems this may be unbounded [available memory permitting] but is fixed for the purposes of this simulation — to avoid the need to write code that dynamically resizes arrays). Note, though, that this line does not allocate any 'ReadReq' objects themselves, they get allocated and placed in this array a few lines of code along.
Regardless of the algorithm implemented, your code needs somewhere to store the requests. In the code given, this is just that fixed-size array, plus head&tail pointers and a size that make it into a queue (technically, a circular buffer). You could just treat the array as a stack (like the LIFO implementation, provided, does) or use something else — up to you! The FIFO implementation uses a circular buffer because that is the simplest in this case — first in, first out. LIFO uses a stack for the same reason, last in first out. SSTF and other algorithms, that may need to re-arrange requests or supply them to the disk in a different order, might make use of something like a linked-list (which is effectively what the circular buffer provides when implemented in an array rather than a list with "next" pointers). But this assessment is not about writing mergesort or other complex algorithms! Bear in mind that the execution efficiency of your code is less important than the effect it has on the simulated performance (i.e. you could write a highly efficient disk scheduling algorithm, that performs well in all the tests, but which in itself is inefficient — to the extent of could-be-better rather than is-2+-orders-of-magnitude worse).
Keywords: assess5-1314
Submission reference: IN2887
Are we allowed to assume the number of tracks is fixed, allowing us to use DiskSim.NTRACKS?
Yes, that's fine — do use DiskSim.NTRACKS though, in case it does change (though it won't be changing at run-time!).
Keywords: assess5-1314
Submission reference: IN2885
For the assessment are you allowed to use the array clone function?
No — if you want that functionality, you'll have to write it yourself, but in this sort of situation there shouldn't be any reason why you would need to do this: copying arrays of things is expensive and isn't the sort of thing OS code would normally do.
Keywords: assess5-1314
Submission reference: IN2880
What are the block request queues?
These provide the blocks that need to be read by the disk (scheduled by your scheduler along the way). In the request files, each useful line defines a single request queue, that consists of a sequence of block numbers. The simulator will try and request several blocks from each queue simultaneously, requesting new ones as old ones are completed.
Keywords: assess5-1314
Submission reference: IN2878
What does this error mean?
highlevel_didread(): read queue 12 got unexpected block 8228500
This is probably caused by the same thing as Question 23 (2013). In this case, it means the high-level code got back a block that it wasn't expecting, possibly because it had previously requested and got it. As in the other case, errors of this kind are usually caused by queue mismanagement.
Keywords: assess5-1314
Referrers: Question 57 (2013) , Question 79 (2013) , Question 81 (2013) , Question 98 (2013)
Submission reference: IN2877
What are logical errors caused by in the assessment?
They are caused by something going wrong: the assessment description says serious errors. I.e. any errors mean your scheduler is doing something wrong (usually returning a block that was already read, or a block that was never requested). In such cases, an error message will have been emitted already stating the specific cause of the error (or at least the resulting symptom of it).
Bottom line: if your solution has errors, it is broken, and any results produced are invalid. Such submissions will probably not score highly (plus I'll have to look at them individually, which may take time).
Keywords: assess5-1314
Submission reference: IN2875
I am correct in assuming that to create a circular scan within the assessment you could sort the request queue, go through this queue, sending each block to the disk to be read, and once all blocks have been dealt with go back to the beginning of the queue and deal with blocks that have been added since the last scan?
That would mostly work, but probably not in the most efficient way. What you cannot do, however, is have a loop that sends all the requests to the disk one after another — requests to the disk to read a block have to go one at a time, and as the FIFO (and LIFO) code shows, this means the next request is dispatched when the previous one has finished (and the system calls DSched.readcomplete(...)). Back to the original point, though, if you process one queue of requests whilst building a second, you might miss the opportunity to read blocks as you pass them in the request queue, but on the other hand, such an approach might give shorter service times in general, as there'll be less in the request queue (depending on the workload).
Keywords: assess5-1314
Submission reference: IN2874
In assessment 5, where is the read-write head initially at?
Look in DiskSim.java! (but to save you searching through that, it's on track 0).
Keywords: assess5-1314
Referrers: Question 54 (2013) , Question 67 (2013)
Submission reference: IN2872
I've been doing the assessment today and have just started getting an error which I don't really understand. Could you explain what causes this error?:
...
highlevel_didread(): read queue 1 already done at time 5874032 (block 2457603)
...
highlevel_didread(): read queue 1 already done at time 5874053 (block 2433090)
...
It appears every time a block is returned from disk.
The most likely cause is returning a block more than once, which may be because that particular block is requested from the disk more than it should be. A reasonable approach is to turn on verbose operation and write a small test requests file with which you can trigger the error. Then you'll be able to see what's going on and use that to debug the problem in your code (or at least point you in the right direction).
Keywords: assess5-1314
Referrers: Question 30 (2013) , Question 57 (2013) , Question 66 (2013) , Question 76 (2013)
Submission reference: IN2859
What kind of score should we be aiming for on our disk scheduling implementation?
As best as you can get it, really! For reference, my fairly rapid (15 minutes) circular scan implementation reports 622 for requests.txt and 2330 for requests-big.txt. But the standard by which you'll be marked is yourselves, i.e. the best performing solution will get 100%, something that implements SSTF correctly will score around 50%, but the exact scaling/etc. will depend on the distribution of submissions. That is, exceptional solutions that way outperform anything else won't mean everyone else scores worse as a result!
Keywords: assess5-1314
|
Maintained by Fred Barnes, last modified Wed May 25 15:07:20 2016 |
