| Question | Answer |
| In a system resource-allocation graph, ____. | a directed edge from a process to a resource is called a request edge |
| _____ occurs when a process spends more time paging than executing. | Thrashing |
| A significant problem with priority scheduling algorithms is _____. | Starvation |
| The first readers-writers problem ____. | requires that no reader will be kept waiting unless a writer has already obtained permission to use the shared database. |
| Monitors are a theoretical concept and are not practiced in modern programming languages | False |
| Windows uses a local page replacement policy _____. | when a process exceeds its working set maximum |
| List at least two possible parts of a program that may be assigned separate segments. | Code, Global variables, The heap, Stacks for each thread, Standard C Library |
| The wait-for graph scheme is not applicable to a resource allocation system with multiple instances of each resource type. | True |
| Assume a system has a TLB hit ratio of 90%. It requires 15 nanoseconds to access the TLB, and 85 nanoseconds to access main memory. What is the effective memory access time in nanoseconds for this system? | 108.5 |
| ____ scheduling is approximated by predicting the next CPU burst with an exponential average of the measured lengths of previous CPU bursts. | SJF |
| What scheduling algorithm assigns the CPU to the process with the shortest burst? | Shortest Job First (SJF) |
| The buddy system for allocating kernel memory is very likely to cause fragmentation within the allocated segments. | True |
| Which of the following is true of multilevel queue scheduling? | Each queue has its own scheduling algorithm. |
| The Linux CFS scheduler identifies _____________ as the interval of time during which every runnable task should run at least once. | targeted latency |
| A system in an unsafe state will ultimately deadlock. | False |
| In Solaris, what is the time quantum (in milliseconds) of an interactive thread with priority 35? | 80 |
| In Peterson's solution, the ____ variable indicates if a process is ready to enter its critical section. | flag[i] |
| Suppose that there are 10 resources available to three processes. Which of the following correctly characterizes this state?
Process Maximum Needs Currently Owned
P0 10 4
P1 3 1
P2 6 4 | It is not safe. |
| The Linux operating system does not rely on segmentation and uses it minimally. | True |
| Load balancing algorithms have no impact on the benefits of processor affinity. | False |
| Deadlock prevention and deadlock avoidance are essentially the same approaches for handling deadlock. | False |
| In Little's formula n = λ x W, what does λ represent ? | average arrival rate for new processes in the queue |
| Which of the following data structures is appropriate for placing into its own segment? | all of the above |
| Assume there are three resources, R1, R2, and R3, that are each assigned unique integer values 15, 10, and 25, respectively. What is a resource ordering which prevents a circular wait? | R2, R1, R3. |
| When using semaphores, a process invokes the wait() operation before accessing its critical section, followed by the signal() operation upon completion of its critical section. Consider reversing the order of these two operations—first calling signal(), t | Several processes could be active in their critical sections at the same time. |
| How many writers may concurrently share the database with the readers-writers problem? | one |
| Semaphores can provide the same functionality as mutex locks. | True |
| Name at least one modern programming language that has incorporated the idea of a monitor. | Java |
| Systems in which memory access times vary significantly are known as __________. | non-uniform memory access |
| Round-robin (RR) scheduling degenerates to first-come-first-served (FCFS) scheduling if the time quantum is too long. | True |
| What does each entry in the page table contain? | The base address of each page in physical memory. |
| What are the names of the two processes associated with the bounded-buffer problem? | Producer and Consumer |
| The multilevel feedback queue scheduling algorithm allows processes to migrate between different queues. | True (multilevel feedback scheduling != multilevel scheduling) |
| With _______ a thread executes on a processor until a long-latency event (i.e. a memory stall) occurs. | coarse-grained multithreading |
| A relocation register is used to check for invalid memory addresses generated by a CPU. | False |
| ____________ occurs when a higher-priority process needs to access a data structure that is currently being accessed by a lower-priority process. | Priority Inversion |
| In general, virtual memory decreases the degree of multiprogramming in a system. | False |
| Which of the following statements is false with regard to allocating kernel memory? | Because the kernel requests memory of varying sizes, some of which may be quite small, the system does not have to be concerned about wasting memory. |
| How many philosophers at most may eat simultaneously in the Dining Philosophers problem with 5 philosophers? | 2 |
| Every object in Java has associated with it a single lock. | True |
| Which of the following is a benefit of allowing a program that is only partially in memory to execute? | All of the above |
| What is available in Linux for updating an integer variable without having to use locks? | atomic_t type, atomic integers. |
| Mutex locks and binary semaphores are essentially the same thing. | True |
| A semaphore ____. | is essentially an integer variable |
| A deadlocked state occurs whenever ____. | every process in a set is waiting for an event that can only be caused by another process in the set |
| What are the four necessary conditions for characterising deadlock? | Mutual exclusion, Hold and wait, No preemption, Circular wait |
| What are the two functions used with mutex locks? | acquire() and release() |
| Windows XP, when accessing a global variable on a uniprocessor system, ____. | masks interrupts for all interrupt handlers that may also access the variable |
| What is the term for describing the situation where shared data may be manipulated concurrently and the outcome of the execution depends upon the order of access? | Race Condition |
| In practice, most systems implement an approximation of the _____ page-replacement algorithm. | LRU |
| Given the logical address 0xAEF9 (in hexadecimal) with a page size of 256 bytes, what is the page offset? | 0xF9 |
| Which of the following is true of cooperative scheduling? | A process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state. |
| A schedule in which each transaction is executed atomically is called a(n) ____. | serial schedule |
| Fragmentation does not occur in a paging system. | False |
| A spinlock ____. | does not require a context switch when a process must wait on a lock |
| _____ can be used to prevent busy waiting when implementing a semaphore. | Waiting queues |
| What two registers can be used to provide a simple form of memory protection? | Relocation register, Limit register |
| Consider a 32-bit address for a two-level paging system with an 8 KB page size. The outer page table has 1024 entries. How many bits are used to represent the second-level page table? | 9 |
| What is the hardware device that maps virtual to physical addresses? | Memory Management Unit (MMU) |
| Virtualization does not allow a single-CPU system to appear as a multiprocessor system. | False |
| A binary semaphore is functionally equivalent to a mutex lock. | True |
| Another problem related to deadlocks is ____________. | indefinite blocking |
| One necessary condition for deadlock is ______, which states that a resource can be released only voluntarily by the process holding the resource. | no preemption |
| Which of the following data structures in the banker's algorithm is a vector of length m, where m is the number of resource types? | Available |
| Suppose a program is operating with execution-time binding and the physical address generated is 300. The relocation register is set to 100. What is the corresponding logical address? | 200 |
| In the enhanced second chance algorithm, which of the following ordered pairs represents a page that would be the best choice for replacement? | 0,0 |
| In preemptive scheduling, the sections of code affected by interrupts must be guarded from simultaneous use. | True |
| Reentrant code cannot be shared. | false |
| What scheduling algorithm assigns the CPU to the process with the highest priority? | Priority Scheduling |
| The wait-for graph can only be used for deadlock detection when there is a single instance of each type. | True |
| A 32-bit logical address with 8 KB page size will have 1,000,000 entries in a conventional page table. | False |
| Which of the following is true of earliest-deadline-first (EDF) scheduling algorithm? | When a process becomes runnable, it must announce its deadline requirements to the system. |
| Fragmentation can still occur in paging systems. | True. Internal fragmentation can occur. External cannot. |
| Which of the following is considered a benefit when using the slab allocator? | no memory fragmentation |
| What are frame protection bits? | They are associated with each frame, normally kept in the page table. A bit can define a page as read-write, or read only, or extended for a finer level of protection. Additionally, one bit is generally a valid-invalid bit, used to differentiate between l |
| In Little's formula n = λ x W, what does W represent? | average waiting time in the queue |
| What size segment will be allocated for a 39 KB request on a system using the Buddy system for kernel memory allocation? | 64KB |
| An address generated by a CPU is referred to as a ____. | logical address |
| Hashed page tables are commonly used when handling addresses larger than 32 bits. | True |
| Load balancing is typically only necessary on systems with a common run queue. | False |
| ____ is the number of processes that are completed per time unit. | throughput |
| Stack algorithms can never exhibit Belady's anomaly. | True |
| The OpenMP #pragma omp critical directive ___________. | behaves like a mutex lock |
| Inverted page tables require each process to have its own page table. | False |
| ______ allows a portion of a virtual address space to be logically associated with a file. | memory-mapping |
| What scheduling algorithm assignments the CPU to the process that first requested it? | First-Come, First-Served (FCFS) |
| What are the two states of a Windows dispatcher object? | Signaled, Nonsignaled |
| What are the two operations that can be performed on a condition variable? | wait() and signal() |
| In a dynamically linked library, ____. | a stub is included in the image for each library-routine reference |
| ________ allows the parent and child processes to initially share the same pages, but when either process modifies a page, a copy of the shared page is created. | copy-on-write |
| In systems that support virtual memory, ____. | physical memory is separated from logical memory. |
| The system model for deadlocks first requires a process request a resource, then use the resource, and finally release the resource. | True |
| In multithreaded programs, the kernel informs an application about certain events using a procedure known as a(n) ____. | upcall |
| Race conditions are prevented by requiring that critical regions be protected by locks. | True |
| An address generated by the CPU is also referred to as a physical address. | False. An address generated by the CPU is a logical or virtual address, an address in memory is a physical address |
| What are the three strategies for selecting a free hole from the set of available holes? | First-fit, Best-fit, Worst-fit |
| Optimal page replacement ____. | is used mostly for comparison with other page-replacement schemes |
| A Java thread may release a lock under which of the following circumstances? | It exits a synchronized method. |
| Which of the following statements is NOT true? | Spinlocks can be used to prevent busy waiting in the implementation of semaphore. |
| A(n) ______ matches the process with each entry in the TLB. | address-space indentifier |
| ______ allows a thread to run on only one processor. | processor affinity |
| _____ is not a technique for handling critical sections in operating systems. | Peterson's solution |
| The rate of a periodic task in a hard real-time system is ____, where p is a period and t is the processing time. | 1/p |
| Provide at least one method for recovering from deadlock. | Abort all deadlocked processes, or, Abort one process at a time until the deadlock cycle is eliminated |
| SMP systems that use multicore processors typically run faster than SMP systems that place each processor on separate cores. | True |
| If a resource-allocation graph has a cycle, the system must be in a deadlocked state. | False |
| True or False? Linux uses spin locks for both single and multiple processor systems. | False. On single processor systems kernel preemption is enabled/disabled in place of acquiring/releasing a spinlock. |
| The vfork() system call in UNIX ____. | allows the child process to use the address space of the parent |
| A race condition ____. | results when several threads try to access and modify the same data concurrently |
| What is the numeric priority of a Windows XP thread in the HIGH_PRIORITY_CLASS with ABOVE_NORMAL relative priority? | 14 |
| The roll out, roll in variant of swapping is used ____. | for priority-based scheduling algorithms |
| A thread will immediately acquire a dispatcher lock that is the signaled state. | True |
| What are the two bursts that CPI schedulers are designed around? | CPU-burst and IO-burst |
| A page fault must be preceded by a TLB miss. | True |
| What are the two types of contention scope for thread scheduling? | Process-contention scope, System-contention scope |
| To handle deadlocks, operating systems most often _____. | pretend that deadlocks never occur |
| Solaris uses both a local and global page replacement policy. | False |
| Which of the following scheduling algorithms must be nonpreemptive? | FCFS |
| The _____ allocation algorithm allocates available memory to each process according to its size. | proportional |
| Which of the following is a benefit of allowing a program that is only partially in memory to execute? | All of the above |
| Given the logical address 0xAEF9 (in hexadecimal) with a page size of 256 bytes, what is the page number? | 0xAE |
| Hierarchical page tables are appropriate for 64-bit architectures. | False |
| What is the term used to describe the segment of code where shared data is accessed and possibly manipulated? | Critical Section |
| List the three common Page Table Structures. | Hierarchical Paging, Hashed Page Tables, Inverted Page Tables |
| The banker's algorithm is useful in a system with multiple instances of each resource type. | True |
| Describe one strategy for dealing with deadlocks. | Prevent/Avoid, Detect/Recover, Ignore |
| Hashed page tables are particularly useful for processes with sparse address spaces. | True |
| If the current value of counter = 5, what are its possible values if the producer consumer processes run concurrently? | 4, 5 or 6 |
| 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 number of page faults for the given reference string, using the LRU page-replacement algorithm? | 8 |
| A nonpreemptive kernel is essentially free from race conditions. | True |
| A solution to the critical section problem does not have to satisfy which of the following requirements? | atomicity |
| What is the numeric priority of a Windows XP thread in the BELOW_NORMAL_PRIORITY_CLASS with NORMAL relative priority? | 6 |
| What are the two parts of an address generated by the CPU? | Page number, Page offset |
| __________ involves the decision of which kernel thread to schedule onto which CPU. | System-contention scope |
| Which one of the following statements are incorrect when a Java thread invokes the wait() method? | The thread that has been waiting the longest becomes the new owner of the lock. |
| What are the three requirements a solution to the critical-section problem must satisfy? | Mutual exclusion, Progress, Bounded waiting |
| What are the two forms of fragmentation? | External fragmentation, Internal fragmentation |
| Systems using a one-to-one model (such as Windows XP, Solaris 9, and Linux) schedule threads using process-contention scope (PCS). | False |
| What is the name for the state of the system if resources can be allocated to all processes in some order and deadlock can still be avoided? | Safe state |
| 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 | 3,4,2 |
| Which of the following is true of compaction? | It is possible only if relocation is dynamic and done at execution time. |
| In Solaris, if an interactive thread with priority 25 is waiting for I/O, what is its priority recalculated to when it is eligible to run again? | 52 |
| Mobile systems typically use swapping. | False. |
| In RR scheduling, the time quantum should be small with respect to the context-switch time. | False |
| In Little's formula n = λ x W, what does n represent ? | average queue length |
| What are the two operations that can be performed on a semaphore? | Wait() and Signal() |
| A transaction ____. | performs a single logical function |
| Which of the following statements is true? | Operations on atomic integers do not require locking. |
| What is the purpose of the mutex semaphore in the implementation of the bounded-buffer problem using semaphores? | It ensures mutual exclusion. |
| 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? | 3,1,4, |
| The ______ occurs in first-come-first-served scheduling when a process with a long CPU burst occupies the CPU. | Convoy effect |
| To be sharable through shared pages, code must be _____. | Reentrant. I.e. code is non-self modifying: it never changes during execution. |
| Which of the following statements is false with regard to Solaris memory management? | The speed at which pages are examined (the scanrate) is constant. |
| What is the only reasonable condition that can be used to prevent deadlocks from occurring? | Circular-wait. Impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration. |
| A(n) ____ page table has one page entry for each real page (or frame) of memory. | inverted |
| Belady's anomaly states that ____. | for some page replacement algorithms, the page-fault rate may increase as the number of allocated frames increases |
| _____ is the method of binding instructions and data to memory performed by most general-purpose operating systems. | Execution time binding |
| Which of the following statements is true? | An unsafe state may lead to a deadlocked state. |
| The circular-wait condition for a deadlock implies the hold-and-wait condition. | True |
| Which of the following is true of cooperative scheduling? | A process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state. |
| The mapping of a logical address to a physical address is done in hardware by the ________. | memory-management-unit (MMU) |
| 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. | Circular wait |
| Which of the following data structures in the banker's algorithm is a vector of length m, where m is the number of resource types? | Available |
| What is the numeric priority of a Windows XP thread in the NORMAL_PRIORITY_CLASS with HIGHEST relative priority? | 10 |
| One necessary condition for deadlock is ______, which states that a process must be holding one resource and waiting to acquire additional resources. | Hold and Wait. |
| A Solaris interactive thread with priority 15 has a higher relative priority than an interactive thread with priority 20 | False |
| What scheduling algorithm assignments the CPU to a process for only its time slice (or time quantum)? | Round-robin |
| A calling thread becomes the owner of a lock when ______________. | It enters a synchronized method. |
| An instruction that executes atomically ____. | executes as a single, uninterruptible unit |
| What is the name of the classic deadlock avoidance algorithm? | Banker's Algorithm |
| True or False? There are no guarantees Peterson's solution works correctly on modern computer architectures. | True |
| Only a fraction of a process's working set needs to be stored in the TLB. | False |
| Which of the following is true of the rate-monotonic scheduling algorithm? | CPU utilization is bounded when using this algorithm. |
| A cycle in a resource-allocation graph is ____. | a necessary and sufficient condition for a deadlock in the case that each resource has exactly one instance |
| The witness software product is a ____. | lock-order verifier that uses mutual-exclusion locks to protect critical sections |
| A _____ could be preempted from a process. | CPU |
| Under preemptive scheduling, when a process switches from the running to the ready state, it may lose control of the CPU. | True |
| Non-uniform memory access has little effect on the performance of a virtual memory system. | False |
| The local variables of a monitor can be accessed by only the local procedures. | True |
| The most complex scheduling algorithm is the multilevel feedback-queue algorithm. | True |
| The ____ scheduling algorithm is designed especially for time-sharing systems. | RR |
| Absolute code can be generated for ____. | compile-time binding |
| Protocols to prevent hold-and-wait conditions typically also prevent starvation. | False |
| Solaris, Windows XP, and Linux assign higher-priority threads/tasks longer time quantums and lower-priority tasks shorter time quantums. | False |
| Ordering resources and requiring the resources to be acquired in order prevents the circular wait from occurring and therefore prevents deadlock from occurring. | False |
| Suppose that there are 12 resources available to three processes. Which of the following correctly characterizes this state?
Process Maximum Needs Currently Owned
P0 10 4
P1 3 2
P2 7 4 | It is safe. |
| A deadlock-free solution eliminates the possibility of starvation. | False |
| Assume an adaptive mutex is used for accessing shared data on a Solaris system with multiprocessing capabilities. Which of the following statements is not true? | Condition variables and semaphores are never used in place of an adaptive mutex. |
| Consider a logical address with a page size of 8 KB. How many bits must be used to represent the page offset in the logical address? | 13 |
| On a system with demand-paging, a process will experience a high page fault rate when the process begins execution. | True |
| What are the Pthreads operations for locking and unlocking a mutex lock? | pthread_mutex_lock(), pthread_mutex_unlock() |
| What is the term that describes when a page number is not present in the TLB? | TLB miss. A memory reference to the page table is made, and the page and frame number are added to the Translation Look-aside Buffer (TLB) |
| Which of the following statements are false with regards to the Linux CFS scheduler? | There is a single, system-wide value of vruntime. |
| The ____ is the number of entries in the TLB multiplied by the page size. | TLB reach |
| _____ is the dynamic storage-allocation algorithm which results in the largest leftover hole in memory. | Worst Fit |
| There is a 1:1 correspondence between the number of entries in the TLB and the number of entries in the page table. | False |
| Assume the value of the base and limit registers are 1200 and 350 respectively. Which of the following addresses is legal? | 1200 |
| Lock ordering cannot guarantee protection from deadlock. | True |
| A(n) ___________ is a sequence of read-write operations that are atomic. | memory transaction |
| A ___ type presents a set of programmer-defined operations that are provided mutual exclusion within it. | monitor |
| With segmentation, a logical address consists of _____. | segment number and offset |
| The _____ binding scheme facilitates swapping. | execution time |
| A Solaris interactive thread with a time quantum of 80 has a higher priority than an interactive thread with a time quantum of 120. | True |
| If the page-fault rate is too high, the process may have too many frames. | False |
| _______ refers to where a process is accessing/updating shared data. | critical section |
| The _____ is an approximation of a program's locality. | working set |
| A spinlock is a type of mutex lock. | True |
| What is the problem if all philosophers simultaneously pick up their left fork? | Deadlock - each philosopher is waiting infinitely for the next. |
| One necessary condition for deadlock is ____, which states that at least one resource must be held in a nonsharable mode. | Mutual Exclusion |
| Without a mechanism such as an address-space identifier, the TLB must be flushed during a context switch. | True |
| The two general approaches to load balancing are __________ and ____________. | push migration, pull migration |
| What is the backing store? | Fast disk space. A process can be swapped out of memory into a backing store temporarily, and then returned to memory for continued execution. |
| In Solaris, if an interactive thread with priority 15 uses its entire time quantum, what is its priority recalculated to? | 5 |
| What are the two general hardware instructions that can be performed atomically? | test_and_set(), compare_and_swap() |
| List the three different times at which address binding may occur. | Compile time, Load time, Execution time |
| Consider a logical address with 18 bits used to represent an entry in a conventional page table. How many entries are in the conventional page table? | 262144 |
| List at least three different criteria for designing a CPU scheduling algorithm. | CPU utilisation (%), Throughput (# of processes completed), Turnaround time (time to complete a process), Waiting time (time spent in waiting in the ready queue), Response time (time from submission to first response) |
| The default scheduling class for a process in Solaris is ____. | time sharing |
| The value of a counting semaphore can range only between 0 and 1. | False |
| _____ is the dynamic storage-allocation algorithm which results in the smallest leftover hole in memory. | Best fit |
| In Linux, tasks that are not real-time have dynamic priorities that are based on their ____ values plus or minus the value 5. | nice |
