|
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: IN5176
Hi Fred, what is your favourite episode of Futurama?
Deferred: I've not had chance to watch everything since season 4 yet :-(.
Submission reference: IN5175
"If we want to enforce that all arrows of a free list point to the right, free(j) must fi nd two free blocks that sandwich j − 1. What if j − 1 comes after the last free block? What if j − 1 comes before the rest free block? Can you handle the latter case by initializing the array with some special blocks?" I understand that the start of a free list and the end of a free list could have some special reserved characters to denote the start and end, what is the interaction between these characters and blocks that are freed after or before a list? Thanks for your time, these questions help a lot.
I'm assuming you look at the picture with the (malloc-style) free list. Let's say head is the index of the first free block (5 in the picture). Let's give the array name A. If somebody gives us j the address of some used block that we should free, then our first task is to find the two blocks of the free list that sandwich j-1, as the problem says. We'll do this by traversing the list. Here's a first attempt:
i := head while ? i = A[i+1]
That traverses the list. But, when should we stop? Well, when the arrow points past j-1.
i := head while j-1 < A[i+1] i = A[i+1]
Now let's see special cases. Will this work when j-1 is after the last free block? If the pointer of the last free block points one past the end of the array, as it does in the picture, then yes the same pseudocode works without any modification. We don't need to do anything special. (That's why I chose the convention with point-one-past-the-end. One could choose to use null, of course.)
What about before the first block? That does't work. In particular, one issue is that we might need to update the value of the variable head. One simple solution, but which wastes a bit of space, is to simply make sure there is a free block of size 0 startting at index 0. Then we don't need head at all — it is always 0! We just need to be careful to not glue this block with what comes after, and now we can use the code from above unchanged! (Another solution is, which doesn't waste space, is given by Linus in this Ted talk. But, you'd probably need a bit more practice with C to understand his solution.)
More concretely, when you initialize the array A, you write in it 0,3,*,n-3,n, ... Here, * means any value, and n is the size of the array.
Submission reference: IN5174
Name and describe the two basic operations provided by the communication primitive commonly known as message passing.
I am confused whether or not it would be send and receive or whether it would be encapsulation and distribution?
I should be send and receive.
‘Operation’ means, here and in other contexts, something like an actual function/procedure/method you can call when you write a program. On the other hand, ‘encapsuation’ and ‘distribution’ are some abstract concepts that describe systems/programs.
Submission reference: IN5173
What is the difference between buffered and un-buffered message passing?
We didn't cover this (because un-buffered message passing is almost extinct). Come to my office (Radu) some day if you are just curious.
Submission reference: IN5172
In the caching notes, there is a question 'Explain the behaviour of the example from the section Memory Hierarchy. [Hint: Think of cache lines.]'.
I cannot find the section entitled 'Memory Heirarchy' in the cache notes, is it in another document?
It's a mistake: It should be Cache Effects.
Submission reference: IN5171
For the cache questions, how can we indicate a fault in the exam? Should we circle the chunk if its a fault(instead of writing in red), or something else? Thanks
Yes, circling is good. Alternatively, you could write an F next to it.
Submission reference: IN5170
Hi in in reference to question 104 I've done the FIFO, I was wondering if you could tell me if this is correct or if I'm completely wrong, I assume because we've ended up with the same cache content at the end I'm somewhat correct. access 1, FAULT, cache content: 1 access 6, FAULT, cache content: 1, 6 access 2, FAULT, cache content: 1, 6, 2 access 0, FAULT, cache content: 1, 6, 2, 0 access 0, cache content: 1, 6, 2, 0 access 9, FAULT, cache content: 6, 2, 0, 9 access 5, FAULT, cache content: 2, 0, 9, 5 access 3, FAULT, cache content: 0, 9, 5, 2 access 9, cache content: 0, 9, 5, 2 access 4, FAULT, cache content: 9, 5, 2, 4 access 3, FAULT, cache content: 5, 2, 4, 3 access 7, FAULT, cache content: 2, 4, 3, 7 access 9, FAULT, cache content: 4, 3, 7, 9 access 7, cache content: 4, 3, 7, 9 access 5, FAULT, cache content: 3, 7, 9, 5 access 6, FAULT, cache content: 7, 9, 5, 6 access 2, FAULT, cache content: 9, 5, 6, 2 access 7, FAULT, cache content: 5, 6, 2, 7 access 4, FAULT, cache content: 6, 2, 7, 4 access 4, cache content: 6, 2, 7, 4 Thanks.
Edit: In a previous version of the answer I said it's correct, because I missed the mistake from below.
There is a small mistake:
access 1, FAULT, cache content: 1 access 6, FAULT, cache content: 1, 6 access 2, FAULT, cache content: 1, 6, 2 access 0, FAULT, cache content: 1, 6, 2, 0 access 0, cache content: 1, 6, 2, 0 access 9, FAULT, cache content: 6, 2, 0, 9 access 5, FAULT, cache content: 2, 0, 9, 5 access 3, FAULT, cache content: 0, 9, 5, 2 <-- should be 0, 9, 5, 3 access 9, cache content: 0, 9, 5, 2 access 4, FAULT, cache content: 9, 5, 2, 4 access 3, FAULT, cache content: 5, 2, 4, 3 access 7, FAULT, cache content: 2, 4, 3, 7 access 9, FAULT, cache content: 4, 3, 7, 9 access 7, cache content: 4, 3, 7, 9 access 5, FAULT, cache content: 3, 7, 9, 5 access 6, FAULT, cache content: 7, 9, 5, 6 access 2, FAULT, cache content: 9, 5, 6, 2 access 7, FAULT, cache content: 5, 6, 2, 7 access 4, FAULT, cache content: 6, 2, 7, 4 access 4, cache content: 6, 2, 7, 4
In marking, the penalty would be small for such a mistake.
Submission reference: IN5169
So in reference to question 103; Num: IN5167. Can a thread still be reading a token while someone is writing to it (providing it is not moved). I assume yes but is it in a sense wrong for the programmer to implement it like this? Would it cause a bad reaction or would it just simply be similar to GoogleDoc where users can read/write simultaneously? e.g. T1: rdlock(data) T2: rdlock(data) T3: wrlock(data) ;; although would this one be? wrlock(data_lock) Sorry added this bit to the end, if rdlock is using data and wrlock uses data_lock will the two variables become out of sync? Maybe I am thinking of this slightly wrong.
Let's reset and try again.
Suppose L is a rw-lock. It is a variable in your program on which you can call three functions: rdlock, wrlock, unlock. Forget about reading and writing for a while. You have several threads calling these functions, and the calls may interleave in different ways; for example, depending on how threads happen to be scheduled. What you are guaranteed is that certain interleavings are possible while others are not.
This is allowed:
rdlock rdlock unlock rdlock rdlock unlock unlock unlock wrlock unlock rdlock
This is disallowed:
rdlock rdlock unlock wrlock unlock unlock
Why? We can add two counters, R and W, next to the lists from above. For each rdlock, we do ++R; for each wrlock, we do ++W; for each unlock, we do "if (W>0) --W; else --R;". Let's see what happens:
R W
0 0
rdlock 1 0
rdlock 2 0
unlock 1 0
rdlock 2 0
rdlock 3 0
unlock 2 0
unlock 1 0
unlock 0 0
wrlock 0 1
unlock 0 0
rdlock 1 0
This sequence is allowed because at every oint we have (a) R is nonnegative, (b) W is 0 or 1, and (c) if W=1 then R=0. Let's see the other sequence:
R W
0 0
rdlock 1 0
rdlock 2 0
unlock 1 0
wrlock 1 1 <--- BAD
unlock 1 0
unlock 0 0
This is not allowed because condition (c) is broken: R and W are both positive at the same time.
So, to recap: When you have multiple threads, their executions can interleaved in many ways. A rw-lock makes sure that some interleavings are ruled out. That's all. From the point of view of the rw-lock there is no reading or writing happening. Why is it called a readers-writer lock then? Because of what it is used for. The easiest way to understand what it is used for is to look at an example.
Suppose we have
list_t xs; // this is pseudocode, not C code
We want to protect this variable with a readers-writer lock.
rwlock xs_lock;
"Writers" do this:
wrlock(xs_lock); xs.append(some_data); unlock(xs_lock);
"Readers" do this:
rdlock(xs_lock);
foreach x in xs {
print x
}
unlock(xs_lock);
Using the rw-rules from the beginning, we can see that we could have multiple threads iterating over the list at the same time. But, we cannot have someone modifying the list while someone is iterating over it. Nor can we have two threads modifying the list at the same time.
Submission reference: IN5158
Hi Fred, I was wondering about type 1 Hypervisor and type 2 Hypervisor. Am I right that type 1 is basically the hypervisor handles the kernel mode instructions, and has 'multiple copies' of the hardware which can run different OSs independently from each other. And type 2 is where you have an OS and then many virtual machines inside of that (like in vmware)?
Also, if I understand right would Xen virtualisation be an example of the type 1 and Linux as a host OS with VMWare running inside be the type 2?
Is virtualisation type 1 and emulation type 2?
Your first view of type 1+2 hypervisors is correct, i.e. Xen is type 1 and VMware/kvm/virtual-box are type 2. But type 1 vs. type 2 isn't terminology I've ever used I don't think: they're just different ways of achieving the same goal fundamentally (i.e. running multiple OSs). Emulation is a software-only thing, but you can use it to run multiple OSs, albeit inefficiently compared to virtualisation. Emulation has the advantage it can simulate other hardware and software, whereas virtualisation can't (you're limited to the same underlying hardware pretty much, since the software under virtualisation will mostly be running natively on the CPU).
Submission reference: IN5164
Might be a bit of a stupid question, but in reference to question 1)a) in the 2013/14 mock paper, are the input values for r16 and r17 (99 and 85) in hexadecimal or decimal?
They'll be in decimal (base 10). If they were in hexadecimal you'd see them written as per most programming languages with a leading "0x" (e.g. "0x99").
Submission reference: IN5161
Where on the AVR-like device are the instructions stored? For example, how does the processor know what to do if you used the 'add' command?
The instructions themselves are stored in the instruction memory. On the AVR, this is the FLASH (generally read-only when the device is in normal operation, but (re-)programmable offline or by the bootloader that's included for the Arduino.
The bit of the processor that decides that whether something is an "add" or "ldi", etc. instruction, and how to deal with it, is the control unit (which it does as part of the instruction decode, driving control signals to other functional units such as the ALU, register-file, etc.). Fundamentally this is (more or less) a pattern matching process, so the typical control unit might be little more than comparators.
Submission reference: IN5168
Hi after reading the caching notes I think I understand how to do the hand FIFO and LRU but I was wondering if you could do a run through of the question you've given us: Consider a cache with 4 lines and the reference string 16200953943797562744. Simulate the FIFO replacement algorithm by hand. Simulate the LRU replacement algorithm by hand. Thanks
I'll do the LRU one. For the FIFO one, please show me what you tried first, in a different question. I will then confirm or correct.
cache initially empty access 1, FAULT, cache content: 1 access 6, FAULT, cache content: 1 6 access 2, FAULT, cache content: 1 6 2 access 0, FAULT, cache content: 1 6 2 0 access 0, cache content: 1 6 2 0 access 9, FAULT, cache content: 6 2 0 9 access 5, FAULT, cache content: 2 0 9 5 access 3, FAULT, cache content: 0 9 5 3 access 9, cache content: 0 5 3 9 access 4, FAULT, cache content: 5 3 9 4 access 3, cache content: 5 9 4 3 access 7, FAULT, cache content: 9 4 3 7 access 9, cache content: 4 3 7 9 access 7, cache content: 4 3 9 7 access 5, FAULT, cache content: 3 9 7 5 access 6, FAULT, cache content: 9 7 5 6 access 2, FAULT, cache content: 7 5 6 2 access 7, cache content: 5 6 2 7 access 4, FAULT, cache content: 6 2 7 4 access 4, cache content: 6 2 7 4 Total number of faults: 13
You may prefer to use the notation from the lecture notes; it's more difficult to use it here in HTML.
Also, note that the programs Fifo.java and Lru.java, which you can find on Moodle, solve such problems.
Submission reference: IN5167
Readers-writers lock specifies that rdlock allows multiple threads to 'touch' (access) the token however it can't be moved. It doesn't say whether it can be modified, I assume that rdlock is only for reading and wrlock is for writing. Can you confirm this for me please? Thanks
Yes, but it is not enforced.
Here's what I mean. In the mutex example there are two variables: counter and counter_mutex. You are supposed to use the counter only while holding the mutex, but the compiler won't tell you if you break this rule (nor the runtime, nor anyone else). In fact, this kind of rule (the correspondence between counter and counter_mutex) needs to be documented, usually in comments. If you do break the rule, most often you'd observe intermittent weird behaviour.
For readers-writer lock, the story is similar. There will typically be a pair of variables, data and data_lock. You are supposed to use the lock using one of the following patterns:
rdlock(data_lock); ... read from data ... unlock(data_lock);
or
wrlock(data_lock); ... write to data; or read from data (***) ... unlock(data_lock);
Nobody checks if you do it correctly.
What is enforced by the runtime are properties like these: the statements bracketed by wrlock(data_lock) and unlock(data_lock) (for example, *** from above) will NOT run at the same time with similar statements from a different thread. In the analogy with the token, you are guaranteed that only one person has the token, but you are not guaranteed that persons not holding the token will behave properly and not write where they're not supposed to write. It is the programmer's responsibility to check that this is so.
Submission reference: IN5162
Can you please show the working of this question? Consider a 64b system, on which integers and addresses take 8 bytes. The memory has 10^9 bytes and is managed using one singly-linked free list, using the first-fit policy. The statement malloc(1), which allocates 1 BYTE, is called 10^6 times. What is the fragmentation? Thanks
To understand this answer you need to have read the notes on dynamic memory.
Initially, the memory is empty:
................................................
Each call to malloc will allocate 8 bytes that hold an integer, which represents the size of the allocated block, plus the 1 byte requested by the user. (Recall that the integer is needed for implementing free.) So, after the first malloc, the memory looks like this:
111111111.......................................The first 9 bytes are now in use, because of the first call to malloc. After four more calls, the memory looks as follows:
111111111222222222333333333444444444555555555...
So, by this time the user requested 5 bytes (with 5 calls to malloc), and 45 of the leftmost (low addresses) bytes are in allocated.
What is the external fragmentation? Recall the definition:
biggest available block
external fragmentation = 1 - -----------------------
total free memory
In our case, there is only one available block: everything that comes after the first 45 allocated bytes. So, the biggest available block is equal to the total free memory, which means that the external fragmentation is 0.
What about the internal fragmentation?
allocated memory
internal fragmentation = ------------------ - 1
requested memory
The allocated memory is 45 bytes, the requested memory is 5 bytes. So, internal fragmentation is 8. Another way of writing the number 8 is 800%.
Note that the number of calls to malloc is irrelevant. (Try the problem with, say, six calls instead of five as I did here.) Also, the total size of the memory is irrelevant. All that was important is how many bytes are occupied by an integer.
The above is a mouthful, to explain in detail what happens. You'd only need to write something much shorter. For example: Since there is no call to free, there is only one free block, and so the external fragmentation is 0. Since for each requested byte we also need 8 extra bytes for an integer (to recall the allocated size), we have internal fragmentation (8+1)/1-1=8.
Submission reference: IN5166
Could you explain the difference in jmp and rjmp? If I understand them in a way, one of them can jump to further lines of code than the other but why bother having two?
"rjmp" is relative jump, so can jump forwards or backwards a certain number of instructions. The other "jmp" is absolute jump, so can jump anywhere in the 16-bit address space. The reason for having both is, as covered in one lecture, is that "jmp" requires two instruction words (32-bits) whereas "rjmp" requires just one. Thus, "rjmp" where it can be used is more efficient, both in terms of code space occupied (FLASH is a limited resource) and in cycles required to execute it.
Submission reference: IN5165
In regards to some of the lecture notes on radu's part of the course, some parts are notated with a * such as garbage collection, what exactly is the * in reference to? Thank you!
It means optional / not in exam. (This is mentioned in the first pdf with lecture notes.)
Submission reference: IN5159
Can we please take your AVR Assembly Quick Reference sheet into the exam?
You say that this is not a cramming memory test, but really we haven't been tested enough through the year to have 'understood' everything on that sheet, for some of us, it might as well be in French, where we occasionally recognise 'Bonjour' and 'Ca va bien'.
At the moment for the majority of students it is a complete cramming game because we have to understand several terms of syntax that we have come across less than 5 times in assessments or simply have never implemented or seen before - let alone understood it.
Unfortunately no. But it wouldn't be that helpful anyway. As I've said, I don't expect people to remember what the mnemonics are — as per past questions, these would be explained in the question.
The issue of understanding verses exposure is not a well formed argument. I spent around 5 lectures going through chunks of assembly programs, plus the practical session, but more than this, you are expected to do reading outside of these to build knowledge and understanding. These are things I said at the start of the module: unfortunately, if you didn't do these things, you are potentially at a disadvantage :-(.
My broad feeling is that people lack appropriate study skills and, to some extent perhaps, a lack of engagement with the module (lecture and class attendance for various modules points towards this, particularly at the end of term). Whilst things like the placement of Easter are unavoidable given the University's term structure, that's not a valid reason for missing things. Nor are reasons such as "I don't like Fred's lectures" — that may well be the case (sorry!) and I cannot cater for all learning styles, but again, not a valid reason for non-attendance.
Back to the point, though, whether a program is written in assembler, C, Java, JavaScript, PHP, Python, etc. the fundamental principles are the same (i.e. procedural programming). You should have sufficient understanding of programming to be able to take concepts from one aspect of the degree (e.g. a loop in Java from CO320/CO520, or algorithmic aspects from CO518) and translate these into other languages, or at least be able to see and appreciate the equivalence between the same construct in different languages. I don't expect people to be excellent assembly programmers (that's not what this module is testing), but I do expect people to be competent programmers in general, so when I show bits of assembly programming, the focus is on the low-level interactions with the machine (add registers, move register to memory, etc.) and not a confusion about the fundamental structure of the code. From having looked at a lot of the systems programming submissions, it's very clear that the general coding ability and general understanding of code, for the group as a whole, is weak (that's a very general statement though). Unfortunately I don't see it as CO527's responsibility to address that particular issue, as it is pre-requisite, but the fact these issues do exist is a problem generally. In the individual feedback (for the 60+ students who got this) I tried to focus on understanding code, thinking about programming and that sort of stuff (as well as how to write SSTF/C-SCAN/etc.). To become a good programmer, you need to write code, outside of assessments and classes: programming should be something you do in your free time for fun! (flippant thought: if you don't enjoy programming, why do CS..?). Programming is like painting or cooking — a fundamentally creative act. It's not something that can be taught outright, it has to be learned, but if you don't take any pleasure in it, becoming successful will be difficult (as it would be for painting or cooking).
Submission reference: IN5163
I was going through what you covered yesterday on bitmaps and free lists however I am struggling with conversion of file sizes from GiB to MiB or GiB to MB and so on. Is there any advice, tutorials or similar that you could give? Everything I try to search just gives me a calculator but it doesn't specify easy ways to calculate it by hand.
If you go to the Wikipedia page for kilobyte, you can see a nice table in the top-right.
1 B = 1 byte = 8b = 8 bits = 2^3 bits 1KiB = 2^10 B 1MiB = 2^20 B 1GiB = 2^30 B
Often it's useful to remember that 2^a * 2^b = 2^(a+b) and 2^a / 2^b = 2^(a-b). Also, (a^b)^c = a^(b*c).
Submission reference: IN5160
In regards to the question 'Consider a file system with total size
16GiB, and blocks of 1KiB. It tracks free space using the free list method.
How many block addresses fit in one block?'.
Is this working right? I think I'm going wrong on calculating the number of
bits to hold an address...
1) Disk size = 16GB = 2^30 * 16 = 2^34 bytes
2) Block size = 1KiB = 2^10 bytes
3) No. Addresses = Disk Size / Block Size = 2^34/2^10 = 2^24 blocks
So there are 2^24 addresses? Does this mean I need 24 bits per address?
4) Block size in bits / address size in bits = (2^10 * 8)/24
= (2^10 * 2^3)/24
= (2^13)/24
= 314.333rec
= 314 addresses per block
So there can be 314 addresses per block, minus one for a pointer?
Thankyou
Yes, that's perfect. Good job!
Update: Actually, there is a tiny mistake in the last step. (2^13)/24 is 341.333, not 314.333.
Submission reference: IN5157
"How many bits are in a block? 8*1024=8192.
How many blocks are in the bitmap? k.
How many bits do we have in the bitmap? 8192*k.
How many data blocks are there? 10^6-k.
Do we have enough bits in the bitmap? Yes, iff 8192k ≥ 10^6-k.
What does that mean in terms of k? k ≥ 10^6/8193 ≈ 122.06
So, the answer is 123."
In this previous Q/A. Why is 1 added to the 8192 for the division and 1
added to the 122.06 ?
Also for Q6 of file implementation. I have tried this:
So 16 Gib total size and 1KiB block sizes.
Converted into bits. (16.(1024.1024.1024)) = 17179869184
log(17179869184) / log(2) = 2^34 bits
1kib = 1024 bits
2^10 / 34 = 30 ?
Why is 1 added to the 8192 for the division [...]
8192*k ≥ 10^6-k
{ add k on both sides }
8192*k+k ≥ 10^6-k+k
{ distributivity, compute }
8193*k ≥ 10^6
{ divide by 8193 on both sides }
k ≥ 10^6/8193
Why is [...] 1 added to the 122.06 ?
We know that k is a number of blocks, and hence an integer. We know that k is at least 122.06. We are looking for the smallest possible k. What is the smallest integer that is at least 122.06?
Also for Q6 of file implementation. I have tried this:
So 16 Gib total size and 1KiB block sizes.
Converted into bits. (16.(1024.1024.1024)) = 17179869184
That's bytes not bits. In general, GiX = 2^30 X, for all units X. Above, X is bytes.
log(17179869184) / log(2) = 2^34 bits
You need one address for each block, not for each byte. So, first you want to find how many blocks are in the file system. There are 2^34 bytes in total (16GiB), and 2^10 bytes fit in a block (1KiB), so there are 2^34/2^10=2^24 blocks. Thus, you need 24 bits.
1kib = 1024 bits
2^10 / 34 = 30 ?
1KiB is 1024 BYTES, not bits. Uppercase B means bytes; lowercase b means bits. There are 8 bits in each byte. So a block's size is 1KiB=2^10B=2^10*2^3b=2^13b. So, 2^13 bits in one blocks, and 24 bits for one address. We have 2^13/24=341.33. We round this down -- we can't use 0.33 of an address. So, 341 addresses fit in one block.
One may also add that one of those 341 addresses will be reserved for the NEXT pointer of the free (block) list.
|
Maintained by Fred Barnes, last modified Wed May 25 15:07:19 2016 |
