OS Test 2

Quiz yourself by thinking what should be in each of the black spaces below before clicking on it to display the answer.

Help!

Question

Answer

A race condition ____.

results when several threads try to access and modify the same data concurrently

🗑

_____ is not a technique for handling critical sections in operating systems.

Peterson's solution

🗑

A solution to the critical section problem does not have to satisfy which of the following requirements?

atomicity

🗑

_______ refers to where a process is accessing/updating shared data.

critical section

🗑

_____ can be used to prevent busy waiting when implementing a semaphore.

Waiting queues

🗑

What is the purpose of the mutex semaphore in the implementation of the bounded-buffer problem using semaphores?

It ensures mutual exclusion.

🗑

How many philosophers at most may eat simultaneously in the Dining Philosophers problem with 5 philosophers?

🗑

An instruction that executes atomically ____.

executes as a single, uninterruptible unit

🗑

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.

🗑

A calling thread becomes the owner of a lock when ______________.

It enters a synchronized method.

🗑

A Java thread may release a lock under which of the following circumstances?

It exits a synchronized method.

🗑

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.

🗑

A semaphore ____.

is essentially an integer variable

🗑

A spinlock ____.

does not require a context switch when a process must wait on a lock

🗑

In Peterson's solution, the ____ variable indicates if a process is ready to enter its critical section.

flag[i]

🗑

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.

🗑

A ___ type presents a set of programmer-defined operations that are provided mutual exclusion within it.

monitor

🗑

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

🗑

Which of the following statements is true?

An unsafe state may lead to a deadlocked state.

🗑

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.

🗑

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.

🗑

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

🗑

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.

🗑

A _____ could be preempted from a process.

CPU

🗑

One necessary condition for deadlock is ____, which states that at least one resource must be held in a nonsharable mode.

Mutual Exclusion

🗑

The circular-wait condition for a deadlock implies the hold-and-wait condition.

True

🗑

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.

🗑

If a resource-allocation graph has a cycle, the system must be in a deadlocked state.

False

🗑

Protocols to prevent hold-and-wait conditions typically also prevent starvation.

False

🗑

The wait-for graph scheme is not applicable to a resource allocation system with multiple instances of each resource type.

True

🗑

Ordering resources and requiring the resources to be acquired in order prevents the circular wait from occurring and therefore prevents deadlock from occurring.

False

🗑

The banker's algorithm is useful in a system with multiple instances of each resource type.

True

🗑

A system in an unsafe state will ultimately deadlock.

False

🗑

Deadlock prevention and deadlock avoidance are essentially the same approaches for handling deadlock.

False

🗑

Lock ordering cannot guarantee protection from deadlock.

True

🗑

One necessary condition for deadlock is ______, which states that a resource can be released only voluntarily by the process holding the resource.

no preemption

🗑

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

🗑

The witness software product is a ____.

lock-order verifier that uses mutual-exclusion locks to protect critical sections

🗑

In a system resource-allocation graph, ____.

a directed edge from a process to a resource is called a request edge

🗑

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

🗑

If the current value of counter = 5, what are its possible values if the producer consumer processes run concurrently?

4, 5 or 6

🗑

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

🗑

What is the term used to describe the segment of code where shared data is accessed and possibly manipulated?

Critical Section

🗑

What are the three requirements a solution to the critical-section problem must satisfy?

Mutual exclusion, Progress, Bounded waiting

🗑

A nonpreemptive kernel is essentially free from race conditions.

True

🗑

True or False? There are no guarantees Peterson's solution works correctly on modern computer architectures.

True

🗑

What are the two functions used with mutex locks?

acquire() and release()

🗑

A spinlock is a type of mutex lock.

True

🗑

Semaphores can provide the same functionality as mutex locks.

True

🗑

What are the two operations that can be performed on a semaphore?

Wait() and Signal()

🗑

A binary semaphore is functionally equivalent to a mutex lock.

True

🗑

What are the names of the two processes associated with the bounded-buffer problem?

Producer and Consumer

🗑

How many writers may concurrently share the database with the readers-writers problem?

one

🗑

What is the problem if all philosophers simultaneously pick up their left fork?

Deadlock - each philosopher is waiting infinitely for the next.

🗑

What are the two operations that can be performed on a condition variable?

wait() and signal()

🗑

Name at least one modern programming language that has incorporated the idea of a monitor.

Java

🗑

What are the two states of a Windows dispatcher object?

Signaled, Nonsignaled

🗑

What is available in Linux for updating an integer variable without having to use locks?

atomic_t type, atomic integers.

🗑

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.

🗑

