109成大電機計系[參考解答]

1. Designed the following cache system:
   For a cache of 32KB and 32-byte line size and the cacheable address space is 4GB, show the cache for a 4-way set associative design. (10%)
   
   參考解答：
   
   $\quad$
2. Show the datapath of implementing a load word instruction in the form of “lw rt, offset(rs).” (10%)
   
   參考解答：
   
   $\quad$
3. A MIPS conditional branch instruction is given in the form of “beq r1, r2, $L_{1}$” and in ARM’s assembly is done by: cmp r1, r2, followed by beq $L_{1}.$ Which of the following is(are) true? (10%)
   (a) To get the binary machine code of beq, the value of $L_{1}$ is computed by the assembler when $L_{1}$ is an external reference.
   (b) To get the binary machine code of beq, the value of $L_{1}$ is computed by the linker when $L_{1}$ is an external reference.
   (c) cmp sets the comparison result in register r1.
   (d) cmp sets the comparison result in a condition code register.
   
   參考解答：B, D
   $\quad$
4. About virtual memory, which of the following is(are) true? (10%)
   (a) A memory protection violation is raised by the MMU unit.
   (b) Swap space is the portion of virtual memory that is on the hard disk or SSD, used when RAM is full.
   (c) A program can be invoked by the operating system into different instances of processes.
   (d) The space on the disk or flash memory reserved for the full physical memory space of a process is called swap space.
   
   參考解答：A
   $\quad$
5. About I/O, which of the following is(are) true? (10%)
   (a) Programmed I/O is a method of transferring data between the CPU and a peripheral where each data item transfer is initiated by an instruction in the program, involving the CPU for every transaction.
   (b) Programmed I/O is performed by the DMA controller which executes the I/O commands.
   (c) A DMA controller is typically programmed by the host CPU for its operation.
   (d) A DMA controller has a bus master and slave interface and performs I/O operation by itself.
   
   參考解答：A, D
   $\quad$
6. Describe how a translation look-aside buffer(TLB) assists in the translation of a logical address to a physical address.
   
   參考解答：TLB is a special cache used to keep track of recent used transactions. TLB containing page table entries that have been most recently used. Given a virtual address, the processor examines the TLB if a page table entry is present, the frame number is retrieved and the real address is formed. If TLB miss, the page number is used as index while processing page table.
   $\quad$
7. Explain the distinction between a demand-paging system and a paging system with swapping.
   
   參考解答：
   (1) Only load pages that are demanded by the executing process.
   (2) As there is more space in memory, more process can be loaded, thus reduce the context switch penalty.
   (3) Less loading latency.
   $\quad$
