|
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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: IN2146
Is it better to run a database as an application on top of an existing operating-system, or to have a dedicated transaction-processing system?
It depends entirely on the circumstances. Generally the former, since this is easier, but suffers the potential for other things to get in the way. Dedicated systems will likely have more predictable performance, but are inherently less maintainable.
Submission reference: IN2147
I have a question regarding Branch instructions. If I have a branch if not equal to instruction located at 0x00002000 (PC) and the following:
RS(Register 4) = 0
RT(Register 3) = 7
Therefore branch does not equal and should then follow the following equation:
if (rs!=rt) goto (PC+offset)
The PC is 0x00002000 and the offset is 0000000000001000.
What I have done is converted the offset to 32 bits which will just have an extra 16 0's to the left but I have no idea how to add the two and the lecture slides aren't particularly clear or give examples on how to do this... So I was just wondering how I could do this to get the new PC? Any help is much appreciated, Thanks!
The logic of what happens when the branch is taken isn't quite right. As Winston showed in the revision session earlier, you can reverse engineer what the new PC is based on the MIPS datapath diagram. Specifically, a constant 4 is always added to the PC, and the offset is always shifted-left 2 (to multiply by 4). So the equation you should be thinking about is:
new_pc = old_pc + 4 + (offset * 4)
But that's just simple arithmetic! The problem you're encountering is because the offset is expressed in binary (base-2) whereas the PC and register contents are expressed in hexadecimal (base-16). Converting between the two should be something you practiced well at stage 1. Once you've got the sign-extended offset in hexadecimal, the addition is trivial. You could convert everything to decimal (base-10), feed it into a calculator, and convert the answer back into hexadecimal, but that's particularly time consuming. On paper, the calculation would look something like:
old PC = 0x00002000 +
0x00000004 + (constant always added to PC, from MIPS datapath diagram)
[4 * 0x00000008] (offset 0000000000001000b sign-extended)
[ == 0x00000020] (shift-left 2 gives 0000000000100000b)
----------
0x00002024 (new PC)
Keywords: architecture
Submission reference: IN2148
From a past exam: "Why are the three main components of the system nucleus together?".
Apart from them all being critical sections of code that and allowing other parts such as a file system to be built on top of the system, why are they together?
Your answer covers one point, more or less (keep critical code together). However, the key point is that these things need to interact with each other frequently, and that all three are needed (can't remove one without having something mostly useless).
Keywords: kernel
Submission reference: IN2149
I am really confused about the questions relating to scheduling in the 2011 past paper (question 1(g)) and the 2009 past paper (question 2(c)). Any suggestions?
The first thing to do is understand what the diagram is telling you. Specifically, these are traces for some user processes (P1, etc.) the OS and others (FLIH and idle-task). As you should know from the lectures, processes exist in one of several states (runnable, running, blocked). This is what the diagrams are showing, with the state names replaced with "A", "B", etc.
The first part of both questions asks what states are represented by the various letters. To make this possible, some additional information is given, e.g. from the 2011 paper "The events at times "t2", "t4" and "t6" are timer interrupts causing time-slicing context switches.". As can be seen in the diagram, at time "t2" process "P1" changes from state "A" to state "B", with some execution by the FLIH and OS inbetween. Similar occurs at times "t4" and "t6" too. From this, it's reasonable to assume that state "A" is running and state "B" is runnable. That leaves "C" to be blocked (which would make sense). Once you've figured that out, the rest of the question becomes simpler.
For the 2011 paper, part (ii) of the question asks how many processor cores there are. If state "A" is running, then there are at least as many processor cores as processes in this state at any given time (i.e. a certain number of processes are running simultaneously). If you scan through the diagram you'll see that this is 2. Thus, there are two processors.
Part (iii) of that question in the 2011 paper asks "Assuming that at time "t1" a request is made by P3 to read a packet from the network, what occurs at time "t3" (or is likely to have occurred) and why?". Given what you know about process states (and what's said in this part of the question may help in answering the first part), "P3" transitions from running to blocked (presumably whilst it waits for the packet). At "t3", whatever happens causes "P3" to transition from blocked to runnable. Based on that, it's reasonable to infer that the event was probably a packet being received for that particular process, or an error (basically, something that causes "P3" to finish waiting for the packet and continue execution).
Keywords: scheduling
|
Maintained by Fred Barnes, last modified Wed May 25 15:07:20 2016 |
