CS444 Final Exam, Dec

CS444 Final Exam, Dec. 16, 2003 NAME:_____Solution______________________

Open books, notes, handouts. Write on these pages, using the backs if need be (I hope not.) Each problem is worth 30 points. I’ll drop the lowest-score problem.

1. Short answer.

a. Describe two ways the kernel code can stop the UART transmitter interrupts from happening while a program is running on an x86 system.

Disable Tx interrupts in the UART via its IER register

Mask its IRQ in the PIC

Do cli to make IF=0 in the CPU’s EFLAGS register

b. In user-level producer consumer using three semaphores (for example the program on pg. 120, or prodcons.c of hw5), suppose the shared buffer can hold 10 elements. What are the maximum counts in each of the three semaphores to use all 10 spots, but no more?

10, 10, and 1 (for mutex semaphore)

c. Suppose a file has 100 file data blocks. If it’s a FAT (File Allocation Table) file, how many disk-block accesses are needed to determine the last byte in the file if the FAT table is filled in for it? 1 If no information for this file is in the table? 100

d. Suppose a page fault occurs on a code page for a process. Where will the OS find the data (program code) for the page? from the program’s executable file What action by the scheduler will soon happen for this process? sleep call/ block process

2. Deadlocks. Suppose there are two resources R and S, and three processes A, B, and C, and:

process A holds T, wants R

process B holds R, wants S

process C holds nothing, wants R and S

Draw the resource allocation graph and determine if there is a deadlock. If so, what processes are involved? If not, show how the processes can “unwind”, i.e., finish execution in some order.

|T| -> (A) -> |R| à (B) à |S|

^ ^

| |

|-----(C) ----|

Unwinding: B gets S, finishes, releases locks on R and S

A gets R, finishes, releases locks on R and T

C gets R and S, finishes.

3. System Call Mechanism. In hw2, hw3, and hw5, and also in Linux, a system call and related execution has the following steps:

1. call assembly language function for system call

2. load system call arguments in registers, system call # in EAX

3. start executing int $0x80

4. save EFLAGS, EIP on stack (also CS)

5. load EIP from IDT[0x80]

6. execute the assembler syscall handler, save registers

7. execute the C syscall handler

8. execute the assembler syscall handler body, restore registers

9. execute the iret instruction

10. execute the next instruction after the int $0x80

a. Which steps are part of the trap cycle of the CPU, (and thus involved in the transition from user to kernel mode under Linux)?

4,5

b. Which step, when executed under Linux, involves a transition from kernel mode to user mode?

c. Which steps, when executed under Linux, are running in user mode in the CPU?

1, 2, 3, 10

d. Which steps, when executed under Linux, are running in kernel mode in the CPU?

6, 7, 8, [9] (9 returns execution to user level, so is somewhat marginal in classification)

e. Which step could contain a call to a device driver (hw’s or Linux)?

f. Which steps would also be in a list like this for handling an interrupt? (Replace “syscall” with “interrupt” in the steps above to answer this.)

4, 5 with 0x80 replaced by interrupt vector number, 6, 7, and 8 (with syscall replaced by “interrupt”), 9

4. Scheduling. Consider the execution of the hw3 kernel with its non-preemptive scheduler with the following programs, which are nearly the same as the standard test programs except for the number of A’s that main1 outputs, and main3, which computes as well as outputting c’s.

int main1()

{

int sum = 0; int i;

write(TTY1, “aaaaaaaaaaa”, 10);

write(TTY1, “zzz”, 3);

for (i=0;i<100000000;i++)

sum += i*i; /* suppose this takes 40ms to run */

write(TTY1, “AAAA”, 4);

}

int main2()

{

write(TTY1,”bbbbbbbbbb”, 10);

}

int main3()

{

int sum = 0; int i;

for (i=0;i<100000000;i++)

sum += i*i; /* suppose this takes 40ms to run */

write(TTY1, “cccc”, 4);

}

The output from the run using hw3’s kernel is simply aaaaaaaaaazzzAAAAbbbbbbbbbbcccc

a. What output is showing when main1 exits? (Don’t forget write-behind)

aaaaaaaaaazzz (AAAA is in the output queue, but zzz has had plenty of time to get output)

b. What output is showing when main2 exits?

aaaaaaaaaazzzAAAAbbbb (bbbbbb is in the output queue. Recall the output queue holds 6 bytes.)

c. Does process 1 ever block? When or why not?

Yes, when it has put 6 a’s in the output queue, it first blocks. Then it blocks on each following a and each of the three z’s. But the old output has drained by the time the A’s are enqueued, so all four are put in the output queue without blocking.

d. Does process 3 ever block? When or why not?

No, the loop allows the output to drain, so the 4 c’s are enqueued without blocking.

e. How would this trio of user programs run under hw5, with its preemptive scheduler? Show the expected debug_log, with preemptions and ticks showing at well as output. You don’t need to show the ~’s, but may if you want.

Showing output insead of ~’s:

There are other possibilities, but there should be 4 ticks with *1 and 4 with *3, each followed by a preemption of that process. Process 3 will be the first to go into a loop, because it will be ready when the others are blocked on their output.

5. Mutex System Calls. Suppose we want to add a user-level mutex service to nonpreemptive tiny UNIX (hw3).

a. Suggest an appropriate set of new system calls for this service. Also give the appropriate names for the kernel functions that implement each system call.

One possible set:

syscall mutex_create with kernel function sys_mutex_create

syscall mutex_destroy with kernel function sys_mutex_destroy

syscall mutex_lock with kernel function sys_mutex_lock

syscall mutex_unlock with kernel function sys_mutex_unlock

b. Explain in what functions the scheduler functions sleep() and wakeup() would be called.

mutex_lock calls sleep, mutex_unlock calls wakeup

c. Would you use cli() and sti() (or set_eflags()) around the call to sleep? Discuss this decision.

Yes, callers of sleep are expected to ensure IF=0 at the call to sleep, and system call functions are called with IF=1, so cli() is needed before the call to sleep and sti or set_eflags after. We know that sleep will call scheduler, and scheduler will choose another process to run, and this process will enable interrupts as appropriate, so they will not be off for long.

6. x86 Paging. The first few PTEs of the SAPC’s only page table look like this, after a reboot:

Address Contents

0x52000 0x00000007

0x52004 0x00001007

0x52008 0x00002007

0x5200c 0x00003007

a. What is the relationship between VA and PA described here? For what range of VAs?

This shows that VA = PA for 0 <= VA <= 0x3fff. (These are the first 4 PTEs, handling the first 4 pages of VA space on the SAPC.)

b. What Tutor command would you use to make page 3 read-only?

ms 5200c 00003005 or any command that turns off bit 1 of byte 5200c

c. How would you change this page table to make an access to VA 0x2056 cause a page fault? (What new value for what address?)

This is a page 2 address, so change PTE2, which is at 0x52008:

ms 52008 00000000 or any command that turns off bit 0 of byte 52008.