Name: NetID: P a g e 1 |
CS3224 Final
Intro to Operating Systems
Prof. G. Sandoval
Dec 19, 2020
Question Points Score
1 40
2 30
3 10
4 10
5 10
Extra
credits
10
Total 110
Name: NetID: P a g e 2 |
Exam Rules:
– The exam must represent your work alone. You may not misrepresent someone else’s work as
yours. You may not submit work of which you are not the sole author.
– While working on the exam you may not communicate with any other student for any reason.
This prohibition includes the use of electronic communication, such as email, texting and phone.
As an exception to this rule, if you have questions during the exam, you may ask the instructors
or TAs. You may not discuss the content of the exam with other students. You may not ask
questions on piazza. Email TA’s or the professor directly.
– Do not copy or distribute the exam document or your answers at any time. After you have
finished and have pushed your exam to Github, delete the exam and your answers from your
computer.
– If we suspect any academic dishonesty, the professor will make a Zoom appointment with you
right after the exam. You will need to support your answers.
Upon completion of the exam, fill in this pledge of academic honesty in the exam.txt file:
I,
with other classmates. I have followed the required rules. I understand that violating these rules
would represent academic dishonesty.
Name: NetID: P a g e 3 |
Part 0: Setup
Your exam is available on Anubis under the assignments tab. Click on the “Create Assignment Repo”
button to create your repository, and then the “Launch Anubis Cloud IDE” button to get started with the
IDE.
There is a file called exam.txt where you should record all your written responses (questions 4 through
6) along with your honesty pledge.
Note:
– You will need to create new files for this assignment.
– Do not modify the Makefile.
Name: NetID: P a g e 4 |
QUESTION 1: (60 points) XV6.
Part A: Use the debugger
Follow the instructions on how to debug XV6 from here. Submit a screenshot of your debugger
(gdb or the vscode debugger will be accepted) in a file called partA.png or partA.jpg. If you are
using the class VM, or Vital, make sure your screenshot takes up the entire VM window not just
the terminal.
Now we will set a breakpoint in the system call that allocates memory. The call that
user-processes use in xv6 to allocate memory is called ̀sbrk()`; it’s kernel-mode
implementation is ̀sys_sbrk()` in `sysproc.c`. Set a breakpoint on the first line inside this
function. Then answer the following questions when you submit your patch:
1. Run a user process like: ‘ls’
2. What is the value of `n` when your breakpoint gets hit?
2. Print out the stackframe (backtrace) for this call.
Part B: Removing Eager Allocation
Change ̀sys_sbrk() ̀ so that it just adjusts ̀proc->sz` and returns the old ̀proc->sz` (i.e.,
remove the call to ̀growproc()`).
After rebuilding xv6, try running a command like `echo hello`:
init: starting sh
$ echo hello
pid 3 sh: trap 14 err 6 on cpu 0 eip 0x12bb addr 0x4004–kill proc
What went wrong, and why? (Answering this question is not part of the assignment, just think
about it).
Part C: Implementing Lazy Allocation
The message above comes from the ̀trap()` function in `trap.c`. It indicates that an exception
(number 14, which corresponds to a page fault on x86) was raised by the CPU; it happened
when `eip` (the program counter) was `0x12bb`, and the faulting address was `0x4004`. It then
kills the process by setting `proc->killed` to 1. Can you find in the code in trap.c where that
happened? (Answering this question is not part of the assignment either, just getting you
familiar with the code)
https://piazza.com/redirect/s3?bucket=uploads&prefix=attach%2Fk5wsd9vc9x81es%2Fj7bbqdaa3213zs%2Fk6mf885d1f54%2Fhowtodebugxv6.pdf
Name: NetID: P a g e 5 |
Add code to ̀trap()` to recognize this particular exception and allocate and map the page
on-demand.
Once you have implemented the allocation, try running `echo hello` again. It should work
normally.
**Hints**:
1. The constant `T_PGFLT`, defined in `traps.h`, corresponds to the exception number for a
page fault.
2. The virtual address of the address that triggered the fault is available in the `cr2` register; xv6
provides the `rcr2()` function to read its value.
3. Look at the code in `allocuvm()` to see how to allocate a page of memory and map it to a
specific user address.
4. Remember that the first access might be in the middle of the page, and so you’ll have to
round down to the nearest PGSIZE bytes. xv6 has a handy function called `PGROUNDDOWN`
you can use for this.
5. You will need to use the `mappages()` function, which is declared as `static`, meaning it can’t
be seen from other C files. You’ll need to make it non-static, and then add its
[prototype](https://en.wikipedia.org/wiki/Function_prototype) to some header file that is included
by both `trap.c` and `vm.c` (`defs.h` is a good choice).
Part D: Handling Some Edge Cases
Although simple commands like `echo` work now, there are still some things that are broken.
For example, try running `cat README`. Depending on how you implemented Part 2, you may
see:
init: starting sh
$ cat README
unexpected trap 14 from cpu 1 eip 80105282 (cr2=0x3000)
cpu1: panic: trap
8010683a 801064fa 80101f4e 80101174 80105725 8010556a 801066f9
801064fa 0 0
Why is this happening? Debug the problem and find a fix (if this part works already, you don’t
need to make any changes).
Next, let’s see if pipes work, by running `cat README.md | grep the`
Name: NetID: P a g e 6 |
$ cat README | grep the
cpu0: panic: copyuvm: page not present
8010828e 80104693 8010630b 8010556a 801066f9 801064fa 0 0 0 0
Find out what’s going on, and implement a fix.
**Hints**
1. Think about what happens if the kernel tries to read an address that hasn’t been mapped yet
(for example, if we use `sbrk()` to allocate some memory and then hand that buffer to the
`read()` syscall). Read the code in `trap()` with that case in mind.
2. Making pipes work is a very tiny change — just one line in one file. Don’t overthink it.
Submitting
As with the previous homeworks, your repo will be your submission. Push to your repo often*.
You have unlimited submissions until the deadline. Please use this tutorial for using git:
https://piazza.com/class/kek3wm1meum2yb?cid=25
*If you are having problems pushing to your repo from the Anubis cloud IDE, let us know. We
are aware of a bug that prevents some users from manual pushing, and are still in the process
of fixing it. Fortunately, the Anubis cloud IDE also automatically pushes your changes every 5
minutes. In the case that you have trouble manually pushing your assignment, please rely on
the auto push feature to push your work.
Put your answers to the following questions in a text file called answers.txt in your repo.
QUESTION 2: (10 points) Parallel HashTable.
A) Recall the parallel hash table implementation that we worked in class.
https://piazza.com/class/kek3wm1meum2yb?cid=25
Name: NetID: P a g e 7 |
Suppose we have two threads inserting keys using insert() at the same time.
1. (5 points) Describe the exact sequence of events (i.e, the order that the
statements in insert() would have to be run by each thread) that results in a key
getting lost.
2. (5 points) In an attempt to fix the problem, suppose we add code that locks the
table just before line 19 and unlocks it right afterward. Would this fix the
problem? Why or why not?
Name: NetID: P a g e 8 |
QUESTION 3: (10 points) Virtual Memory
Suppose the page table for the process currently executing on the processor looks like
the following. Note: All numbers are decimal, everything is numbered starting from
zero. The page size for this problem is 1000 bytes.
(a) (9 points) Describe exactly how, in general, a virtual address generated by the
CPU is translated into a physical memory address?
(b) (6 points) What physical addresses (physical page + offset), if any, would
each of the following virtual addresses correspond to? If there would be a
pagefault just say so (Do not try to handle page faults)
a. 4100 =
b. 5200 =
c. 990 =
Virtual Page
number
Valid Bit Reference
Bit
Modify Bit Physical
Page frame
number
0 1 1 0 4
1 1 1 1 7
2 0 0 0 –
3 1 0 0 2
4 0 0 0 –
5 1 0 1 0