What are the Pthreads operations for locking and unlocking a mutex lock?

pthread_mutex_lock(), pthread_mutex_unlock()

🗑

What are the two bursts that CPI schedulers are designed around?

CPU-burst and IO-burst

🗑

Under preemptive scheduling, when a process switches from the running to the ready state, it may lose control of the CPU.

True

🗑

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)

🗑

What scheduling algorithm assigns the CPU to the process with the highest priority?

Priority Scheduling

🗑

The multilevel feedback queue scheduling algorithm allows processes to migrate between different queues.

True (multilevel feedback scheduling != multilevel scheduling)

🗑

What scheduling algorithm assignments the CPU to the process that first requested it?

First-Come, First-Served (FCFS)

🗑

What scheduling algorithm assignments the CPU to a process for only its time slice (or time quantum)?

Round-robin

🗑

What scheduling algorithm assigns the CPU to the process with the shortest burst?

Shortest Job First (SJF)

🗑

What are the two types of contention scope for thread scheduling?

Process-contention scope, System-contention scope

🗑

What are the two general hardware instructions that can be performed atomically?

test_and_set(), compare_and_swap()

🗑

The system model for deadlocks first requires a process request a resource, then use the resource, and finally release the resource.

True

🗑

What are the four necessary conditions for characterising deadlock?

Mutual exclusion, Hold and wait, No preemption, Circular wait

🗑

Describe one strategy for dealing with deadlocks.

Prevent/Avoid, Detect/Recover, Ignore

🗑

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.

🗑

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

🗑

What is the name of the classic deadlock avoidance algorithm?

Banker's Algorithm

🗑

The wait-for graph can only be used for deadlock detection when there is a single instance of each type.

True

🗑

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

🗑

What two registers can be used to provide a simple form of memory protection?

Relocation register, Limit register

🗑

List the three different times at which address binding may occur.

Compile time, Load time, Execution time

🗑

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 is the hardware device that maps virtual to physical addresses?

Memory Management Unit (MMU)

🗑

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.

🗑

Mobile systems typically use swapping.

False.

🗑

What are the three strategies for selecting a free hole from the set of available holes?

First-fit, Best-fit, Worst-fit

🗑

What are the two forms of fragmentation?

External fragmentation, Internal fragmentation

🗑

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

🗑

What are the two parts of an address generated by the CPU?

Page number, Page offset

🗑

What does each entry in the page table contain?

The base address of each page in physical memory.

🗑

Fragmentation can still occur in paging systems.

True. Internal fragmentation can occur. External cannot.

🗑

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)

🗑

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

🗑

To be sharable through shared pages, code must be _____.

Reentrant. I.e. code is non-self modifying: it never changes during execution.

🗑

List the three common Page Table Structures.

Hierarchical Paging, Hashed Page Tables, Inverted Page Tables

🗑

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.

🗑

A transaction ____.

performs a single logical function

🗑

A thread will immediately acquire a dispatcher lock that is the signaled state.

True

🗑

Mutex locks and binary semaphores are essentially the same thing.

True

🗑

Monitors are a theoretical concept and are not practiced in modern programming languages

False

🗑

Race conditions are prevented by requiring that critical regions be protected by locks.

True

🗑

Which of the following statements is NOT true?

Spinlocks can be used to prevent busy waiting in the implementation of semaphore.

🗑

The local variables of a monitor can be accessed by only the local procedures.

True

🗑

A deadlock-free solution eliminates the possibility of starvation.

False

🗑

A schedule in which each transaction is executed atomically is called a(n) ____.

serial schedule

🗑

The value of a counting semaphore can range only between 0 and 1.

False

🗑

Every object in Java has associated with it a single lock.

True

🗑

Windows XP, when accessing a global variable on a uniprocessor system, ____.

masks interrupts for all interrupt handlers that may also access the variable

🗑

In multithreaded programs, the kernel informs an application about certain events using a procedure known as a(n) ____.

upcall

🗑

Hierarchical page tables are appropriate for 64-bit architectures.

False

🗑

Inverted page tables require each process to have its own page table.

False

🗑

Fragmentation does not occur in a paging system.

False

🗑

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?

🗑

_____ is the dynamic storage-allocation algorithm which results in the largest leftover hole in memory.

Worst Fit

🗑

A(n) ______ matches the process with each entry in the TLB.

address-space indentifier

🗑

Which of the following data structures is appropriate for placing into its own segment?

all of the above

🗑

With segmentation, a logical address consists of _____.

segment number and offset

🗑

Absolute code can be generated for ____.

compile-time binding

🗑

