UNIT-I

Operating System Introduction: Operating Systems Objectives and functions, Computer System
Architecture, OS Structure, OS Operations, Evolution of Operating Systems - Simple Batch, Multi
programmed, time shared, PersonalComputer, Parallel, Distributed Systems, Real-Time Systems, Special -
Purpose Systems, Operating System services, user OS Interface, System Calls, Types of System Calls,
System Programs, Operating System Design and Implementation, OS Structure, Virtual machines

1
2
Operatingsystemperformsthefollowing functions:

1. Booting
Booting isaprocessofstartingthecomputer operatingsystemstartsthecomputerto work. It
checks the computer and makes it ready to work.
2. Memory Management
It is also an important function of operating system. The memory cannot be managed
without operating system. Different programs and data execute in memoryat one time. if
there is no operating system, the programs may mix with each other. The systemwill not
work properly.
3. LoadingandExecution
A program is loaded in the memory before it can be executed. Operating system provides
the facility to load programs in memory easily and then execute it.
4. Datasecurity
Data is an important partofcomputer system. The operating systemprotectsthe data storedon the
computer from illegal use, modification or deletion.
5. DiskManagement
Operatingsystemmanagesthe [Link] way.
6. ProcessManagement
CPUcanperformonetask at onetime. ifthereare many tasks, operating systemdecideswhich task
should get the CPU.
7. DeviceControlling
operating systemalso controlsalldevicesattached to [Link] hardware devices are
controlled with the help of small software called device drivers..
8. Providinginterface
It is used in order that user interface acts with a computer mutually. User interface controls
how youinput dataand instructionandhow information [Link]
system offers two types of the interface to the user:
1. Graphical-lineinterface:It interactswithofvisualenvironmentto communicate
with the computer. It uses windows, icons, menus and other graphicalobjectsto issues
commands.
2. Command-line interface:it provides an interface to communicate with the computer by
typing commands.

3
ComputerSystem Architecture
Computersystemcan bedivided intofourcomponentsHardware–provides basic
computing resources
CPU,memory,I/Odevices,Operat ing system
Controlsandcoordinatesuseofhardwareamongvariousapplicationsandusers
Applicationprograms–definethewaysinwhichthesystemresourcesareusedtosolvethecomputing problems of
the users
Wordprocessors,compilers,webbrowsers,databasesystems,videogames
Users
People,machines,othercomputersFour
Components of a Computer System

Computer architecture means construction/design ofa computer. A computer system may be

organized in different ways. Some computer systems have single processor and others have
multiprocessors. So based on the processors used in computer systems, they are categorized
into the following systems.

1. Single-processorsystem

2. Multiprocessorsystem

3. ClusteredSystems:

1. Single-ProcessorSystems:

Some computers use only one processor such as microcomputers (or personal computers PCs).
On a single-processor system, there is only one CPU that performs all the activities in the
computer system. However, most of these systems have other special purpose processors, such
as I/O processors that move data quickly among different components of the computers. These
processorsexecuteonlya limited systemprograms and do not runtheuser program. Sometimes
4
they are managed by the operating system. Similarly, PCs contain a special purpose
microprocessorinthekeyboard,whichconvertsthekeystrokesintocomputercodesto besentto the
[Link] use ofspecialpurpose microprocessors iscommon inmicrocomputer. But itdoes not
mean that this system is multiprocessor. A system that has only one general-purpose CPU,is
considered as single- processor system.

2. MultiprocessorSystems:

In multiprocessor system, two or more processorsworktogether. Inthis system, multiple programs

(more than one program) are executed on different processors at the same time. This type of
processing isknown as multiprocessing. Some operating systems have featuresof multiprocessing.
UNIX is an example of multiprocessing operating system. Some versions of Microsoft Windows
also support multiprocessing.

Multiprocessor system is also known as parallel system. Mostly the processors of

multiprocessor systemshare the common system bus, clock, memory and peripheral devices.
This system is very fast in data processing.

TypesofMultiprocessorSystems:

Themultiprocessorsystemsarefurtherdividedintotwo types; (i).

Asymmetric multiprocessing system
(ii).Symmetricmultiprocessingsystem

(i) AsymmetricMultiprocessing System(AMS):

The multiprocessing system, in which each processor is assigned a specific task, is known as
Asymmetric Multiprocessing System. For example, one processor is dedicated for handling
user's requests, one processor isdedicated for running application program, and one processor
is dedicated for running image processing and so on. In this system, one processor works as
master processor, while other processors work as slave processors. The master processor
controls the operations of system. It also schedules and distributes tasks among the slave
processors. The slave processors perform the predefined tasks.

(ii) SymmetricMultiprocessing System(SMP):

The multiprocessing system, in which multiple processors worktogether on the same task, is
known as Symmetric Multiprocessing System. In this system, each processor can perform all
[Link]-slaverelationshipexists between the
processors.

5
For example, different processorsinthesystemcancommunicatewitheachother. Similarly, an I/O
canbe processed onanyprocessor. However, I/O must be controlled to ensure that the data
reaches the appropriate processor. Because all the processors share the same memory, so the
input data given to the processors and their results must be separately controlled. Today all
modern operating systems including Windows and Linux provide support for SMP.

It mustbe noted that in the same computer system, the asymmetric multiprocessing
andsymmetric multiprocessing technique can be used through different operating systems.

ADual-CoreDesign

3. ClusteredSystems:

Clustered system is another formof multiprocessor system. This systemalso contains multiple
processors but it differs from multiprocessor system. The clustered system consists of two or
more individual systems that are coupled together. In clustered system, individual systems (or
clustered computers) share the same storage and are linked together ,via Local Area Network
(LAN).

A layer of cluster software runs on the cluster nodes. Each node can monitor one or more of
the other nodes over the LAN. If the monitored machine fails due to some technical fault (or
due to other reason), the monitoring machine can take ownership of its storage. The
monitoring machine can also restart the applications that were running on the failed machine.
The users of the applications see only an interruption of service.

TypesofClusteredSystems:

Likemultiprocessorsystems,clusteredsystemcanalsobeoftwo types (i).

Asymmetric Clustered System
(ii).SymmetricClustered System
(i). AsymmetricClusteredSystem:
Inasymmetricclusteredsystem,onemachineisinhot-standbymodewhiletheother
6
machine is running the application. The hot-standby host machine does nothing. It only
monitors the active server. If the server fails, the hot-standby machine becomes the active
server.
(ii). SymmetricClusteredSystem:
In symmetric clustered system, multiple hosts (machines) run the applications. They also
monitor each other. This mode is more efficient than asymmetric system, because it uses all
the available hardware. This mode is used only if more than one application be available to
run.

