辅导 CSCI-UA.202: Operating Systems (Undergrad): Spring 2020 Final Exam辅导 R编程

CSCI-UA.202: Operating Systems (Undergrad): Spring 2020

Final Exam

• This exam is 110 minutes.

• The answer sheet is available here:

– Section 001 (Aurojit Panda)

– Section 003 (Michael Walfish)

The answer sheet has the hand-in instructions.

• There are 14 problems in this booklet. Many can be answered quickly. Some may be harder than others, and some earn more points than others. You may want to skim all questions before starting.

• This exam is closed book and notes. You may not use electronics: phones, tablets, calculators, laptops, etc. You may refer to TWO two-sided 8.5x11” sheets with 10 point or larger Times New Roman font, 1 inch or larger margins, and a maximum of 55 lines per side.

• Do not waste time on arithmetic. Write answers in powers of 2 if necessary.

• If you find a question unclear or ambiguous, be sure to write any assumptions you make.

• Follow the instructions: if they ask you to justify something, explain your reasoning and any important assumptions. Write brief, precise answers. Rambling brain dumps will not work and will waste time. Think before you start writing so that you can answer crisply. Be neat. If we can’t understand your answer, we can’t give you credit!

• If the questions impose a sentence limit, we will not read past that limit. In addition, a response that includes the correct answer, along with irrelevant or incorrect content, will lose points.

• Don’t linger. If you know the answer, give it, and move on.

• If you have questions about the exam please go to https://campuswire.com/p/G7536A0B2 (if you need access, use code 7012).

• Write your name and NetId on the document in which you are working the exam.

I Fundamentals (7 points)

1. [3 points] The primary architecture that we have used in this class is a -bit architecture. Fill in the blank above with the right number of bits.

64.

2. [4 points] The read system call takes three arguments: a ﬁle descriptor, and two others:

int read(int fd , , );

What are the two other arguments? For each argument, state both its type and what the variable represents.

arg2 is void* or char*, a pointer to the memory area that holds the data to be read. arg3 is size t, the number of bytes to read.

II Concurrency (21 points)

3. [4 points] Consider a machine with two x86 CPUs, and assume that each CPU is currently executing a different thread from the same process. Recall that in the x86 architecture, a CPU’s %cr3 register contains the physical address of the level-1 page table that determines memory translations on that processor.

In this scenario, do the two processors have the same or different values for %cr3? Justify your answer in no more than two sentences.

They have the same value of %cr3. Threads share memory, and the way that this is implemented is to give them the same “view” of memory; that is, two threads share the same page tables.

4. [2 points] Consider a multi-threaded program that runs correctly under all interleavings on a time-sliced single processor with preemptive scheduling. It does not necessarily follow the concurrency commandments.

Is the following statement True or False? “This program is guaranteed to run correctly if each thread is run on a separate CPU of a shared-memory multiprocessor.” Justify using two sen- tences.

False. Code that is correct under a single CPU (and sequential consistency) may be incorrect (because of more possible interleavings) under a different memory model. An example is the double-checked locking code that we saw in class.

5. [15 points] To make a water molecule, assume you need only two Hydrogen atoms and one Oxygen atom (we are ignoring real chemistry). Using monitors, you will write a solution that makes water whenever the needed resources are available. You will ﬁll in three methods: GenOxygenAtom, which generates an Oxygen atom; GenHydrogenAtom, which generates a Hydrogen atom; and MakeWaterMolecule, which generates water.

Each of these methods can be executed an arbitrary number of times concurrently—concurrently with other invocations of the method and concurrently with the other methods. For example, you can imagine 500 threads, each of which is in a loop calling GenOxygenAtom; 500 more, each of which is in a loop calling GenHydrogenAtom; and another 500, each in a loop calling MakeWaterMolecule. To be clear, those numbers are just examples: your code needs to be correct for any number of threads.

Note that this kind of concurrency is often our assumption when working with monitors.

As an additional constraints:

– You must follow the class’s concurrency commandments.

