Problem 1 : Short Answer
Part B: USING 30 WORDS OR FEWER, explain why devices abstracted as files in the file descriptor array?
Part C: USING 20 WORDS OR FEWER, explain why arguments are passed to system calls in a different way than in the x86 C calling convention that you learned earlier in the course.
Part D: Your other teammate B says A¡¯s design will create a deadlock, because both the newly created process will hold on to same lock as the parent. USING 30 WORDS OR FEWER, explain why this is not an issue.
USING 30 WORDS OR FEWER, explain why the child process is always printing the same number.
1
Problem 2 : The A-MAZE-ing Mode S!
Part D: What is the minimum number of memory addresses to represent a full screen in mode S (not counting the palette color data)?
Part D-Variant2: What is the minimum number of memory addresses to represent a full screen in mode S (not counting the palette color data)?
Part E: You want to assign a different color to each object, can you implement the mazegame in mode S? Justify your answer USING 30 OR FEWER WORDS.
Part E-Variant2: You want to assign a different color to each object, can you implement the mazegame in mode S? Justify your answer USING 30 OR FEWER WORDS.
2
Part F: You want to change the color of the player every second, cycling through 42 colors. Can you implement the mazegame in mode S? Justify your answer USING 40 OR FEWER WORDS.
Part F-Variant2: You want to change the color of the player every second, cycling through 42 colors. Can you implement the mazegame in mode S? Justify your answer USING 40 OR FEWER WORDS.
3
Problem 3 : TUX Controller
Part B-1: Betty presses the buttons on the TUX and notices that nothing happens, that is, the player doesn¡¯t move. USING 30 OR FEWER WORDS, explain the problem and provide a fix for her issue.
Part B-2: After fixing the bug in Part B.1, Betty notices that when she tries to quit the game using the ¡°`¡±(BACKTICK) character, the game continues running, but the clock stops, and keyboard inputs stop working. Assuming that all references to the thread for the TUX are given to you in the code above, and USING 20 WORDS OR FEWER, explain the problem.
4
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
int tuxctl_ioctl (struct tty_struct* tty, struct file* file,
unsigned cmd, unsigned long arg) {
unsigned char to_tux[5]; // never sending more than 5 bytes to TUX
switch (cmd) {
case TUX_INIT:
busy = BUSY;
to_tux[0] = MTCP_BIOC_ON; // init button handling
Part C: Complete the code given below to achieve John¡¯s design by filling in the blanks with valid C commands. You may not add additional lines nor remove any lines. You may not need to fill in all the blanks.
1
2
3
4
5
6
7 * 8 * 9 *
*
10 * 11 */
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 * 27 * 28 * 29 * 30 * 31 * 32 * 33 * 34 */
#define BUSY 1
#define FREE 0
volatile int busy = FREE;
/*
} }
/* *
tuxctl_handle_packet()
DESCRIPTION: handles packets sent by the Tux Controller
INPUTS: tty – tty_struct
packet – returned data from tux controller
OUTPUTS: none
void tuxctl_handle_packet (struct tty_struct* tty, unsigned char* packet) {
switch (packet[0]) {
case MTCP_ACK:
busy = BUSY; // BLANK 1
break;
case MTCP_RESET:
// ASSUME IMPLEMENTED CORRECTLY, WITH NO FALL THROUGH
case MTCP_BIOC_EVENT:
// ASSUME IMPLEMENTED CORRECTLY, WITH NO FALL THROUGH
tuxctl_ioctl
DESCRIPTION: handles the commands parsed by user
INPUTS:
tty – passed through by driver
file – driver file
cmd – command to handle
arg – argument of the command
OUTPUTS: depends on the command
RETURN VALUE: depends on the command
SIDE EFFECTS: may loose data if the previous command haven’t finished
to_tux[1] = MTCP_LED_CLK;
to_tux[2] = MTCP_CLK_RESET;
to_tux[3] = MTCP_CLK_UP;
________________________
tuxctl_ldisc_put(tty, to_tux, 4); // BLANK 6
return 0;
case TUX_BUTTONS:
// ASSUME IMPLEMENTED CORRECTLY, WITH NO FALL THROUGH
case TUX_START_CLOCK:
if (busy == BUSY) {
return -EINVAL;
}
// BLANK 7
// BLANK 2
// BLANK 3
5
// BLANK 4
// BLANK 5
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
busy = BUSY;
to_tux[0] = MTCP_CLK_RUN;
tuxctl_ldisc_put(tty, to_tux, 1);
return 0;
// BLANK 8
case TUX_STOP_CLOCK:
if (busy == BUSY) {
return -EINVAL;
// BLANK 9
}
busy = BUSY;
to_tux[0] = MTCP_CLK_STOP;
tuxctl_ldisc_put(tty, to_tux, 1);
return 0;
// BLANK 10
case TUX_RESET_CLOCK:
// ASSUME IMPLEMENTED CORRECTLY, WITH NO FALL THROUGH
default:
return -EINVAL;
} }
6
Problem 4 : Virtual Memory
Part A: Consider the following scenario from MP3 Checkpoint 1. Before enabling paging, you print out the address of the page table and observe the result 0x00503910. USING 20 WORDS OR FEWER, explain why the given address is unacceptable.
Part B: Following is a snippet of code from your kernel.c. After fixing the bug in Part A, you notice that your OS crashes while inside the printf call on line 15. Notice that the code before line 15 executed without crashing, including the printf on line 12. USING 20 WORDS OR FEWER, explain the most likely reason for this crash.
/* Omitted Code */
Part C: Now you start to add test cases for paging. Which of the following tests should generate a page fault? CIRCLE EXACTLY ONE ANSWER.
7
Part D: What is the size of the virtual address space in bytes if we use 57-bit virtual addresses on a 64-bit processor?
Part E-1: What is the maximum number of entries contained in a single paging structure?
Part E-2: What is the minimum number of levels of indirection needed to translate a 57-bit virtual address to the base address of a 4 kB page?
Part E.3: Assume that the size of all paging structures (page directories, page tables and so forth) and all pages is exactly 4kB.
Assume that you need to set up the paging structures to map two regions: 1MB for code, and 8kB for stack. Assuming that the two regions are not adjacent in any level of paging, what is the total size of all paging structures required for this mapping if 5 levels of indirection are used? Show your calculation.
Part F: Now assume that the size of all paging structures (page directories, page tables and so forth) and all pages is exactly 2MB.
Assume that you need to set up the paging structures to map two regions: 1MB for code, and 8kB for stack. Assuming that the two regions are not adjacent in any level of paging, what is the total size of all paging structures required for this mapping if 2 levels of indirection are used? Show your calculation.
8
Problem 5 : Interrupts and Exceptions
Part A: USING 20 WORDS OR FEWER, explain why the fault occurs and how you fix the problem.
Part B: Pointing out that Linux sets the processor¡¯s IF flag back to 1 while executing interrupt handlers, your teammate suggests using trap gates in the IDT for interrupts generated by the 8259A PICs. As you know, trap gates do not clear IF. In terms of the interrupt handling strategy and implementation used by the Linux in your class VM (as discussed in class), and USING 50 WORDS OR FEWER, explain one problem that arises from such a change.
Part C: After finishing your initialization code for paging, IDT, PIC, RTC, and so forth, you decide to start a debugging run. You set breakpoints in every interrupt handler and at several places in the code, then walk through your execution. Just after you turn on interrupts (set IF to 1), the machine jumps to the double fault exception handler (IDT entry 0x08)! USING 30 WORDS OR FEWER, explain what probably happened.
Part D: He finds that the mouse generates IRQ 4, so he sets entry 0x24 in the IDT to &mouse handler. However, after executing the mouse handler function in response to the first mouse interrupt, the kernel crashes (after the handler executes to completion). Assuming that the handler is implemented correctly, and USING 20 WORDS OR FEWER, explain the problem with Ben¡¯s implementation.
9