Operating System – Structure

OperatingSystemStructure
Multiprogrammingneeded for efficiency
Single user cannot keep CPU and I/O devices busy at all times
Multiprogramming organizesjobs (code and data) so CPU alwayshas one
toExecute A subset of total jobs in system is kept in memory

7
8
2)Multitasking

9
Operating-systemOperations

1) Dual-ModeOperation·
In order to ensure the proper execution of the operating system, we must be able to distinguish
between the execution of operating-system code and user defined code. The approach taken by
most computer systems is to provide hardware support that allows us to differentiate among
various modes of execution.

[Link].
Abit,calledthe modebit isaddedtothehardwareofthecomputerto indicatethecurrent mode: kernel
(0) or user (1).with the mode bit we are able to distinguish between a task that isexecuted
onbehalfofthe operatingsystemandone thatisexecuted onbehalfoftheuser,When

the computer system is executing on behalf of a user application, the system is in user mode.
However, when a user application requests a service from the operating system (via a.. system
call), it must transition from user to kernel mode to fulfill the request.

At system boot time, the hardware starts in kernel mode. The operating system is then loaded
and starts user applications in user mode. Whenever a trap or interrupt occurs, the hardware
switches fromuser mode to kernel mode (that is, changes the state ofthe mode bit to 0). Thus,
whenever the operating system gains control of the computer, it is inkernel mode. The system
always switches to user mode (by setting the mode bit to 1) before passing control to a user
program.
10
The dual mode of operation provides us with the means for protecting the operating system
from errant users-and errant users from one another. We accomplish this protection by
designating some of the machine instructions that may cause harm as privileged [Link]
hardware allows privileged instructions to beexecuted only inkernel mode. Ifan attempt is made
to execute a privileged instruction in user mode, the hardware does not execute the instruction
but rather treats it as illegal and traps it to the operating system. The instruction to switch to
kernel mode is an example of a privileged instruction. Some other examples include I/0 control
timer management and interrupt management.

11
12
13
14
Personal-ComputerSystems(PCs)
A personal computer (PC) is a small, relatively inexpensive computer designed for an
individual user. In price, personal computers range anywhere from a few hundred dollars to
thousands of dollars. All are based on the microprocessor technology that enables
manufacturers to put an entire CPU on one chip.
At home, the most popular use for personal computers is for playing games. Businessesuse
personal computers for word processing, accounting, desktop publishing, and for
runningspreadsheet and database managementapplications.

15
Specialpurposesystems

a) Real-TimeEmbeddedSystems
These devices are found everywhere, fromcar engines and manufacturing robotsto DVDs
and microwave ovens. They tend to have very specific tasks.
Theyhavelittleornouserinterface,preferringtospendtheirtimemonitoringand managing
hardware devices, such as automobile engines and robotic arms.

16
b) MultimediaSystems
Mostoperating systemsaredesignedto handleconventionaldatasuchastext files, programs,
word-processing documents, and spreadsheets. However, a recent trend in technology is the
incorporation of multimedia data into computer systems. Multimedia data consist of audio
and video files as well as conventional files. These data differ fromconventional data in that
multimedia data-such as frames of video-must be delivered (streamed) according to certain
time restrictions (for example, 30 frames per second). Multimedia describes a wide range of
applications in popular use today. These include audio files such as MP3, DVD movies,video
conferencing, and short video clips of movie previews or news stories downloadedover the
Internet. Multimedia applications mayalso include live webcasts (broadcasting over the
World Wide Web)

