· Process concept:
· A system consists of a collection of process.
· The process are
§ Operating system process
§ User process.
· All these process can execute with the CPU.
3.1.1 The Process:
· Process is a program in execution
· A process consist of
§ Text section
§ Program counter
§ Process stack
§ Data section
§ Heap section
· Ref fig 3.1 Process in memory.
· Program is a passive entity
· Process is an active entity
· A program becomes a process when an executable file is loaded into memory.
3.1.2 Process State:
· Process execute, it changes state.
· The state of a process is defined in part by the current activity of that process.
· Ref fig 3.2 diagram of process state
§ 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 its execution
· Only one process can be running on any processor at any instant
· Many process may be ready and waiting state.
3.1.3 Process Control Block:
· Each process is represented in the os by a process control block- PCB.
· It contains many piece of information
§ Process state
§ Program counter
§ CPU register
§ CPU scheduling information
§ Memory management information
§ Accounting information
§ I/O status information
· Ref fig- 3.3 Process control Block and 3.4 CPU switches from process to process.
Process state:
§ The state may be new, ready, running, waiting and halted.
Program counter:
§ The counter indicates the address of the next instruction to be executed.
CPU registers:
§ The registers are varying in numbers and type, depending on the computer architecture.
§ It includes accumulators, index registers, stack pointers.
CPU Scheduling Information:
§ It includes process priority, pointers to scheduling queue, etc..,
Memory management information:
§ It includes information as the value of the base and limit registers, page tables, etc.
Accounting Information:
§ It includes amount of CPU & real –time used, time limits, job/ process number, etc.
I/O Status information:
§ It includes list of I/O devices allocated to process, a list of open files.
· PCB simply serves as the repository for any information.
3.1.4 Threads:
§ A Process is a program that performs a single thread of execution.
§ The single thread of control allows the process to perform only one task at a time.
§ Os have extended the process concept to allow a process to have multiple threads of execution and thus to perform more than one task at a time.
3.2 Process Scheduling:
Objectives:
Multi-programming:
§ Some process running at all times to maximize CPU utilization.
Time sharing:
§ Switch the cpu among process
Process scheduler:
§ Selects an available process for program execution on the CPU.
3.2.1 Scheduling Queues:
· Processes are put into job queue.
Job Queue:
§ It consists of all process in the system.
Ready Queue:
§ Process that are residing in main memory and are ready and waiting to execute are kept on list called the ready queue.
§ It is stored as a linked list.
§ It contains pointer to the first and final PCB in the list.
· Each PCB includes pointer field that points to the next PCB.
Device Queue:
§ The process may wait for the disk.
§ The list of process waiting for a particular I/O device is kept here.
· Once the process is allocated the CPU and is executing, one of the several events could occur.
§ The process could issue an I/O request and then be placed in an I/O queue.
§ The process could create a new sub process & wait for the sub process termination.
§ The process could be removed forbidly from the CPU, as a result of an interrupt, and be put back in the ready queue.
· Ref fig 3.5 &3.6
3.2.2 Schedulers:
· Os must select for scheduling purpose. The selection process is carried out by the appropriate scheduler
· The scheduler is of
§ Long term scheduler
§ Short term scheduler
§ Medium term scheduler
Long term schedule r(job scheduler):
§ It selects a process from job pool and loads them into memory for execution.
§ It executes less frequently.
§ It controls the degree of multi- programming
§ If the degree of multi programming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system.
I/O Bound Process:
§ It spends more of its time doing I/O than it spends doing computations.
CPU Bound Process:
§ It generates i/o requests infrequently, using more of its time doing computation
Short term scheduler (CPU Scheduler):
§ It selects the process that is ready to execute & allocates the CPU.
§ It selects a new process for the CPU frequently.
§ Process may execute only a few milliseconds before waiting for an I/O request.
§ It executes at least once in every 100 milliseconds.
§ It must be fast.
Medium term scheduler:
§ Time sharing system may introduce intermediate level of scheduling.
§ It is to remove process from memory & thus reduce the degree of multi programming.
Swapping:
§ The process is swapped out & later swapped in by medium term scheduler.
§ Ref fig 3.7.
3.2.3 Context Switch:
§ When an interrupt occurs, the system needs to save the current context of the process currently running on the CPU, it can restore the context when its processing is done, essentially suspending the process & then resuming it.
§ The context is represented in the PCB of the process.
§ It includes the value of the CPU registers, the process state & Memory Management information.
State save:
§ Save the current state of the CPU.
State restore:
§ Resume operations.
Context switch:
§ Switching the CPU to another process requires performing a state of the current process and a state restore of a different process.
§ The kernel saves the context of the old process in its PCB & loads the saved context of the new process scheduled to run.
§ Speed varies from machine to machine, depending on the memory speed, the number of registers that must be copied.
§ Context switch times are highly dependent on h/w support
3.3 Operation on Process:
· The process can execute concurrently they may be created & deleted dynamically.
· Systems must provide a mechanism for process creation & termination.
Process Creation:
· A process may create several new processes by creating process system call during the course of execution.
· The creating process is a parent process.
· The new processes are called child process.
· Most os identify process according to a unique process identifier, two possibilities exists in terms of execution.
§ The parent continues to execute concurrently with its children
§ The parent waits until some or all of its children have terminated.
· There are also two possibilities in terms of the address space of the new process.
§ The child process is a duplicate of the parent process.
§ The child process has a new program loaded into it.
· A new process is created by the fork system call.
· Ex.
· int main( )
· {……..
· pid= fork();
· if(pid<0){
· /* fork failed*/ exit(-1);}
· else if(pid==0){
· /* child process*/
· }
· else {
· /* parent process*/
· /* wait until child completion */
· exit(0);
· }}
· The return value of fork is zero for child process and non-zero for parent process.
· Ref fig 3.10 process creation.
3.3.2 Process termination:
· A process terminates when it finishes executing its final statement & asks the os to delete it by using the exit () system call.
· Process may return a status value to its parent process.
· A person can cause the termination of another process via an appropriate system call.
· When one process creates a new process, the identity o the newly created process is passed to the parent.
· A parent may terminate the execution of one of its children for variety of reasons.
· The child has exceeded its usage of some of the resources that it has been allocated.
· The task assigned to the child is no longer required.
· The parent is executing and the os does not allow a child to continue if its parent terminates.
Cascading Termination:
· If a parent process terminates then all its children must also be terminated.
3.4 Inter-process Communication:
Independent Process:
· Any process that does not share data with any other process executing in the system.
Co-operating process:
· Any process that shares data with other process.
· Several reasons for providing environment that allows process co-operation.
§ Information sharing
§ Computation speedup
§ Modularity
§ Convenience
Information sharing:
· A process must provide an environment to allow concurrent access to share information.
Computation speed up:
· A task must break it into sub tasks, each of which will execute in parallel with the others.
· Speed up can be achieved by multiprocessing elements.
Modularity:
· System functions are divided into separate process. Threads.
Convenience:
· Individual user may work on many tasks at the same time.
· Co-operating process requires an IPC (Inter- Process Communication) mechanism that allows exchanging data & information.
§ Shared memory
§ Message Passing
Shared Memory Model:
· A region of memory that is shared by co-operating process.
· Process can exchange the information by reading &writing the data to the shared region.
· It allows maximum speed& convenience of communication.
· It is faster than message passing.
· All access are treated as routine memory access, kernel is not required.
Message passing:
· Communication takes place by means of messages exchanged between co-operating process.
· It is useful for exchanging smaller amount of data.
· It is easier to implement.
· Ref fig Communication models.
3.4.1 Shared Memory Systems:
· It requires communication process to establish a region of shared memory.
· The information is exchanged by reading & writing data in shared areas.
· The form of data & location are determined by these processes.
· The process is also responsible for ensuring that they are not writing to same location simultaneously.
Producer-Consumer Problem:
· The producer produces information that is consumed by a consumer process.
· It also provides a useful metaphor for the client server paradigm.
· To allow producer & consumer process to run concurrently.
· Buffer of items that can be filled by the producer & emptied by the consumer.
· A producer can produce one item while the consumer is consuming other item.
· It must be synchronized.
· Buffers are two types:
§ Bounded Buffer
§ Unbounded Buffer
Bounded Buffer:
· A fixed buffer size.
· The consumer must wait if the buffer is empty, and the producer must wait if the buffer is full.
Unbounded Buffer:
· No limit on the size of the buffer.
· Consumer may have to wait for new items, but the producer can always produce new items.
3.4.2 Message Passing:
· It provides a mechanism to allow process to communicate & to synchronize their actions without sharing the same address space.
· The operations are
§ send(message)
§ receive (message)
· Message sent by process can be either fixed or variable size.
· Several methods for logically implementing link and send () or receive() operations.
§ Direct or Indirect Communication
§ Synchronous or Asynchronous communication
§ Automatic or explicit buffering
3.4.2.1 Naming:
· Process that want to communicate must have a way to refer each other.
· They can use either direct or indirect communications.
Direct Communication:
· Each process that wants to communicate must explicitly name the recipient or sender of each communication.
· send (P, message)- send message to process P
· receive (Q, message)- receive message from process Q.
communication link
· The communication link has the following properties
· A link is established automatically between every pair of process that wants to communicate.
· A link is associated with exactly two processes between each pair of process there exists exactly one link.
· The addressing is of
§ Symmetry in addressing
§ Asymmetry in addressing
Symmetry in addressing:
· Both the sender and the receiver process must name the other to communicate.
Asymmetry in addressing:
· The sender must name the recipient but the recipient is not required to name the sender.
· send (P, message) – send message to process P.
· receive (id, message) - messages from any process. Id-> variable id.
Indirect Communication:
· The messages are sent to & receive from mailboxes, ports.
· Messages can be placed by process & from which messages can be removed.
· Each mailbox has a unique identification.
· send (A, message) - send a message to mailbox A.
· receive (A, message) – receive a message from mailbox A.
Communication Link:
§ A link is established between a pair of process only if both members of the pair have a shared mailbox.
§ A link may be associated with more than two processes between each pair of communicating process; there may be a number of different links, with each link corresponding to one mailbox.
· The os must provide a mechanism that allows a process to do
§ Create a new mail box
§ Send & receive messages through the mailbox.
§ Delete a mailbox.
· 3.4.2.2 Synchronization:
· There are different design options for implementing send & receive primitives.
§ Blocking send
§ Non blocking send
§ Blocking receive
§ Non Blocking receiver.
Blocking send:
· Sending process is blocked until the message is received by the receiving process or mailbox.
Non blocking send:
· The sending process sends the message & resumes the operation.
Blocking receive:
· The receiver blocks until a message is available.
Non blocking receive:
· The receiver retrieves either valid messages or null.
3.4.2.3 Buffering:
· Message exchanged by communicating process reside in temporary queue.
· The queues are
§ Zero capacity
§ Bounded capacity
§ Unbounded capacity
· Zero capacity:
· The queue has a maximum length of zero, the sender must block until the recipient receives the message.
· Bounded capacity:
· The queue has finite length n. The links capacity is finite.
· The sender must block until space is available in the queue.
· Unbounded capacity:
· The queues length is potentially infinite. Any number of messages can wait in it.
· The sender never blocks.
3.6 Communication In Client- Server Systems:
3.6.1 Sockets:
· It is defined as an endpoint for communication.
· Pair of processes communicating over a network employs a pair of sockets.
· A socket is identified by an IP address concatenated with a port number.
· It uses client- server architecture.
· The packets travelling between the hosts are delivered to the appropriate process based on the destination port number.
· Ref fig 3.17 communication using socket.
· Java provides three different types of sockets.
Connection –oriented (TCP) Socket:
§ Implemented with Socketclass.
Connectionless (UDP) sockets:
§ Use DatagramSocketclass
Multicast Socket Class:
§ Sub class of DatagramSocketclass. Data to be sent to multiple recipients.
Loopback:
§ The IP address 127.0.0.1 is special IP address known as the loopback.
· Communication using sockets are common and efficient.
· It is low level form of communication between distributed networks.
3.6.2 Remote Procedure calls.
· It abstracts the procedure call mechanism for use between systems with network connections.
· Messages exchanged in RPC communication are well structured.
· Each message is addressed to an RPC daemon listening to a port on the remote system.
· A port is simply included at the start of a message packet.
· Remote process needs a service. It addresses a message to the proper port.
· Any remote system could obtain the needed information by sending an RPC message to port 3027 on the server.
· RPC system hides the details that allow communication to take place by providing a stub on the client side.
· Client invokes a remote procedure, RPC system calls the appropriate stub, passing the parameters provided to the remote procedure.
Parameter Marshalling:
· It involves the packaging the parameters into a form that can be transmitted over network.
· A similar stub on the server side receives. This message invokes the procedure on the server.
Binding:
· The binding information may be predetermined in the form of fixed port addresses.
· Binding may be done dynamically by matchmaker mechanism.
3.6.3 Remote Method Invocation:
· RMI is a java feature similar to RPC’s.
· It allows a thread to invoke a method on a remote object.
· The remote object may be in a different JVM on the same computer or on a remote host connected by a network.
· RMI is object based. It supports invocation of methods on remote objects.
· It is possible to pass object as parameters to remote methods.
· RMI implements the remote object using stub and skeleton.
· A stub is a proxy for the remote object, it resides with the client.
· When client invokes a remote method, a stub for the remote object is called.
· The skeleton is responsible for un-marshalling the parameters and invoking the desired method on the server.
· RMI provides stub and skeleton transparent.
Object serialization:
· Marshaled parameters are local objects; the parameters are passed by copy using object serialization.
· If the parameters are remote objects, they are passed by reference.
Chapter- 4
MULTI THREADED PROGRAMMING
Thread is a basic unit of CPU utilization. It consists of thread ID, program counter, register set & a stack.
- It shares code section, data section, resources if thread belongs to same process. Traditional process has a single thread of control
4.1.1 Motivation:
- It is generally more efficient to use one process that contains multiple threads.
- The several would create separate thread that would listen for client request.
- When a request made rather than creating another process the server would create another thread to service the request.
- Thread plays a vital role in RPC.
- Many os kernels are now multithreaded.
- Several threads operate in the kernel & each thread performs a specific task.
4.1.2 Benefits:
The benefits are
§ Responsiveness
§ Resource sharing
§ Economy
§ Utilization of multiprocessor Architecture
Responsiveness:
· Multithreading an interactive application may allow program to continue running even if part of it is blocked or is performing a lengthy operation thereby increasing responsiveness to the user.
Resource sharing:
· Sharing code and data is that it allows an application to have several different threads of activity within the same address space.
Economy:
· Allocating memory and resources for process creation is costly.
· Thread shares resources of the process to which they belong.
· It is more economical to create & context switch threads.
· It takes more time to create & manage processes than threads.
Utilization of multiprocessor architecture:
· Benefits of multithreading can be greatly increased in a multiprocessor architecture.
· Threads may be running in parallel on different processors.
· It increases concurrency.
4.2 Multithreading Models:
· Threads may be provided at user level for user threads and kernel level for kernel threads.
User threads:
· It is supported above the kernel and is managed without kernel support.
Kernel threads:
· It is supported and managed directly by operating system.
4.2.1 Many to one model:
· Maps many user level threads to one kernel thread.
· Thread management is done by the thread library is user space.
· It is efficient.
· Entire process will block if a thread makes a blocking system call.
4.2.2 one to one model:
· Maps each user thread to a kernel thread.
· Provides more concurrency.
· Allows another thread to run when a thread makes a blocking system call.
· Creating a user thread requires creating the corresponding kernel thread.
4.2.3 many to many model:
· Multiplexes many user level threads to a smaller or equal number of kernel threads.
· Developers can create as many user threads as necessary.
· The corresponding kernel threads can run in parallel on a multiprocessor.
· When a thread performs a blocking system call, the kernel can schedule another thread for execution.
· It allows a user-level thread to be bound to a kernel thread – two level model
4.3 Thread libraries:
· Thread library provides the programmer an API for creating & managing threads.
§ Provide a library entirely in user space with no kernel support.
§ All code & data structures for the library exist in user space.
· Library results in a local function call in user space & not a system call.
§ Implement a kernel level library supported directly by the os.
§ Code & data structures for the library exist in kernel space.
· Library results in a system call to the kernel.
4.3.1 Pthreads:
· It refers to the POSIX standard defining an API for thread creation & synchronization.
· It is a specification for thread behavior, not an implementation.
· 
The thread can be created by set of attributes
The thread can be created by set of attributes
pthread_create (&tid, &attr, runner, argv[1]); Thread id parameter
Thread execution
· To get default attributes
pthread_attr_init (&attr);
· We did not explicitly set any attributes so use the default attributes.
4.3.2 win32 Threads:
· Creating threads using the win32 thread library is similar to the pthreads technique.
· Threads are created in win32 API using Create thread ( ) function.
· Set of attributes for the thread is passed to this function.
· The attribute include security information, size of the stack, a flag.
4.3.3 Java threads:
· Threads are fundamental model of program execution in a java program.
· API provides a rich set of features for creation & management of threads.
· All Java programs comprise at least a single thread of control.
· Create a new class that is derived from the thread class & to override its run ( ) method.
· Define a class that implements the runnable interface.
· When a class implements Runnable, it must be define a run ( ) method.
· public interface Runnable{
· public abstract void run();
· }
· Sharing a data between threads occurs easily in win32 and pthreads as shared data are simply declared globally.
· Java has no global data.
· Sharing occurs by passing reference to the shared object to the appropriate threads.
4.4 Thread Issues:
4.4.1 The fork ( ) and exec () system calls:
· The fork () system call duplicates all threads.
· Duplicates only the thread that invoked the fork () system call.
· The exec () system call the program specified in the parameter.
· exec () will replace the entire process including all threads.
4.4.2 Cancellation:
· Thread cancellation is the task of terminating a thread before it has completed.
· Ex:
§ If multiple threads are concurrently searching through database & one thread returns the result, the remaining threads might be cancelled.
· A thread that is to be cancelled is often reffe3red to as the target thread.
§ Asynchronous cancellation
§ Deferred cancellation
Asynchronous cancellation:
· One thread immediately terminates the target thread.
Deferred Cancellation:
· The target thread periodically checks whether it should terminate, allowing it an opportunity to terminate itself in an orderly fashion.
4.4.3 Signal Handling:
· A signal is used in UNIX systems to notify a process that a particular event has occurred.
· Signal may be synchronous or asynchronous.
· All signals follow the same pattern.
§ A signal is generated by the occurrence of a particular event.
§ A generated signal is delivered to a process.
§ Once delivered the signal must be handled.
· An asynchronous signal is sent to another process.
· Every signal may be handled by one of two possible handlers.
§ Default handler
§ User-defined signal handler
· When should a signal be delivered?
§ Deliver the signal to the thread to which the signal applies.
§ Deliver the signal to every thread in the process.
§ Deliver the signal to certain thread in the process.
§ Assign a specific thread to receive all signals for the process
4.4.4 Thread Pools:
· Thread pool is to create a number of threads at process startup & place them into a pool, where they sit and wait for work.
· When a server receives a request, it awakens a thread from this pool. If one is available & passes it to the service.
· Once the thread completes its service, it returns to the pool & awaits more work.
· If the pool contains no available thread, the server waits until one becomes free.
4.4.5 Thread Specific Data:
· Threads belonging to a process share the data of the process.
· Each thread might need its own copy of certain data. Such data is thread specific data.
4.4.6 Scheduler Activation:
· Communication between user thread library and kernel is known as scheduler activation.
· The kernel provides an application with a set of virtual processors & the application can schedule user threads onto an available virtual processor.
· The kernel must inform an application about certain event-upcall .
· Upcalls are handled by the thread library with an upcall handler.
· Upcall handler must run on a virtual processor.
CHAPTER-5
PROCESS SCHEDULING
5.1 Basic Concepts:
· Scheduling of this kind is a fundamental os function.
· All computer resources are scheduled before use.
· CPU is one of the primary computer resources. Its scheduling is central to os design.
5.1.1 CPU – I/O Burst Cycle:
· Process execution consists of a cycle of CPU execution and I/O wait.
· Process alternate between these states.
· Process execution begins with a CPU burst and is followed by I/O burst.
· Ref fig 5.1.
5.1.2 CPU Scheduler:
· Whenever the CPU becomes idle, the os must select one of the processes in the ready queue to be executed.
· This selection is carried-out by CPU or Short term Scheduler.
· The scheduler selects the process from the process in memory that is ready to execute and allocates the CPU to that process.
5.1.3 Preemptive Scheduling:
· CPU scheduling decisions may take place under the following circumstances.
§ When a process switches from the running state- waiting state->non preemptive
§ when a process switches from running – ready state-> preemptive
§ When a process switches from waiting- ready state.-> preemptive
§ When a process terminates.- >non preemptive
· Scheduling is of two types:
§ Preemptive scheduling
§ Non preemptive scheduling
Non preemptive scheduling:
· Once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to waiting state.
5.1.4 Dispatcher:
· It is the module that gives control of the CPU to the process selected by the short-term scheduler.
· Function involves:
§ Switching context
§ Switching to User mode
§ Jumping to the proper location in the user program to restart that program.
Dispatcher latency:
· The time it takes for the dispatcher to stop one process & start another running is known as dispatcher latency.
· 5.2 Scheduling Criteria:
· Many criteria have been suggested for comparing CPU scheduling algorithm.
· The criteria includes
§ CPU utilization
§ Throughput
§ Turnaround Time
§ Waiting Time
§ Response Time
CPU Utilization:
· Keep the CPU as busy as possible.
· CPU utilization can range from 0 to 100 percent.
· In real systems it should range from 40-90 percent.
Throughput:
· Measure of work is the number of process that is completed per time unit.
· Long process ---- one process per hour
· Short process ---- 10 process per second.
Turnaround Time:
· The interval from the time of submission of a process to the time of completion.
Waiting time:
· The sum of periods spent waiting in the ready queue.
Response time:
· The time from the submission of a request until the first response is produced.
· It is desirable to maximize CPU utilization & throughput, to minimize turnaround time, waiting time & response time.
5.3 Scheduling Algorithm:
· There are many different CPU scheduling algorithms.
§ First-come First Served Scheduling Algorithm (FCFS).
§ Shortest Job First Scheduling Algorithm (SJF).
§ Priority Scheduling Algorithm.
§ Round Robin scheduling Algorithm (RR).
§ Multilevel Queue Scheduling Algorithm.
§ Multilevel Feedback Queue Scheduling Algorithm
5.3.1 First-come First Served Scheduling Algorithm (FCFS).
· The process that requests the CPU first is allocated the CPU first.
· It is easily managed with FIFO queue.
· When a process enters the ready queue, its PCB is linked onto the tail of the queue.
· When the CPU is free, it is allocated to the process at the head of the queue.
· The running process then removed from the queue.
· Code is simple to write and understand.
· It is non preemptive scheduling algorithm.
· Ex.
Process Burst time
P1 24
P2 3
P3 3
| P1 | P2 | P3 |
0 24 27 30
Average waiting time= (0+24+27)/3= 17 milliseconds
· If the process enter like p2, p3, p1 then average waiting time is 3 Milliseconds.
· The average waiting time is substantial. Generally it is not minimal.
· It results lower CPU and device utilization.
Shortest Job First Scheduling Algorithm (SJF).
· It would be shortest –next- CPU – burst algorithm because scheduling depends on the length of the next COU burst of a process.
· Ex.
Process Burst time
P1 6
P2 8
P3 7
| P1 | P3 | P2 |
0 6 13 21
Average waiting time= (0+6+13)/3= 6.3 milliseconds
· It gives minimum average waiting time.
· The difficulty is knowing the length of next CPU request.
· The length o the next CPU request can be predicted by exponential average.
Exponential average
For α, 0<=α<=1.
T n+1 = α t n +(1-α)T n
t n - current history
T n - past history
· If α value is zero the code has no effect
· If α value is one it is old and irrelevant CPU burst.
· If α value is 1/2, equally weighted.
· It can be either preemptive or non preemptive.
Preemptive SJF Scheduling:
· It will preempt the currently executing process
· It is also called as Shortest – remaining- time- first Scheduling.
Non Preemptive SJF Scheduling:
· It will allow the currently executing process to finish its CPU burst.
· Ex.
Process arrival Time Burst time
P1 0 8
P2 1 4
P3 2 9
| P1 | P2 | P1 | P3 |
0 1 5 12 21
Average waiting time= ((5-1) + (1-1) + (12-2))/3
= (4+0+10)/3
= 4.6 milliseconds
5.3.3 Priority Scheduling Algorithm.
· The SJF algorithm is a special case of priority scheduling algorithm.
· Priorities are generally indicated by some fixed range of numbers. ie) 0-7/ 0-4095.
· Low number represents high priority.
· Priorities can be defined internally or externally.
· Internally defined priorities:
· It uses some measurable quantity or quantities.
· Externally defined priorities:
· Priorities are set by criteria outside the os.
· It can be either preemptive or non preemptive scheduling
· When a process arrives at the ready queue, its priority is compared with the priority of the currently running process.
· Ex.
Process priority Burst time
P1 2 8
P2 3 4
P3 1 4
| P3 | P1 | P2 |
0 4 12 16
Average waiting time= (4 + 12 + 0)/3
= 5.3 milliseconds
Preemptive Scheduling:
§ It will preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process.
Non Preemptive Scheduling:
§ It will simply put the new process at the head of the ready queue.
· It can leave some low priority processes waiting indefinitely.
§ The process will eventually be run.
§ System will eventually crash and lose all unfinished low priority process.
Aging:
· Gradually increasing the priority of process that wait in the system for long time.
5.3.4 Round Robin scheduling Algorithm (RR).
· Designed especially for time sharing systems.
· Similar to FCFS but preemption is added between processes.
· A small unit of time called as time quantum or time slice.
· Time quantum is generally from 10- 100 milliseconds.
· Ready queue is treated as circular queue.
· Ready queue as FIFO queue of process.
· New processes are added to the tail of the ready queue.
· The scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum and dispatches the process.
· The process may have a CPU burst less than 1 time quantum.
§ The process itself will release the CPU voluntarily.
· Running process is longer than 1 time quantum,
§ The timer will go off & will cause an interrupt to the os.
· The average waiting time is long.
· Ex.
Process Burst time
P1 24
P2 3
P3 3
Time quantum=4
| P1 | P2 | P3 | P1 | P1 | P1 | P1 | P1 |
0 4 7 10 14 18 22 26 30
Average waiting time= ((10-4) + 4 + 7) /3
= 5.66milliseconds
· If n process in ready queue, q time quantum, each process gets 1/n of the CPU time.
· Each process must wait no longer than (n-1)*q time units until its next time quantum.
· The smaller time quantum increases context switches.
· Time quanta to be large with respect to the context switch time.
· The context switch time is a small fraction of the time quantum.
· Turnaround time also depends on the size of time quantum.
5.3.5 Multilevel Queue Scheduling Algorithm.
· Processes are classified as
·
·
·
0 comments:
Post a Comment