8. Multiple Choice Questions 40%
   (1) _____ provide(s) an interface to the services provided by an operating system.
   (A) Shared memory
   (B) System calls
   (C) Simulators
   (D) Communication
   
   (2) _____ is a mobile operating system designed for the iPhone and iPad.
   (A) Mac OS X
   (B) Android
   (C) UNIX
   (D) iOS
   
   (3) Which of the following cases could force a process removed from the CPU?
   (A) I/O request
   (B) fork a child
   (C) interrupt or time slice expired
   (D) all of the above
   
   (4) If process P0 is switched to process P1, state for P0 will be saved into _____, and state from _____ will be reloaded?
   (A) PCB0, PCB0
   (B) PCB0, PCB1
   (C) PCB1, PCB0
   (D) PCB1, PCB1
   
   (5) Assume the shared buffer is implemented as a circular array with two logical pointers: in and out. The variable in points to the next free position in the buffer; out points to the first full position in the buffer. Which of the following is true?
   (A) The buffer is empty when in == out; the buffer is full when ((in + 1) % BUFFER_SIZE) == out;
   (B) The buffer is full when in == out; the buffer is empty when ((in + 1) % BUFFER_SIZE) == out;
   (C) All the elements of the buffer can be used;
   (D) Both A and C
   
   (6) In a multithreaded server architecture, which of the following is used to service a new user request?
   (A) a new created thread
   (B) a new created process
   (C) the same process for prior users
   (D) none of the above
   
   (7) In multithreaded programs, the kernel informs an application about certain events using a procedure known as a(n) _____.
   (A) signal
   (B) upcall
   (C) event handler
   (D) pool
   
   (8) The _____ occurs in first-come-first-served scheduling when a process with a long CPU burst occupies the CPU.
   (A) dispatch latency
   (B) waiting time
   (C) convoy effect
   (D) system-contention scope
   
   (9) Which of the following is preemptive?
   (A) rate-monotonic scheduling
   (B) earliest-deadline-first scheduling
   (C) both of the above
   (D) none of the above
   
   (10) Which of the following is true for the solutions to critical-section problems?
   (A) No deadlock implies progress, and progress implies bounded waiting
   (B) Bounded waiting implies progress, and progress implies no deadlock
   (C) Progress implies no deadlock, and no deadlock implies bounded waiting
   (D) Bounded waiting implies no deadlock, and no deadlock implies progress
   
   (11) Which of the following is NOT true regarding semaphore implementation?
   (A) It suffers from the busy waiting problem
   (B) Semaphore has a waiting queue associated with the semaphore
   (C) When a process executes the wait() operation and finds that the semaphore value is not positive, it will suspend itself
   (D) A process that is suspended, waiting on the semaphore, should be restarted when some other process executes a signal() operation.
   
   (12) Which of the following is true about the two versions of readers-writers problem?
   (A) In the first readers-writers problem, a writer may starve if a continuous series of readers arrive before the earlier readers exit their critical section.
   (B) In second readers-writers problem, a reader may starve if a continuous series of readers arrive before the earlier readers exit their critical section.
   (C) In the first readers-writers problem, a writer may starve if a continuous series of writers arrive before the earlier writers exit their critical section.
   (D) In the second readers-writers problem, a writer may starve if a continuous series of readers arrive before the earlier readers exit their critical section.
   
   (13) In an asymmetric solution for the dining philosophers problem, deadlock is avoided, because
   (A) there is no contention for acquiring chopsticks.
   (B) neighboring philosophers will never get hungry at the same time.
   (C) any neighboring philosophers would have already acquired one of their chopsticks before attempting to acquire the shared chopstick.
   (D) a philosopher will release a chopstick in case she is unable to acquire the other chopstick.
   
   (14) Deadlocks can be prevented only if
   (A) all four necessary conditions cannot hold.
   (B) at least one of the four necessary conditions cannot hold.
   (C) mutual exclusion condition cannot hold.
   (D) circular wait condition cannot hold.
   
   (15) Suppose that there are ten resources available to three processes. At time 0, the following data is collected. The table indicates the process, the maximum number of resources needed by the process, and the number of resources currently owned by each process.
   
   Process Maximum Needs Currently Owned
   

   P0	10	4
   P1	3	1
   P2	5	4

   
   At time 1, P1 requests a resource. Which of the following is correct?
   (A) The request will be granted, since the current state is safe.
   (B) The request will not be granted, since the current state is not safe.
   (C) The request will be granted, since the state after granting the request will be safe.
   (D) The request will not be granted, since the state after granting the request will be unsafe.
   
   (16) Assume the value of base and limit registers are 1200 and 350 respectively. Which of the following addresses is legal?
   (A) 355
   (B) 1200
   (C) 1551
   (D) all of the above
   
   (17) Given the logical address 0xAEF9 (in hexadecimal) with a page size of 256 bytes, what is the page number?
   (A) 0xAE
   (B) 0xF9
   (C) 0xA
   (D) 0x00F9
   
   (18) An advantage of virtual memory is that
   (A) a program can be much larger than the size of physical memory.
   (B) the programmers can concentrate programming the problem instead of worrying about the amount of physical memory available.
   (C) it provides a way to execute a program that is only partially loaded in memory.
   (D) All of the above.
   
   (19) The dirty (modify) bit identifies
   (A) a page that has been corrupted.
   (B) a page that needs to be reloaded when accessed.
   (C) a page that is shared by multiple processes.
   (D) a page that has been modified since it was loaded.
   
   (20) Suppose we have the following page accesses: 1 2 3 4 2 3 4 1 2 1 1 3 1 4 and that there are three frames within our system. Using the FIFO replacement algorithm, what is the number of page faults for the given reference string?
   (A) 14
   (B) 8
   (C) 13
   (D) 10
   
   參考解答：
   (1) B (2) D (3) D (4) B (5) A (6) A (7) C (8) C (9) C (10) 略 (11) A (12) A (13) C (14) B (15) D (16) B (17) A (18) D (19) D (20) B
   

試題(pdf)：連結

有任何問題，或想要完整解釋的，歡迎在下方留言唷！