c) HandheldSystems
Handheld Systems include personaldigitalassistants (PDAs, cellular telephones. Developers of
handheld systems and applications face many challenges, most of which are due to the limited
size of such devices. For example, a PDA is typically about 5 inches in height and 3 inches in
width, and it weighs less than one-half pound. Because of their size, most handheld deviceshave
small amounts of memory, slow processors, and small display screens.

17
OperatingSystemServices

One set of operating-system services provides functions that are helpful to theuser
Communications–Processes mayexchange information, onthesamecomputerorbetweencomputers
overanetworkCommunicationsmaybe viasharedmemoryorthroughmessagepassing(packetsmoved by the
OS)
Error detection – OS needs to beconstantlyaware of possible errors Mayoccur inthe CPU and
memoryhardware, inI/Odevices, inuserprogramForeachtypeoferror,OSshouldtaketheappropriate action
to ensure correct and consistent computing Debugging facilities can greatly enhance the user’s and
programmer’s abilities to efficiently use the system
AnothersetofOSfunctionsexistsfor ensuringtheefficient operationofthesystemitselfviaresource
Sharing

18
 Resourceallocation -Whenmultipleusersormultiple jobsrunningconcurrently, resources must be
allocated to each of them
Manytypesofresources- Some(suchasCPU cycles, mainmemory, and filestorage) mayhavespecial
allocation code, others (such as I/O devices) mayhave general request and release code
Accounting -Tokeeptrackofwhichusersusehow muchandwhatkindsofcomputerresources
Protection and security - The owners of information stored in a multiuser or networked computer
system may want to control use of that information, concurrent processes should not interfere with each
other
Protectioninvolvesensuringthatallaccesstosystemresources iscontrolled
Security ofthe systemfromoutsiders requires user authentication, extends to defending externalI/O
devices from invalid access attempts
Ifa systemisto beprotectedand secure, precautions mustbeinstitutedthroughout it. Achain isonlyas
strong as its weakest link.
UserOperating SystemInterface-CLI
CommandLineInterface(CLI)orcommandinterpreterallowsdirectcommand entry
Sometimesimplementedinkernel,sometimesbysystemsprogram
sometimes multiple flavors implemented – shells
Primarilyfetchesacommandfromuser andexecutesit

UserOperating SystemInterface-GUI

User-friendly desktop metaphor interfaceUsually

mouse, keyboard, and monitor Icons represent
files, programs, actions, etc
Various mouse buttons over objects in the interface cause various actions (provide information,
options, execute function, open directory (known as a folder)
InventedatXeroxPARC
Many systems now include both CLI and GUI
interfaces Microsoft Windows is GUI with CLI
“command” shell
Apple Mac OS X as “Aqua” GUI interface with UNIX kernel underneath and shells
available Solaris is CLI with optional GUI interfaces (Java Desktop, KDE)
SystemCalls

Programming interface to the services provided by the OS

Typically written in a high-level language (C or C++)
Mostly accessed by programs via a high-level Application Program Interface (API) rather than
direct systemcallusenThree most commonAPIsare Win32 API for Windows, POSIXAPI for POSIX-
based systems (including virtually all versions of UNIX, Linux, and Mac OS X), and Java API for the
Java virtual machine (JVM)
WhyuseAPIsratherthansystemcalls?

19
ExampleofSystemCalls

ExampleofStandardAPI
ConsidertheReadFile()functioninthe
Win32API—afunctionforreadingfromafile

Adescriptionoftheparameterspassedto ReadFile()HANDLEfile—the filetoberead

LPVOID buffer—a buffer where the data will be read into and written
fromDWORD bytesToRead—the number ofbytes to be read into the
buffer LPDWORD bytesRead—the number of bytes read during the
last read LPOVERLAPPED ovl—indicates ifoverlapped I/O is being
used
SystemCallImplementation
Typically, anumber associatedwitheachsystemcall
System-callinterfacemaintainsatableindexedaccordingtotheseNumbers
The system call interface invokes intended system call in OS kernel and returns status of the system
call and any return values
The caller need know nothing about how the system call is
implementedJustneedstoobeyAPIandunderstandwhatOSwill

20
 doasaresultcallMostdetailsofOSinterfacehiddenfrom programmer by API
Managed by run-time support library (set of functions built into libraries included with compiler)
API – System Call – OS Relationship
StandardCLibraryExample

SystemCallParameterPassing
Often,moreinformationisrequiredthansimplyidentity ofdesiredsystem call
Exact type and amount of information vary according to OS and call Three
general methods used to pass parameters to the
OSSimplest:passtheparametersinregisters
Insomecases,maybemoreparametersthanregisters
Parameters stored ina block, or table, inmemory, and address ofblock passed as a parameter in
a register
ThisapproachtakenbyLinuxandSolaris
Parameters placed, or pushed, onto the stack bythe programand popped off the stack bytheoperating
system
Blockandstackmethodsdonotlimitthe numberorlengthofparametersbeingpassed

21
 ParameterPassingviaTable

TypesofSystemCalls
1. Processcontrol
2. Filemanagement
3. Devicemanagement
4. Informationmaintenance
5. Communications
Processcontrol
Arunningneedstohaltitsexecutioneithernormallyor abnormally.
If a system call is made to terminate the running program, a dump of memory is
sometimestaken and an error message generated which can be diagnosed by a debugger
o end,abort
oload,execute
o createprocess,terminate process
ogetprocessattributes,setprocessattributes
owaitfor time
owaitevent,signalevent
oallocateandfreememory
Filemanagement
OSprovidesanAPI tomakethesesystemcallsformanagingfiles
ocreatefile,deletefile
oopen,closefile
oread, write, reposition
ogetandsetfileattributes
Device management
Process requires several resources to execute, if these resources are available, they will be
granted and control retuned to user process. Some are physical such as video card and other
such as file. User program request the device and release when finished
orequestdevice,releasedevice
oread, write, reposition
ogetdeviceattributes, setdeviceattributes
o logicallyattachordetachdevices
22
 Informationmaintenance
System calls exist purely for transferring information between the user
programandOS. It canreturninformationaboutthesystem, suchasthenumberofcurrent users, the
versionnumber ofthe operating system, the amount offree memoryor disk space and so on.
o gettimeordate,settimeordate
o getsystemdata,setsystemdata
o getandsetprocess,file,ordevice attributes

Communications
Twocommonmodelsofcommunication
Message-passingmodel,informationisexchangedthroughaninterprocess-
communication facility provided by the OS.
Shared-memory model, processes use map memorysystemcalls to gainaccess to regions of
memory owned by other processes.
ocreate, deletecommunicationconnection
osend,receivemessages
otransferstatus information
oattachanddetachremotedevices

ExamplesofWindowsandUnixSystemCalls

23
 MS-DOS execution

(a) At system startup (b)runninga

program FreeBSD Running Multiple Programs

24
SystemPrograms
Systemprogramsprovideaconvenient environment forprogramdevelopment andexecution. Thecan be
divided into:
Filemanipulation
Statusinformation
File modification
Programminglanguagesupport
Program loading and execution
Communications
Applicationprograms

Most users’ view of the operation system is defined by system programs, not the actual
systemcalls provide a convenient environment for programdevelopment and execution
Someofthemare simplyuserinterfacesto systemcalls;othersare considerablymore complex
Filemanagement-Create,delete,copy,rename,print,dump,list,andgenerallymanipulatefilesand directories
 Statusinformation
Some ask the system for info - date, time, amount of available memory, disk space, number of users
Others provide detailed performance, logging, and debugging information
Typically, these programs format and print the output to the terminal or other output
devicesSome systems implement a registry - used to store and retrieve configuration
information
 Filemodification
Texteditorstocreateandmodifyfiles
Special commands to search contents of files or perform transformations of the text
Programming-language support - Compilers, assemblers, debuggers and interpreters sometimes
provided
Program loading and execution- Absolute loaders, relocatable loaders, linkage editors, andoverlay-
loaders, debugging systems for higher-level and machinelanguage

25
 Communications- Providethe mechanismforcreating virtualconnectionsamongprocesses, users,and
computer systems
Allowuserstosendmessagestooneanother’sscreens,browsewebpages,sendelectronic-mail messages, log
in remotely, transfer files from one machine toanother

OperatingSystemDesign andImplementation
Design and Implementation ofOS not “solvable”, but some approaches have proven successful
Internal structure of different Operating Systems can vary widely
StartbydefininggoalsandspecificationsAffectedby
choice of hardware, type of system User goals and
System goals
Usergoals–operatingsystemshouldbeconvenienttouse,easytolearn,reliable, safe, andfast
System goals–operatingsystem shouldbeeasytodesign,implement,andmaintain,aswell asflexible, reliable,
error-free, and efficient
Importantprincipletoseparate
Policy:Whatwillbe done?
Mechanism:Howtodoit?
Mechanismsdeterminehowtodosomething,policiesdecidewhatwillbe done
Theseparationof policyfrommechanismisaveryimportantprinciple,itallowsmaximumflexibilityif policy
decisions are to be changed later
SimpleStructure
MS-DOS – written to provide the most functionality in the least space Not divided
intomodules
AlthoughMS-DOShassomestructure,itsinterfacesandlevelsofFunctionalityarenotwellseparated

26
 MS-DOSLayerStructure

The operating system isdivided into a numberoflayers(levels), each built ontopoflower [Link]
bottom layer(layer 0), isthe hardware; the highest (layer N) isthe userinterface.
With modularity, layers are selected such that each uses functions (operations) and services of
only lower-level layers
TraditionalUNIXSystemStructure

UNIX

UNIX–limited byhardware functionality,theoriginalUNIXoperatingsystemhad limitedstructuring. The

UNIX OS consists of two separable parts

Systemsprograms
The kernel
Consistsofeverythingbelowthesystem-callinterfaceandabovethephysicalhardware Provides the
file system, CPU scheduling, memory management, and other operating-system

27
functions;alargenumberoffunctionsforonelevel Layered
Operating System

MicrokernelSystemStructure
Movesasmuch fromthekernelinto“user”space
Communicationtakesplacebetweenusermodulesusingmessagepassing Benefits:
Easiertoextenda microkernel
Easier to port the operating system to new architectures More reliable (less codeis
running in kernel mode)
Moresecure
Detriments:
Performanceoverheadofuserspacetokernelspacecommunication
MacOS X Structure

28
Modules

Most modern operating systems implement kernel modules

Uses object-oriented approach
Eachcorecomponentisseparate
Each talks to the others over known interfacesEach
is loadable as needed within the kernel Overall,
similar to layers but with more flexible

SolarisModularApproach

VirtualMachines
[Link] hardwareand the operating system
kernel as though they were allhardware
Avirtualmachineprovidesaninterfaceidenticaltotheunderlyingbarehardware
Theoperatingsystem hostcreatestheillusion thataprocesshasitsown processorand(virtual memory) Each guest
provided with a (virtual) copy of underlying computer
VirtualMachines HistoryandBenefits
First appearedcommerciallyinIBMmainframesin1972
Fundamentally, multipleexecutionenvironments(differentoperatingsystems)cansharethesamehardware
Protect from each other
Somesharing offilecanbepermitted,controlled
Commutate with each other, other physical systems via networking
Useful for development, testing
Consolidationofmanylow-resourceusesystemsontofewerbusiersystems
“OpenVirtualMachineFormat”,standardformatofvirtualmachines,allowsaVMtorunwithinmany different
virtual machine (host) platforms

29
Para-virtualization
Presentsguestwithsystemsimilarbutnotidenticaltohardware Guest
must be modified to run on par virtualized hardware
GuestcanbeanOS,orinthecaseofSolaris10applicationsrunningincontainers Solaris 10 with
Two Containers

30
VMwareArchitecture

TheJava VirtualMachine

Operating-SystemDebugging

Debugging is finding and fixing errors, or bugs

generate log files containing error information
Failure of an application can generate core dump file capturing memory of the process
Operating system failure can generate crash dump file containing kernel memory Beyond
crashes, performance tuning can optimize system performance
Kernighan’s Law: “Debugging is twice as hard as writing the code in the rst place. Therefore, if you
write the code as cleverlyas possible, you are, bydefinition, not smart enoughto debug it.”
DTrace tool in Solaris, FreeBSD, Mac OS X allows live instrumentation on production systems
Probesfirewhencodeisexecuted,capturingstatedataandsending it toconsumersofthoseprobes

31
Process
Aprocessis aprogramatthetimeofexecution.
DifferencesbetweenProcessand Program

Process Program
Processisadynamicobject Programisastaticobject

Process is sequence of instruction Programisasequence ofinstructions

execution
Processloaded into mainmemory Programloadedintosecondarystorage
devices
Timespanofprocessislimited Timespanofprogramisunlimited
Processisaactiveentity Programisapassive entity

Process States

When a process executed, it changes the state, generally the state of process is determined by
the current activityof the process. Each process may be in one of the following states:
1. New :Theprocessisbeingcreated.
2. Running :Theprocessisbeingexecuted.
3. Waiting :Theprocess iswaitingforsomeeventtooccur.
4. Ready :Theprocessiswaitingtobeassignedtoaprocessor.
5. Terminated:TheProcesshasfinishedexecution.
Onlyoneprocesscanberunninginanyprocessoratany time,Butmanyprocessmaybein ready and
waiting states. The ready processes are loaded into a “ready queue”.
Diagramofprocessstate

32
a) New ->Ready : OScreatesprocessandpreparesthe
process to be executed,thenOSmoved the process into readyqueue.
b) Ready->Running :OSselectsoneoftheJobs fromreadyQueueandmovethemfrom ready
to Running.

