Operating Systems, OS, OS Midterm 1, OS quiz 2, OS Midterm, OS 2, OS 3, Operating Systems, OS Final
Section 1
Preview this deck
As a process executes, it changes state. What are the states
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
0
All-time users
0
Favorites
0
Last updated
6 years ago
Date created
Mar 1, 2020
Cards (507)
Section 1
(50 cards)
As a process executes, it changes state. What are the states
new, running, waiting, ready, terminated.
context switch
When CPU switches to another process, the system must save the state of the old process via a context switch
Process identifier (pid)
Generally, process identified and managed via a process identifier
Time-shared Systems
user programs or tasks
CPU-bound process
spends more time doing computations; few very long CPU bursts.
Heap
containing memory dynamically allocated during run time.
A process memory is divided into four sections
The text section, stack, data section, heap
A new process is initially put in
ready queue
wait
Output data from child to parent
fork system call
creates new process
short-term scheduler (or CPU scheduler)
selects which process should be executed next and allocates CPU
Resource sharing
parent and children share all resources. child share subset of parent resources. parent and child share no resources.
abort
Parent may terminate execution of child processes
Current activity of process include
program counter, processor registers
the function fork returns
an integer equal to 0 to the child process and one different from 0 to the parent process.
Parent process create
new processes (children) which in turn create other processes forming a tree of processes
Address Space
Child duplicate of parent. Child has a program load into it
Process scheduling maintains scheduling queues of processes
Job Queue, Ready Queue, Device Queue
exec call
used after a fork to replace the process memory space ith a new program
The more complex the OS and the PCB the ->
longer the context switch
Information associated with each process
Process id, process state, program counter, CPU registers, CPU scheduling information, Memory-management information, Accounting information, I/O status information.
the eleclp system calls used
after a fork system call by one of the processes to replace the process memory space with a new program
Job Queue
set of ll processes in the system
I/O-bound process
spends more time doing IO than computations; many short PCU bursts
Short term scheduler is invoked very
frequently
Stack Containing temp data
Function parameters, return addresses, return addresses, local variables
mid-term, scheduler (medium-term - swapping)
Removes processes from the memory. Reduces the degree of multi-programming. (speed between long & short.)
Long-term Scheduler (job scheduler)
selects which processes should be brought into the ready queue
The operating System at all times has a table called the
process table
Batch System
jobs
Process Control Block (PCB)
Process State-> Process Number-> Program Counter-> registers-> memory limits-> list of open files
Data Section
containing global variables
When are processes terminated?
When they're done, When an error occurs, When a fatal error occurs, or When killed by another process
process
a program in execution, which forms the basis of all computation; process execution must progress in sequential fashion
can one program have several processes?
yes
When are processes created?
On system start-up, On system calls, On user requests
Process schedulaer
selects among available process for next execution on CPU
text section
the program code
exit
Process executes last statement and asks the operating system to delete it
The parent waits for the child process to complete with
the wait system call (example in 3.30)
Execution
Parent and child execute concurrently. Parent waits until children terminate.
Time dependent on
Memory speed, Speed of saving registers, # of registers
Context- switch time is overhead
the system does no useful work while switching
Ready Queue
set of processes waiting for an I/O device
Contest switching of a process is represented in
PCB
long term scheduler controls the
degree of multiprogramming
long term scheduler is invoked very
frequently
program is a _____ entity whereas process is ____
passive, active
Child process creation statement
pid = fork()
The OS manages processes by
creating & deleting, suspending & restarting, assigning, Scheduling, Synchronizing, Providing communication between.
Section 2
(50 cards)
Reasons for cooperating processes
information sharing, Computation speed up, modularity, convenience
Some computer systems do not provide a privileged mode of operation in hardware. Is it possible to construct a secure operating system for these computer systems? Give arguments both that it is and that it is not possible.
An operating system for a machine of this type would need to remain in control (or monitor mode) at all times. This could be accomplished by two methods: Software interpretation of all user programs. The software interpreter would provide, in software, what the hardware does not provide. Require meant that all programs be written in high-level languages so that all object code is compiler-produced. The compiler would generate the protection checks that the hardware is missing.
What is peer to peer computing?
In the peer-to-peer model all nodes in the system are considered peers and thus may act as either clients or servers - or both. A node may request a service, or provide such a service to other peers in the system.
OS is a resource allocator
Manages all resources. Decides between conflicting requests for efficient and fair resource use
How are links established?
Link is established automatically between communicating processes.
What is the capacity of a link?
Zero capacity - the link cannot have any messages waiting in it. Sender must wait for receiver Bounded capacity - finite length of n messages Sender must wait if link is full Unbounded capacity - infinite length
context - switching
save old process and load new. overhead. time dependent.
Is the size of a message that the link can accommodate fixed or variable?
both?
Cooperating processes require
an inter process communication mechanism (IPC)
What is a Client Server?
The client-server model firmly distinguishes the roles of the client and server. Under this model, the client requests services that are provided by servers.
Two models of IPC?
Shared memory. Message passing
Processes within a system may be
independent or cooperating
What are 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 processor terminated: The process has finished execution
Reasons for cooperating processes?
Information sharing, Computation speedup, Modularity, Convenience
What are the steps to process creation? (be able to show how processes are created.)
Know how to read coding examples with forking.
ready queue
main memory, ready, and wait to execute
Device queue
set of processes waiting for IO device
MS-DOS provided no means of concurrent processing. Discuss three major complications that concurrent processing adds to an operating system.
A method of time sharing must be implemented to allow each of several processes to have access to the system . Processes and system resources must have protections and must be protected from each other. Any given process must be limited in the amount of memory it can use and the operations it can perform on devices like disks. Care must be taken in the kernel to prevent deadlocks between processes, so processes aren't waiting for each other's allocated resources.
OS is a control program
Controls execution of programs to prevent errors and improper use of the computer
What is Dual mode operation?
allows OS to protect itself and other system components (User mode and kernel mode)
scheduler
long term (job - ready queue - slow - infrequent), short term (CPU - executing - fast - frequent), mid-term(medium -Swap)
Is a link unidirectional or bi-directional?
The link may be unidirectional, but is usually bi-directional.
Message system
processes communicate with each other without sharing the same address space
multi-threading benefits
simplify code, increase efficiency >> Responsiveness, >> Resource sharing >> Economy >> Scalability
process scheduler
selects among available processes for next execution on CPU
cooperating process
producer consumer, shared mem, protection, need to prevent deadlocks
How many links can there be between every pair of communicating processes?
Exactly one link for every pair of processes.
What is Timer for?
Timer to prevent infinite loop / process hogging resources
Operating system goals:
Ease of use, Compromise between individual usability and resource utilization, optimized for usability and battery life
process
a program in execution
Two models of IPC
shared memory, Message passing
IPC facility provides two operations:
send(message) - message size fixed or variable. receive(message)
What is a shared memory system?
shared memory requires communicating processes to establish a region of shared memory. Resides in the address space of the Process. Other processes must attach the shared memory to their address space
process creation (fork)
system start up, system call, user requests
Process states
new, running, waiting, ready, terminated
What are some differences between client server and peer-to-peer computing?
no central server. Each workstation on the network shares its files equally with the others. There's no central storage or authentication of users. separate dedicated servers and clients in a client/server network.
process termination
done, error, fatal, error, killed.
Criteria for CPU Scheduling
Cannot affect CPU time or IO time. Can affect time in ready queue and ready queue wait time.
Parent terminating child process execution
Child exceeds allocated resources, Task assigned to child is no longer required, if parent is exiting (cascading termination)
multi-threading models
many to 1, one to one, many to many
The services and functions provided by an operating system can be divided into two sets.
To provide functions that are helpful to the user. To ensure efficient operation of the system itself.
job queue
system
Threading issues
semantics of fork and execution, thread cancellation of target, signal handling, thread pools, thread specific data, schedular activation
creating process using unix and C example
3.34
what is interprocess communication?
Cooperating processes require an interprocess communication (IPC) mechanism
What is Operating System?
A program that acts as an intermediary between a user of a computer and the computer hardware.
Can a link be associated with more than two processes
Link is associated with exactly two processes. (1 pair)
process control block
state, number, counter, registers, memory limits, list of open files
Cooperating process can affect or be affected by other processes including
Sharing data
What is a message passing system?
a mechanism to allow processes to communicate and to synchronize their action
Section 3
(50 cards)
What does SRTF stand for? Describe it.
Shortest-remaining-time-first. After every interrupt select the process with shortest next burst time. Preemptive - if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. Advantage: Can yield minimum average waiting time. Disadvantage: Increased Overhead
Explain Scheduling in the threading system.
Both many-to-many and Two-level models require communication to maintain the appropriate number of kernel threads allocated to the application Scheduler activations provide upcalls - a communication mechanism from the kernel to the thread library This communication allows an application to maintain the correct number kernel threads
What are the goals of Operating Systems for personal computers and mainframe computers?
Convenience and efficiency
Provide one programming example in which multithreading does provide better performance than a single-threaded solution and one example in which multithreading does not provide better performance than a single-threaded solution.
A Web server that services each request in a separate thread. (2) A parallelized application such as matrix multiplication where different parts of the matrix may be worked on in parallel. Any kind of sequential program is not a good candidate to be threaded, for example, calculating an individual tax return.
Synchronization Hardware. What does TestANDSet() do?
What main services that OS provides?
Program execution I/O operations File System manipulation Communication Error Detection Resource Allocation Protection
The traditional UNIX scheduler enforces an inverse relationship between priority numbers and priorities: the higher the number, the lower the priority. The scheduler recalculates process priorities once per second using the following function: Priority = (recent CPU usage / 2) + base, where base = 60 and recent CPU usage refers to a value indicating how often a process has used the CPU since priorities were last recalculated. Assume that recent CPU usage for process P1 is 40, for process P2 is 18, and for process P3 is 10. What will be the new priorities for these three processes when priorities are recalculated? Based on this information, does the traditional UNIX scheduler raise or lower the relative priority of a CPU-bound process?
The priorities assigned to the processes are 80, 69, and 65 respectively. The scheduler lowers the relative priority of CPU-bound processes.
What role do simulations play in algorithm evaluations?
Queueing models limited, Simulations more accurate. (Programmed model of computer system, Clock is a variable, Gather statistics indicating algorithm performance, Data to drive simulation gathered)
What is queuing modeling?
Describes the arrival of processes, and CPU and I/O bursts probabilistically
What is deterministic modeling?
Type of analytic evaluation, Takes a particular predetermined workload and defines the performance of each algorithm for that workload.
Describe the Round Robin Algorithm.
Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue. If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units. Timer interrupts every quantum to schedule next process. Performance (q large =>FIFO, q small =>q must be large with respect to context switch, otherwise overhead is too high)
User vs. Kernel level thread
don't need system calls then use user-level threads because they are faster. If the threads need system calls then kernel-level threads are better
When a process creates a new process using the fork() system call, which of the following states is shared between the parent process and the child process? a.) Stack b.) Heap c.) Shared memory segments
Heap and shared memory segments are shared between the parent process and the newly forked child process.
What are kernel level threads?
Supported and managed by OS, Virtually all modern general-purpose operating systems support them Kernel sees every thread of every process. If a thread makes a system call, other threads within that process can run. Switching among threads of a process is done via interrupts. Context switching is slower than for user-level threads but faster than process context switching. Takes advantage of multiprocessor
Describe the Priority SchedulingAlgorithm.
A priority number (integer) is associated with each process: The CPU is allocated to the process with the highest priority (smallest integer= highest priority): Preemptive, Nonpreemptive. SJF is priority scheduling where priority is the inverse of predicted next CPU burst time. Problem = Starvation - low priority processes may never execute. Solution = Aging - as time progresses increase the priority of the process.
Synchronization Hardware. What are Semephores?
variable or abstract data type that is used for controlling access, by multiple processes, to a common resource in a concurrent system such as a multiprogramming operating system
What is the bounded-buffer problem?
a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue. N -cells buffer, each cell can hold one item Semaphore mutex initialized to the value 1 Semaphore full initialized to the value 0 Semaphore empty initialized to the value N
One way to evaluate an algorithm?
The first step in determining which algorithm ( and what parameter settings within that algorithm ) is optimal for a particular operating environment is to determine what criteria are to be used, what goals are to be targeted, and what constraints if any must be applied. For example, one might want to "maximize CPU utilization, subject to a maximum response time of 1 second". Once criteria have been established, then different algorithms can be analyzed and a "best choice" determined. The following sections outline some different methods for determining the "best choice".
What role does algorithms play in algorithm evaluations?
Determine criteria, then evaluate algorithms, Deterministic modeling: Type of analytic evaluation, Takes a particular predetermined workload and defines the performance of each algorithm for that workload.
What are advantages and disadvantages of using kernel-level threads?
Advantages: Because kernel has full knowledge of all threads, Scheduler may decide to give more time to a process having large number of threads than process having small number of threads. Kernel-level threads are especially good for applications that frequently block. Disadvantages: The kernel-level threads are slow and inefficient. For instance, threads operations are hundreds of times slower than that of user-level threads. Since kernel must manage and schedule threads as well as processes. It require a full thread control block (TCB) for each thread to maintain information about threads. As a result there is significant overhead and increased in kernel complexity.
Name activities are performed by OS to context switch between processes.
Save state of P1 Service interrupt Select next user process P2 Restore state of P2 and restart CPU
Under what circumstances is better to use kernel-level threads than user-level threads?
User-level threads are threads that the OS is not aware of. They exist entirely within a process, and are scheduled to run within that process's timeslices. The OS is aware of kernel-level threads. Kernel threads are scheduled by the OS's scheduling algorithm, and require a "lightweight" context switch to switch between (that is, registers, PC, and SP must be changed, but the memory context remains the same among kernel threads in the same process). User-level threads are much faster to switch between, as there is no context switch; further, a problem-domain-dependent algorithm can be used to schedule among them. CPU-bound tasks with interdependent computations, or a task that will switch among threads often, might best be handled by user-level threads. Kernel-level threads are scheduled by the OS, and each thread can be granted its own timeslices by the scheduling algorithm. The kernel scheduler can thus make intelligent decisions among threads, and avoid scheduling processes which consist of entirely idle threads (or I/O bound threads). A task that has multiple threads that are I/O bound, or that has many threads (and thus will benefit from the additional timeslices that kernel threads will receive) might best be handled by kernel threads. Kernel-level threads require a system call for the switch to occur; user-level threads do not.
Thread Basics
Threads of the same process share the entire process address space as well as all open files. Each thread has its own program counter and CPU register set. Cooperation among threads is much easier Also context switching among the threads of the same process is faster Notice the need to protect critical sections Programmer defines the threads in a process
What does FCFS stand for? Describe it.
First-Come, First-Served (FCFS) Scheduling. Non-preemptive (Processes are assigned the CPU in the same order as they arrive at the Ready Queue) Advantage: Easy to implement and fairness (no starvation). Disadvantage: Low overall system throughput
What are some of the scheduling algorithms?
FCFS, SJF, SRTF
what are some multi-threading models?
Many-to-One One-to-One Many-to-Many
Describe the action taken by kernel to context -switch between processes.
1. In response to a clock interrupt, the OS saves the PC and user stack pointer of the currently executing process, and transfers control to the kernel clock interrupt handler, 2. The clock interrupt handler saves the rest of the registers, as well as other machine state, such as the state of the floating point registers, in the process PCB. 3. The OS invokes the scheduler to determine the next process to execute, 4. The OS then retrieves the state of the next process from its PCB, and restores the registers. This restore operation takes the processor back to the state in which this process was previously interrupted, executing in user code with user mode privileges.
Assume that an operating system maps user-level threads to the kernel using the many-to-many model and that the mapping is done through the use of LWPs. Furthermore, the system allows program developers to create real-time threads. Is it necessary to bind a real-time thread to an LWP?
Yes. Timing is crucial to real-time applications. If a thread is marked as real-time but is not bound to an LWP, the thread may have to wait to be attached to an LWP before running. Consider if a real-time thread is running (is attached to an LWP) and then proceeds to block (i.e. must perform I/O, has been preempted by a higher-priority real-time thread, is waiting for a mutual exclusion lock, etc.) While the real-time thread is blocked, the LWP it was attached to has been assigned to another thread. When the real-time thread has been scheduled to run again, it must first wait to be attached to an LWP. By binding an LWP to a real-time thread you are ensuring the thread will be able to run with minimal delay once it is scheduled.
What are some Threading issues?
Semantics of fork() and exec() system calls. Thread cancellation of target thread. Thread pools. Thread-specific data. Scheduler activation's.
Describe possible states in which a process can be.
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 processor terminated: The process has finished execution
What is Peterson's solution?
a concurrent programming algorithm for mutual exclusion that allows two or more processes to share a single-use resource without conflict, using only shared memory for communication.
What are scheduling criteria?
CPU utilization - keep the CPU as busy as possible Throughput - # of processes that complete their execution per time unit Turnaround time - amount of time to execute a particular 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 (for time-sharing environment)
What are differences between symmetric and asymmetric multiprocessing? What are three advantages and one disadvantages of multiprocessing?
Symmetric processing treats all processors as equals; I/O can be processed on any of them. Asymmetric processing designates one CPU as the master, which is the only one capable of performing I/O; the master distributes computational work among the other CPUs. advantages: Multiprocessor systems can save money, by sharing power supplies, housings, and peripherals. Can execute programs more quickly and can have increased reliability. disadvantages: Multiprocessor systems are more complex in both hardware and software. Additional CPU cycles are required to manage the cooperation, so per-CPU efficiency goes down.
Synchronization Hardware. What does Swap() do?
Describe three different models of establishing relationship between user-level and kernel-level threads.
Three common ways of establishing a relationship between user threads and kernel threads are: Many-to-One One-to-One Many-to-Many
What are user level threads?
Support provided at the user-level Managed above the kernel without kernel support Management is done by thread library Does not take advantage of multiprocessors
Describe the differences among short term, medium term, and long term schedulers.
Long-term scheduler (or job scheduler) - selects which processes should be brought into the ready queue Short-term scheduler (or CPU scheduler) - selects which process should be executed next and allocates CPU Medium-term scheduler - removes processes from memory to reduce the degree of multiprogramming.
What are two differences between user-level threads and kernel-level threads? Under what circumstances is one type better than the other?
Kernel sees every thread of every process. If a thread makes a system call, other threads within that process can run. Takes advantage of multiprocessors Switching among kernel-level threads of a process is done via interrupts Context switching of kernel-level threads is slower than for user-level threads but faster than process context switching. Switching among user-level threads of a process is done by calls to library modules and is done very quickly. If a user-level thread makes a system call, other threads within that process will be blocked. Does not take advantage of multiprocessors
Which of the following components of program state are shared across threads in a multithreaded process? a) Register values b) Code c) Global variables d) Stack memory
Threads share the heap, global memory and the page table. They have private register values and private stack segments.
DO ROUND ROBIN EXAMPLES!!!
DO ROUND ROBIN EXAMPLES!!!
Compare the overhead of context switch between threads of the same process and the overhead of context switch between processes.
Context-switching between two threads is faster than between two processes. Switching among threads of a process is done by calls to library modules and is done very quickly
What are some benefits of a multi-threading program?
Responsiveness (May allow a program to continue running if part of it is blocked). Resource Sharing (Sharing code, data, memory, and the resources of process) Economy (Allocating memory and resources for process creation is costly, Context switching is faster, More efficient use of multiple CPUs, Easier cooperation among threads) Scalability (Threads may be running in parallel on different processors, A single-threaded process can only run on one processor, regardless how many are available)
What does SJF stand for? Describe it.
Shortest-Job-First (SJF) Scheduling. Associate with each process the length of its next CPU burst (Use these lengths to schedule the process with the shortest time, The earlier the I/O begins -the more work done by the system). Nonpreemptive - once CPU given to the process it cannot be preempted until completes its CPU burst. Advantage: SJF is optimal - gives minimum average waiting time for a given set of processes. Disadvantage: Non preemptive nature is not good for time sharing, The difficulty is knowing the length of the next CPU request, Could ask the user
Process Synchronization. What are some requirements/ solutions to the critical section?
A Critical Section is a code segment that accesses shared variables and has to be executed as an atomic action. It means that in a group of cooperating processes, at a given point of time, only one process must be executing its critical section. If any other process also wants to execute its critical section, it must wait until the first one finishes.
What are advantages and disadvantages of each of the following? Synchronous and asynchronous communication Fixed-sized and variable-sized messages Consider both the system level and the programmer level.
A benefit of synchronous communication is that it allows a rendezvous between the sender and receiver. A disadvantage of a blocking send is that a rendezvous may not be required and the message could be delivered asynchronously. As a result, message-passing systems often provide both forms of synchronization. In fixed-size messages, a buffer with a specific size can hold a known number of messages. (Easier for designers and more complicated for users) In variable-sized messages the number of messages that can be held by such a buffer is indefinite length. (Easier for users and more complicated for designers)
Distinguish between PCS and SCS scheduling
PCS scheduling is done local to the process. It is how the thread library schedules threads onto available LWPs. SCS scheduling is the situation where the operating system schedules kernel threads. On systems using either many-to-one or many-to-many, the two scheduling models are fundamentally different. On systems using one-to-one, PCS and SCS are the same.
What is Bounded-Waiting exclusion with TestANDSet()?
Process Synchronization. What is it?
Process Synchronization means sharing system resources by processes in a such a way that, Concurrent access to shared data is handled thereby minimizing the chance of inconsistent data. Maintaining data consistency demands mechanisms to ensure synchronized execution of cooperating processes.
What are two models of interprocess communication? Briefly describe each of them.
Shared-memory model. Strength: 1. Shared memory communication is faster the message passing model when the processes are on the same machine. Weaknesses: 1. Different processes need to ensure that they are not writing to the same location simultaneously. 2. Processes that communicate using shared memory need to address problems of memory protection and synchronization. Message-passing model. Strength: 1. Easier to implement than the shared memory model Weakness: 1. Communication using message passing is slower than shared memory because of the time involved in connection setup
Can multithreaded solution using multiple user-level threads achieve better performance on a multiprocessor system than on a single-processor system?
We assume that user-level threads are not known to the kernel. In that case, the answer is because the scheduling is done at the process level. On the other hand, some OS allows user-level threads to be assigned to different kernellevel processes for the purposes of scheduling. In this case the multithreaded solution could be faster.
Section 4
(50 cards)
no pre-emption
The processes must not have resources taken away while that resource is being used. Otherwise, deadlock could not occur since the operating system could simply take enough resources from running processes to enable any process to finish.
What are two sets of the services and functions provided by an operating system? Briefly describe those two sets.
One class of services provided by an operating system is to enforce protection between different processes running concurrently in the system. Processes are allowed to access only those memory locations that are associated with their address spaces. Also, processes are not allowed to corrupt files associatedwith other users. A process is also not allowed to access devices directly without operating system intervention. The second class of services provided by an operating system is to provide new functionality that is not supported directly by the underlying hardware. Virtual memory and file systems are two such examples of new services provided by an operating system.
Throughput
# of processes that complete their execution per time unit
What are the user and system goals in operating system design?
User goals include convenience, reliability, security, and speed. System goals include ease of design, implementation, maintenance, flexibility, and efficiency.
Data parallelism
distributes subsets of the same data across multiple cores, same operation/task on each
What are advantages and disadvantages of the synchronous and asynchronous communication?
A benefit of synchronous communication is that it allows a rendezvous between the sender and receiver. A disadvantage of a blocking send is that a rendezvous may not be required and the message could be delivered asynchronously. As a result, message-passing systems often provide both forms of synchronization.
Deadlock detection
check allocation against resource availability for all possible allocation sequences to determine if the system is in deadlocked state
Under what circumstances is better to use kernel-level threads than user- level threads?
User-level threads are threads that the OS is not aware of. They exist entirely within a process, and are scheduled to run within that process's timeslices. The OS is aware of kernel-level threads. Kernel threads are scheduled by the OS's scheduling algorithm, and require a "lightweight" context switch to switch between (that is, registers, PC, and SP must be changed, but the memory context remains the same among kernel threads in the same process).
Waiting time
amount of time a process has been waiting in the ready queue
Can multithreaded solution using multiple user-level threads achieve better performance on a multiprocessor system than on a single-processor system?
We assume that user-level threads are not known to the kernel. In that case, the answer is because the scheduling is done at the process level. On the other hand, some OS allows user-level threads to be assigned to different kernellevel processes for the purposes of scheduling. In this case the multithreaded solution could be faster.
What are six major categories of system calls?
Process Control, File Manipulation, Device Manipulation, Information Manipulation, Communication, Protection.
What is Parallelism
implies a system can perform more than one task simultaneously
Explain the differences 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. bullet b. RR—treats all jobs equally (giving them equal bursts of CPU time) so short jobs will be able to leave the system faster since they will finish first.
What is the fundamental idea behind a virtual machine?
an operating system (OS) or application environment that is installed on software, which imitates dedicated hardware.
Describe four criteria to be used in selecting a CPU scheduling algorithm
When a process switches from the running state to the waiting state, such as for an I/O request or invocation of the wait( ) system call. When a process switches from the running state to the ready state, for example in response to an interrupt. When a process switches from the waiting state to the ready state, say at completion of I/O or a return from wait( ). When a process terminates.
Resource-Allocation graph
A resource allocation graph tracks which resource is held by which process and which process is waiting for a resource of a particular type. It is very powerful and simple tool to illustrate how interacting processes can deadlock.
Provide two programming examples of multithreading that would not improve performance over a single-threaded solution.
Any kind of sequential program is not a good candidate to be threaded. An example of this is a program that calculates an individual tax return. (2) Another example is a "shell" program such as the C-shell or Korn shell. Such a program must closely monitor its own working space such as open files, environment variables, and current working directory.
What is non-preemptive scheduling?
A process is removed from the CPU by itself (system call) or by an interrupt generated by some other system component. After interrupt is serviced, the CPU may be assigned to any process that is ready to run.
Banker's algorithm
When a process starts up, it must state in advance the maximum allocation of resources it may request, up to the amount available on the system. When a request is made, the scheduler determines whether granting the request would leave the system in a safe state. If not, then the process must wait until the request can be granted safely.
What are advantages of providing process cooperation?
Information sharing - Computation speed-up - Modularity - Convenience
CPU utilization
keep the CPU as busy as possible
Task parallelism
distributing threads across cores, each thread performing unique operation
What are advantages and disadvantages of the fixed-sized and variable-sized messages?
The implications of this are mostly related to buffering issues; with fixed-size messages, a buffer with a specific size can hold a known number of messages. The number of variable-sized messages that can be held by such a buffer is unknown. Consider how Windows 2000 handles this situation: with fixed-sized messages (anything < 256 bytes), the messages are copied from the address space of the sender to the address space of the receiving process. Larger messages (i.e. variable-sized messages) use shared memory to pass the message.
Consider a multiprocessor system and a multithreaded program written using the many-to-many threading model. Let the user-level threads in the program be more than the number of processors in the system. Discuss the performance implications of the following scenarios. a. The number of kernel threads allocated to the program is less than the number of processors b. The number of kernel threads allocated to the program is equal to the number of processors c. The number of kernel threads allocated to the program is grater than the number processors but less than the user-level threads
When the number of kernel threads is less than the number of processors, then some of the processors would remain idle since the scheduler maps only kernel threads to processors and not user-level threads to processors. When the number of kernel threads is exactly equal to the number of processors, then it is possible that all of the processors might be utilized simultaneously. However, when a kernel-thread blocks inside the kernel (due to a page fault or while invoking system calls), the corresponding processor would remain idle. When there are more kernel threads than processors, a blocked kernel thread could be swapped out in favor of another kernel thread that is ready to execute, thereby increasing the utilization of the multiprocessor system
When are processes created?
On system startup. Daemons, or background processes, are automatically started by the Operating System when the system is initialized and they work in the background either listening for events to occur or maintaining some part of the system. 2. On system calls. A process that is already running may wish to give birth to additional processes to help it in a particular task. The latter processes are known as child processes and the former is the parent. It is common to have such a hierarchy of processes. 3. On user requests. Double clicking on a program icon or executing it via the command line automatically creates a process for that program. It is more than likely that it will then generate child processes to perform separate tasks.
mutual exclusion
The resources involved must be unshareable; otherwise, the processes would not be prevented from using the resource when necessary.
What is Concurrency
supports more than one task making progress
resource waiting or circular wait
A circular chain of processes, with each process holding resources which are currently being requested by the next process in the chain, cannot exist. If it does, the cycle theorem (which states that "a cycle in the resource graph is necessary for deadlock to occur") indicated that deadlock could occur.
What are five major activities of an operating system with regard to process management?
Creation and deletion of user and system processes. Suspension and resumption of processes. A mechanism for process synchronization. A mechanism for process communication. A mechanism for deadlock handling.
Deadlock prevention
Deadlocks can be prevented by preventing at least one of the four required conditions
Many CPU scheduling algorithms are parameterized. For example, the RR algorithm requires a parameter to indicate the time slice. Multilevel feedback queues require parameters to define the number of queues, the scheduling algorithms for each queue, the criteria used to move processes between queues, and so on. These algorithms are thus really sets of algorithms (for example, the set of RR algorithms for all time slices, and so on). One set of algorithms may include another (for example, the FCFS algorithm is the RR algorithm with an infinite time quantum). What (if any) relation holds between the following pairs of sets of algorithms? a. Priority and SJF b. Multilevel feedback queues and FCFS c. Priority and FCFS d. RR and SJF
a. The shortest job has the highest priority. b. The lowest level of MLFQ is FCFS. c. FCFS gives the highest priority to the job having been in existence the longest. d. None.
Turnaround time
amount of time to execute a particular process
Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context switching overhead is 0.1millisecond and that all processes are long-running tasks. What is the CPU utilization for a round-robin scheduler when: a. The time quantum is 1 millisecond b. The time quantum is 10 milliseconds
a) The time quantum is 1 millisecond Anwser: i. CPU utilization of the tasks 1ms ∗ 11 = 11ms ii. Every task will use up the whole quantum. The I/O operations for the I/O bound tasks will return in time for their next turn. Only non utilizations will be the context switch 11 ∗ .1 = 1.1ms iii. 1.1ms + 11ms = 12.1ms total time. iv. 11/12.1 = .909, 90.9% b) The time quantum is 10 milliseconds Anwser: i. Total time (1ms + .1ms) ∗ 10 + 10 + .1 = 21.1 ii. CPU utilization of CPU-bound task = 10ms iii. CPU utilization of I/O bound tasks = 1ms then context switch iv. 1 ∗ 10 + 10 = 20ms total CPU utilization v. 20/21.1 = .9478, 94.78%
What is preemptive scheduling?
If an interrupt causes the removal of a process from the CPU, after the interrupt is serviced the CPU is given back to the process that had the CPU. Consider access to shared data. Consider preemption while in kernel mode. Consider interrupts occurring during crucial OS activities
hold and wait or partial allocation
The processes must hold the resources they have already been allocated while waiting for other (requested) resources. If the process had to release its resources when a new resource or resources were requested, deadlock could not occur because the process would not prevent others from using resources that it controlled.
MS-DOS provided no means of concurrent processing. Discuss three major complications that concurrent processing adds to an operating system.
1. A method of time sharing must be implemented to allow each of several processes to have access to the system . 2. Processes and system resources must have protections and must be protected from each other. Any given process must be limited in the amount of memory it can use and the operations it can perform on devices like disks. 3. Care must be taken in the kernel to prevent deadlocks between processes, so processes aren't waiting for each other's allocated resources
A CPU scheduling algorithm determines an order for the execution of its scheduled processes. Given n processes to be scheduled on one processor, how many possible different schedules are there? Give a formula in terms of n.
n!
What are advantages and disadvantages of using user-level threads?
The most obvious advantage of this technique is that a user-level threads package can be implemented on an Operating System that does not support threads. Some other advantages are User-level threads does not require modification to operating systems. Simple Representation: Each thread is represented simply by a PC, registers, stack and a small control block, all stored in the user process address space. Simple Management: This simply means that creating a thread, switching between threads and synchronization between threads can all be done without intervention of the kernel. Fast and Efficient: Thread switching is not much more expensive than a procedure call. Disadvantages: There is a lack of coordination between threads and operating system kernel. Therefore, process as whole gets one time slice irrespect of whether process has one thread or 1000 threads within. It is up to each thread to relinquish control to other threads. User-level threads requires non-blocking systems call i.e., a multithreaded kernel. Otherwise, entire process will blocked in the kernel, even if there are runable threads left in the processes. For example, if one thread causes a page fault, the process blocks.
Necessary conditions for deadlock
mutual exclusion hold and wait no preemption circular wait.
Can a link be associated with more than two processes?
A link is associated with exactly one pair of communicating processes.
What are three different forms of a user interface that almost all an operating system have?
user interface=> command-line interface, batch interface, graphical user interface
What advantage is there in having different time-quantum sizes on different levels of a multilevel queueing system?
Processes which need more frequent servicing, such as interactive processes, can be in a queue with a small q. Processes that are computationally intensive can be in a queue with a larger quantum, requiring fewer context switches to complete the processing, making more efficient use of the CPU.
What are two models of inter-process communication? Briefly describe each of them.
1. Shared Memory Model: The co operating process shares a region of memory for sharing of information. 2. Message Passing Mode: data is shared between process by passing and receiving messages between co-operating process.
Provide two programming examples of multithreading giving improved performance over a single-threaded solution.
A Web server that services each request in a separate thread. (2) A parallelized application such as matrix multiplication where different parts of the matrix may be worked on in parallel. (3) An interactive GUI program such as a debugger where a thread is used to monitor user input, another thread represents the running application, and a third thread monitors performance.
Deadlock avoidance
The system needs to have information about all the processes to know what they may request in the future
Define the difference between preemptive and nonpreemptive scheduling.
(1) Preemptive scheduling allows a process to be interrupted in the midst of its execution, taking the CPU away and allocating it to another process. Nonpreemptive scheduling ensures that a process relinquishes control of the CPU only when it finishes with its current CPU burst. (2) If nonpreemptive scheduling is used in a computer center, a process is capable of keeping other processes waiting for a long time.
What is the main advantage for an operating-system designer of using a virtual-machine architecture? What is the main advantage for a user?
The system is easy to debug, and security problems are easy to solve. Virtual machines also provide a good platform for operating system research since many different operating systems may run on one physical system and system bugs will not crash machine and cause downtime.
Which of the following components of program state are shared across threads in a multithreaded process? 1. Register values 2. Code 3. Global variables 4. Stack memory
Threads share the heap, global memory and the page table. They have private register values and private stack segments.
Response time
amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)
In what ways is the modular kernel approach similar to the layered approach? In what ways does it differ from the layered approach?
The modular kernel approach requires subsystems to interact with each other through carefully constructed interfaces that are typically narrow (in terms of the functionality that is exposed to external modules). The layered kernel approach is similar in that respect. However, 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.
Section 5
(50 cards)
Fragmentation in both systems
Binding of data to physical memory
memory addresses must be bound to physical memory addresses, which typically occurs in several stages: Compile Time, Load Time, and Execution Time
Process Synchronization: Readers-writers problem
Memory allocation Dynamic storage allocation
Second-Chance Algorithm
Second-Chance algorithm is actually a FIFO replacement algorithm with a small modification that causes it to approximate LRU
Recovery from deadlock
Recovery from deadlock
(1)Inform the system operator, and allow him/her to take manual intervention. (2)Terminate one or more processes involved in the deadlock (3)Preempt resources.
Memory protection in a paging system
Second chance algorithm
Wait-for graph
Fragmentation in both systems
There is external fragmentation in segmentation and internal in paging
Wait-for graph
A wait-for graph can be constructed from a resource-allocation graph by eliminating the resources and collapsing the associated edges, as shown in the figure below.
Necessary conditions for deadlock
mutual exclusion, hold and wait, no preemption, circular wait
Deadlock avoidance
apply the resource allocation graph to know what is needed
Different structures of the page table
physical address (frame)>protection bits(read/write/execute)>bits for (valid, reference, modify, copy on write, age)
Steps in handling a page fault
reference>trap>page is on backing store>bring in missing page> reset page table>restart instruction
Allocation algorithms Global vs local
Effective access time
Effective access time
TLB lookup takes 5 nano sec. Memory access time is 100 nano sec. Hit ratio (probability to find page number in TLB) is ? Effective Access Time = (5+100) ? +( 5+100+100)(1- ?) Suppose ? = 80% (for example, TLB size = 16) EAT = 105.8 + 205.2 = 125 nano sec.
Benefits of virtual memory
The primary benefits of virtual memory include freeing applications from having to manage a shared memory space, increased security due to memory isolation, and being able to conceptually use more memory than might be physically available, using the technique of paging.
Page replacement methods
Memory allocation Strategies of selecting the free space
Dynamic storage allocation
Two basic operations in dynamic storage management: Allocate a given number of bytes Free a previously allocated block Two general approaches to dynamic storage allocation: Stack allocation (hierarchical): restricted, but simple and efficient. Heap allocation: more general, but less efficient, more difficult to implement.
Demand paging
Memory protection in segmentation systems
Effective access time (virtual memory)
Deadlock prevention
prevent one of the necessary conditions
Memory protection in a paging system
Memory protection implemented by associating protection bit with each frame. Valid-invalid bit attached to each entry in the page table: 1. "valid" indicates that the associated page is in the process' logical address space, and is thus a legal page. 2. "invalid" indicates that the page is not in the process' logical address space.
Benefits of virtual memory
Copy-on-write
Resource-Allocation graph
Advantages of the paging system over segmentation system
Thrashing
Banker's algorithm
Binding of data to physical memory
Deadlock detection
Deadlock detection is the process of actually determining that a deadlock exists and identifying the processes and resources involved in the deadlock. The basic idea is to check allocation against resource availability for all possible allocation sequences to determine if the system is in deadlocked state
Advantages of the paging system over segmentation system
May save memory if segments are very small and should not be combined into one page. Segment tables: only one entry per actual segment as opposed to one per page in VM Average segment size >> average page size Less overhead.
Steps in handling a page fault
Logical address space vs physical address space
Copy-on-write
Multiple callers ask for resources which are initially indistinguishable, you can give them pointers to the same resource. This function can be maintained until a caller tries to modify its "copy" of the resource, at which point a true private copy is created to prevent the changes becoming visible to everyone else. All of this happens transparently to the callers. The primary advantage is that if a caller never makes any modifications, no private copy need ever be created.
Advantages of the segmentation system over paging system
No internal fragmentation (advantage) There is external fragmentation (disadvantage) Keeps blocks of code or data as single units (advantage
The method of implementing paging system
We can implement paging by breaking physical memory into frames (fixed memory blocks) and logical memory into pages (equal sized blocks)
Process Synchronization: The bounded-buffer problem
Demand paging
Processes reside in secondary memory and pages are loaded only on demand, not in advance.
Strategies of selecting the free space
The method of implementing paging system
Logical address space vs physical address space
The address generated by the CPU is a logical address, whereas the address actually seen by the memory hardware is a physical address.
Memory protection in segmentation systems
Segmentation is one of the most common ways to achieve memory protection. In a computer system using segmentation, an instruction operand that refers to a memory location includes a value that identifies a segment and an offset within that segment. A segment has a set of permissions, and a length, associated with it. If the currently running process is allowed by the permissions to make the type of reference to memory that it is attempting to make, and the offset within the segment is within the range specified by the length of the segment, the reference is permitted; otherwise, a hardware exception is raised.
Different structures of the page table
Process Synchronization: Monitors
In concurrent programming, a monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become true. Monitors also have a mechanism for signalling other threads that their condition has been met
Section 6
(50 cards)
If a graph contains no cycles, is there a potential for Deadlock?
No
Different approaches to multi-processing and main memory sharing
Partition memory into fixed size chunks Partition memory into variable size chunks Keep a process in the same memory space as it executes Allow a process to change memory location as it executes Require that a process be placed in one uninterrupted block Allow a process to be placed into separate portions of memory
Program structure
Describe memory partitions of a Single User System
One for the OS One for the USER
Deadlock avoidance - addition priori info
Each process declares the max number of each type of resource it may need. The avoidance algorithm examines resource-allocation state to ensure no circular-wait condition
Main Memory Placement Strategy First-Fit
Allocate the first hole that is big enough
Describe a multi-partiton system
Many fixed partitions of memory
Name two Avoidance Algorithms
Single instance of resource type: Resource-allocation graph Multiple instances of resource type: Use the Banker's Algorithm
Describe Deadlock
When a process is holding a resource and waiting to acquire a second resource held by another process Example: Process 1 wants A and B, has A. Process 2 has B still
Deadlock Recovery Method Process Termination
Abort all processes About one at a time until the deadlock is eliminated. Order: Priority, how long it's been computing and how much time is left, resources the process has used, resources it still needs, how many processes will be terminated, Is the process interactive of batch
Describe the Readers-Writers problem
Multiple readers can read at the same time but only one Writer can access at a time
Define "Mutual Exclusion"
Only one process at a time
Describe the Bounded-Buffer Problem
Set number of buffers can only hold one item each
Deadlock prevention: Hold and wait
- guarantee that when a process requests a resource, it does not hold any other resource
Describe Readers and Writers
With a shared dataset, Readers can only read data Writers can read and write
Define "Hold and Wait"
A process is holding at least one resource and waiting to acquire more from other processes
Deadlock Recovery Method Resource Pre-emption
Select a victim process to minimize cost Roll back to a safe start and restart process for that state
In early multi-programming systems, processes were assigned ______ at compile time
Absolute memory addresses
List the Deadlock prevention methods
Mutual Exclusion Hold and wait No Pre-emption Circular Wait
Methods to handle Deadlock
Ensure to never enter a deadlock state Allow system to enter Deadlock, then recover Ignore and pretend it DNE. (Used by most OSes)
Main Memory Placement Strategy Worst-fit
Allocate the largest hole. Worst among the 3 strategies
Relocatable memory addresses allowed what in a Multi-Partition System
Processes can run in any memory partition it can fit. Inefficient because a process might not occupy the entire partition May cause another process to wait because a partition is too small
Prepaging
How to reduce fragmentation?
Compaction Shuffle memory contents to create contiguous blocks of free memory Only possible if relocation is dynamic and done at execution
What is multi-processes?
Several processes sharing main memory
What addresses do programs deal with?
Logical addresses. Never sees the real physical address
Page size
Describe the variations of the Readers-Writers problem
1: No reader kept waiting unless the writer has permission to used the shared object 2: Once a Writer is ready it performs ASAP
What four conditions must hold simultaneously to cause Deadlock?
Mutual Exclusion, Hold and wait, No pre-emption, Circular wait
Resource-Allocation graph scheme Request edge converts to assignment edge when
The resource is allocated to the process
Define "Circular Wait"
If processes P0, P1, P2...Pn exist, such P0 is waiting for a resource from P1 P1 is waiting for a resource from P2 and on and on
Banker's Algorithm
Each process claims max resource use The requesting process may have to wait until it can get all it's needed resources it MUST return them in a finite amount of time
Functions of the memory manager
Allocating main memory to processes Protecting each process' memory space Using disk as extension of Main Mem
Describe the Dining-Philosophers Problem
A round table of philospohers eat from a shared bowl. A fork is place between each one and you need two forks to eat. Thus, if an adjacent person is eating, you cannot eat until it is finished and you can take their other fork. Eat for a fixed amount of time then stop to allow other processes. illustrates how to avoid deadlock (starvation) of processes where no progress is made.
Main Memory Placement Strategy Best-fit
Allocate the smallest hole that is big enough. Must search entire list unless it's ordered by size Produces smallest leftover hole
Define a Safe State for the system
IF resource Pi is not immediately available, the process can wait When the holding process is finished, the waiting processes can obtain needed resources and execute fully When the process terminates, the next process can get it's resources , and so on.
Describe Monitors
Encapsulates sub-processes so only one can operate at a time and only access variables defined within the functions definition.
Memory-Management Unit does what
Hardware. At runtime, maps virtual addresses to physical addresses
What is a way to solve the Reader-Writer problem?
Reader-Writer locks that prevent
How can processes exceed the total physical memory space that exists?
With Swapping of memory
Describe Contiguous Memory Allocation System
Multiple, variable partitions allocated as needed by the processes if a large enough, contiguous space exists The OS maintains a table containing the allocated partitions and free partitions
Resource-Allocation graph scheme When a resource is released, the assignment edge is converted to
A claim edge
List methods to recover from Deadlock
Terminate all processes Resource Pre-emption
Deadlock prevention: No Pre-emption
- If a requesting process requests additional resource and cannot immediate access it, release all held resources. Process is only restarted when it can regain all needed resources
Deadlock Detection algorithm w/ Multiple instances of resource types
Let WORK[] and FINISH[] be vectors of m and n (processes and resources) Find an index such WORK and FINISH are true it will allocate and do work else, the system is in deadlock
Resource-Allocation graph scheme Claim edge converts to request edge when
A process requests a resource
Working-set model
Deadlock prevention: Circular Wait
- Impose an order and resource types and require each request in increasing order
Resource-Allocation graph scheme Claim Edge
Dashed line Represents the process may request a resource
Define "No Pre-emption"
A resource can only be released by the holding process after it has completed it's task.
Section 7
(50 cards)
Segmentation Architecture Logical Addressing Structure
Segment #, Offset
Regarding Segmentation and Paging Every process has what
A segment table, which each segment has a page table. Multiple page tables per process
Swapping Method: Backing Store
Fast disk w/ copies of memory images for all users. Must provide direct access
Segment-Table Base Register
Points to segment table's location in Mem
Calculating Effective Access Time
EAT = (MA + e)a + (2MA + e)(1 - a) = 2MA + e - MAa Hit ratio = a Associative Lookup = e time unit
T/F Pages of a Segment do not need to be contiguous in Memory
True
Segment Table
Maps 2D logical addresses to physical addresses
Advantages of FIFO Replacement
Replaces the oldest frame Easy to implement
STLR
Segment-Table Length Register
LRU Implementation Methods
Counters for each page Stack of page numbers, doubly linked
Where is a page table implemented?
IN Main Mem Which means every data access requires two Mem Accesses. Resolved with the use of a Translation Look-aside buffer (TLB)
Segmentation Table Each entry has
Base - Starting Physical address where segment resides in memory Limit - Length of the segment
Define: Pages
Logical memory divided into blocks of the same size called pages
Describe valid and invalid bit meanings
Valid - indicates the page is part of the processes' logical address space and thus legal Invalid - Page is not in the processes' logical address space
Define: Page Table
Translates logical to physical addresses
Paging: Calculate internal fragmentation
Process Size / Page Size = # Pages Page Size - (# Pages + Page Size) = Fragmentation
What page table is common when greater than 32 bit systems
Hashed Page Tabes
T/F: Physical address space of a process can be non-contiguous
TRUE
T/F Pages of a Segment do not need to be in Mem at the same time
True
T/F: Relocation registers are used to protect user processes from eachother
true
Describe a Hashed Page Table
Virtual Page # is hashed into page table.
Describe an Inverted Page Table
Instead of tracking all logical pages, Track physical pages Associate page to pid
Hashed Paging What does each element contain?
Virtual Page Number Value of the page frame Pointer to next element
Page Replacement Strategeies
Random FIFO Least Recently Used Optimal Least Frequently Used Most Frequently Used
Segment-Table Length Register
Number of segments used by a program
Page-Replacement Algorithm
Chooses which frames to replace with the lowest page-fault rate on first access and re-access
Working Set
Collection of Pages a process is actively referencing
Describe the logical -> physical address in a Pentium
CPU -> Logical Address -> [Segmentation Unit] -> Linear Address -> [Paging Unit] -> Physical Address -> [Physical Memory]
The Ready Queue contains
Ready-to-run processes with memory stored on disk
Forward-Mapped Page Table
With two-level paging Where P1 is an index for an outer page table, which points to P2 of the inner page table
Virtual Address =
= ( S, P, D) S - Virtual Segment # P - Page # within this Segment D - Displacement from the start of the Page
How to determine page number and offset of a logical address
Page number = Address / Size of Page Offset = Address mod(Size of Page)
What are the major concerns of swapping?
Transfer time and amount of memory being swapped
Translation look-aside buffer (TLB)
Hardware Stores address-space identifiers in each entry
Describe use of Shared Pages in memory
Read-only. Good to store copy of re-entrant code shared among processes. Also used for inter-processes communications
Advantages of random replacement
Low overhead
STBR
Segment-Table Base Register
Swapping Method: Roll out, Roll in
Used for priority-based scheduling Lower-priority processes are swapped out so high-prioirty processes can be loaded and executed
Describe Optimal Algorithm
Replace page that will not be referenced for the longest period of time
Describe the address translation scheme
Page Number (p) | Page Offset (d)
PTLR
Page-Table Length Register Indicates size of the page table
Describe Two-Level Page Table Translation
P1 P2 D P1 -> P2 P2 -> D offset
Describe a method for protecting pages
Using protection bit to indicate read, read-write, or execute status is allowed
Translation look-aside buffer, AKA
Associative Memory
Define: Frames
Physical memory divided into fixed-sized blocks
Least Recently Used (LRU) Algorithm
Replace page not used in the most amount of time
Frame-Allocation algorithm determines
How many frames to give each process
Disadvantage of random replacement
Unpredictability
PTBR
Page-Table Base register
Disadvantages of FIFO Replacement
You may replace a heavily used page
Section 8
(50 cards)
Considerations on logically organizing directory files to improve efficiency
Naming Grouping by similar properties
File Allocation Table (FAT)
A table contains a list of all blocks Each block position in the table stores the number of the next block in the file
Mandatory File Locking
File access is denied depending on locks held and requested
Memory Allocation First-fit
Allocate the first hole big enough
i node or index node
Properties for each file managed by the OS
Stateless file service
Avoids state information by making each request self-contained. Server does not need to keep a table of open files. No need to establish and terminate a connection.
Advantages of Disk Allocation
File size can change. Fragmentation avoided, any free block can be used. Direct access is efficient.
Free-Space Management Free-Space table can be implemented as
Bit vector or bit map of n size
Thrashing
When CPU utilization decreases significantly due to an increase in page faults The process is very busy swapping pages in and out
How to guarantee no cycles with a graph directory structure?
Allow only links to files, not to sub-directories Garbage Collection When a new link is added, use a detection function to verify
Unix File System (UFS)
Writes to an open file visible immediately to other users of the same file. Sharing file pointer allow multiple users to read/write concurrently
Sequential file access
Records accesses one after another
Benefits of Acyclic-Graph Directories
Like tree directory but with shared subdirectories and files
Explain "Buddy System" allocation
Round up the request to the next highest power of 2 And make fixed size allocations, in half until the desired chunk is achieved.
What do inodes (index nodes) store?
Name Owner Type Location Size Time and date User ID Protection
File Locking types
Shared Lock Exclusive Lock
Free-Space Management Advantages of Bit Map
Simple and effecient to find the first free block Map shows how disk is allocated making it easier to allocate groups physically close Table can be kept in main memory while the
Disadvantage to the Buddy System?
Fragmentation
Advisory File Locking
Processes can find the lock status and decide what to do
Free-Space Management Disadvantages of Linked List (free list)
Not efficient to traverse
How to prevent thrashing?
Provide a process with as many frames as it needs
Describe the working-set strategy
Look at how many frames a process is actually using and keep track of the working set of frames
Problems with Single-Level Directories for all Users
Naming and Grouping
Free-Space Management Linked List (free list)
Linked list of free disk blocks
Memory Allocation Best-fit
Allocate smallest hole that is big enough,
Disadvantages of Contiguous allocation
Finding contiguous space for a new file may be impossible Programmer must specify size before hand External fragmentation occurs
NFS
Set of remote file operation calls. Stateless
Memory Allocation Worst-fit
Allocate the largest hole
Free-Space Management Advantages of Linked List (free list)
No waste of space
Linked Disk Allocation
Files blocks are linked by a linked list and do not need to be physically next to eachother
Disadvantages of Link Disk Allocation
Only sequential access to a file is efficient Pointers to next block of file uses storage space
Free-Space Management Disadvantages of Bit Map
Requires extra space
Advantages of Contiguous allocation
No space required to determine location of next block Sequential access required minimum head movement File descriptors are easy to implement Easily implemented
Disadvantages of Disk Allocation
Wasted disk space used for index block of every file
Indexed Disk Allocation
Files stored on linked list of blocks with all the pointers stored in one "index block"
Stateful file service
Client must open() and close(). Server fetches info about file and stores in Memory. Gives a unique connection identifier Higher performance but volatile in a crash
Benefits / Disadvantages Of Two-level Directory
Separate directory for each user Path naming Can have same file name for different users Efficient search No grouping
Consistency Semantics
Specify how multiple users access a shared file simulatenously
Describe Slab Allocation
Cache is mapped to one or more contiguous slabs of physical memory
File System Access Methods
Sequential Direct (relative Indexed
Indexed file access
Built on top of Direct Access method. Index contains a key and block number and kept in Main Mem
Benefits to the Buddy System?
Ability to quickly merge unused chunks into larger chunks
Contiguous allocation
Files stored physically next to eachother
Andrew File System (AFS)
Writes only visible to sessions started after the file is closed. Once a file is closed, changes are visible only in later sessions
What is preemption?
While a process is waiting for resources, and holding resources. The held resources are implicitly released and added to the list of resources it is waiting for. The process will only be restarted when all required resources are available
Direct (relative) file access
Records accessed directly by reading / writing to the sector directly Data must be accessed sequentially once the sector is obtained
Advantages of Link Disk Allocation
Size of file can change External fragmentation avoided since any free block and be used
NFS Operations
Searching, Reading, Manipulating links and directories, Accessing file attributes, Read/Write files
Benefits to Tree Directories
Efficient Search Grouping ability Current working directory capability
How do you ensure hold and wait condition never occurs?
We don't allocate resources to a process if it is currently holding resources
Section 9
(50 cards)
The processor execution mode that user programs typically execute in is referred to as:
User Mode
Types of file access
Read, Write, Execute, Append, Delete, List
One of the disadvantages of User-‐Level Threads (ULTs) compared to Kernel-‐Level Threads (KLTs) is:
When a ULT executes a system call, all threads in the process are blocked.
It is a facility that allows programs to address memory from a logical point of view, without regard to the physical amount of main memory.
Virtual Memory
A computer hardware feature that is vital to the effective operation of a multiprogramming operating system is:
I/O interrupts and DMA
It is the portion of the operating system that selects the next process to run.
What is the Dispatcher?
T / F - The Process Image refers to the binary form of the program code.
False; it refers to the process elements. Such as the program, data, stack and attributes
T / F - An SMP O/S manages processor and other resources so that the user may view the system in the same fashion as a multiprogramming uniprocessor system.
True
When an external device becomes ready to be serviced by the processor, the device sends this type of signal to the processor:
Interrupt Signal
T / F - An operating system controls the execution of applications and acts as an interface between applications and the computer hardware.
True
The basic thread operation related to the change in thread state that occurs when a thread needs to wait for an event is referred to as the:
Block Operation
T / F - In a pure User-Level Thread (ULT) facility, all of the work of thread management is done by the application, but the kernel is aware of the existence of threads.
False; The kernel is not aware of the existence of threads.
The behavior of an individual process can be characterized by examining:
A Single Process Trace.
The instruction execution consists of what two steps?
Fetch, Execute
In a Linux system, it is a process that has been terminated but, for some reason, still must have its task structure in the process table.
What is a zombie?
T / F - The portion of the Process Control Block that consists of the contents of the processor registers is called the Process Control Information.
False; processor state information portion of the PCB contains registers.
The Process Identification, Processor State Information and the Process Control Information are the general categories that collectively make up what is referred to as the ______________________.
Process Control Block.
Two accepted methods of dealing with multiple interrupts is to:
Define priorities for the interrupts, Disable interrupts while an interrupt is being processed
Where does the processor hold the address of the next instruction?
Program Counter (PC)
Read-Ahead technique
Requested page and several subsequent pages are read and cached
Buffer Cache
Separate section of Main Mem for frequently used blocks
When a new block of data is written into cache memory, the following determines which cache location the block will occupy:
Mapping Function
The behavior of a processor can be characterized by examining:
The interleaving of the process traces.
What is faster, Main Memory or Registers?
Registers are faster than main memory.
A Computer's Basic Elements. List the 4 high level components of a computer:
Processor, Bus (Control), I/O, Memory
When to use Synchronous writes
When writes are occasionally requested
Efficiency is dependent on
Disk allocation and directory algorithms. Types of data Pre-allocation or as-needed allocation structures. Fixed or varying data structure sizes.
T / F - In a symmetric multiprocessing (SMP) system, each processor has access only to a private main memory area.
False
What is true regarding the relationship between processes and threads:
It takes less time to create a new thread in an existing process than to create a new process. Less time to terminate a thread. Switching between two threads takes less time. Threads can communicate with each other without invoking the kernel.
T / F - The concept of thread synchronization is required in multithreaded systems because threads of a single process share the process's process control block (PCB).
False
Direct Memory Access (DMA) operations require the following information from the processor:
Address of I/O device, Starting memory location to read/write, Number of words to be read/written
The User Data, User Program, System Stack and Process Control Block elements collectively make up what is referred to as the __________________.
Process Image
A common class of interrupts is:
Program, Timer, I/O
-Exploits the hardware resources of one or more processors -Provides a set of services to system users -Manages secondary memory and I/O devices
What is an Operating System?
In the operating system scheduling system, it contains processes that are in main memory.
Short term queue
What is smaller, Main Memory or Registers?
Registers are smaller than main memory.
Where does the processor fetch an instruction from?
Cache / Main Memory
It is the listing of a sequence of instructions that execute for a particular process.
What is a Trace?
When to use asynchronous writes
When writes are more frequent
Free-Behind technique
Remove a page from the buffer as soon as the next page is requested
It includes all information needed by the operating system and processor to manage and execute the process. It characterizes the process.
Process State
Where does the processor hold the instruction fetched?
Instruction Register (IR)
3 Types of registers typically available are:
Data Registers (storing data), Address Registers (stack pointer, frame pointer), Condition Codes (addl, mult)
T / F - The philosophy underlying the microkernel is that only absolutely essential core operating system functions should be in the kernel.
True
T / F - The operating system typically runs in parallel with application programs, on it's own special O/S processor.
False
...contains the address of an instruction to be fetched.
What is the Program Counter?
T / F - The primary advantage of the basic microkernel design over layered kernel designs involves increased performance.
False; performance is a disadvantage
...contains the instruction most recently fetched.
What is the Instruction Register (IR)?
A process is comprised of what three parts:
Set of data, State of program, Code (data functions) / Control
The processor typically maintains the current operating mode (i.e., user or kernel) in the _________________.
Program Status Word (PSW)
Section 10
(50 cards)
One step in the procedure for creating a new process involves:
Initializing the process control block, Allocating space for the process, Assigning a unique identifier
It is the reclaiming of reclaiming of the resources from the processor before the process is finished using it. The resources can be the process itself.
What is Preemption?
Reasons for Process Suspension:
Swapping, Other OS Reason, Interactive User Request, Timing, Parent Process Request
What are the 4 actions that a michine instruction can specify
Processor-memory, Processor-I/O, Data Processing, Control
Message Passing Syncronus
Reduces overhead Has error detection Efficient But receiver needs to sample at correct intervals
What is multithreading?
A technique in which a process is divided into threads that can run concurrently.
A technique used to overcome the problem of blocking threads. The purpose is to convert a blocking system call into a non-blocking system call.
What is Jacketing
What is temporal locality?
Temporal Locality = processor accesses memory locations that have been used recently; happens w/loops. This methods keeps recently used instructions and data in cache memory.
Describe process creation
Parent processes create child processes.
Purpose of Interprocess communications?
Information Sharing Increase computation throughput or overall speed Modularity Convenience
What are the strategies for exploiting temporal locality?
Temporal = exploits the cache by keeping recently used instructions & data values in cache memory and by exploiting the cache hierarchy.
What resources are shared by all threads of a process?
The state and resources of the process (including address space, file resources, and execution privileges)
What is Programmed I/O?
the processor must determine when the instruction is complete
Process States
New Ready Waiting Running Terminated
What is multiprogramming?
An approach at logic flow that will allow the processor to switch between jobs in an effective fashion.
Describe a shared memory system
Multiple processes can share a section of memory and communicate or share data. But can have protection/security issues
What is spatial locality?
Spacial locality = multiple, clustered, memory locations; they will be fetched sequentially.
What is a Thread?
Threads are a dispatchable unit of work which includes a processor context and its own data area for a stack.
T / F - The principal function of the processor is to execute machine instructions residing in main memory.
True
What 3 states exist for threads?
Running, Ready, Blocked, Spawn, Block, Unblock, Finish *(The status Suspended is a process-level concept & A thread can spawns another thread)
If we have a 32 bit instruction and the first 8 bits contain opcode...how large must the IR be?
either 8 bits (for opcode) or 32 bits (to contain the whole instruction)
What are the advantages of KLT?
-The kernel can simultaneously schedule multiple threads from the same process on multiple processors. -If one thread in a process is blocked, the kernel can schedule another thread of the same process. -Kernel routines themselves can be multithreaded.
Define the two main categories of processor registers.
User-Visible registers, Control and Status registers
T / F - A process trace is a listing of the sequence of instructions that execute for that process.
True
The scheduling strategy where each process in the queue is given a certain amount of time, in turn, to execute and then returned to the queue, unless blocked is referred to as:
Round-Robin
It is the portion of the operating system that selects the next process to run.
What is the Dispatcher?
List 2 separate characteristics embodied in the concept of a process.
Resource ownership, Scheduling/execution
What characteristics distinguish the various elements of a memory hierarchy?
Speed(top=fast ->bottom=slow), Size(top=small->bottom=large), Cost(top=high->bottom=low), Access Frequency(top=often->bottom=infrequent)
It is a process state in which a process cannot execute until some event occurs.
What is a Blocked State?
T / F - The principal responsibility of the operating system is to control the execution of processes.
True
If we have a 32 bit instruction and the first 8 bits contain opcode...how large must the program counter be?
32-8 = 24 bits (at least)
What is a KLT?
Kernel Level Thread: Kernel maintains context information for the process and the threads (No thread management done by application) Scheduling is done on a thread basis.
What is Interrupt-driven I/O?
The I/O module will interrupt the processor to request service when it is ready to exchange data with the processor
What is the kernel of an OS?
Kernel = located in main memory, contains most freq used funcs in the OS. Link between programs and processes.
What are the benefits of a Microkernel Organization?
Uniform interfaces on requests made by a process - all services -> message passing • Extensibility - add new services • Flexibility - remove existing services • Portability - across processors • Reliability - rigorous testing & limited API • Distributed System Support • Object Oriented Operating Systems
What are the strategies for exploiting spatial locality?
Spatial = exploits the cache by using larger cache blocks and incorporating pre-fetching mechanisms into cache control logic.
A process switch may occur when the system encounters an interrupt condition, such as that generated by a:
Memory fault, Supervisor call, Trap
It is the action that refers to when the OS moves one of the blocked processes out onto disk into a suspended queue. Then the OS brings in another process from the suspended queue.
What is Swapping?
Describe: Message Passing System
Processes share a common channel to send messages
4 General examples of the use of threads in a single-user multiprocessing system.
Foreground/Background work, Asynchronous processing, Speed of execution, Modular program structure
What is Cache
When processor attempts to read byte/word, a check is made to determine if the byte/word is in cache. If not, a block of main memory is read into the cache, then the byte/word is delivered to the processor
What is a process switch?
process switch you must switch the processor context, program counter and the registers must be saved before the process control block of the process is moved to another queue. after executed the previous process is switch back in.
The 4 types of entities that the OS maintains tables for include:
I/O, Memory, File, Process
3 Techniques for I/O operations
Interrupts-driven I/O, DMA, Programmed I/O
Cache Design Issues Include:
- Cache size - Block size - Mapping function - Replacement algorithm - Write policy
Message Passing Asynchronus
Self-contained Higher overhead and no error detection
What is the disadvantage of KLT?
The transfer of control from one thread to another within the same process requires a mode switch to the kernel.
What is the Key Responsibility of the OS? What is its fundamental Task?
Key responsibility of an OS is to "manage system resources." Its fundamental task is "Process Management" -taufer
What is a mode switch?
mode switch is when the processor simply sets the pc to the starting address of an interrupt handler and switches from user modes to kernel mode.
List the 5 storage management responsibilities of a typical OS.
Process Isolation, Automatic allocation and management, support of modular programming, protection and access control, long-term storage
Section 11
(7 cards)