CS644 Practice Final Exam Solution

 

Open books, notes, handouts.  You can write short answers on these papers and longer ones on the backs of pages or on other paper.  Points: problem 1 = 40pts, 2=40pts, 3=30pts, 4=40pts. 

 

1.       Shorter Answer:  Assume Linux 2.6 (on x86).

a.                   What Linux function corresponds to resched() in Xinu?

 

schedule()

 

b.                   What is done in Xinu system call code to block the current process (give the 2 lines of code)?

 

proctab[currproc].pstate = PRRECV or whatever

resched()

 

 

c.                    What is done in Linux system call code to block the current process (give example lines of code—there is more than one way)?

 

set_current_state(TASK_INTERRUPTIBLE)      or      current->state = TASK_INTERRUPTIBLE

schedule()

 

d.                   What is done in Xinu system call code to unblock another process?  In interrupt handler code?

ready(pid, RESCHYES/NO)                                                               same

 

 

e.                    Interrupts are allowed in a greater part of Linux kernel code than in Xinu kernel code.  Explain why.

 

Linux kernel must run on multiprocessors, where disabling interrupts does not provide kernel mutex.  Instead, spinlocks are used with interrupts enabled, so where code in Xinu would have IF=0 for mutex, Linux just has a spinlock in use (usually with IF=1).

 

 

f.                    Can interrupt handlers block—in Linux?  In Xinu?

no              no

 

 

g.                    Both Linux and Xinu have clock interrupt handlers.  List two actions they do in common.

 

Send EOI to PIC

Count down the current process’s CPU quantum.

Preempt processes under at least some circumstances.

 

 

h.                   What specific mechanism prevents user-level code from accessing kernel memory in 32-bit x86 Linux, which holds the kernel in the uppermost 1GB of the 4GB virtual address space?

Each page has a U bit in its PTE that controls access to that page by user code. Kernel pages have U=0 to disallow access by user code.

 

 

2.       Consider the following multiprocessor) Linux memory areas:

KGD       kernel global data, not including per-process data

KS                          kernel stack

PENT                     process entry (task_struct)

UI                           user image: code, data, stack, etc.

 

a.       Which of these areas are per-process, so that each process on the system has one?

KS, PENT, UI (UI may be shared between threads)

 

b.       Which of these areas are process-private?

KS, UI (in effect, that is, the kernel assumes that simultaneous syscalls from two threads of the same process involve independent data)

 

c.        Which areas allow update of their contents by the kernel without needing mutex?

KS, UI

 

 

d.       Which one can be empty for an active currently-running process?

KS  (The kernel stack is empty when the process is running at user level.)

 

e.       In which area are the serial line input buffers?

KGD

 

f.        In which area is the semaphore table, underlying System V semaphores?

KGD

 

g.       In which area is the C library code used by the user process?

UI

 

1.      Recall the mloop program of hw4. Suppose it is running with 3 worker processes (pids 40, 41 and 42) and using the original send/receive, and using sleep100(5) for delay, that is, 50 ms delay between receiving and sending the message around the loop. The clock tick is 10 ms on Xinu.

a. Suppose the last send was 25 ms ago by process 41, plenty of time for the system to settle down to a certain state. What are the pstate values for the three worker processes?

Process 41 has looped back to receive, so has pstate PRRECV.

Process 41 has sent the message to process 40 (say), which received it and is now in sleep, on the clockq, with pstate PRSLEEP.

Process 42 is also blocked in receive, so has pstate PRRECV.

b. What do you expect to see on Xinu's clockq at this time? Give the key value(s) on the delta queue.

Only one process, the one sent to by process 41, process 40 in a., with key value 2 or 3, for 25 ms remaining being 2 or 3 ticks depending on exactly when the tick happens.

 

2.       Projects—do one of these.

Printer driver