c) Running->Terminated: When the Execution of a process has Completed,

OSterminatesthatprocess from running state. Sometimes OS terminates the process for
someother reasons including Time exceeded, memory unavailable, access violation,
protection Error, I/O failure and soon.
d) Running->Ready:Whenthetimeslot oftheprocessor expired(or)Ifthe
processorreceivedanyinterrupt signal, the OS shifted Running -> ReadyState.

e) Running->Waiting:Aprocessisputintothewaitingstate,iftheprocessneedan event occur

(or) an I/O Devicerequire.
f) Waiting->Ready : A processin the waiting state ismoved to ready
state whenthe eventforwhichit has beenCompleted.
ProcessControlBlock:

Eachprocessisrepresented intheoperating SystembyaProcessControlBlock.

[Link] Process.

ProcessState

ProgramCounter

CPURegisters

CPUScheduling Information

Memory–ManagementInformation

AccountingInformation

I/OStatusInformation

ProcessControlBlock
1. ProcessState :TheStatemaybenew,ready,running,andwaiting,Terminated…
2. ProgramCounter :indicatestheAddressofthenextInstructionto beexecuted.
3. CPUregisters :registersincludeaccumulators,stackpointers,
General purpose Registers….

33
4. CPU-SchedulingInfo : includes a process pointer, pointers to
schedulingQueues,other scheduling parametersetc.
5. Memory managementInfo: includespagetables, segmentationtables, value of
base and limit registers.
6. AccountingInformation: includesamountofCPUused,timelimits,Jobs(or)Processnumbers.
7. I/O StatusInformation: Includes the list ofI/O Devices Allocated to theprocesses, list ofopen
files.

Threads:

Aprocess isdivide into numberoflight weight process, each light weight processissaid to be a
Thread. The Thread has a program counter (Keeps track of which instruction to execute next),
registers (holds its current working variables), stack (execution History).
Thread States:

1. bornState : Athread isjustcreated.

2. readystate :ThethreadiswaitingforCPU.
3. running :Systemassignsthe processortothethread.
4. sleep :Asleeping threadbecomesreadyafterthedesignatedsleeptimeexpires.
5. dead :TheExecutionofthethreadfinished.

Eg:Wordprocessor.
Typing,Formatting,Spellcheck,savingarethreads.
DifferencesbetweenProcessand Thread

Process Thread
Processtakesmoretimeto create. Thread takeslesstimeto create.
ittakesmoretimetocompleteexecution& Lesstimeto terminate.
terminate.
Execution isveryslow. Executionisveryfast.
It takes more time to switch b/w two Ittakeslesstimetoswitchb/wtwo
processes. threads.
Communicationb/wtwoprocessesisdifficult . Communicationb/wtwothreadsis
easy.
Processcan’tsharethesame memoryarea. Threadscansharesamememoryarea.
Systemcallsarerequestedtocommunicate Systemcallsare notrequired.
each other.
Processislooselycoupled. Threadsaretightlycoupled.
Itrequiresmoreresourcesto execute. Requiresfewresourcestoexecute.

34
Multithreading

[Link] Threads with

in a Process execute at a time is called Multithreading.
If a program, is multithreaded, even when some portion of it is blocked, the whole program is
not [Link] rest of the program continues working If multiple CPU’s are available.
Multithreading gives best [Link] we have only a single thread, number of CPU’s
available, No performance benefits achieved.
 Processcreationisheavy-weightwhilethreadcreationis light-weight
Can simplify code, increase efficiency

Kernelsaregenerallymultithreaded
CODE-Contains instruction
DATA-holdsglobalvariableFILES-
openingandclosingfiles
REGISTER-containinformationaboutCPUstate
STACK-parameters, local variables, functions
Types Of Threads:

1) User Threads : Thread creation, scheduling, management happen in user space by

ThreadLibrary. user threads are fasterto create and manage. Ifa user thread performs a system
call, which blocks it, allthe otherthreads inthat process one also automaticallyblocked, whole
process is blocked.

Advantages
 ThreadswitchingdoesnotrequireKernelmodeprivileges.
 Userlevelthreadcanrunonanyoperatingsystem.
 Schedulingcanbeapplicationspecificintheuserlevelthread.
 Userlevelthreadsarefasttocreateand manage.

35
Disadvantages

 Inatypicaloperatingsystem,mostsystemcallsareblocking.
 Multithreadedapplicationcannottakeadvantageofmultiprocessing.

2) Kernel Threads: kernel creates, schedules, manages these threads .these threads are
slower, manage. Ifone thread in a process blocked, over allprocess need not be blocked.

Advantages
 Kernelcansimultaneouslyschedulemultiplethreadsfromthesameprocess onmultiple
processes.
 Ifonethreadinaprocessis blocked, theKernelcanscheduleanotherthreadofthesameprocess.
 Kernelroutinesthemselvescanmultithreaded.

Disadvantages

 Kernelthreadsaregenerallyslowertocreateand managethantheuserthreads.
 Transfer ofcontrolfromonethreadtoanother withinsameprocess requiresa modeswitchto the
Kernel.

MultithreadingModels

Some operating systemprovides a combined user level thread and Kernel level thread facility. Solaris isa
good example of this combined approach. In a combined system, multiple threads within the same
applicationcanruninparallel onmultipleprocessorsanda blockingsystemcallneed not blocktheentire
process. Multithreading models are three types
 Manytomanyrelationship.
 Manytoonerelationship.
 Onetoonerelationship.

ManytoManyModel

Inthis model,manyuser levelthreads multiplexestotheKernelthread ofsmaller [Link] number of

Kernel threads maybespecific to either a particular application ora particularmachine.
[Link] thismodel,developerscancreateasmanyuser 36
threadsasnecessaryandthecorrespondingKernelthreadscanruninparallelsonamultiprocessor.
 ManytoOneModel

Manytoonemodelmaps manyuser [Link] done in user

space. When thread makes a blocking system call, the entire process will be blocks. Only one
threadcanaccess theKernelatatime,so multiplethreads areunabletoruninparallel on multiprocessors.

Iftheuser levelthreadlibraries areimplementedintheoperatingsysteminsucha waythat systemdoes not

support them then Kernel threads use the many to one relationship modes.

OnetoOneModel

Thereis onetoonerelationship ofuser [Link] modelprovides more

concurrency than the many to one model. It also another thread to run when a thread makes a blocking
system call. It support multiple thread to execute in parallel on microprocessors.

Disadvantageofthis modelisthatcreatinguser [Link]/2, windows

NT and windows 2000 use one to one relationship model.

37
38
 PROCESS SCHEDULING:

CPU is alwaysbusyin Multiprogramming. BecauseCPUswitches fromonejobtoanotherjob. Butin

simplecomputersCPUsitidleuntiltheI/Orequestgranted.
scheduling is a important OS function. All resources are scheduled before use.(cpu,
memory, devices…..)
Process scheduling is an essential part of a Multiprogramming operating systems. Such
operatingsystemsallow morethanoneprocesstobe loaded into theexecutable memoryat a
time and the loaded process shares the CPU using time multiplexing
. SchedulingObjectives
Maximizethroughput.
Maximizenumberofusersreceivingacceptableresponsetimes. Be
predictable.
Balanceresourceuse.
Avoidindefinitepostponement.
Enforce Priorities.
Givepreferencetoprocessesholdingkeyresources

SCHEDULING QUEUES: people live in rooms. Process are present in rooms knows
as queues. There are 3types
1. job queue: when processes enter the system, they are put into a job queue, which
consistsallprocesses inthe system. Processes inthe jobqueue reside onmassstorageand await the
allocation of main memory.
2. ready queue:if a processis presentin mainmemory andis ready to be allocated to cpu
forexecution, is kept in readyqueue.
3. devicequeue:ifaprocessispresentinwaitingstate(or)waitingforani/oeventto complete is
said to bein device queue.(or)
Theprocesseswaiting foraparticularI/Odeviceiscalleddevicequeue.

39
Schedulers:Thereare3 schedulers

1. Longtermscheduler.
2. Mediumterm scheduler
3. Shorttermscheduler.

Schedulerduties:

 Maintainsthequeue.
 SelecttheprocessfromqueuesassigntoCPU.
