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.)
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.
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.