– The monitor can hold no more than 1000 Oxygen atoms and 2000 Hydrogen atoms; these capacities are independent (so it can hold 1000 Oxygen and 2000 Hydrogen atoms at the same time).

– Avoid unnecessary thread wakeups. Use your judgment about what constitutes an unnecessary wakeup.

class Water {

public:

Water(); // Initializes state and synchronization variables ˜Water();

GenOxygenAtom();

GenHydrogenAtom();

MakeWaterMolecule();

private:

// FILL THIS IN

};

// Here and on the next page, give the implementations of

// Water::Water();

// void Water::GenOxygenAtom()

// void Water::GenHydrogenAtom();

// void Water::MakeWaterMolecule();

Space for code and/or scratch

Data members in Water:

class Water {

....

private:

Mutex lock;

Cond cv_enough_atoms;

Cond cv_oxy_notfull;

Cond cv_hyd_notfull;

m_oxy;

m_hyd;

m_water;

};

Methods:

Water::Water() {

m_oxy = 0;

m_hyd = 0;

m_water = 0;

lock.init();

cv_enough_atoms.init();

cv_oxy_notfull.init();

cv_hyd_notfull.init();

}

void

Water::GenOxygen() {

lock.acquire();

while (m_oxy == 1000) {

cv_oxy_notfull.wait(lock);

}

m_oxy++;

cv_enough_atoms.signal();

lock.release();

}

void

Water::GenHydrogen() {

lock.acquire();

while (m_hyd == 2000) {

cv_hyd_notfull.wait(lock);

}

m_hyd++;

if (m_hyd >= 2)

cv_enough_atoms.signal();

lock.release();

}

void

Water::MakeWater() {

lock.acquire();

while (! (m_hyd >= 2 && m_oxy >= 1) ) {

cv_enough_atoms.wait(lock);

}

m_water++;

m_hyd -= 2;

m_oxy -= 1;

if (m_hyd <= 1998) // the guard is optional

cv_hyd_notfull.broadcast(lock);

if (m_oxy <= 999) // the guard is optional

cv_oxy_notfull.signal(lock);

lock.release();

}

III Context switches (9 points total)

6. [9 points] In this question, you will implementswtch(), which switches between two user-level threads. You will do so for a user-level threading package, running on the TeensyArch processor. TeensyArch has 4 general registers, %r0-%r3, a stack pointer, a base (or frame) pointer, and an instruction pointer %rip. Assume the same stack frame structure as the architecture we’ve been covering in class (x86); further, all registers need to be saved by a function’s callee (that is, registers are callee-saved, also known as call-preserved).

Fill out swtch() on the next page. Below are deﬁnitions, declarations, and utility functions that you can use.

struct thread {

int thread_id;

uint64_t stack;

/* . . . */

};

enum register {

R0,

R1,

R2,

R3,

RBP,

RSP

};

// Push CPU’s register r to the stack

void push_register(register r);

// Pop from the stack and into the CPU’s register r

void pop_register(register r);

// Returns the CPU’s current value of register r .

uint64_t read_register(register r);

// Update the CPU’s register r so it holds value ‘value‘ .

void write_register(register r, uint64_t value);

// Context switch from thread t1 to thread t2 .

void swtch(struct thread *t1, struct thread *t2) {

// On entry this function is run by thread t1 .

// Your code here . We have started it for you .

push_register(RBP);

push_register(R0);

// YOUR CODE HERE

return; // The function should return to the

// point where thread t2 called swtch() .

}

void swtch(struct thread *t1, struct thread *t2) {

// On entry this function is run by thread t1 .

push_register(RBP);

push_register(R0);

push_register(R1);

push_register(R2);

push_register(R3);

t1->stack = read_register(RSP);

write_register(RSP, t2->stack);

pop_register(R3);

pop_register(R2);

pop_register(R1);

pop_register(R0);

pop_register(RBP);

return; // The function should return to the

// point where thread t2 called swtch .

}

IV mmap and ptrace (23 points total)

7. [8 points] Consider the following code excerpt that uses mmap():