Typesof schedulers

1. Long term scheduler:

select the jobs from the job pool and loaded these jobs into main memory (ready
queue).Long term scheduler is also called job scheduler.
2. Shorttermscheduler:
select theprocessfromreadyqueue,and allocatesitto the cpu.
If a process requires an I/Odevice,whichis not presentavailable then process enters device
queue.
shorttermschedulermaintainsreadyqueue,[Link].
3. Medium term scheduler: if process request an I/O device in the middle of the
execution, then the process removed fromthe main memory and loaded into the waiting queue.
When the I/O operation completed, then the job moved from waiting queue to ready queue.
These two operations performed by medium term scheduler.

40
Context Switch: Assume, main memory contains more than one process. If cpu is executing a process, if
time expires or if a high priority process enters into main memory, then the scheduler saves information
about current process in the PCB and switches to execute the another process. The concept of moving CPU
by scheduler from one process to other process is known as context switch.
Non-Preemptive Scheduling: CPU is assigned toone process, CPU do not release untilthe competitionof
that process. The CPU will assigned to some other process only after the previous process has finished.
Preemptive scheduling: here CPU can release the processes even in the middle of the
execution. CPU received a signal from process p2. OS compares the priorities of p1 ,p2. If
p1>p2, CPU continues the execution of p1. If p1<p2 CPU preempt p1 and assigned to p2.
Dispatcher: The main job of dispatcher is switching the cpu from one process to another
process. Dispatcher connects the cpu to the process selected by the short term scheduler.
Dispatcher latency: The time it takes by the dispatcher to stop one process and start another
processisknownasdispatcher [Link] latencyisincreasing,thenthedegreeof
multiprogramming decreases.
SCHEDULINGCRITERIA:

1. Throughput:howmanyjobsarecompletedbythecpuwithinatimeperiod.
2. Turn around time : The time interval between the submission ofthe process
and time of the completion is turn around time.
TAT = Waiting time in ready queue + executing time + waiting time in waiting queue for
I/O.
3. Waitingtime:Thetimespentbytheprocesstowaitfor cputo beallocated.
4. Responsetime:Timedurationbetweenthesubmissionandfirstresponse.
5. CpuUtilization:CPUiscostlydevice, it mustbekeptasbusyaspossible. Eg:
CPU efficiency is 90% means it is busy for 90 units, 10 units idle.
CPUSCHEDULINGALGORITHMS:

1. First come First served scheduling: (FCFS): The process that request the CPU
first is holds the cpu first. If a process request the cpu then it is loaded into the ready queue,
connect CPU to that process.
Consider the following set of processes that arrive at time 0, the length of the cpu burst time
given in milli seconds.
bursttimeisthetime,requiredthecputoexecute thatjob,itisinmilliseconds.

Process Bursttime(milliseconds)
P1 5
P2 24
P3 16
P4 10
P5 3

41
 Averageturnaroundtime:

Turnaroundtime=waitingtime+bursttime

Turnaroundtimeforp1=0+5=5.
Turn around time for
p2=5+24=29 Turn around time
for p3=29+16=45 Turn around
time for p4=45+10=55 Turn
around time for p5= 55+3=58
Averageturnaroundtime= (5+29++45+55+58/5)=187/5=37.5millisecounds

Averagewaitingtime:

waitingtime=startingtime-arrivaltime

Waitingtimeforp1=0
Waiting time for p2=5-0=5
Waiting time for p3=29-0=29
Waiting time for p4=45-0=45
Waiting time for p5=55-0=55
Averagewaitingtime=0+5+29+45+55/5 =125/5=25 ms.

AverageResponseTime:

Formula :FirstResponse -Arrival

Time Response Time for P1 =0
Response Time for P2 => 5-0 = 5
Response Time for P3 => 29-0 = 29
Response Time for P4 => 45-0 = 45
Response Time for P5 => 55-0 = 55
AverageResponseTime=>(0+5+29+45+55)/5 =>25ms

42
1) FirstComeFirstServe:

ItisNonPrimitiveSchedulingAlgorithm.

PROCESS BURST ARRIVAL

TIME TIME
P1 3 0

P2 6 2

P3 4 4

P4 5 6

P5 2 8

Processarrived intheorderP1,P2,P3,P4,P5. P1
arrived at 0 ms.
P2 arrived at 2 ms.
P3 arrived at 4 ms.
P4 arrived at 6 ms.
P5 arrived at 8 ms.

AverageTurnAroundTime
Formula:TurnaroundTime=:waitingtime+bursttime Turn
Around Time for P1 => 0+3= 3
Turn Around Time for P2 => 1+6 = 7
Turn Around Time for P3 => 5+4 = 9
TurnAround Time for P4 => 7+ 5=12
TurnAroundTimeforP5=>2+10=12
AverageTurnAround Time=>(3+7+9+12+12)/5=>43/5 =8.50 ms.
AverageResponseTime:
Formula:ResponseTime=FirstResponse-ArrivalTime
Response Time of P1 = 0
Response Time of P2 => 3-2 = 1
Response Time of P3 => 9-4 = 5
Response Time ofP4 => 13-6 = 7
ResponseTimeofP5=>18-8=10
AverageResponseTime=>(0+1+5+7+10 )/5=>23/5 =4.6ms
Advantages:EasytoImplement,Simple.
43
Disadvantage:Averagewaitingtimeisveryhigh.
2) ShortestJobFirst Scheduling(SJF):

Which processhavingthesmallestCPUbursttime,CPUisassignedto [Link] two process

having the same CPU burst time, FCFS is used.

PROCESS CPUBURSTTIME

P1 5

P2 24

P3 16

P4 10

P5 3

P5 having the leastCPU burst time ( 3ms ). CPU assigned to that( P5 ). After completion ofP5
short term scheduler search for nest ( P1 ).......
AverageWaiting Time:

Formula=StaringTime-ArrivalTime waiting
Time for P1 => 3-0 = 3
waitingTimeforP2=>34-0=34
waiting Time for P3 =>18-0 =18
waiting Time for P4 =>8-0=8
waiting time for P5=0
Averagewaiting time=>(3+34+18+8+0)/5 =>63/5 =12.6 ms

AverageTurnAroundTime:

Formula=waitingTime+burstTime

TurnAroundTimeforP1=>3+5=8
Turn Around for P2 => 34+24 =58
Turn Around for P3 => 18+16 = 34
44
TurnAroundTimeforP4=>8+10=18 Turn
Around Time for P5 => 0+3 = 3
AverageTurnaroundtime => (8+58+34+18+3)/5=> 121/5=24.2ms
AverageResponseTime:

Formula:FirstResponse-ArrivalTime

First Response time for P1 =>3-0 = 3

FirstResponsetimeforP2=>34-0=34
FirstResponsetimeforP3=>18-0=18 First
Response time for P4 => 8-0 = 8
FirstResponsetimeforP5=0
Average Response Time => ( 3+34+18+8+0 )/5 => 63/5 = 12.6 ms
SJF is Non primitive scheduling algorithm
Advantages : Least average waiting time
LeastaverageturnaroundtimeLeast
average response time
Averagewaitingtime( FCFS)=25 ms
Averagewaitingtime(SJF)=12.6ms50%timesavedinSJF.
Disadvantages:
 KnowingthelengthofthenextCPUbursttimeisdifficult.
 Aging(BigJobsarewaitingforlongtimeforCPU)

3) ShortestRemainingTimeFirst( SRTF);

Thisisprimitivescheduling algorithm.

Short termscheduler always choosesthe process that has termshortest remaining time. Whena
new process joins the ready queue , short term scheduler compare the remaining time of
executing process and new process. If the new process has the least CPU burst time, The
scheduler selects that job and connect to CPU. Otherwise continue the old process.

PROCESS BURSTTIME ARRIVALTIME

P1 3 0
P2 6 2
P3 4 4
P4 5 6
P5 2 8

45
P1 arrives at time 0, P1 executing First ,P2arrives attime 2. Compare P1 remaining time and P2 ( 3-2 =
1)and6. So,continueP1after P1,executingP2,attime4,P3arrives,compareP2remainingtime(6-1=5
) and 4 ( 4<5 ) .So, executing P3 at time 6, P4 arrives. Compare P3 remaining time and P4 ( 4-
2=2 ) and 5 (2<5 ). So, continue P3 , after P3, ready queue consisting P5 is the least out ofthree.
So execute P5, next P2, P4.
FORMULA :Finish time - Arrival
Time Finish Time for P1 => 3-0 = 3
Finish Time for P2 => 15-2 = 13
Finish Time for P3 => 8-4 =4
Finish Time for P4 => 20-6 = 14
Finish Time for P5 => 10-8 = 2

AverageTurnaroundtime =>36/5= 7.2ms.

4)ROUNDROBINSCHEDULINGALGORITHM:

It is designed especially for time sharing systems. Here CPU switches between the processes.
Whenthe time quantumexpired, the CPU switched to another job. Asmallunit oftime, called a
time quantum or time slice. A time quantum is generally from 10 to 100 ms. The time quantum
is generally depending on OS. Here ready queue is a circular queue. CPU scheduler picks the
first process from ready queue, sets timer to interrupt after one time quantum and dispatches
the process.

PROCESS BURSTTIME

P1 30

P2 6

P3 8

46
AVERAGEWAITINGTIME:

Waitingtimefor P1 =>0+(15-5)+(24-20) =>0+10+4=14

Waitingtimefor P2 =>5+(20-10)=>5+10=15
WaitingtimeforP3=>10+(21-15)=>10+6=16 Average waiting
time => (14+15+16)/3 = 15 ms.

AVERAGETURNAROUNDTIME:
FORMULA:Turnaroundtime=waitingtime+burst Time Turn
around time for P1 => 14+30 =44
Turnaroundtime forP2=>15+6=21
TurnaroundtimeforP3=> 16+8= 24
Averageturnaroundtime => (44+21+24)/3= 29.66ms

5) PRIORITYSCHEDULING:

PROCESS BURST PRIORITY

TIME
P1 6 2

P2 12 4

P3 1 5

P4 3 1

P5 4 3

P4hasthehighestpriority.AllocatetheCPUtoprocessP4firstnextP1,P5,P2,P3.

AVERAGEWAITINGTIME:

Waiting time for P1 => 3-0 =3

Waiting time for P2 => 13-0 = 13
Waiting time for P3 => 25-0 = 25
Waiting time for P4 => 0
WaitingtimeforP5=>9-0=9

Averagewaiting time=>(3+13+25+0+9 )/5=10ms

47
AVERAGETURNAROUNDTIME:

Turn around time for P1 =>3+6 = 9

Turnaroundtime forP2=>13+12=25
Turnaroundtime for P3=> 25+1 = 26
TurnaroundtimeforP4=>0+3=3 Turn
around time for P5 => 9+4 = 13

AverageTurnaroundtime=> (9+25+26+3+13 )/5= 15.2ms

Disadvantage:Starvation

Starvationmeansonlyhighpriorityprocessareexecuting,butlowpriority process are

waiting for the CPU for the longest period of the time.

Multiple–processorscheduling:
When multiple processes are available, thenthe scheduling getsmore complicated,
because there is more than one CPU which must be kept busy and in effective use
at all times.
Load sharing resolves around balancing the load between multiple processors.
Multi processor systems may be heterogeneous (It contains different kinds of
CPU’s) ( or ) Homogeneous(all the same kind of CPU).
1) Approaches to multiple-processorscheduling
a)Asymmetric multiprocessing
One processoris themaster,controlling all activities and running all kernel
code,while the other runs only user code.
b)Symmetricmultiprocessing:
Each processor schedules its own job. Each processor may have its own private queue of ready
processes.

2) ProcessorAffinity
Successive memory accesses by the process are often satisfied in cache memory.
what happens if the process migrates to another processor. the contents of cache
memory must be invalidated for the first processor, cache for the second processor
must be repopulated. Most Symmetric multi processor systems try to avoid
migration of processes from one processor to another processor, keep a process
running on the same processor. This is called processor affinity.
a) Soft affinity:
Soft affinity occurs when the system attempts to keep processes on the same
processor but makes no guarantees.

48
 b) Hardaffinity:
Processspecifiesthatitisnottobemovedbetweenprocessors.
3) Loadbalancing:
[Link] can be
achived through push migration or pull migration.

Pushmigration:
Push migration involves a separate process that runs periodically(e.g every 200 ms)
and moves processes from heavily loaded processors onto less loaded processors.
Pullmigration:
Pullmigrationinvolvesidleprocessorstakingprocessesfromthereadyqueuesoftheother processors.

