CS计算机代考程序代写 Name: NetID: P a g e​ ​1 |

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, , affirm that I have completed the exam completely on my own, without consulting
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