OS Cheat Sheet - Answers to quizzes and exam questions PDF

Preview

Summary

Answers to quizzes and exam questions...

Description

MC SJF scheduling is approximated by predicting the next CPU burst with an exponential average of the measured lengths of previous CPU bursts. Which of the following scheduling algorithms must be nonpreemptive? FCFS What method can be used to prevent a starvation condition? Aging can be used to gradually increase the priority of a process. Load balancing is typically only necessary on: Systems with a separate queue for every processor. The necessary condition(s) for deadlock is ____, a) At least one resource must be held in a nonsharable mode. b) Process is holding some resources and waiting for others. c) There is a circular wait between processes d) Resources cannot be pre-empted √ e) All of the other options. 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. Which of the following correctly characterizes this state?

It is not safe. The factor(s) that influence(s) the decision of when to invoke a deadlock detection algorithm is (are): a) How often a deadlock is likely to occur b) How many processes will be affected by deadlock when it happens c) When the CPU utilization drops below a certain threshold. √d) All of the other options.

Consider a logical address of length 20 bits with a page size of 8 KB. How many bits must be used to represent the page offset in the logical address? 13 Which of the following statements is true? a) Inverted page tables require each process to have its own page table. b) Fragmentation does not occur in a paging system. c) Mobile operating systems typically support swapping. d) Without a mechanism such as an address-space identifier, the TLB must be flushed during a context switch. 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? 8 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 LRU replacement algorithm, what is the number of page faults for the given reference string? 8 Which of the following statements is true? a) On a system with demand-paging, a process will experience a high page fault rate when the process begins execution. b) If the page-fault rate is too high, the process may have too many frames. c) On systems that provide it, vfork() should always be used instead of fork(). d) In general, virtual memory decreases the degree of multiprogramming in a system 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 LRU algorithm is applied? 4, 1, 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? 2, 3, 4 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? 3, 4, 2

Consider the following set of processes, with the length of the CPU burst time given in milliseconds (1ms = 1 unit time):

The processes are assumed to have arrived at time zero shown in the table and the scheduling decisions are made at the 1 unit time boundary. Draw Gantt charts that illustrate the execution of these processes using the following scheduling algorithms:

The Convoy effect occurs in FCFS scheduling when a process with a long CPU burst occupies the CPU Processor affinity allows a thread to run on only one processor. Supposed that the following processes arrive for execution at the times indicated. Each process will run for the amount of time listed. In answering the questions, use preemptive scheduling, and base all decisions on the information you have at the time the decision must be made (each unit time. Process

Arrival Time

Burst Time

1

0

8

2

1

4

3

2

1

What is the average turnaround time for these processes with the Shortest remaining job first scheduling algorithm? 6.33

The RR (Round Robin) scheduling algorithm is designed especially for time-sharing systems. A significant problem with priority scheduling algorithm is starvation SJF scheduling is approximated by predicting the next CPU burst with an exponential average of the measured lengths of previous CPU bursts Throughput is the number of processes that are completed per time unit The trend in developing parallel applications is to use implicit threading A mutex lock is essentially a boolean variable The Many to many multithreading model multiplexes many user-level threads to a smaller or equal number of kernel threads. Assume you had a function named update() that updates shared data. Illustrate how a mutex lock might be used to prevent a race condition in update() Ans: void update(){ mutex.acquire //update shared data mutex.release } A counting semaphore is essential an integer variable Which of the following would be an acceptable signal handling scheme for a multithreaded program? All of the options Options include: Deliver the signal to the thread to which the signal applies. Deliver the signal to only certain threads in the process. Deliver the signal to every thread in the process. Which of these statements involving threads is false? Sharing is automatically provided in java threads. Ensuring there is a sufficient number of cores is not a challenge when designing applications for multicore systems A race condition results when several threads try to access and modify the same data concurrently

The stack of a process contains temporary data such as function parameters, return addresses, and local variables. A Process control block Includes information on the process's state

The list of processes waiting for a particular I/O device is called a(n) device queue. When a child process is created, which of the following is a possibility in terms of 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. A context switch saves the state of the currently running process and restores the state of the next process to run. A process may transition to the ready state by which of the following actions? A. Completion of an I/O event. B. Awaiting it's turn on the CPU C. Newly-admitted process D. All of the above In a(n) zero capacity temporary queue, the sender must always block until the recipient receives the message. A blocking send( ) and blocking receive( ) is known as a(n) rendezvous 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. When communicating with sockets, a client process initiates a request for a connection and is assigned a port by the host computer. Which of the following would be a valid port assignment for the host computer? 1625 Type Port number range Well-known 1-1023 Registered 1024-65535

Imagine that a host with IP address 150.55.66.77 wishes to download a file from the web server at IP address 202.28.15.123. Select a valid socket pair for a connection between this pair of hosts. 150.55.66.77.2000 and 202.28.15.123.80 A process that has terminated, but whose parent has not yet called wait( ), is known as a(n) zombie process. In a linux operating system, the init process is assigned as the parent to orphaned processes. A matchmaker service does what? Provides a service to help connect a client and server (T/F) Ordinary pipes in UNIX require a parent-child relationship between the communicating processes T (T/F) Named pipes continue to exist in the system after the creating process has terminated. T (T/F) The difference between a program and a process is that a program is an active entity while a process is a passive entity. F (T/F) The exec( ) system call creates a new process. F (T/F) Shared memory is a more appropriate IPC mechanism than message passing for distributed systems (e.g. client-server) F The mailbox can be owned by a process or the operating system. T Pthreads refers to a specification for thread behavior The many-to-many model multithreading model multiplexes many user-level threads to a smaller or equal number of kernel-threads Ensuring there is a sufficient number of cores is not considered a challenge when designing applications for multicore systems. A Thread Library provides an API for creating and managing threads The one-to-one model maps each user-level thread to one kernel-thread. The two-level model allows a user-level thread to be bound to one kernel-thread. In Win32, a parent uses a WaitForSingleObject( ) function to wait for it's child to complete. What is the equivalent function in Pthreads? pthread_join( )

Task Parallelism involves distributing tasks across multiple computing cores. Cancellation points are associated with deferred thread cancelation Thread-local storage is data that is unique to each thread Windows uses the one-to-one model The two types of parallelism are task and data A method of implicit threading that starts with a bounded set of threads is known as thread pools (T/F) Deferred cancellation is preferred over asynchronous cancellation True (T/F) A traditional (or heavyweight) process has a single thread of control True (T/F) Virtually all contemporary operating systems support kernel threads True (T/F) Each thread has its own register set and stack True (T/F) It is possible to create a thread library without any kernel-level support True (T/F) it is possible to have concurrency without parallelism True An instruction that executes automatically executes as a single, uninterruptible unit. A mutex lock prevents racing conditions What is the correct order of operations for protecting a critical section using mutex locks? acquire( ) followed by release( ) A solution to the critical section problem DOES NOT have to satisfy which of the following requirements? Atomicity A(n) critical section refers to where a process is accessing/updating shared data.

The first readers-writers program requires that no reader will be kept waiting unless a writer has already obtained permission to use the shared database A monitor type presents a set of programmer-defined operations that are provided mutual exclusion within it. Priority Inversion occurs when a higher-priority process needs to access a data structure that is currently being accessed by a lower-priority process. What is the correct order of operations for protecting a critical section using a binary semaphore? wait( ) followed by signal( ) Waiting queues can be used to prevent busy waiting when implementing a semaphore. How many philosophers may eat simultaneously in the Dining Philosophers problem with 5 philosophers? 2 Another problem related to deadlocks is indefinite blocking (T/F) Race conditions are prevented by requiring that critical regions be protected by locks True (T/F) The value of a counting semaphore can range only between 0 and 1 False (T/F) A deadlock-free solution eliminates the possibility of starvation False (T/F) Mutex locks and binary semaphores are essentially the same thing True Which of the following is true of multilevel queue scheduling? Each queue has its own scheduling algorithm System-contention scope involves the decision of which kernel thread to schedule onto which CPU With course-grained multithreading a thread executes on a professor until a long-latency event (i.e. a memory stall) occurs. A significant problem with priority scheduling algorithms is starvation

The convoy effect occurs in the first-come-first-served scheduling when a process with a long CPU burst occupies the CPU. The rate of a periodic task in a hard real-time system is 1/p, where p is a period and t is the processing time. Which of the following is true of the rate-monotonic scheduling algorithm? CPU utilization is bounded when using this algorithm 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. The two general approaches to load balancing are push migration and pull migration (T/F) In preemptive scheduling, the sections of code affected by interrupts must be guarded from simultaneous use. True (T/F) In RR scheduling, the time quantum should be small with the respect to the context-switch time. False (T/F) Load balancing is typically only necessary on systems with a common run queue. False (T/F) SMP systems that use multicore processors typically run faster than SMP systems that place each processor on separate cores. True (T/F) Load balancing algorithms have no impact on the benefits of processor affinity. False (T/F) A multicore system allows two (or more) threads that are in compute cycles to execute all the same time True Name two differences between a rate-monotonic and an EDF scheduler. What is the primary advantage of an EDF? - EDF scheduling does not require that processes be periodic, a process doesn't require a constant amount of CPU time per burst, and priorities are dynamic. - The appeal of EDF scheduling is that it is optimal - theoretically, it can schedule processes so that each process can meet its deadline requirements and CPU utilization will be 100%

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 To handle deadlocks, operating systems most often pretend that deadlocks never occur Which of the following statements is true? A. A safe state is a deadlocked state B. A safe state may lead to a deadlocked state C. An unsafe state is necessarily, and by definition, always a deadlocked state D. An unsafe state may lead to a deadlocked state. Consider the following snapshot of a system. _________________Allocation______Max______Available __________________ABCD_________ABCD_______ABCD P0________________0012____________0012_________1520 P1________________1000____________1750 P2________________1354____________2356 P3________________0632____________0652 P4________________0014____________0656 What is the matrix NEED? Is the system in a safe state? Need: (0,0,0,0) (0,7,5,0) (1,0,0,2) (0,6,4,2) The system is in a safe state. (one option of few) Can this change be made safely? Increase Available (new resources added) This change could safely be made without any problems. Can this change be made safely? Decrease Available (resource permanently removed from system) This could have an effect on the system and introduce the possibility of deadlock as the safety of the system assumed there were a certain number of available resources.

Can this change be made safely? Increase Max for one process (the process needs more resources than allowed, it may want more) This could have an effect on the system and introduce the possibility of deadlock Can this change be made safely? Decrease Max for one process (the process decides it does not need that many resources) This change could safely be made without any problems. Can this change be made safely? Decrease the number of processes This change could safely be made without any problems. Absolute code can be generated for compile-time binding Execution-time binding is the method of binding instructions and data to memory performed by most general-purpose operating systems An address generated by a CPU is referred to as a logical address Suppose a program is operating with execution-time binding and the physical address generated is 301. The relocation register is set to 100. What is the corresponding logical address? 201 The mapping of a logical address to a physical address is done in hardware by the memory-management-unit (MMU) In a dynamically linked library, a stub is included in the image for each library-routine reference The roll out, roll in variant of swapping is used for priority-based scheduling algorithms Best fit is the dynamic storage-allocation algorithm which results in the smallest-leftover hole in memory. Worst fit is the dynamic storage-allocation algorithm which results in the largest leftover hole in memory. 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 if relocation is dynamic and done at execution.

Assume the value of the base and limit registers are 1400 and 350 respectively. Which of the following addresses is legal? A. 355 B. 1400 C. 1751 D. all of the above Which of the following is not a reason explaining why mobile devices generally do not support swapping? A. Limited space constraints of flash memory B. Small size of mobile applications do not require use of swap space. C. Limited number of writes of flash memory D. Poor throughput between main memory and flash memory A(n) inverted page table has only one page entry for each real page (or frame) of memory. Consider a logical address with a page size of 16 KB. How many bits must be used to represent the page offset in the logical address? 14 Given the logical address 0xAEF9 (in hexadecimal) with a page size of 256 bytes, what is the page number? 0xAE Consider a 32-bit address for a two-level paging system with a 4 KB page size. The outer page table has 1024 entries. How many bits are used to represent the second-level page table? 10 With segmentation, a logical address consists of segment number and offset Which of the following data structures is appropriate for placing into its own segment? A. heap B. kernel code and data C. user code and data D. all of the above A(n) address-space identifier matches the process with each entry in the TLB.

(T/F) Reentrant code cannot be shared False (T/F) There is 1:1 correspondence between the number of entries in the TLB and the number of entries in the page table. False (T/F) Hierarchical page tables are appropriate for 64-bit architectures False

(T/F) Hashed page tables are particularly useful for processes with sparse address spaces. True (T/F) Without a mechanism such as an address-space identifier, the TLB must be flushed during a context switch. True (T/F) Hashed page table are commonly used when handling addresses larger than 32 bits. True Given the Effective Access Time(EAT) formula: EAT = (Memory Access)a + (TLB access)(1-a) If a memory access takes 100ns, but a TLB miss takes two memory accesses, what would the EAT be for a hit rate of 80%: How about for a more realistic hit rate of 99%: EAT = 0.8 x 100 + 0.2 x 200 = 120ns EAT = 0.99 x 100 + 0.01 x 200 = 101ns Belady's anomaly states that for some page replacement algorithms, the page-fault rate may increase as the number of allocated frames increases Optimal page replacement is used mostly for comparison with other page-replacement schemes In the enhanced second chance algorithm, which of the following ordered pair represents a page that would be the best choice for replacement? (0,0) The proportional allocation algorithm allocates available memory to each process according to its size. Copy-on-write 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. LRU is the algorithm implemented on most systems. ...