Realtime scheduling:
Realtime scheduling is generallyused in the case of multimedia operating systems.
Here multiple processescompete for the CPU. How to schedule processes A,B,C so
that each one meets its deadlines. The general tendency is to make them pre-
emptable, so that a process in danger of missing its deadline can preempt another
process. When this process sends its frame, the preempted process can continuefrom
where it had left off. Here throughput is not so significant. Important is that tasks
start and end as per their deadlines.
RATEMONOTONIC(RM)SCHEDULINGALGORITHM
Rate monotonic scheduling Algorithmworksonthe principle ofpreemption. Preemptionoccurs on
a given processor when higher prioritytask blocked lower prioritytask fromexecution. This
blocking occurs due to priority level of different tasks in a given task [Link] monotonic is a
preemptive algorithm which means if a task with shorter period comes during execution it will
gain a higher priorityand can block or preemptive currentlyrunning tasks. In RM priorities are
assigned according totime period. Priorityofa task is inverselyproportionalto itstimer period.
Task with lowest time period has highest priority and the task with highest period will have
lowest priority.
Forexample,wehaveataskset that consistsofthreetasksas follows

Tasks Executiontime(Ci) Timeperiod(Ti)

T1 0.5 3

T2 1 4

T3 2 6

49
 [Link] set
U= 0.5/3+1/4+2/6=0.167+ 0.25+0.333=0.75
As processor utilization is less than 1or 100% so task set is schedulable and it also satisfies the
aboveequation of rate monotonic scheduling algorithm.

Figure1.RMschedulingofTasksetintable1.
Atasksetgivenintable1itRMschedulingisgiveninfigure1. Theexplanationofaboveisasfollows
1. According to RM scheduling algorithm task with shorter period has higher priority so T1 has
high priority, T2 has intermediate priority and T3 has lowest priority. At t=0 all the tasks are
released. Now T1 has highest priority so it executes first till t=0.5.
2. At t=0.5taskT2has higher prioritythanT3 so it executes first forone-time units tillt=1.5. After its
completion only one task is remained in the system that is T3, so it starts its execution and
executes till t=3.
3. At t=3 T1 releases, as it has higher priority than T3 so it preempts or blocks T3 and starts it
execution till t=3.5. After that the remaining part of T3 executes.
4. At t=4 T2 releases and completes it execution as there is no task running in the system at this
time.
5. At t=6 both T1 and T3 are released at the same time but T1 has higher priority due to shorter
period so it preempts T3 and executes tillt=6.5, after that T3 startsrunning and executes tillt=8.
6. Att=8 T2withhigherprioritythanT3releasessoitpreemptsT3and startsits execution.
7. At t=9 T1 is released again and it preempts T3 and executes first and at t=9.5 T3 executes its
remaining part. Similarly, the execution goes on.

EarliestDeadlineFirst(EDF)SchedulerAlgorithm
The EDF is a dynamic algorithm, Job priorities are re-evaluated at everydecision point, this re-
evaluationis basedonrelativedeadlineofa jobortask,theclosertothedeadline, thehigherthepriority. The EDF
has the following advantages:
1. Veryflexible(arrivaltimesanddeadlinesdonotneedtobeknownbeforeimplementation).
2. Moderatecomplexity.
3. Abletohandleaperiodicjobs.
TheEDFhasthefollowing disadvantages:
1. Optimallyrequirespre-emptivejobs.
2. Notoptimalonseveralprocessors.
3. Difficulttoverify.

50
 Example
Considerthefollowingtaskset inTable1. PrepresentsthePeriod, etheExecutiontimeandDstands for the
Deadline. Assume that the job priorities are re-evaluated at the release and deadline ofa job.

P e D

T1 2 0.5 2

T2 4 1 4

T3 5 1.5 5

Solution

Markalldeadlinesrelated to allthetasks
 First markalldeadlinesrelatedtothetasksasshowninFig. 1.T1,T2andT3arerepresented with
Red, Green and Blue colour respectively. The schedule is from0 – 20ms as shown.
 At T =0,T1hastheclosestdeadline, soscheduleT1.
 At T=0.5,T1iscompleted,itsnext releasetime isat 2ms.T2iscloserto itsdeadlineso T2is
scheduled next and executes for 1s.
 At T=1.5,T2jobiscompleted.T3isnext because it isclosertoitsdeadlinewhileT2hasnot been
released.
 At T=2,anew instanceofT1isreleased,therefore,T3isinterruptedandhas1msleft to complete
execution. T1 executes
 AtT=2.5,Theonlyready jobisT3which isscheduleduntilcompletion.
 AtT=4,anewinstanceofT1isreleasedwhichexecutesfor0.5ms.
 AtT =4.5,T1is nowcompleted, soT2isnowthetaskclosesttoitsdeadlineandisscheduled.
 AtT=5.5,T3isscheduledbutispre-emptedatT=6sorunsfor 0.5ms
 AtT=6,anewinstanceofT1 isreleasedand thereforescheduled.
 At T=6.5,T3isclosestto itsdeadlinebecauseT1andT3havenotbeenreleased.SoT3is allowed to
complete its execution which is 1ms.
 AtT=8,anewinstanceofT1isreleasedandisscheduled.
 At T=8.5,T2isthetaskhavingtheclosest deadlineandso isscheduledto runforitsexecution time.
 AtT=10,thenextreleaseofT1is scheduled.

51
  At T=10.5,thenext jobwiththeclosest deadline isT3becausethenext
T2jobwillbereleased at T = 12. So T3 is scheduled until completion.
 AtT=12,thenextreleaseofT1is scheduled.
AtT =12.5,T2isscheduledas itisthejobwiththeclosestdeadline.
AtT=14,thenextreleaseofT1is scheduled.
At T=15,thenext releaseofT3 isscheduledbecause it isnowthejobwiththeclosest deadline
because the next release of T1 and T2 is at 16ms. T3 runs for 1ms.
At T=16,T3ispre=emptedbecauseanewreleaseofT1whichhas theclosest deadline isnow
available.
T=16.5,T2isthe jobwiththeclosest deadline,soit isscheduled forthedurationofits execution
time.
At T=17.5,sinceT1andT2havecompleted,T3resumesexecutionto completeitstaskwhich ran
for only1ms the last time. T3 completes execution at T = 18.
AtT=18,anewinstanceofT1isreleasedandscheduledtorunfor itsentireexecutiontime.
AtT =18.5,nojobisreleasedyetbecauseanewreleaseofT1, T2andT3areat20ms.
Fig. 2showstheEDF schedulefromT= 0toT= 20.
.

52