CS-537: Midterm Exam (Fall 2008)

Hard Questions, Simple Answers

Please Read All Questions Carefully!

There are seven (7) total numbered pages.

Please put your NAME and student ID on THIS page, and JUST YOUR student ID (but NOT YOUR NAME)
on every other page. Why are you doing this? So I can grade the exam anonymously. So, particularly important if
you think I have something against you! But of course, I don’t. I really do want all of you to do well. Really! OK,
most of you.

Name and Student ID:

1
 Grading Page

Points Total Possible

Q1 25

Q2 25

Q3 25

Q4 25

Total 100

2
1. Bit by Bit. Assume you have a small virtual address space of size 64 KB. Further assume that this is a system
that uses paging and that each page is of size 8 KB.

(a) How many bits are in a virtual address in this system?

16 (1-KB of address space needs 10 bits, and 64 needs 6; thus 16).
(b) Recall that with paging, a virtual address is usually split into two components: a virtual page number
(VPN) and an offset. How many bits are in the VPN?
3. Only eight 8-KB pages in a 64-KB address space.
(c) How many bits are in the offset?
16 (VA) - 3 (VPN) = 3.
(d) Now assume that the OS is using a linear page table, as discussed in class. How many entries does this
linear page table contain?
One entry per virtual page. Thus, 8.

Now assume you again have a small virtual address space of size 64 KB, that the system again uses paging, but
that each page is of size 4 bytes (note: not KB!).

(a) How many bits are in a virtual address in this system?

Still 16. The address space is the same size.
(b) How many bits are in the VPN?
14.
(c) How many bits are in the offset?
Just 2 (4 bytes).
(d) Again assume that the OS is using a linear page table. How many entries does this linear page table
contain?
214 , or 16,384.

Finally, the OS tracks the linear page table for a process by remembering it’s base address, which we will
assume for this problem to be the address where the page table is located in kernel physical memory. Given the
address of the start of the page table (pt base), and a VPN that you wish to translate into a PPN (physical page
number), write some code to that calculates a pointer to the right page table entry (pte) for this VPN and
returns it to the caller:

struct pte *p
find_pte(void *pt_base, int VPN)
{
struct pte *p = ???
return p;
}

(a) Write your code here:

This would work, because pt base is a void pointer and we need to add the right number of bytes to get us to the
page specified by the VPN:

struct pte *p = pt_base + (VPN * sizeof(struct pte));

This would also work; by first casting the base as a ’struct pte’, adding VPN to it achieves the same as the code
above, and thus points us to the VPN’th entry in the array of page table entries.

struct pte *p = (struct pte *)pt_base + VPN;

3
2. Scheduling with Uncertainty.
Assume we have three jobs that enter a system and need to be scheduled. The first job that enters is called A,
and it needs 10 seconds of CPU time. The second, which arrives just after A, is called B, and it needs 15 seconds
of CPU time. The third, C, arrives just after B, and needs 10 seconds of CPU time.
For all questions involving round-robin, assume that there is no cost to context switching. Also assume that if
job X arrives just before Y, a round-robin scheduler will schedule X before Y.

(a) Assuming a shortest-job-first (SJF) policy, at what time does B finish?

Order of completion: A, C, B. B finishes last, after 35 seconds.
(b) Assuming a longest-job-first (LJF) policy, at what time does B finish?
B, A, C. B finishes first, after 15 seconds.
(c) Assuming a round-robin policy (with a time slice length of 1 second), when does job A finish?
A needs to run ten times to finish (10 seconds @ 1 second/slice).
ABC ABC ABC ABC ABC ABC ABC ABC ABC ABC
012 345 678 901 234 567 890 123 456 789
11 111 111 112 222 222 222
The first A starts at 0 and ends at 1. Then starts at 3 and ends at 4. Then 6 to 7, 9-10, 12-13, 15-16, 18-19,
21-22, 24-25, and finally, starts at 27 and completes its last time slice at 28. Thus, 28.
(d) Assuming a round-robin policy (with a time-slice length of 1 second), when does job B finish?
This is easy. B runs the longest and thus finishes last. We know the total time for all workloads is 35.
Thus, B finishes at 35.
(e) Assuming a round-robin policy (with an unknown time-slice which is some value less than or equal to
2 seconds), when does job B finish?
With any small time slice, B finishes last again, and thus at 35 again.
(f) Assuming a round-robin policy (with an unknown time-slice), for what values of the time-slice will B
finish before C?
There are two interesting cases. When the time slice is greater than or equal to 15, B will finish in its first
time slice and thus finish before C. The other case arises when the time slice is greater than or equal to 7.5
seconds but less than 10 seconds. In this case, B will finish in two slices (as will C), but B will finish first.

