ECE391 Exam 2, Fall 2021, CONFLICT
Wednesday 28 October
• Be sure that your exam booklet has 16 pages.
Copyright By PowCoder代写 加微信 powcoder
• Write your NetID at the top of each page.
• This is a closed book exam.
• You are allowed TWO 8.5× 11″ sheet of notes.
• Absolutely no interaction between students is allowed.
• Show all of your work.
• Don’t panic, and good luck!
Problem 1 20 points
Problem 2 17 points
Problem 3 20 points
Problem 4 21 points
Problem 5 17 points
Total 95 points
Problem 1 (20 points): Short Answer
Part A (5 points): T/F
TRUE FALSE It is possible that your MP3 OS will keep operating even when the ESP0 field in the TSS is
corrupted.
TRUE FALSE Having too little available memory left in the system cannot be the reason for a fork system call
TRUE FALSE When leaving kernel space (e.g. when returning from an interrupt), threads perform a context
switch and switch from using physical addresses to virtual addresses.
TRUE FALSE During a memory access, the processor checks whether the target virtual address translation is
cached in the CR3 register.
TRUE FALSE Soft interrupts can be deferred by the CPU when it is operating in a critical section,
while hard interrupts cannot.
Part B (3 points): Recall that the x86 architecture provides a hardware context switch capability through Task
State Segment (TSS). However, Linux does not utilize this feature. Apart from that a TSS entry is mandatory in x86,
why is TSS still necessary to accomplish a software defined context switch?
Part C (3 points): In your MP3, can you use Trap Gate for Division by Zero exception handler?
CIRCLE ONE: (1 pt) Yes No
Explain the difference between a Trap Gate and an Interrupt Gate.
Part D (3 points): Recall that we implemented Tux driver in a half-polling-half-interrupting approach in MP2.
Explain why this is a much better approach than polling from the Tux device directly, in terms of response time.
Part E (6 points): Consider an integer array and a linked list. The array is on the stack and the list nodes in the
linked list are allocated on the heap as new nodes are added. See the code below for how values are added to each data
structure.
typedef struct ListNode{
struct ListNode *next;
int value;
} list_node;
/***********************************************************************/
/* Data Structure Declaration */
int arr[700000];
list_node *head = (list_node *)malloc(sizeof(list_node));
list_node *cur = head;
/* Value Initialization */
for (int i = 0; i < 700000; i++){
cur->value = i;
cur->next = (list_node *)malloc(sizeof(list_node));
cur = cur->next;
arr[i] = i;
/* Loop One */
cur = head;
for (int i = 0; i < 700000; i++){
printf("%d", cur->value);
cur = cur->next;
/* Loop Two */
for (int i = 0; i < 700000; i++){
printf("%d", arr[i]);
The same integer sequence {0, 1, 2, ..., 699998, 699999} is stored in the two data structures. Now if we were to print
out the whole sequence {0, 1, 2, ..., 699998, 699999} from the array and the linked list using the two for loops (Loop
One and Loop Two), which for loop is likely to finish faster?
(Hint 0: the code is bug-free. Hint 1: this is a computer system course)
CIRCLE ONE: (1 pt) Loop One Loop Two Less than 1% difference in the runtime between the two
Explain your answer:
Problem 2 (17 points): MP2 5
You are implementing ModeX for a smaller screen, with 8 pixels widths and 2 pixels height, which uses 4 planes
as in MP2. The following figure shows the layout of the entire image you wish to display with the corresponding pixel
number in each slot. Note that the pixel numbers are not for representing the colors. They are simply the index that
specifies each pixel.
The following figure shows the planes in your build buffer, with the pixel numbers contained in each plane.
Part A (4 points): Map each buffer plane(A, B, C, D) to the corresponding image plane and logical plane(the
plane of the logical view). Write down the numbers in the table below.
Plane Image plane Logical plane
Part B (3 points): Suppose you shifted the logical view to the left by one pixel, so the original rightmost pixels
are not on the screen anymore. Which build buffer planes contain the same content as before the shift?
Part C (4 points): Map the buffer planes after the shift to the image and logical plane. If you were not able to
answer part A, fill out part A with your best guesses and answer part B based on that. Note that although the content
of some buffer planes might have changed due to the shift, they still contain a portion of the original content, which
allows us to specify them with the same name.
Plane Image plane Logical plane
Consider ModeF, a VGA mode that is similar to ModeX except that it only has 32 entries in the palette and the entire
color space is 12 bits, 4bits per R, G and B. You are implementing the adventure game for ModeF as you did in MP2.
Assume that every image in the game uses 12 bits for representing a pixel.
Part D (3 points): You were asked to run Octree algorithm to select palette colors. The specification tells you
to use level 1 and level 2 nodes of the tree, as opposed to level 2 and level 4 in MP2. If you must not have any holes
for any arbitrary image, and if 8 palette entries are reserved for special use as in MP2, how many level 2 nodes can be
assigned a palette entry?
Part E (3 points): After running the algorithm, you noticed that a level 1 node (100) and its child (100100)
represented in (RGB) and (RRGGBB) format were selected to be on the palette. You also observed that there are only
three pixels that belongs to the subtree rooted at (100). The following is a table that contains the value of the three
Pixel # R G B
1 1011 0100 0010
2 1000 0110 0101
3 1001 0110 0000
What are the R, G, B values stored in the palette entries that corresponds to the nodes (100) and (100100)?
Node R G B
Problem 3 (20 points): Virtual Memory
Part A (4 points): For each statement below, CIRCLE EITHER TRUE OR FALSE.
TRUE FALSE A system’s physical address space can be smaller than its virtual address space.
TRUE FALSE Two distinct programs that are running concurrently cannot both execute at the virtual addresses
between 0x42 MB and 0x46 MB.
TRUE FALSE Suppose that in a system’s memory layout, a 4 MB kernel page is mapped between 4 MB and
8 MB and the addresses after 8 MB are marked not present. If the kernel attempts to deference a
pointer at address 0x7FFFFF, there can be a page fault.
TRUE FALSE If the descriptor privilege level (DPL) is larger than max(current privilege level (CPL), requested
privilege level (RPL)), a general protection fault will be generated
Part B (12 points): Suppose that you want to design a new processor with 42-bit virtual addresses and 16-bit
addressability. In the paging scheme you designed, there are TWO layers of indirections, one using page directories
and one using page tables. The size of the smaller pages is 8 KB. The size of PDEs and PTEs are both 32-bits, but
the size of a page directory is FOUR TIMES the size of a page table. Unit of sizes in your answers should be KB,
1. (4 points) During paging, how many bits are used as offset into the 8 KB page? Justify your answer.
Problem 3, continued:
2. (4 points) What is the size of a page table in the design? Justify your answer.
3. (4 points) What is the size of the larger pages? Justify your answer.
Part C (4 points): Suppose that for the newly designed Illinix operating system, which is byte-addressable,
paging structures (page directories, page tables) must fit inside a single 8KB page, and the size of entries in the paging
structures is 32-bit. What is the minimum number of levels of indirection needed to translate a 46-bit virtual address
to the base address of a 8KB page?
Problem 4 (21 points): File System 10
Grace has been asked to modify the MP3 filesystem structure to support multiple directories. Specifically, her new
filesystem must support a single Superdirectory that can both contain subdirectories and files, while subdirectories can
contain only files.
A full description of Grace’s Filesystem is also included as an Appendix to this exam. Please TEAR IT OFF
AND READ IT THOROUGHLY before answering the questions below.
Part A (11 points): State your answer and show your work for any credit for the questions below. Assume that
the file system has unlimited memory resources. First write down your answer, then give a brief reasoning to justify
your answer using no more than 25 words. You will receive a 0 if you don’t have any reasoning to justify the answer.
1. What is the maximum number of files a subdirectory can store?
2. What is the maximum number of files the whole file system can store?
3. What is the maximum file size that this file system can store in bytes?
4. Assume this file system is storing maximum number of files, and each file is storing 8KB data. And this file
system will not have any spare empty unused blocks. What fraction of this total filesystem size is used to store
the actual data? (It’s enough to list the equation – E.g. (14+43) / 79 would be a valid answer)
Part B (4 points): Grace is trying to implement a search function to check whether a file exists in her filesystem.
She gets stuck trying to calculate the address of a subdirectory node given its index. Given the address FSP at which
the filesystem is loaded and the index IDX of the subdirectory node, fill in the blanks below to help Grace calculate the
address of the subdirectory node.
_________________ + _________________ x (_________________ + _________________)
Part C (6 points): Grace decided to use her file system to store her ECE391 notes so that she could brag about
it to the recruiter when they would have their followup call. Grace always begins her notes by noting down the
lecture number in the format ’Lecture #N’. Her boyfriend David, in an attempt of Halloween prank, corrupted
all the directory entries - in both the super directory block and the subdirectory nodes with garbage values in
Grace’s file system. Desperate to study about file systems for midterm 2, Grace asks for your help to recover her notes
for Lecture #16.
Is it possible to recover Grace’s notes for only Lecture #16? Circle one option.
NO YES, BUT ONLY PARTIALLY YES, COMPLETELY
Justify your choice above in no more than 40 words. You will receive a 0 if you don’t have any reasoning to justify
the answer.
Problem 5 (17 points): Scheduling
Part A (8 points): Basic Scheduling Algorithms
(1) Listed below is a table of processes with their associated arrival and run time.
Process ID Arrival Time Run Time
Please fill in the table below for different scheduling schemes (assume all processes have same priority level) (6
• First-In-First-Out (FIFO): system service processes in the same order as they arrive
• Round-Robin (RR): system service each process for a quantum then switch to the next one in the queue. RR1
stands for the RR with a quantum = 1, while RR5 stands for the RR with a quantum = 5.
• You can assume the context switch overhead is 0 for this part.
• If the process finishes before the current quantum ends, the system should wait until the next quantum begin
before switching process.
• When a new process arrives, it is put into the queue to wait for its chance to get executed.
• When multiple processes need to be queued at the same time, use alphabetical order to break the tie (i.e., From
Process A to G, A has the highest priority to be queued and G has the lowest priority.) For example at time
= 9, the arriving Process B, E, and F all need to be enqueued. According to the alphabetical order, B will be
enqueued first, and then E, and then F.
Time Slot FIFO RR1 RR5
(2) The time quantum of Round-Robin algorithm is a tunable parameter affecting CPU resource allocation. What can
you conclude about the relationship between the time quantum, the run time and arrival time of the processes, and the
order in which the processes complete?
1. When the time quantum is small (e.g., Round-Robin-1), the order in which the processes complete mainly de-
pends on (circle one of the following) (1 point):
- A. the arrival order of the processes
- B. the run time of the processes
2. When the time quantum is large (e.g, Round-Robin-5), the completion time of a process mainly depends on
(circle one of the following) (1 point):
- A. the arrival order of the processes
- B. the run time of the processes
Part B (9 points): Priority Scheduling
Some applications, such as real-time autonomous control systems, have a unique need to be responsive. These systems
often use a priority-based scheduling scheme, where higher priority tasks are allowed to preempt the execution of a
lower priority task. In this problem, we assume the tasks that run on the OS are periodic (Each task has a period Ti
associated with it, and the task gets scheduled once every Ti units of time). Each task is assigned a priority based on
how frequently it should be scheduled, the higher the frequency (i.e., the smaller the period) the higher the priority of
the task. When the scheduler chooses a task to schedule it looks for the highest priority task that can be scheduled and
schedules that task. The scheduler runs a task to completion or until a higher priority task is ready to be scheduled.
As an example, Table 1 lists two tasks (task I and task J) to be scheduled. Figure 1 below shows the resulted schedule
taking their priorities into account. This type of scheduling is known as priority scheduling.
Table 1: Priority Scheduling Example Task Info
Task Period Duration Priority
I 2ms 1ms P2
J 6ms 3ms P1
Figure 1: Priority Scheduling of task I and task J
Your Task:
Based on the example on the previous page, complete the table below for the three tasks A, B, C following priority
scheduling. Note that you should assign priorities to the three tasks such that P3 indicates the highest priority and P1
indicates the lowest priority. (2points)
Table 2: Priority Based Scheduling Problem
Task Period Duration Priority
B 12ms 4ms
Draw out the schedule of the three tasks A, B, C for 0ms ≤ t ≤ 14ms (7 points):
Appendix: You may tear off this page to use as reference, but must return it with your exam.
MP3 File System
Filesystem structure used in Problem 4. You may tear off this page, but must return it with your exam.
Data Structures used by Grace’s Filesystem
• Each block in the filesystem has a size of 1 kB (1024 bytes).
• The first block is called the Superdirectory block. The first 64 B of this block consists of metadata, such as the
numbers of subdirectory nodes, index nodes, and data blocks. It also contains the number of directory entries in
the Superdirectory. The first directory entry in the superdirectory always refers to the superdirectory itself.
• The format of the 64 B directory entries is shown above. Each directory entry contains:
– the name of the file/subdirectory
– the type of the directory entry:
* 0 - User level access to real-time clock (RTC)
* 1 - superdirectory
* 2 - file
* 3 - subdirectory
– The inode index if the entry is of type file, or the subdirectory index if the entry is of type subdirectory.
– The number of directory entries in the subdirectory node if the entry is of type subdirectory. These bytes
are unused otherwise.
• Each snode contains directory entries describing the files that the subdirectory contains. With the exception of
the first directory entry, which always refers to the subdirectory itself, the type of directory entries in the snodes
CANNOT be subdirectory nor superdirectory.
• Each inode contains 4 B entries, where the first entry has the length of the file in bytes, and the rest of the entries
are the indices of the data blocks.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com