int main(int argc, char* argv[]) {

// . . .

// readme.txt is a file that is 5KB in length .

int fd = open("readme.txt", O_RDWR, 0);

char *map1 = (char*)mmap(NULL, 5120, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0); char *map2 = (char*)mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);

// assume that neither mmap call fails

char x = 0;

char y = 0;

// Line 1

for (int i = 0; i < 5120; i++) {

x = map1[i];

y = map2[i % 4096];

}

// Line 2

// . . .

}

// The signature of mmap is:

// void* mmap(void *addr, size_t len, int prot, int flags, int fd, off_t offset); //

// If addr is NULL, the kernel chooses the start virtual address .

// If not already in memory, disk blocks are fetched into physical pages on access . //

// Each separate call to mmap() with the same fd maps the file in a separate // location and does not undo prior mappings . This means that in the example // above, the file can be read and written from multiple virtual addresses

// within the same address space .

Assume the operating system minimizes the number of virtual and physical pages required in order to implement mmap().

How many last-level (level-4) page table entries are created or modiﬁed as a result of the two mmap() calls?

3. Page size is 4096, so map1 consumes 2 entries, and map2 consumes one entry.

At line 2, how many physical pages are mapped into the process as a result of themmap() calls?

2. The 3 virtual pages map to two physical pages in the OS buffer cache.

8. [15 points] In class, we studied the system call ptrace(), which allows the caller to manipulate a target process in various ways. In this question, you will implement a version of ptrace for lab4’s WeensyOS:

sys_ptrace_getregs(pid_t pid, x86_64_registers* regs);

This system call should retrieve values for all processor registers that were in effect at the time just before the process with PID pid blocked. You should copy the registers’ values to the memory address given by theregs parameter.

Assume that we have modiﬁed WeensyOS’s syscall dispatch logic so that, when a user-level pro- cess invokes sys_ptrace_getregs(pid_t pid, x86_64_registers* regs), the kernel calls ptrace_getregs_impl(); this latter function is what you will implement. This function should meet the following speciﬁcation:

– Return -1 on error, 0 on success.

– There is no isolation; any process can ptrace any other valid process.

– It is an error if pid does not reference a legitimate process (by non-legitimate, we mean that the corresponding process slot is free);

– It is an error if the memory referenced by regs cannot be read or written by the current process.

– To help you check the prior condition, assume you have access to a function: virtual_memory_checkperms(x86_64_pagetable* pt, uintptr va, size_t len, int perm);

that returns 0 when the range of memory [va,va+len) has permissionsperm in the view of memory given by pt. Returns -1 otherwise.

– You can use as a utility function:

void* memcpy(void* dst, const void* src, size_t n);

which copies n bytes from address src to address dst.

On the next page, implement ptrace getregs impl() in syntactically correct C.

int ptrace_getregs_impl(pid_t pid, x86_64_registers* regs) {

// YOUR CODE HERE

// NOTE 1: The following page has possibly-useful excerpts from WeensyOS

// NOTE 2: You do not need a lot of code; the staff solution has 5-7 lines

}

typedef enum procstate {

P_FREE = 0, // free slot

P_RUNNABLE, // runnable process

P_BLOCKED, // blocked process

P_BROKEN // faulted process

} procstate_t;

// Process descriptor type

typedef struct proc {

pid_t p_pid;

x86_64_registers p_registers; procstate_t p_state;

x86_64_pagetable* p_pagetable; } proc;

// process ID

// process’s current registers

// process state (see above)

// process’s page table

static proc processes[NPROC]; proc* current;

// array of process descriptors

// pointer to currently executing proc

// YOU DO NOT NEED THE FUNCTIONS BELOW . We include them to aid with // recall about certain details in the labs .

// virtual_memory_map(pagetable, va, pa, sz, perm, allocator)

// Map virtual address range ‘[va, va+sz)‘ in ‘pagetable‘ .

// When ‘X >= 0 && X < sz‘, the new pagetable will map virtual address // ‘va+X‘ to physical address ‘pa+X‘ with permissions ‘perm‘ .