Reentrant code cannot be shared.

false

🗑

Hashed page tables are commonly used when handling addresses larger than 32 bits.

True

🗑

Hashed page tables are particularly useful for processes with sparse address spaces.

True

🗑

The mapping of a logical address to a physical address is done in hardware by the ________.

memory-management-unit (MMU)

🗑

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

🗑

_____ is the method of binding instructions and data to memory performed by most general-purpose operating systems.

Execution time binding

🗑

The Linux operating system does not rely on segmentation and uses it minimally.

True

🗑

The _____ binding scheme facilitates swapping.

execution time

🗑

A relocation register is used to check for invalid memory addresses generated by a CPU.

False

🗑

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 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

🗑

Given the logical address 0xAEF9 (in hexadecimal) with a page size of 256 bytes, what is the page number?

0xAE

🗑

Given the logical address 0xAEF9 (in hexadecimal) with a page size of 256 bytes, what is the page offset?

0xF9

🗑

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

🗑

Which of the following is true of compaction?

It is possible only if relocation is dynamic and done at execution time.

🗑

_____ is the dynamic storage-allocation algorithm which results in the smallest leftover hole in memory.

Best fit

🗑

Without a mechanism such as an address-space identifier, the TLB must be flushed during a context switch.

True

🗑

The roll out, roll in variant of swapping is used ____.

for priority-based scheduling algorithms

🗑

A(n) ____ page table has one page entry for each real page (or frame) of memory.

inverted

🗑

In a dynamically linked library, ____.

a stub is included in the image for each library-routine reference

🗑

Assume the value of the base and limit registers are 1200 and 350 respectively. Which of the following addresses is legal?

1200

🗑

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?

🗑

An address generated by a CPU is referred to as a ____.

logical address

🗑

The ____ is the number of entries in the TLB multiplied by the page size.

TLB reach

🗑

If the page-fault rate is too high, the process may have too many frames.

False

🗑

In practice, most systems implement an approximation of the _____ page-replacement algorithm.

LRU

🗑

What size segment will be allocated for a 39 KB request on a system using the Buddy system for kernel memory allocation?

64KB

🗑

Belady's anomaly states that ____.

for some page replacement algorithms, the page-fault rate may increase as the number of allocated frames increases

🗑

Non-uniform memory access has little effect on the performance of a virtual memory system.

False

🗑

On a system with demand-paging, a process will experience a high page fault rate when the process begins execution.

True

🗑

Only a fraction of a process's working set needs to be stored in the TLB.

False

🗑

Solaris uses both a local and global page replacement policy.

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.

🗑

The _____ allocation algorithm allocates available memory to each process according to its size.

proportional

🗑

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

🗑

______ allows a portion of a virtual address space to be logically associated with a file.

memory-mapping

🗑

________ 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

🗑

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?

🗑

Optimal page replacement ____.

is used mostly for comparison with other page-replacement schemes

🗑

A page fault must be preceded by a TLB miss.

True

🗑

The buddy system for allocating kernel memory is very likely to cause fragmentation within the allocated segments.

True

🗑

Stack algorithms can never exhibit Belady's anomaly.

True

🗑

_____ occurs when a process spends more time paging than executing.

Thrashing

🗑

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,

🗑

In systems that support virtual memory, ____.

physical memory is separated from logical memory.

🗑

The _____ is an approximation of a program's locality.

working set

🗑

The vfork() system call in UNIX ____.

allows the child process to use the address space of the parent

🗑

In general, virtual memory decreases the degree of multiprogramming in a system.

False

🗑

Which of the following is a benefit of allowing a program that is only partially in memory to execute?

All of the above

🗑

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

🗑

Which of the following statements is false with regard to Solaris memory management?

The speed at which pages are examined (the scanrate) is constant.

🗑

A 32-bit logical address with 8 KB page size will have 1,000,000 entries in a conventional page table.

False

🗑

Solaris, Windows XP, and Linux assign higher-priority threads/tasks longer time quantums and lower-priority tasks shorter time quantums.

False

🗑

In preemptive scheduling, the sections of code affected by interrupts must be guarded from simultaneous use.

True

🗑

Load balancing is typically only necessary on systems with a common run queue.

False

🗑

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

🗑

In Little's formula n = λ x W, what does W represent?

average waiting time in the queue

🗑

In Little's formula n = λ x W, what does λ represent ?

average arrival rate for new processes in the queue

🗑

In Little's formula n = λ x W, what does n represent ?

average queue length

🗑

____ is the number of processes that are completed per time unit.

throughput

🗑

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?

🗑