Of course, SJF is unrealistic, because usually the OS doesn’t know how long jobs are. In this system, though,
the user gives the OS an estimate. The problem is that the users aren’t so good at estimation. In fact, if they tell
you a job will last N seconds, it might last anywhere between N − 5 and N + 5 seconds. But, being a nice,
trusting OS, the OS assumes the user is exactly right.

(a) Assuming SJF, what estimates (by the user) will lead the OS to make the worst decisions for these jobs in
terms of achieving the lowest average response time?
Anything that makes B run first. Thus, anything estimate when A’s and C’s estimates are each X and B’s
estimate is Y and X > Y . This is possible because the estimates can only be off by 5 seconds in either
direction but the run times of B, (A,C) are only 5 seconds apart.

|-------------A--------------|
|-------------C--------------|
|--------------B--------------|

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
(b) In this case, what will the average response time of each job (oops: ALL JOBS) be?
B’s response time will be 0 (it ran first). A’s would be 15 (after B finishes), and C’s would be 25 (after A
finishes). Thus, (0 + 15 + 25)/3, or 13 31 .

4
(c) What would the average response time of each job (oops: ALL JOBS) be if you instead had used LJF?
If we used LJF with our mis-estimates, C would run (0), then A (10), and then B (20). Thus 30/3 = 10.
(d) Assume we can arbitrarily change the run-time of job B. What should the run-time of B be changed to so
that SJF delivers the best average response time to jobs A, B, and C, even if there are bad estimates?
This was accidentally a trick question, and the trick answer is 0. What I meant was: how far apart do the
run-times of A, B, and C have to be for the mis-estimation not to matter? The answer to that would be
10 seconds apart, because the worst mis-estimate is 5 seconds in one direction and 5 seconds in the other.
Sorry about that!

5
3. Translation station.
Assume a 32-bit virtual address space and further assume that we are using paging. Also assume that the virtual
address is chopped into a 20-bit virtual page number (VPN) and a 12-bit offset.
The TLB has the following contents in each entry: a 20-bit VPN, a 20-bit PPN, and an 8-bit PID field. This
TLB only has four entries, and they look like this:

VPN PPN PID

00000 00FFF 00
00000 00AAB 01
00010 F000A 00
010FF 00ABC 01

Note all these numbers are in hex. Thus, each represents four bits (e.g., hex “F” is “1111”, hex “A” is “1010”,
hex “7” is “0111”, and so forth). That is why the 20-bit VPN and PPN are represented by five hex numbers
each.
Now, for each of the following virtual address, say whether we have a TLB hit or a TLB miss. IMPORTANT:
If it is a hit, provide the resulting physical address (in hex). Note: unless said otherwise, virtual addresses
are also in hex.

(a) PID 00 generates the virtual address: 00000000

The first five hex numbers are the VPN (0x00000); the last three are the offset (0x000). Thus, we check if
00000 is in the table for PID 00.
hit. page 00000 is in table for PID 00; translates to 00FFF000. (use the PPN and old offset to get the
physical address).
(b) PID 01 generates the virtual address: 00000000
hit. page 00000 is in table for PID 01; translates to 00AAB000.
(c) PID 00 generates the virtual address: FF00FFAA
miss. no page FF00F in table.
(d) PID 00 generates the virtual address: 0010FFAA
miss. no page 0010F in table.
(e) PID 01 generates the virtual address: 0010FFAA
miss. no page 0010F in table.
(f) PID 00 generates the virtual address: 000000FF
hit. page 00000 is in table for PID 00; translates to 00FFF0FF.
(g) PID 01 generates the virtual address: 00000FAB
hit. page 00000 is in table for PID 01; translates to 00AABFAB.
(h) PID 00 generates the virtual address: 010FFFFF
miss. no page 010FF in table for PID 00.
(i) PID 01 generates the binary virtual address 00000001000011111111010100001111
binary 00000001000011111111010100001111 becomes 0000 0001 0000 1111 1111 0101 0000 1111 be-
comes hex 010FF50F.
hit. page 010FF is in table for PID 01; translates to 00ABC50F.
(j) PID 00 generates the binary virtual address 00000001000011111111010100001111
binary 00000001000011111111010100001111 becomes 0000 0001 0000 1111 1111 0101 0000 1111 be-
comes hex 010FF50F.
miss. no page 0x010FF for PID 00 in TLB.
(k) PID 02 generates the virtual address: 00000000
miss. no PID 02 entries in table.