Suppose two processes are trying to print at the same time.  Process A is printing 1000 A’s and process B is printing 1000 B’s.  Process A calls write(LP, buf, 1000) first, followed as soon as possible by process B, using another user buffer. No other user processes exist. Suppose the printer output buffer can hold 100 characters.  Assume lpwrite is just a loop of lpputc’s with no kernel mutex of its own (which is fine, since lpputc is itself the guts of a system call and thus takes care of its mutex needs.)

 

  1. In general, explain how the printer driver controls all this data going through it and ensures that 2000 characters are printed.
  2. In particular, what happens when process A calls write, up to the moment it loses the CPU—

i.         With a full quantum remaining, so it can do a lot of processing without preemption.

ii.        With a small amount of CPU remaining in its quantum, enough for 2 lpputc’s.

Don’t forget to discuss the common elements of the execution, such as getting the printer started.

  1. Consider a moment later when both processes have called write and the printer output buffer is full, and the printer is currently (slowly) outputting a character. List all the processes on the system, including process 0 but excluding any frame layer daemons, and their current process state.

 

    1. The printer driver here is handling two data producers, the two user processes doing write, and one data consumer, the interrupt handler.  It has a shared buffer between the producers and the consumer.  It uses a semaphore to block the producers, much like classic producer-consumer, but can’t use a second semaphore to block the consumer because interrupt handlers can’t block.  Instead, when the buffer goes empty, the output essentially gets shut down, and needs to be restarted when data shows up again.  All characters are eventually printed because the writers are blocked until space is available in the buffer, and then unblocked.
    2. i. Process A fills the output buffer and then blocks, losing the CPU.  In the first lpputc, it has to arrange to output one byte from the upper half to get started, since the only way to get an interrupt for this device is from an acknowledgement of a previous character sent to the printer.  To output a byte, you need to put it in the printer data register, then construct a probe signal via the printer control register.  After the first byte, this output should be from the interrupt handler.  After the first byte, the lpputc code just enqueues the byte, knowing the interrupt handler will output it.

ii.  It does the 2 lpputc’s, and then gets preempted, losing the CPU to B.  The rest of the discussion is the same as part i.

                    c.

                                kernel process 0: PRCURR

                                user process A: PRWAIT

                                user process B: PRWAIT

 

     Datagram Service

The datagram service is handling two user-level server processes at once on one Xinu system.  One is waiting for datagrams on port 100 and the other on port 200. 

a.       Before any client processes come into existence, list all the processes on the system, including process 0, and their current process state.

b.      Suppose two user processes come into existence to be clients of the server on port 200.  Explain how it could happen that they are both executing in dgram_send at the same time, that is, their current or saved EIP (in pregs in pentry) is in dgram_send.

c.        Consider the two processes described in b that are both executing in dgram_send to port 200. In general, explain how the datagram service ensures that their client interactions with the service occur in an orderly fashion, even if two datagrams destined for the same port exist in the system at the same time. 

d.       Continuing from part c., the server on port 200 can receive the datagrams with dgram_receive. How does the server tell one client from another?

      a.

·             (kernel) process 0: PRCURR

·             (user) process for server on port 100: PRWAIT on the semaphore underlying input on Xinu port for port 100

·             (user) process for server on port 100: PRWAIT on the semaphore underlying input on Xinu port for port 200

 

b.       One client process starts executing dgram_send, and while it is executing in dgram_send, it runs out of its quantum and gets preempted by the other client process, which also calls dgram_send. Then both processes are “in” dgram_send, one by the real EIP and one by the saved-EIP in its pentry.

c.        Mutex (disable/restore) is used to make sure than no actions interfere with each other destructively in kernel code, including dgram_send and dgram_receive. Similarly psend and preceive have mutex protection, so their actions can be done concurrently. So in the case of two dgram_sends, each with a psend to the same Xinu port, both messages will be properly delivered into the Xinu port.

d.       Each client has a source port to tell the server where to send back to. These need to be different for each client to get back its own result from the server. This source port is the id used by the server.