In Solaris, if an interactive thread with priority 15 uses its entire time quantum, what is its priority recalculated to?

🗑

In Linux, tasks that are not real-time have dynamic priorities that are based on their ____ values plus or minus the value 5.

nice

🗑

The ____ scheduling algorithm is designed especially for time-sharing systems.

🗑

With _______ a thread executes on a processor until a long-latency event (i.e. a memory stall) occurs.

coarse-grained multithreading

🗑

The most complex scheduling algorithm is the multilevel feedback-queue algorithm.

True

🗑

A Solaris interactive thread with priority 15 has a higher relative priority than an interactive thread with priority 20

False

🗑

____ scheduling is approximated by predicting the next CPU burst with an exponential average of the measured lengths of previous CPU bursts.

SJF

🗑

______ allows a thread to run on only one processor.

processor affinity

🗑

Round-robin (RR) scheduling degenerates to first-come-first-served (FCFS) scheduling if the time quantum is too long.

True

🗑

Systems using a one-to-one model (such as Windows XP, Solaris 9, and Linux) schedule threads using process-contention scope (PCS).

False

🗑

A significant problem with priority scheduling algorithms is _____.

Starvation

🗑

Which of the following scheduling algorithms must be nonpreemptive?

FCFS

🗑

The ______ occurs in first-come-first-served scheduling when a process with a long CPU burst occupies the CPU.

Convoy effect

🗑

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.

🗑

Load balancing algorithms have no impact on the benefits of processor affinity.

False

🗑

__________ involves the decision of which kernel thread to schedule onto which CPU.

System-contention scope

🗑

Virtualization does not allow a single-CPU system to appear as a multiprocessor system.

False

🗑

What is the numeric priority of a Windows XP thread in the HIGH_PRIORITY_CLASS with ABOVE_NORMAL relative priority?

🗑

What is the numeric priority of a Windows XP thread in the NORMAL_PRIORITY_CLASS with HIGHEST relative priority?

🗑

What is the numeric priority of a Windows XP thread in the BELOW_NORMAL_PRIORITY_CLASS with NORMAL relative priority?

🗑

Which of the following is true of multilevel queue scheduling?

Each queue has its own scheduling algorithm.

🗑

In RR scheduling, the time quantum should be small with respect to the context-switch time.

False

🗑

SMP systems that use multicore processors typically run faster than SMP systems that place each processor on separate cores.

True

🗑

In Solaris, what is the time quantum (in milliseconds) of an interactive thread with priority 35?

🗑

The default scheduling class for a process in Solaris is ____.

time sharing

🗑

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

🗑

____________ occurs when a higher-priority process needs to access a data structure that is currently being accessed by a lower-priority process.

Priority Inversion

🗑

Which of the following statements is true?

Operations on atomic integers do not require locking.

🗑

A(n) ___________ is a sequence of read-write operations that are atomic.

memory transaction

🗑

The OpenMP #pragma omp critical directive ___________.

behaves like a mutex lock

🗑

Another problem related to deadlocks is ____________.

indefinite blocking

🗑

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.

🗑

Which of the following statements are false with regards to the Linux CFS scheduler?

There is a single, system-wide value of vruntime.

🗑

The Linux CFS scheduler identifies _____________ as the interval of time during which every runnable task should run at least once.

targeted latency

🗑

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

🗑

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 __________ and ____________.

push migration, pull migration

🗑

Which of the following is a benefit of allowing a program that is only partially in memory to execute?

All of the above

🗑

Windows uses a local page replacement policy _____.

when a process exceeds its working set maximum

🗑

Systems in which memory access times vary significantly are known as __________.

non-uniform memory access

🗑

Which of the following is considered a benefit when using the slab allocator?

no memory fragmentation

🗑

Review the information in the table. When you are ready to quiz yourself you can hide individual columns or the entire table. Then you can click on the empty cells to reveal the answer. Try to recall what will be displayed before clicking the empty cell.

To hide a column, click on the column name.

To hide the entire table, click on the "Hide All" button.

You may also shuffle the rows of the table by clicking on the "Shuffle" button.

Or sort by any of the columns using the down arrow next to any column heading.
If you know all the data on any row, you can temporarily remove it by tapping the trash can to the right of the row.

Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

Normal Size Small Size show me how

Created by: bcannoles

Popular Computers sets

Definitions for Word Processing and the main parts of the MS Word 2010 window

WP Page Formatting

WP Paragraph Formatting terms

Review business letter parts

Review the three paragraph formats (block, indented, hanging indent)

WP font formatting features in Word 2010

Arkansas CBA unit 1 Hardware