Final -Summer 2015-Operating System – Solutions

Download  file with the answers

Final -Summer 2015-Operating System - Solutions

1 file(s)   1.49 MB

Not a member!
Create a FREE account here to get access and download this file with answers

03-60-330-01 Final Examination June 26, 2015
SCHOOL OF COMPUTER SCIENCE
OPERATING SYSTEM CONCEPTS (03-60-330-01)
FINAL EXAMINATION
TEST ID # 01 Duration: 03 hours
Student ID:
FIRST Name:
LAST Name:
Instructions:
1) This is a closed-book examination – NO notes or books or slides may be used.
2) Do not copy from other students or communicate in any way. All questions will be answered only by
the attending proctors.
3) Do not remove any papers from this booklet or add new ones. You may not remove any staples
holding this exam together.
4) You may not use any reference material(s) except what has been provided within this examination
booklet.
5) The examination must be surrendered immediately when the instructor announces the end of the test
period.
6) Each student must sign the examination exit list before leaving the classroom.
“I have neither given nor received unauthorized help with this examination. Any suspicion of cheating
will automatically void my mark on this examination”
________________________________________________________________________
(Signature)
Unsigned examination booklets will not be graded.
Signature implies agreement with the above statement in quotes.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 2 of 25 03-60-330-01 Final Examination
Part I (100 marks) – Multiple Choice Questions
All questions are Multiple Choice or True/False. In each Multiple Choice question, you are to choose only
one response which best answers the question. Use the Scantron sheet provided to indicate your answers. If
an error is made you must carefully erase the error and then fill in the circle you intend to choose. USE
PENCIL ONLY ON THE SCANTRON SHEET
1. Belady’s anomaly states that ____.
A) giving more memory to a process will improve its performance
B) as the number of allocated frames increases, the page-fault rate may decrease for all page
replacement algorithms
C) for some page replacement algorithms, the page-fault rate may decrease as the number of
allocated frames increases
D) for some page replacement algorithms, the page-fault rate may increase as the number of
allocated frames increases
2. Given the reference string of page accesses: 1 2 3 4 2 3 4 1 2 1 1 3 1 4 and a system with three page
frames, what is the final configuration of the three frames after the true LRU algorithm is applied?
A) 1, 3, 4 B) 3, 1, 4 C) 4, 1, 2 D) 1, 2, 3
3. 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 will be the final configuration
of the three frames following the execution of the given reference string?
A) 4, 1, 3 B) 3, 1, 4 C) 4, 2, 3 D) 3, 4, 2
4. The _____ allocation algorithm allocates available memory to each process according to its size.
A) equal B) global C) proportional D) slab
5. If the page-fault rate is too high, the process may have too many frames.
A) True B) False
6. Which of the following is a benefit of allowing a program that is only partially in memory to execute?
A) Programs can be written to use more memory than is available in physical memory.
B) CPU utilization and throughput is increased.
C) Less I/O is needed to load or swap each user program into memory.
D) All of the above
7. On a system with demand-paging, a process will experience a high page fault rate when the process
begins execution.
A) True B) False
8. The purpose of a Memory Management Unit is to ___________ .
A) perform run-time mapping from virtual to physical addresses
B) ensure protection of the memory space allocated to every process
C) Both A and B are correct responses.
D) None of these responses is correct.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 3 of 25 03-60-330-01 Final Examination
9. Absolute code can be generated for ____.
A) compile time binding B) load time binding
C) execution time binding D) interrupt binding
10. Which of the following methods of binding instructions and data to memory is performed by
most general-purpose operating systems?
A) interrupt binding B) compile time binding
C) execution time binding D) load time binding
11. An address generated by a CPU is referred to as a ____.
A) physical address B) logical address
C) post relocation register address D) Memory-Management Unit (MMU) generated address
12. In a dynamically linked library, ____.
A) loading is postponed until execution time
B) system language libraries are treated like any other object module
C) more disk space is used than the option of using a statically-linked library
D) a stub is included in the image for each library-routine reference
13. Which of the following dynamic storage-allocation algorithms results in the smallest
leftover hole in memory?
A) first fit B) best fit C) worst fit D) None of the above
14. One necessary condition for deadlock is ____, which states that at least one resource must
be held in a non-sharable mode.
A) hold and wait B) mutual exclusion C) circular wait D) no preemption
15. If a resource-allocation graph has a cycle, the system must be in a deadlocked state.
A) True B) False
16. A deadlocked state occurs whenever ____.
A) a process is waiting for I/O to a device that does not exist
B) the system has no available free resources
C) every process in a set is waiting for an event that can only be caused by another process in
the set
D) a process is unable to release its request for a resource after use
17. Which of the following is true of compaction?
A) It can be done at assembly, load, or execution time.
B) It is used to solve the problem of internal fragmentation.
C) It cannot shuffle memory contents.
D) It is possible only if relocation is dynamic and done at execution time.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 4 of 25 03-60-330-01 Final Examination
18. In a system resource-allocation graph, ____.
A) a directed edge from a process to a resource is called an assignment edge
B) a directed edge from a resource to a process is called a request edge
C) a directed edge from a process to resource is called a request edge
D) None of the above
19. A deadlock may occur if _____________ .
A) at least one resource remains in a sharable mode
B) a process holds at least one resource and is waiting to acquire additional resources held
by other processes
C) resources in the system can be preempted
D) None of the above responses is correct.
20. A cycle in a resource-allocation graph is _____________.
A) a necessary and sufficient condition for deadlock in the case that each resource has more than
one instance
B) a necessary and sufficient condition for a deadlock in the case that each resource has
exactly one instance
C) a sufficient condition for a deadlock in the case that each resource has more than once
instance
D) is neither necessary nor sufficient for indicating deadlock in the case that each
resource has exactly one instance
21. Which of the following is most often used by operating systems to handle deadlocks?
A) Pretend that deadlocks never occur B) Use protocols to prevent or avoid deadlocks
C) Detect and recover from deadlocks D) None of the above
22. Valid-Invalid bits are used to ______ .
A) denote existence of disk blocks B) trap illegal page addresses
C) permit access to process frames D) decide access to I/O devices
23. Suppose a computer is operating with execution-time binding and the physical address generated by
the CPU is 400. The relocation register is set to 200. What is the corresponding logical address?
A) 400 B) 600 C) 300 D) None of these responses is correct.
24. In order to solve the critical section problem it is necessary to satisfy the condition
that ________ .
A) No thread may be executing in its critical section if a thread is currently executing in
its critical section.
B) Only those threads that are not executing in their critical sections can participate in
the decision on which process will enter its critical section next.
C) A bound must exist on the number of times that other threads are allowed to enter their
critical state after a thread has made a request to enter its critical state.
D) All of the above.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 5 of 25 03-60-330-01 Final Examination
25. _______ refers to the situation where, for a set of processes, every process in the set
must be waiting for an event that can be caused only be another process in the set.
A) Deadlock B) Starvation C) Locking D) Blocking
26. A semaphore ____.
A) is essentially an integer variable
B) is accessed through only one standard operation
C) can be modified simultaneously by multiple threads
D) cannot be used to control access to a thread’s critical sections
27. The resource allocation graph below _______
A) contains a cycle, but it is not deadlocked B) contains a cycle and it is deadlocked
C) contains no cycles and is not deadlocked D) contains no cycles and is deadlocked
28. One way to ensure that a circular-wait condition never holds is to _________ ?
A) apply a deadlock prevention policy.
B) assign each resource type a unique integer number to distinguish those occurring at the
same time in the ordering.
C) impose a total ordering of all resource types and to require that each process requests
resources in an increasing order of enumeration.
D) None of these responses is correct.
29. A race condition ____.
A) results when several threads try to access the same data concurrently
B) results when several threads try to access and modify the same data concurrently
C) will result only if the outcome of execution does not depend on the order in which
instructions are executed
D) None of the above
30. An instruction that executes atomically ____.
A) must consist of only one machine instruction
B) executes as a single, uninterruptible unit
C) cannot be used to solve the critical section problem
D) All of the above
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 6 of 25 03-60-330-01 Final Examination
31. The Producer-Consumer problem is related to _________ .
A) the handling of process control blocks B) the scheduling of process states
C) the allocation of resources to process states D) Both A and C are correct answers.
32. A spinlock ____.
A) is never advantageous
B) will ultimately result in a context switch when a process must wait on a lock
C) does not require a context switch when a process must wait on a lock
D) is useful when locks are expected to be held for long amounts of time
33. A _________ is issued if a desired page is not in main memory.
A) paging error B) page replacement policy
C) page fault D) page placement policy
34. Medium-term scheduling is performed _________ .
A) typically on submitted jobs
B) when processes must be moved from waiting to ready state
C) on processes in the ready queue
D) None of the above are correct.
35. _______ scheduling is approximated by predicting the next CPU burst with an exponential average of
the measured lengths of previous CPU bursts.
A) Multilevel queue B) RR C) FCFS D) SJF
36. Which of the following scheduling algorithms must be nonpreemptive?
A) SJF B) RR C) FCFS D) priority algorithms
37. To overcome the problem of doubling the memory access time, most virtual memory schemes make
use of a special high-speed cache for page table entries called a __________ .
A) kernel memory allocator B) lazy swapper
C) translation lookaside buffer (TLB) D) hashed page table
38. Which of the following is true of cooperative scheduling?
A) It requires a timer.
B) A process keeps the CPU until it releases the CPU either by terminating or by switching to
the waiting state.
C) It incurs a cost associated with access to shared data.
D) A process switches from the running state to the ready state when an interrupt occurs.
39. Long-term scheduling is performed _________ .
A) typically on submitted jobs
B) when processes must be moved from waiting to ready state
C) on processes in the ready queue
D) All of the above are correct.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 7 of 25 03-60-330-01 Final Examination
40. Which of the following is true of multilevel queue scheduling?
A) Processes can move between queues.
B) Each queue has its own scheduling algorithm.
C) A queue cannot have absolute priority over lower-priority queues.
D) It is the most general CPU-scheduling algorithm.
41. In scheduling, the term Aging involves ___________ .
A) higher priority processes preventing low-priority processes from ever getting the CPU.
B) gradually increasing the priority of a process so that a process will eventually execute.
C) processes that are ready to run but stuck waiting indefinitely for the CPU.
D) processes being stuck in ready queues so long that they die.
42. In RR scheduling, the time quantum should not be _________ the context-switch time.
A) small with respect to B) large with respect to
C) the same size as D) irrelevant to
43. Aging can only be implemented if ________ scheduling is used by an operating system.
A) round robin B) priority
C) shortest job first – nonpreemptive D) exponential predictive
44. Assume the following processes, each with their arrival time and burst time.
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
For SJF Non-Preemptive job scheduling, the average waiting time is
A) 3 B) 4 C) 7.5 D) 10
45. A circular queue is the most appropriate data structure for ______ scheduling.
A) RR B) FCFS C) SJF D) Priority
46. Assume the following processes arrive at time 0, for Round Robin (RR) job scheduling with
time quantum equal to 4, the average waiting time is
Process Burst Time
P1 3
P2 24
P3 3
P4 8
A) 8.0 B) 7.25 C) 8.75 D) 9.75
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 8 of 25 03-60-330-01 Final Examination
47. __________ involves the decision of which kernel thread to schedule onto which CPU.
A) Process-contention scope B) System-contention scope
C) Dispatcher D) Round-robin scheduling
48. A significant problem with priority scheduling algorithms is _____.
A) complexity B) determining the length of the next CPU burst
C) starvation D) determining the length of the time quantum
49. One necessary condition for deadlock is ______, which states that there is a chain of waiting
processes whereby P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2,
and Pn is waiting for a resource held by P0.
A) hold and wait B) mutual exclusion
C) circular wait D) no preemption
50. What is the purpose of the mutex semaphore in the implementation of the bounded-buffer problem
using semaphores?
A) It indicates the number of empty slots in the buffer.
B) It indicates the number of occupied slots in the buffer.
C) It controls access to the shared buffer.
D) It ensures mutual exclusion.
51. Which of the following statements is true?
A) A counting semaphore can never be used as a binary semaphore.
B) A binary semaphore can never be used as a counting semaphore.
C) Spinlocks can be used to prevent busy waiting in the implementation of semaphore.
D) Counting semaphores can be used to control access to a resource with a finite number of
instances.
52. Assume the value of the 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
53. In most computers a hardware mode bit with a timer counter is required to ensure that the O/S
______ .
A) can switch between kernel and user process B) can react to events
C) is able to time processes accurately D) is able to log information correctly
54. _____ is the dynamic storage-allocation algorithm which results in the largest leftover hole in
memory.
A) First fit B) Best fit C) Worst fit D) None of the above
55. Optimal page replacement ____.
A) is the page-replacement algorithm most often implemented.
B) is used mostly for comparison with other page-replacement schemes.
C) can suffer from Belady’s anomaly.
D) requires that the system keep track of previously used pages.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 9 of 25 03-60-330-01 Final Examination
56. The two modes of operation of an operating system are called ___________ .
A) process and kernel B) ready and running
C) interrupt and system D) kernel and user
57. In multiprocessor environments, two copies of the same data may reside in the local cache of each
CPU. Whenever one CPU alters the data, the cache of the other CPU must receive an updated
version of this data. This is called Cache _________ .
A) redundancy B) integrity C) coherency D) normalization
58. When a child process is created, which of the following is a possibility in terms of the execution or
address space of the child process?
A) The child process runs concurrently with the parent.
B) The child process has a new program loaded into it.
C) The child is a duplicate of the parent.
D) All of the above
59. A ___________ can be used to prevent a user program from never returning control to the operating
system.
A) portal B) program counter C) firewall D) timer
60. Two important design issues for cache memory are ____.
A) speed and volatility B) size and replacement policy
C) power consumption and reusability D) size and access privileges
61. CPU registers are often used to ________ .
A) save memory for storing programs B) store values for reuse by other user programs
C) pass parameters to the operating system D) All of the above responses are correct.
62. Thread-specific data is data that ____.
A) is not associated with any process
B) has been modified by the thread but not yet updated to the parent process
C) is copied and not shared with the parent process
D) is generated by the thread independent of the thread’s process
63. When a process creates a new process using the fork() operation, which of the following states is
shared between the parent process and the child process?
A) Stack B) Shared memory segments
C) Heap D) Process Control Block
64. The __________ structure indexes page table entries by frame number rather than by virtual page
number.
A) hash table B) segment table C) page table D) inverted page table
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 10 of 25 03-60-330-01 Final Examination
65. Dispatch latency _____________
A) is also called switching context
B) is the time it takes for the dispatcher to stop one process and start another running
C) happens when two processes communicate through message passing
D) is context switching between processes is carried out by the interrupt handler
66. The addresses a program may use to reference memory are distinguished from the addresses the
memory system uses to identify physical storage sites.
A) True B) False
67. A message-passing model is ____.
A) easier to implement than a shared memory model for intercomputer communication
B) faster than the shared memory model
C) a network protocol, and does not apply to operating systems
D) only useful for small simple operating systems
68. The major difficulty in designing a layered operating system approach is ____.
A) debugging a particular layer
B) making sure that each layer hides certain data structures, hardware, and operations from higherlevel
layers
C) appropriately defining the various layers
D) making sure each layer is easily converted to modules
69. A microkernel is a kernel ____.
A) containing many components that are optimized to reduce resident memory size
B) that is compressed before loading in order to reduce its resident memory size
C) that is compiled to produce the smallest size possible when stored to disk
D) that is stripped of all nonessential components
70. An I/O-bound process _________ .
A) spends equal time seeking I/O operations and doing computational work
B) spends more of its time doing computational work than seeking I/O operations
C) spends more of its time seeking I/O operations than doing computational work
D) spends less of its time seeking I/O operations than doing computational work
71. The ____ of a process contains temporary data such as function parameters, return addresses, and
local variables.
A) text section B) stack C) program counter D) data section
72. A process control block ____.
A) includes information on the process’s state
B) stores the address of the next instruction to be processed by a different process
C) determines which process is to be executed next
D) is an example of a process queue
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 11 of 25 03-60-330-01 Final Examination
73. The following are valid process states, including extensions to the 5-state basic model.
A) Next, Running, Halting B) Terminating, Waiting, Threshing
C) Running, Blocked, Waiting D) None of these responses is correct
74. _____ is/are not a technique for passing parameters from an application to a system call.
A) Cache memory B) Registers C) Stack D) Special block in memory
75. A file is ___________ .
A) a logical storage unit that is an abstraction from the physical properties of its storage device
B) a named collection of related information that is recorded on secondary storage
C) the smallest allotment of logical secondary storage allowed to a user
D) All of the above responses are correct.
76. An operating system may be viewed as a resource allocator of such things as CPU time, memory
space, file-storage space, I/O devices, and so on, due to the requirement that _________________ .
A) such things need to allocated to be useful for operating systems to work
B) conflicts of resource usage must not be permitted to happen
C) computer users must be satisfied that resources are available on request
D) resources be used efficiently by users
77. When a process is accessing its stack space, it exists in the _________ .
A) Running state B) Waiting state C) Terminating state D) Ready state
78. When a process performs I/O, its PCB is moved to the ________ .
A) Ready queue B) Wait queue C) Terminate queue D) Running queue
79. Remove processes from main memory then its execution can be continued where it left off after
reintroducing into memory is called ___________.
A) dispatcher B) swapping C) context switching D) All of the above
80. A shared memory model is ____.
A) context switching
B) a mechanism of storing process state information in process control block
C) an interprocess communication model
D) Symmetric Multiprocessing
81. The _____________ refers to the number of processes in memory.
A) process count B) long-term scheduler
C) degree of multiprogramming D) CPU scheduler
82. A process may transition to the Ready state by which of the following actions?
A) Completion of an I/O event B) Awaiting its turn on the CPU
C) Newly-admitted process D) All of the above
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 12 of 25 03-60-330-01 Final Examination
83. In a(n) ____ temporary queue, the sender must always block until the recipient receives the
message.
A) zero capacity B) variable capacity
C) bounded capacity D) unbounded capacity
84. A blocking send() and blocking receive() is known as a(n) _________________
A) synchronized message B) rendezvous
C) blocked message D) asynchronous message
85. In the Dynamic Partitioning technique of memory management, the placement algorithm that
chooses the block that is closest in size to the request is called __________ .
A) first-fit B) best-fit C) last-fit D) next-fit
86. In a system employing a paging scheme for memory management wasted space is due to
_________ .
A) internal fragmentation B) pages of different specified sizes
C) external fragmentation D) frames of different specified sizes
87. In the context of operating systems, the term Mechanism ____________.
A) determines how to do something B) determines what will be done
C) is not likely to change across places D) is not likely to change over time
88. Which of the following statements is true?
A) Shared memory is typically faster than message passing.
B) Message passing is typically faster than shared memory.
C) Message passing is most useful for exchanging large amounts of data.
D) Shared memory is far more common in operating systems than message passing.
89. The ____ multithreading model multiplexes many user-level threads to a smaller or equal number of
kernel threads.
A) many-to-one model B) one-to-one model
C) many-to-many model D) one-to-many model
90. A _____ uses an existing thread — rather than creating a new one — to complete a task.
A) lightweight process B) thread pool
C) scheduler activation D) asynchronous procedure call
91. _____ provide(s) an interface to the services provided by an operating system.
A) Shared memory B) System calls C) Simulators D) Communication
92. One technique for overcoming external fragmentation is __________ .
A) loading B) compaction
C) relocation D) partitioning
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 13 of 25 03-60-330-01 Final Examination
93. Turnaround time refers to the amount of time ______.
A) that CPU utilization is minimized
B) it takes from when a request was submitted until the first action is produced
C) a process has been waiting in the ready queue
D) needed to execute a particular process
94. A circular queue is the most appropriate data structure for ______ scheduling.
A) RR
B) FCFS
C) SJF
95. Context switching between processes is carried out by the__________ ..
A) dispatcher
B) short term scheduler
C) interrupt handler
D) thread manager
96. Nonpreemptive scheduling ensures
A) a process to be interrupted in the midst of its execution, taking the CPU away and
allocating it to another process.
B) that a process relinquishes control of the CPU only when it finishes with its
current CPU burst.
C) Both A and B
D) None of the above are correct.
97. Aging can only be implemented if ________ scheduling is used by an operating system.
A) round robin
B) priority
C) shortest job first – nonpreemptive
D) exponential predictive
For Questions 98 and 99, assume the following processes, each with their arrival time and burst time.
Process Arrival Time Burst Time
P1 0.0 8
P2 2.0 2
P3 4.0 1
P4 5.0 4
P5 6.0 3
98. For SJF Non-Preemptive job scheduling, the average waiting time is
A) 4.6 B) 5.0
C) 5.2 D) 5.4
99. For FCFS job scheduling, the average waiting time is _______.
A) 5.6 B) 5.4
C) 4.75 D) 5.2
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 14 of 25 03-60-330-01 Final Examination
100. Which of the following is true of cooperative scheduling?
A) It requires a timer.
B) A process keeps the CPU until it releases the CPU either by terminating or by
switching to the waiting state.
C) It incurs a cost associated with access to shared data.
D) A process switches from the running state to the ready state when an interrupt occurs.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 15 of 25 03-60-330-01 Final Examination
Part II (100 marks) – Comprehensive
101. Assume a program has just referenced an address in virtual memory. Describe a scenario how each
of the following can occur: (If a scenario cannot occur, explain why.)
• TLB miss with no page fault (2.5 marks)
• TLB miss and page fault (2.5 marks)
• TLB hit and no page fault (2.5 marks)
• TLB hit and page fault (2.5 marks)
Answer:
• TLB miss with no page fault page has been brought into memory, but has been removed from the
TLB
• TLB miss and page fault page fault has occurred
• TLB hit and no page fault page is in memory and in the TLB. Most likely a recent reference
• TLB hit and page fault cannot occur. The TLB is a cache of the page table. If an entry is not in the
page table, it will not be in the TLB.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 16 of 25 03-60-330-01 Final Examination
102. Consider the following page reference string:
7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0 , 1.
Assuming demand paging with three frames, how many page faults would occur for the following
replacement algorithms?
• LRU replacement (3 marks)
• FIFO replacement (4 marks)
• Optimal replacement (3 marks)
Answer:
• 18
• 17
• 13
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 17 of 25 03-60-330-01 Final Examination
103. Explain the difference between internal and external fragmentation.
Answer: (5 marks for ‘internal’ and 5 marks for ‘external’)
• Internal fragmentation is the area in a region or a page that is not used by the job occupying that
region or page. This space is unavailable for use by the system until that job is finished and the
page or region is released.
• External fragmentation is unused space between allocated regions of memory. Typically external
fragmentation results in memory regions that are too small to satisfy a memory request, but if we
were to combine all the regions of external fragmentation, we would have enough memory to
satisfy a memory request.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 18 of 25 03-60-330-01 Final Examination
104. What is the purpose of paging the page tables?
Answer:
In certain situations the page tables could become large enough that by paging the page tables, one could
simplify the memory allocation problem (by ensuring that everything is allocated as fixed-size pages
as opposed to variable-sized chunks) and also enable the swapping of portions of page table that are not
currently used.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 19 of 25 03-60-330-01 Final Examination
105. Consider a system consisting of four resources of the same type that are shared by three processes,
each of which needs at most two resources. Show that the system is deadlock-free.
Answer:
Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting
for one more. Since there are three processes and four resources, one process must be able to obtain two
resources. This process requires no more resources and, therefore it will return its resources when done.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 20 of 25 03-60-330-01 Final Examination
106. Why is it important for the scheduler to distinguish I/O-bound programs from CPU-bound programs?
Answer:
I/O-bound programs have the property of performing only a small amount of computation before
performing I/O. Such programs typically do not use up their entire CPU quantum. CPU-bound programs,
on the other hand, use their entire quantum without performing any blocking I/O operations.
Consequently, one could make better use of the computer’s resources by giving higher priority to I/Obound
programs and allow them to execute ahead of the CPU-bound programs.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 21 of 25 03-60-330-01 Final Examination
107. Explain why interrupt and dispatch latency times must be bounded in a hard real-time system.
Answer: (5 marks for ‘interrupt’ and 5 marks for ‘dispatch’)
Interrupt latency time is the time it takes to: save the currently executing instruction, determine the type
of interrupt, save the current process state, and then invoke the appropriate interrupt service routine.
Dispatch latency time is the time associated with stopping one process and starting another. Both
interrupt and dispatch latency needs to be minimized in order to ensure that real-time tasks receive
immediate attention. Furthermore, sometimes interrupts are disabled when kernel data structures are
being modified, so the interrupt does not get serviced immediately. For hard real-time systems, the timeperiod
for which interrupts are disabled must be bounded in order to guarantee the desired quality of
service.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 22 of 25 03-60-330-01 Final Examination
108. Race conditions are possible in many computer systems. Consider a banking system with two
methods: deposit(amount) and withdraw(amount). These two methods are passed the
amount that is to be deposited or withdrawn from a bank account. Assume that a husband and wife
share a bank account and that concurrently the husband calls the withdraw() method and the wife
calls deposit(). Describe how a race condition is possible and what might be done to prevent the
race condition from occurring. Assume the balance in the account is 250$ and the husband calls
withdraw(50$) and the wife calls deposit(100$).
Answer:
Assume the balance in the account is 250 and the husband calls withdraw(50) and the wife calls
deposit(100). Obviously the correct value should be 300. Since these two transactions will be
serialized, the local value of balance for the husband becomes 200, but before he can commit the
transaction, the deposit(100) operation takes place and updates the shared value of balance to
300. We then switch back to the husband and the value of the shared balance is set to 200 – obviously an
incorrect value.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 23 of 25 03-60-330-01 Final Examination
109. Explain why interrupts are not appropriate for implementing synchronization primitives in
multiprocessor systems.
Answer:
Interrupts are not sufficient in multiprocessor systems since disabling interrupts only prevents other
processes from executing on the processor in which interrupts were disabled; there are no limitations on
what processes could be executing on other processors and therefore the process disabling interrupts
cannot guarantee mutually exclusive access to program state.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 24 of 25 03-60-330-01 Final Examination
110. Which of the following components of program state are shared across threads in a multithreaded
process?
a. Register values
b. Heap memory
c. Global variables
d. Stack memory
Answer: (2.5 marks for each correct answer)
The threads of a multithreaded process share heap memory and global variables. Each thread has its
separate set of register values and a separate stack.
________________________ ________________________ _________________________
(First Name) (Last Name) (Student ID)
2015 IS 25 of 25 03-60-330-01 Final Examination
This page was left intentionally blank.