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

日期：2024-05-07 03:27

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 file 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 fill 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 definitions, 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 modified 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.