Operating System Flashcards
1
Q
operating system services function
A
provides functions that are helpful to the user
1
Q
user interface
A
command-line, GUI, batch
2
Q
what is a Operating System
A
A program that acts as an intermediary between the user and the computer
3
Q
functions of operating system
A
resource allocator
control program
4
Q
goals of operating system
A
Execute programs and solve problems more easily
Make the computer system convenient for the user
Use computer hardware efficiently
5
Q
Components of computer system
A
- Hardware
- Operating system
- Application program
- User
6
Q
Computer-System Operation
A
I/O devices and the CPU can execute concurrently
Each device controller is in charge of a certain device type
Each device has a local buffer
CPU moves data from/to main memory to/from local buffer
7
Q
functions of interrupt
A
- Interrupt transfers control to the interrupt service routine through the interrupt vector
- Interrupt architecture saves the address of the interrupted instruction
8
Q
Direct Memory Access Structure
A
Used for high-speed I/O devices able to transmit information at close to memory speeds
Device controller transfers blocks of data from buffer storage directly to main memory without CPU intervention
Only one interrupt is generated per block, rather than the one interrupt per byte
9
Q
Interrupt handling
A
- The operating system preserves the state of the CPU by storing registers and the program counter
- Separate segments of code determine what action should be taken for each type of interrupt
10
Q
why is the O/S called a resource allocator
A
o Manages all resources
o Decides between conflicting requests for efficient and fair resource use
11
Q
why is O/S known to control programs?
A
o Controls execution of programs to prevent errors and improper use of the computer
o Management of the operation and control of I/O devices
12
Q
Storage Structure
A
- Main memory (large storage media that the CPU can access directly)
- Secondary memory (acts as extension of main memory that provides large non-volatile storage capacity)
- Magnetic disk (rigid metal covered with magnetic recording material)
13
Q
Storage-Device Hierarchy
A
register > Cache > Main memory > Electronic disk > Magnetic disk > Optical disk > Magnetic tapes
14
Q
Advantages of Multiprocessor systems
A
Increased throughput
Economy of scale
Increase reliability
15
Q
Timesharing (multitasking)
A
logical extension in which CPU switches jobs so frequently that users can interact with each job while it is running, creating interactive computing
16
Q
Types of Multiprocessor System
A
- Asymmetric multiprocessing - Each processor performs a task
- Symmetric multiprocessing - Each processor performs all task
17
Q
Types of Cluster System
A
- Asymmetric clustering - has one machine in hot-standby mode
- Symmetric clustering - has multiple nodes running applications and monitoring each other
18
Q
activities of process management
A
Creating and deleting user and system processes
Suspending and resuming processes
Providing mechanisms for process synchronization
Providing mechanisms for process communication
Providing mechanisms for deadlock handling
19
Q
memory management activities
A
- Keeping track of which parts of memory are currently being used and by whom
- Deciding which part of processes and data to move into and out of memory
- Allocating and deallocating memory space as needed
20
Q
Storage management activities
A
- Creating and deleting files and directories
- Primitives to manipulate files and dirs
- Mapping files onto secondary storage
- Backup files onto stable storage media
21
Q
List the services provided by an O/S
A
- Program execution - The system must be able to load a program into memory and to run that program, end execution, either normally or abnormally
- I/O operations - A running program may require I/O, which may involve a file or an I/O device
- File-system manipulation - programs need to read and write files and directories, create and delete them, search them, list file Information, permission management.
- Communication - Processes may exchange information, on the same computer or between computers over a network
- Error detection - OS needs to be constantly aware of possible errors
- Resource allocation - When multiple users or multiple jobs running concurrently, resources must be allocated to each of them
- Accounting - To keep track of which users use how much and what kinds of computer resources, either for billing purposes or for statistical record keeping.
- Protection and security - Protection involves ensuring that all access to system resources is controlled. Security of the system from outsiders requires user authentication, and extends to defending external I/O devices from invalid access attempts
22
Q
Describe The Functions of Command Line Interface
A
- allows direct command entry
- Primarily fetches a command from user and executes it
23
Q
GUI
A
- Usually mouse, keyboard, and monitor
- Icons represent files, programs, actions, etc
- Various mouse buttons over objects in the interface cause various actions
24
System calls
- Provides an interface to the services provided by the OS
- Typically written in a high-level language (C or C++)
- Mostly accessed by programs via a high-level Application Program Interface (API) rather than direct system call use
25
System Call Implementation
- A number is associated with each system call
- System-call interface maintains a table indexed according to these numbers
- The system call interface invokes intended system call in OS kernel and returns status of the system call and any return values
26
API - System Call - OS Relationship
The use of APIs provides for greater program portability between different systems. The API makes the appropriate system calls through the system call interface, using a table lookup to access specific numbered system calls.
27
Methods of System Call Parameter Passing
Simplest: pass the parameters in registers
Parameters stored in a table, in memory, and address of block passed as a parameter in a register
Parameters placed, onto the stack by the program and popped off the stack by the operating system
28
types of system calls
Process control
File management
Device management
Information maintenance
Communications
Protection
29
System programs provide?
a convenient environment for program development and execution
30
system program can be divided into
File manipulation
Status information
File modification
Programming language support
Program loading and execution
Communications
Application programs
31
describe the monolithic structure of kernel organization
- Consists of everything below the system-call interface and above the physical hardware
32
describe the layered approach
The operating system is divided into a number of layers, each built on top of lower layers and relies solely on the services provided by the next lower layer. The bottom layer is the hardware; the highest is the user interface
33
describe the modular approach
- Uses an object-oriented approach, with a relatively small core kernel and a set of module which can be linked in dynamically.
- Each core component is separate
- Each talks to the others over known interfaces
- Each is loadable as needed within the kernel
34
Modular vs layered
Modules are similar to layers in that each subsystem has clearly defined tasks and interfaces, but any module is free to contact any other module, eliminating the problems of going through multiple intermediary layers
The kernel is relatively small in this architecture, similar to microkernels, but the kernel does not have to implement message passing since modules are free to contact each other directly.
35
Benefits of Microkernel System Structure
adding a new service does not require modifying the kernel
b. it is more secure as more operations are done in user mode than in kernel mode
c. a simpler kernel design and functionality typically results in a more reliable operating system
36
Solaris modular approach consists of?
1. scheduling classes
2. file system
3. loadable system calls
4. executable formats
5. STREAMS modules
6. miscellaneous modules
7. device and bus drivers
37
describe Virtual machine
A virtual machine takes the layered approach to its logical conclusion. It treats hardware and the operating system kernel as though they were all hardware
A virtual machine provides an interface identical to the underlying hardware
The operating system host creates the illusion that a process has its own processor and virtual memory
Each guest is provided with a virtual copy of underlying computer
38
List the four steps that are necessary to run a program on a completely dedicated machine—a
computer that is running only that program
reserve machine time.
Manually load program into memory
load starting address and begin execution
monitor and control execution of program from console
39
How does the distinction between kernel mode and user mode function as a rudimentary form
of protection (security) system?
- certain instructions could be executed only when the CPU is in kernel mode
- hardware devices could be accessed only when the program is in kernel mode
- control over when interrupts could be enabled or disabled is possible only when the CPU is in kernel mode
- CPU has limited capability when executing in user mode, thereby enforcing protection of critical resources
40
What is the purpose of interrupts?
An interrupt can be used to signal the completion of an I/O to obviate the need for device polling
A trap can be used to call operating system routines or to catch arithmetic errors
41
What are the differences between a trap and an interrupt?
An interrupt can be used to signal the completion of an I/O to obviate the need for device polling
An interrupt is a hardware-generated change of flow within the system
A trap can be used to call operating system routines or to catch arithmetic errors
A trap is a software-generated interrupt
42
What is the purpose of traps?
A trap can be used to call operating system routines or to catch arithmetic errors
43
Propose of CPU Scheduler
Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them
44
when does CPU scheduling decisions take place
when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
45
Describe Context Switch
- When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process via a context switch, -- involves saving and restoring all of the registers, program counter(s), and process control blocks
46
what Are The Scheduling Algorithm Optimization Criteria?
Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
47
list the process in memory
program counter
stack
data section
Text
heap
48
List the Process States
* New: The process is being created.
* Running: Instructions are being executed.
* Waiting: The process is waiting for some event to occur.
* Ready: The process is waiting to be assigned to a process.
* Terminated: The process has finished execution.
49
List Out Process Control Block (PCB)
Process State
Process ID, and parent process ID.
CPU registers and Program Counter
CPU-Scheduling information
Memory-Management information
Accounting information
I/O Status information
50
State Objectives of Process Scheduling Queues
1. to keep the CPU busy at all times
2. to deliver "acceptable" response times for all programs, particularly for interactive ones.
- The process scheduler must meet these objectives by implementing suitable policies for swapping processes in and out of the CPU.
51
state the Process Scheduling Queues
o Job queue – set of all processes in the system
o Ready queue – set of all processes residing in main memory, ready and waiting to execute
o Device queues – set of processes waiting for an I/O device
52
list out the Schedulers
- Long-term scheduler: selects which processes should be brought into the ready queue
- Medium-term scheduler: When system loads get high, this scheduler will swap one or more processes out of the ready queue system for a few seconds, in order to allow smaller faster jobs to finish up quickly and clear the system
- Short-term scheduler: selects which process that in ready queue should be executed next and allocates CPU
53
Describe Process Creation
- Parent process creates children processes through appropriate system calls, such as fork or spawn, which, in turn, create other processes, forming a tree of processes
- Process is identified and managed via a process identifier (PID). The parent PID (PPID) is also stored for each process.
54
Describe the Resource Sharing Types
Parent and children share all resources
Children share subset of parent’s resources
Parent and child share no resources
55
Describe the Execution Types
Parent and children execute concurrently
Parent waits until children terminate
56
Describe Address space
o Child duplicate of parent
o Child has a program loaded into it
57
State the UNIX examples
fork system call creates new process
exec system call used after a fork to replace the process’ memory space with a new program
58
Describe Process Termination
Process executes last statement and asks the operating system to delete it (exit)
Output data from child to parent (via wait)
Process’ resources are deallocated by operating system
Parent may terminate execution of children processes (abort)
Child has exceeded allocated resources
Task assigned to child is no longer required
If parent is exiting, some operating system do not allow child to continue if its parent terminates
59
Describe Inter-process Communication
Two models of IPC
Shared memory - is faster once it is set up, because no system calls are required and access occurs at normal memory speeds. However, it is more complicated to set up and doesn't work as well across multiple computers. Shared memory is generally preferable when large amounts of information must be shared quickly on the same computer.
Message passing -- requires system calls for every message transfer, and is therefore slower, but it is simpler to set up and works well across multiple computers. Message passing is generally preferable when the amount and/or frequency of data transfers is small, or when multiple computers are involved.
60
State the Reasons for cooperating processes
Information Sharing - There may be several processes that need access to the same file
Computation speedup - Often a solution to a problem can be solved faster if the problem can be broken down into sub-tasks to be solved simultaneously
Modularity - The most efficient architecture may be to break a system down into cooperating modules.
Convenience - Even a single user may be multi-tasking, such as editing, compiling, printing, and running the same code in different windows.
61
State The Benefits of Multi-Threading
Increased responsiveness - Even if one thread is blocked, other threads can still run.
Resource sharing: - Code sharing, and memory sharing.
Economy - Creation of threads uses fewer resources as compared to processes.
Taking advantage of multiprocessors - Threads can run parallel on different processors.
62
describe single thread
There is one program counter, and one sequence of instructions that can be carried out at any given time.
63
describe multi-thread
multi-threaded applications have multiple threads within a single process, each having their own program counter, stack and set of registers, but sharing common code, data, and certain structures such as open files.
64
List the Challenges of Multithreading Programming
Dividing activities – identifying concurrent task
Balance - Finding tasks to run concurrently that provide equal value.
Data splitting - To prevent the threads from interfering with one another.
Data dependency - If one task is dependent upon the results of another, then the tasks need to be synchronized to assure access in the proper order.
Testing and debugging - Inherently more difficult in parallel processing situations, as the race conditions become much more complex and difficult to identify.
65
Describe user threads
Thread management is done by user-level threads library
Three primary thread libraries: POSIX threads, Win32 threads, Java threads
66
Describe kernel threads
Managed by the kernel
Supported by Windows, Linux, Mac OS X
67
List the Multithreading Models
Many-to-One
One-to-One
Many-to-Many
68
describe many-to-one Multithreading Model
Many user-level threads mapped to single kernel thread
many user-level threads are all mapped onto a single kernel thread.
Thread management is handled by the thread library in user space, which is very efficient.
However, if a blocking system call is made, then the entire process will block because a single kernel thread can operate only on a single CPU, the many-to-one model does not allow individual processes to be split across multiple CPUs.
69
describe one-to-one Multithreading Model
Maps each user-level thread to kernel thread
The one-to-one model creates a separate kernel thread to handle each user thread.
One-to-one model overcomes the problems involving blocking system calls and the splitting of processes across multiple CPUs.
the overhead of managing the one-to-one model is more significant, involving more overhead and slowing down the system.
Most implementations of this model place a limit on how many threads can be created.
70
describe Many-to-Many Multithreading Model
Allows many user level threads to be mapped to many kernel threads
Allows the operating system to create a sufficient number of kernel threads
The many-to-many model multiplexes any number of user threads onto an equal or smaller number of kernel threads, combining the best features of the one-to-one and many-to-one models.
Users have no restrictions on the number of threads created.
Blocking kernel system calls do not block the entire process.
Processes can be split across multiple processors.
Individual processes may be allocated variable numbers of kernel threads, depending on the number of CPUs present and other factors.
71
what are signal handling used for
A signal handler is used to process signals
- Signal is generated by a particular event
- Signal is delivered to a process
- Signal is handled
72
state the approaches to thread cancellation
Asynchronous cancellation terminates the target thread immediately
Deferred cancellation allows the target thread to periodically check if it should be cancelled. It sets a flag indicating the thread should cancel itself when it is convenient. It is then up to the cancelled thread to check this flag periodically and exit nicely when it sees the flag set.
73
Describe symmetric and asymmetric multiprocessing.
Symmetric multiprocessing treats all processors as equals, and I/O can be processed on any CPU.
Asymmetric multiprocessing has one master CPU and the remainder CPUs are slaves. The master
distributes tasks among the slaves, and I/O is usually done by the master only.
74
What are three
advantages and one disadvantage of multiprocessor systems?
Multiprocessors can save money by not duplicating power supplies, housings, and peripherals.
They can execute programs more quickly
can have increased reliability.
They are more complex in both hardware and software than uniprocessor systems.
75
Describe Two-level Model
Similar to M:M, except that it allows a user thread to be bound to kernel thread
76
State the function of thread pools
Create a number of threads in a pool where they await work
77
State the Advantages of Thread Pools
Usually slightly faster to service a request with an existing thread than create a new thread
Allows the number of threads in the application(s) to be bound to the size of the pool
78
State the Function of Thread Specific Data
Allows each thread to have its own copy of data
Useful when you do not have control over the thread creation process
79
What is the purpose of booting in a computer? When does it start?
The purpose of booting is to load the kernel from secondary storage to primary memory and
initialize the registers, memory and I/O devices and their controllers. After the booting the O/S is
ready to accept commands and to provide services to application programs and users.
The booting starts when you switch on the power or resets the computer.
80
How does the distinction between kernel mode and user mode function as a rudimentary form
of protection (security) system?
The distinction between kernel mode and user mode provides a rudimentary form of protection
in the following manner. Certain instructions could be executed only when the CPU is in kernel
mode.
Similarly, hardware devices could be accessed only when the program is executing in kernel
mode. Control over when interrupts could be enabled or disabled is also possible only when the
CPU is in kernel mode. Consequently, the CPU has very limited capability when executing in user
mode, thereby enforcing protection of critical resources.
81
Direct memory access is used for high-speed I/O devices in order to avoid increasing the CPU’s
execution load.
* How does the CPU interface with the device to coordinate the transfer?
* How does the CPU know when the memory operations are complete?
The CPU is allowed to execute other programs while the DMA controller is transferring data.
Does this process interfere with the execution of the user programs? If so, describe what forms of
interference are caused.
The CPU can initiate a DMA operation by writing values into special registers that can be
independently accessed by the device. The device initiates the corresponding operation once it
receives a command from the CPU.
When the device is finished with its operation, it interrupts the CPU to indicate the completion of
the operation. Both the device and the CPU can be accessing memory simultaneously. The
memory controller provides access to the memory bus in a fair manner to these two entities. A
CPU might therefore be unable to issue memory operations at peak speeds since it has to
compete with the device in order to obtain access to the memory bus.
82
Give two reasons why caches are useful.
Caches are useful when two or more components need to exchange data, and the
components perform transfers at differing speeds.
* Caches solve the transfer problem by providing a buffer of intermediate speed between the
components. If the fast device finds the data it needs in the cache, it need not wait for the
slower device.
83
What problems does cache solve?
Caches solve the transfer problem by providing a buffer of intermediate speed between the components. If the fast device finds the data it needs in the cache, it need not wait for the slower device.
84
If a cache can be made as large as the device for which it is caching (for instance, a cache
as large as a disk), why not make it that large and eliminate the device?
A component may be eliminated by an equal-sized cache, but only if: (a) the cache and the
component have equivalent state-saving capacity (that is, if the component retains its data
when electricity is removed, the cache must retain data as well), and (b) the cache is
affordable, because faster storage tends to be more expensive.
85
Illustrate with an example how data
residing in memory could in fact have two different values in each of the local caches. (SMP system)
Say processor 1 reads data A with value 5 from main memory into its local cache. Similarly,
processor 2 reads data A into its local cache as well. Processor 1 then updates A to 10. However,
since A resides in processor 1’s local cache, the update only occurs there and not in the local
cache for processor 2.
86
What do you mean by BUS organized computer?
In a digital computer CPU, multiple device controllers are connected through a system bus, to shared memory. For this reason it is called bus organized computer.
87
Describe briefly about memory hierarchy.
As the CPU Registers are very fast, memory should be compatible with them. Fast storage tends
to be large, expensive and power hungry. We can use levels of increasingly large (and increasingly
slow) storage, with the most likely information to be used soon stored at each level. Often the
information at each larger level is a superset of the information stored at the next smaller level.
Memory levels get slower and larger as they get farther from the processor.
88
Differentiate between the operating system models handling master-slave multiprocessors and
symmetric multiprocessors.
In OS model handling master-slave multiprocessors, one copy of the operating system and its
tables is present on CPU1 and not on any of the others. All system calls are redirected to CPU1 for
processing. This model is called master-slave since CPU1 is the master and all the others are
slaves.
Advantages:
* There is a single data structure that keeps track of ready processes. When a CPU goes idle, it
asks the OS on CPU1 for a process to run and is assigned one. No overloading possible.
* Pages can be allocated among all the processes dynamically.
Disadvantage:
* Since master CPU must handle all system calls from all CPUS, master will become a
bottleneck with many CPUs in the system. This model is workable for small multiprocessors.
89
What is the purpose of system calls?
System calls allow user-level processes to request services of the operating system.
90
What is the purpose of system programs?
System programs can be thought of as bundles of useful system calls. They provide basic functionality to
users so that users do not need to write their own programs to solve common problems.
91
Would it be possible for the user to develop a new command interpreter using the system-call interface
provided by the operating system?
A user should be able to develop a new command interpreter using the system-call interface provided by
the operating system. The command interpreter allows a user to create and manage processes and also
determine ways by which they communicate (such as through pipes and files). As all of this functionality
could be accessed by a user level program using the system calls, it should be possible for the user to
develop a new command-line interpreter.
92
What are the disadvantages of using the
microkernel approach?
The disadvantages of the microkernel architecture are the overheads associated with interprocess communication and the frequent use of the operating system’s messaging functions in order to enable the
user process and the system service to interact with each other.
93
In what ways is the modular kernel approach similar to the layered approach?
The modular kernel approach and layered kernel approach requires subsystems to interact with each other through carefully constructed interfaces that are typically narrow.
94
In what ways does it differ
from the layered approach?
the layered kernel imposes a
strict ordering of subsystems such that subsystems at the lower layers are not allowed to invoke
operations corresponding to the upper-layer subsystems. There are no such restrictions in the modular-
kernel approach, wherein modules are free to invoke each other without any constraints.
95
What is the relationship between a guest operating system and a host operating system in a system like
VMware?
A guest operating system provides its services by mapping them onto the functionality provided by the
host operating system.
96
What factors need to be considered in choosing the host operating system?
whether it is sufficiently general in terms of its system-call interface in order to support the functionality associated with the guest operating system.
97
describe CPU scheduler
Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them
CPU scheduling decisions take place when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
Scheduling under 1 and 4 is nonpreemptive
All other scheduling is preemptive
97
describe dispatcher
Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:
switching context
switching to user mode
jumping to the proper location in the user program to restart that program
98
state the scheduling criteria
CPU utilization – keep the CPU as busy as possible
Throughput – number of processes that complete their execution per time unit
Turnaround time – amount of time to execute a process
Waiting time – amount of time a process has been waiting in the ready queue
Response time – amount of time it takes from when a request was submitted until the first response is produced, not output
99
state scheduling algorithm optimization criteria
Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
100
Explain the difference in the degree to which the following scheduling algorithms discriminate in favor of short processes.
a) FCFS
b) RR
a) FCFS – discriminates against short jobs since any short jobs arriving after long jobs will have a longer waiting time.
b) RR – treats all jobs equally so short jobs will be able to leave the system faster since they will finish first
101
What is the difference between preemptive and non-preemptive scheduling?
Preemptive scheduling allows a process to be interrupted during its execution, taking the CPU away and allocate it to another process.
Non-preemptive scheduling ensures that a process relinquishes control of the CPU only when it finishes with its current CPU burst.
102
Why is it important for the scheduler to distinguish I/O-bound programs from CPU-bound
programs?
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/O-bound programs and allow them to execute ahead of the CPU-bound
programs
103
describe multilevel queue
Ready queue is partitioned into separate queues:
foreground(interactive)
background (batch)
Each queue has its scheduling algorithm
foreground – RR
background – FCFS
104
list out multilevel queue scheduling (highest > lowest priority)
System processes > Interactive processes > Interactive editing processes > batch processes > Student processes
105
Describe Multilevel Feedback Queue
Multilevel-feedback-queue scheduler defined by the following parameters:
number of queues
scheduling algorithms for each queue
method used to determine when to upgrade a process
method used to determine when to demote a process
method used to determine which queue a process will enter when that process needs service
106
what are the classical Problems of Synchronization?
Bounded-Buffer Problem
Readers and Writers Problem
Dining-Philosophers Problem
107
Semaphore Implementation with no Busy waiting
With each semaphore, there is an associated waiting queue. Each entry in a waiting queue has two data items:
value (of type integer)
pointer to the next record in the list
Two operations:
block – place the process invoking the operation on the appropriate waiting queue.
wakeup – remove one of the processes in the waiting queue and place it in the ready queue.
108
The solution to Critical-Section Problem
1. Mutual Exclusion: If process Pi is executing in its critical section, then no other processes can be executing in their critical sections
2. Progress: If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed
3. Bounded Waiting: A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
109
describe ways for deadlock prevention
Mutual Exclusion: Ensure that resources are acquired mutually exclusively. If a process holds a resource, then no other process should be able to access it until the holding process releases it.
Hold and Wait: Ensure that a process must hold all its required resources before it starts execution. If it cannot get all the resources it needs at once, it should release whatever resources it holds and try again later.
No Preemption: Resources cannot be forcibly taken away from a process; they can only be released voluntarily.
Circular Wait: Avoid circular waits by imposing a total ordering of all resource types and ensuring that each process requests resources in increasing order of enumeration.
110
describe progress
If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely
111
describe bounded waiting
a bound must exist on the number of times that other processes are allowed to enter their critical section after a process has requested to enter its critical section and before
that request is granted
112
What is the meaning of the term busy waiting?
Busy waiting means that a process is waiting for a condition to be satisfied in a tight loop without relinquishing the processor.
113
Briefly explain Peterson’s solution to the critical-section problem
Peterson’s solution is restricted to two processes that alternate execution between their critical
sections and remainder sections.
Assume that the LOAD and STORE instructions are atomic; that is, they cannot be interrupted.
The two processes share two variables, int turn; and Boolean flag[2].
The variable turn indicates whose turn it is to enter the critical section.
The flag array is used to indicate if a process is ready to enter the critical section. flag[i] = true implies that process Pi is ready to enter its critical section.
The structure of the process Pi in Peterson’s solution is given below:
114
Bounded Buffer Problem
write the code for the structure of the producer process
do {
// produce an item in nextp
wait (empty);
wait (mutex);
// add the item to the buffer
signal (mutex);
signal (full);
} while (TRUE);
115
Bounded Buffer Problem
write the code for the structure of the consumer process
do {
wait (full);
wait (mutex);
// remove an item from buffer to nextc
signal (mutex);
signal (empty);
// consume the item in nextc
} while (TRUE);
116
write the code for the structure process Pi in Peterson's solution
do {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = FALSE;
remainder section
} while (TRUE);
/ do nothing
117
Explain the four conditions that must hold for deadlock to occur.
* Mutual exclusion: Only one process can use a resource at a time.
* Hold and wait: A process holding at least one resource is waiting to acquire additional resources held by other processes.
* No preemption: a resource can be released only voluntarily by the process holding it after it has completed its task.
* Circular wait: There exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that P1 holds, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that Pn holds, and P0 is waiting for a resource that is held by P0.
118
describe the methods of handling deadlock
1) Deadlock prevention or avoidance
2) Deadlock detection and recovery
3) Ignore the problem altogether: If deadlock is very rare, then let it happen and reboot the system.
119
120
describe semaphore
Synchronization tool that does not require busy waiting
Semaphore S is an integer variable
Two standard operations modify S: wait() and signal()
Less complicated
Can only be accessed via two indivisible (atomic) operations:
121
describe semaphore as general synchronization tool
Counting semaphore – integer value can range over an unrestricted domain
Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement
Also known as mutex locks
Can implement a counting semaphore S as a binary semaphore
Provides mutual exclusion
122
write the code for Semaphore
Semaphore mutex; // initialized to 1
do {
wait (mutex);
// critical Section
signal (mutex);
// remainder section
} while (TRUE);
123
write the code for wait operation
wait (s) {
while s <= 0
; // no-op
s--;
}
124
write the code for signal operation
signal (s) {
s++;
}
125
write the code for the structure of the reader process
do {
wait (mutex) ;
readcount ++ ;
if (readcount == 1)
wait (wrt) ;
signal (mutex)
// reading is performed
wait (mutex) ;
readcount -- ;
if (readcount == 0)
signal (wrt) ;
signal (mutex) ;
} while (TRUE);
126
write the code for the structure of Philosopher
do {
wait ( chopstick[i] );
wait ( chopStick[ (i + 1) % 5] );
// eat
signal ( chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
// think
} while (TRUE);
127
describe semaphore implementation
Must guarantee that no two processes can execute wait () and signal () on the same semaphore at the same time.
Thus, implementation becomes the critical section problem where the wait and signal code are placed in the critical section.
128
state the ways to recover from deadlock
process termination - Abort all deadlocked processes
resource preemption
129
What is the optimistic assumption made in the deadlock-detection algorithm? How could this
assumption be violated?
The optimistic assumption is that there will not be any form of circular wait in terms of resources allocated and processes making requests for them. The assumption could be violated if a circular wait does indeed occur in practice
130
What are the process elements in a process control block (PCB)?
§ Identifier: A unique identifier associated with this process, to distinguish it from all other processes.
§ State: If the process is currently executing, it is in the running state.
§ Priority: Priority Level relative to other processes.
§ Program counter: The address of the next instruction in the program to be executed.
§ Memory pointers: Includes pointers to the program code and data associated with this process, plus any memory blocks shared with other processes.
§ Context data: These are data present in the processor's registers while the process is executing.
§ I/O status information: Includes outstanding I/O requests, I/O devices (e.g., tape drives ) assigned to this process, a list of files used by the process, and so on.
§ Accounting information: May include the amount of processor time and clock time used, time limits, account numbers, and so on
131
Describe the actions taken by a kernel to context-switch between processes
In general, the operating system must save the state of the currently running process and restore the state of the process scheduled to be run next. Saving the state of a process typically includes the values of all the CPU registers in addition to memory allocation. Context switches must also perform many architecture-specific operations, including flushing data and instruction caches.
132
Sate the Implementation of Page Table
Page table is kept in main memory
Page-table base register (PTBR) points to the page table
Page-table length register (PRLR) indicates size of the page table
133