6
4. A Simple File System. In this question, we are going to unearth the data and metadata from a very simple file
system. The disk this file system is on has a fixed block size of 16 bytes (pretty small!) and there are only 20
blocks overall. A picture of this disk and the contents of each block is shown on the next page.
The disk is formatted with a very simple file system, which looks a lot like that old Unix file system we have
talked about in class. Specifically, the first block is a super block, the next 9 blocks each contain a single inode,
and the final 10 blocks are data.
The super block (block 0) has just four integers in it: 0, 1, 2, and 3, in that order.
The root inode of this file system is in inode number 2 (at block 3 in the diagram).
The format of an inode is also quite simple:

type: 0 means regular file, 1 means directory

size: number of blocks in file (can be 0, 1, or 2)
direct pointer: pointer to first block of file (if there is one)
direct pointer: pointer to second block of file (if there is one)

(assume that each of these fields takes up 4 bytes of a block)

Finally, the format of a directory is also quite simple:

name of file
inode number of file
name of next file
inode number of next file

(again assume that each field takes up 4 bytes of a block)

Finally, assume that in all cases, no blocks are cached in memory. Thus, you always have to read from this disk
all the blocks you need to satisfy a particular request. Also assume you never have to read the super block (just
to make your life easier).
That’s it! Well, not quite; now you have to answer some questions:

(a) To read the contents of the root directory, which blocks do you need to read?
The root directory is called “/” and its inode (inode number 2) is the block numbered 3. Thus, Block 3 (the
root inode) must be read. Inside, it points to block 14 (the contents of the root inode). Thus, block 14 must
be read.
(b) Which files and directories are in the root directory? List the names of each file/directory as well as its
type (e.g., file or directory).
In /, there are two directories: “a” and “b”.
(c) Starting at the root, what are all the reachable regular files in this file system?
In directory “a”, there are two files, “foo” and “bar”.
In directory “b”, there are two files, “cs” and “537”.
(d) What are all the reachable directories?
There are just three: “/”, “/a”, and “/b”.
(e) What is the biggest file in the file system?
It is “bar”, which contains 2 blocks.
(f) What are the contents of the biggest file?
7 8 9 10 hi 10 you 12
(g) What blocks are free in this file system? (that is, which inodes/data blocks are not in use?)
inodes 5 and 8 (in blocks 6 and 9) are not in use.
data blocks 16 and 17 are not in use.

7
 S
H I N T : I N O D E

H I N T : H I N T :

S U P
E R R O O T

B L O C K I N O D E

0 1 1 1 0 0 0 0 0 1

2 2
1 1 1 1 1 1 1 1

2 2 3
1 0 1 8 1 4 1 1 1 1 5 1 9 0

3 3
0 0 0 1 7 1 0 0 0 8

B l o c k 0 B l o c k 1 B l o c k 2 B l o c k 3 B l o c k 4 B l o c k 5 B l o c k 6 B l o c k 7 B l o c k 8 B l o c k 9

f o o
h i a i
3
7 1 0 1 1 0

c s

o o u v
b a r l
3 6
4 8 1 0 0 0

o u o o f
b a r b
3
5 9 1 1 5 7 0

c s
y

o o
d a
6 2 3
4 1 0 1 1 5 7 7 0

B l o c k 1 0 B l o c k 1 1 B l o c k 1 2 B l o c k 1 3 B l o c k 1 4 B l o c k 1 5 B l o c k 1 6 B l o c k 1 7 B l o c k 1 8 B l o c k 1 9