// Precondition: ‘va‘, ‘pa‘, and ‘sz‘ must be multiples of PAGESIZE // (4096) .

// Typically ‘perm‘ is a combination of ‘PTE_P‘ (the memory is Present), // ‘PTE_W‘ (the memory is Writable), and ‘PTE_U‘ (the memory may be

// accessed by User applications) . If ‘!(perm & PTE_P)‘, ‘pa‘ is ignored . //

// Returns 0 if the map succeeds, -1 if it fails because a required // page table could not be allocated .

int virtual_memory_map(x86_64_pagetable* pagetable, uintptr_t va,

uintptr_t pa, size_t sz, int perm,

x86_64_pagetable* (*allocator)(void));

// virtual_memory_lookup(pagetable, va)

// Returns information about the mapping of the virtual address ‘va‘ in // ‘pagetable‘ . The information is returned as a ‘vamapping‘ object,

// which has the following components:

typedef struct vamapping {

int pn;

uintptr_t pa;

int perm;

} vamapping;

// physical page number; -1 if unmapped

// physical address; (uintptr_t) -1 if unmapped

// permissions; 0 if unmapped

vamapping virtual_memory_lookup(x86_64_pagetable* pagetable, uintptr_t va);

int ptrace_getregs_impl(pid_t pid, x86_64_registers* regs) {

if (processes[pid].p_state == P_FREE) {

return -1;

}

if (virtual_memory_checkperms(current->p_pagetable,

regs,

sizeof(x86_64_registers),

PTE_P | PTE_U | PTE_W)) {

return -1;

}

memcpy(regs, &processes[pid].p_registers, sizeof(x86_64_registers)); // alt: *regs = processes[pid].p_registers;

return 0;

}

V Disks and ﬁle systems (28 points total)

9. [6 points] A disk driver must schedule disk requests for tracks 10, 22, 20, 2, 40, 6, and 38. A seek takes 6 msec per track moved (note that, among other simpliﬁcations, we are not taking into account the length of the seek). Assume that the disk arm is initially at track 20.

How much seek time is needed to handle all of these requests if the driver follows the SSTF (Shortest seek time ﬁrst) scheduling algorithm? Show your work.

20 — 22 — 10 — 6 — 2 — 38 — 40. So the time is (2 +12 +4 +4 +36 +2) · 6 ms = 360 ms.

How much seek time is needed if the driver follows the SCAN (aka elevator) scheduling algo- rithm? Show your work.

If traveling up ﬁrst, 20 — 22 — 38 — 40 — 10 — 6 — 2. So the seek time is (2 + 16 + 2 + 30 + 4 + 4) · 6 ms = 348 ms. Or if it travels down ﬁrst: 20 — 10 — 6 — 2 — 22 — 38 — 40. And seek time is (10 +4 + 4 +20 +16 +2) · 6 ms = 336 ms.

10. [8 points] In what follows, Jo executes a program that writes the string “Done with CS202” to the ﬁle notes.txt. Unfortunately, Jo’s computer crashes during this write. For each of the scenarios below, we state where Jo’s computer crashed; you will state whether or not notes.txt contains the string “Done with CS202” when Jo restarts their computer.

Part (a). Jo’s computer is using ZFS, which relies copy-on-write for crash consistency. The following sequence of operations occur:

– A new data block is allocated.

– A pointer to the data block is added to a new copy of the notes.txt inode.

– The string “Done with CS202” is written to the newly allocated data block.

– The computer crashes.

When Jo restarts their computer, does notes.txt contain the string “Done with CS202”? Justify in one sentence.

No, because a new version of the uberblock wasn’t written.

Part (b). Jo’s computer is using EXT4, which uses redo logging for crash consistency. The following sequence of operations occur:

– A TxnBegin block is written to the log.

– All of the updates and sub-operations for Jo’s write—inoode updates, data bitmap updates, and data block modiﬁcations—are logged.

– The computer crashes.

When Jo restarts their computer, does notes.txt contain the string “Done with CS202”? Justify in one sentence.