CS1208

Operating Systems

Process scheduling

• Bachelor of Science (Hons) in Computer Science | Software Engineering | Information Technology

• Department of Computing
• Faculty of Computing and Technology
• Saegis Campus
• Nugegoda
Processes

• In the early days, computer systems executed only a single program at a time.
• This program was also generally written in Machine Language, with no need for
Compilation.
• The single running program therefore had access to all the computer’s resources.
• Things changed however when Multiprogramming Operating Systems were
developed, and High-Level Languages came to be used.
• Thus, multiple programs were resident in the Main Memory of the computer, all
vying for the access of the CPU, for their execution.
• Since the programs were developed in a High-Level Language, compilation was
required to convert them to machine code.
• Thus, the concept of Processes came into being; all resident in memory and
executing concurrently in the CPU of the computer.
Processes

• A Process therefore is a Program in Execution.

• A process is more than the program code, which is sometimes known as the Text
Section.
• It also includes the current activity, as represented by the value of the Program Counter
(PC) and the contents of the processor's registers.
• A process generally also includes the Process Stack, which contains temporary data
(such as function parameters, return addresses, and local variables), and a Data Section,
which contains global variables.
• A process may also include a Heap, which is memory that is dynamically allocated
during process run time. The structure of a process in memory is shown in the following
figure.
Processes
• A program is a passive entity, such as a file containing a list of instructions
stored on disk (often called an executable file), whereas a process is an
active entity, with a program counter specifying the next instruction to
execute and a set of associated resources.

• A program becomes a process when an executable file is loaded into

memory.
 Process State

• As a Process executes in the CPU, it changes state many times.

• The state of a process is determined by the immediately preceding activity that
brought the process to its current state.
• Each process may be in one of the following states :
• New : The process has been created.
• Running : Process instructions are being executed by the CPU.
• Waiting : The process is waiting for some event to occur (such as an
I/O completion or receipt of a signal).
• Ready : The process is waiting to be assigned to a processor.
• Terminated : The process has finished execution.
Process State Transition
Diagram
Process scheduling

• Process scheduling policy

– Decides which process runs at given time
– Different schedulers will have different goals
• Maximize throughput
• Minimize latency
• Prevent indefinite postponement
• Complete process by given deadline
• Maximize processor utilization
Scheduling Levels
• High-level scheduling
– Determines which jobs can compete for resources
– Controls number of processes in system at one time
• Intermediate-level scheduling
– Determines which processes can compete for
processors
– Responds to fluctuations in system load
• Low-level scheduling
– Assigns priorities
– Assigns processors to processes
Scheduling Levels
Figure 1 Scheduling levels.
Preemptive vs. Nonpreemptive
Scheduling
• Preemptive processes
– Can be removed from their current processor
– Can lead to improved response times
– Important for interactive environments
– Preempted processes remain in memory
• Nonpreemptive processes
– Run until completion or until they yield control of a processor
– Unimportant processes can block important ones indefinitely
Priorities
• Static priorities
– Priority assigned to a process does not change
– Easy to implement
– Low overhead
– Not responsive to changes in environment
• Dynamic priorities
– Responsive to change
– Promote smooth interactivity
– Incur more overhead than static priorities
• Justified by increased responsiveness
Scheduling Objectives
• Different objectives depending on system
– Maximize throughput
– Maximize number of interactive processes receiving
acceptable response times
– Minimize resource utilization
– Avoid indefinite postponement
– Enforce priorities
– Minimize overhead
– Ensure predictability
Scheduling Objectives

• Several goals common to most schedulers

– Fairness
– Predictability
– Scalability
Scheduling Criteria
• Processor-bound processes
– Use all available processor time
• I/O-bound
– Generates an I/O request quickly and relinquishes
processor
• Batch processes
– Contains work to be performed with no user interaction
• Interactive processes
– Requires frequent user input
Scheduling Algorithms

• Scheduling algorithms
– Decide when and for how long each process runs
– Make choices about
• Preemptibility
• Priority
• Running time
• Run-time-to-completion
• fairness
First-In-First-Out (FIFO) Scheduling

• FIFO scheduling
– Simplest scheme
– Processes dispatched according to arrival time
– Nonpreemptible
– Rarely used as primary scheduling algorithm
First-In-First-Out (FIFO) Scheduling
Figure 2 First-in-first-out scheduling.
 Round-Robin (RR) Scheduling

• Round-robin scheduling
– Based on FIFO
– Processes run only for a limited amount of time called a time slice or
quantum
– Preemptible
– Requires the system to maintain several processes in memory to
minimize overhead
– Often used as part of more complex algorithms
Round-Robin (RR) Scheduling
3 Round-robin scheduling.
Round-Robin (RR) Scheduling
• Selfish round-robin scheduling
– Increases priority as process ages
– Two queues
• Active
• Holding
– Favors older processes to avoids unreasonable delays
Shortest-Process-First (SPF) Scheduling
• Scheduler selects process with smallest time to finish
– Lower average wait time than FIFO
• Reduces the number of waiting processes
– Potentially large variance in wait times
– Nonpreemptive
• Results in slow response times to arriving interactive requests
– Relies on estimates of time-to-completion
• Can be inaccurate or falsified
– Unsuitable for use in modern interactive systems
Shortest-Remaining-Time (SRT) Scheduling

• SRT scheduling
– Preemptive version of SPF
– Shorter arriving processes preempt a running process
– Very large variance of response times: long processes wait
even longer than under SPF
– Not always optimal
• Short incoming process can preempt a running process that is near
completion
• Context-switching overhead can become significant
Multilevel Feedback Queues
• Different processes have different needs
– Short I/O-bound interactive processes should generally run
before processor-bound batch processes
– Behavior patterns not immediately obvious to the scheduler
• Multilevel feedback queues
– Arriving processes enter the highest-level queue and execute
with higher priority than processes in lower queues
– Long processes repeatedly descend into lower levels
• Gives short processes and I/O-bound processes higher priority
• Long processes will run when short and I/O-bound processes
terminate
– Processes in each queue are serviced using round-robin
• Process entering a higher-level queue preempt running processes
Multilevel Feedback Queues
• Algorithm must respond to changes in environment
– Move processes to different queues as they alternate
between interactive and batch behavior
• Example of an adaptive mechanism
– Adaptive mechanisms incur overhead that often is offset
by increased sensitivity to process behavior
Multilevel Feedback Queues
Figure 4 Multilevel feedback queues.
Fair Share Scheduling
• FSS controls users’ access to system resources
– Some user groups more important than others
– Ensures that less important groups cannot monopolize
resources
– Unused resources distributed according to the proportion
of resources each group has been allocated
– Groups not meeting resource-utilization goals get higher
priority
Deadline Scheduling
• Deadline scheduling
– Process must complete by specific time
– Used when results would be useless if not delivered on-
time
– Difficult to implement
• Must plan resource requirements in advance
• Incurs significant overhead
• Service provided to other processes can degrade
Real-Time Scheduling
• Real-time scheduling
– Related to deadline scheduling
– Processes have timing constraints
– Also encompasses tasks that execute periodically
• Two categories
– Soft real-time scheduling
• Does not guarantee that timing constraints will be met
• For example, multimedia playback
– Hard real-time scheduling
• Timing constraints will always be met
• Failure to meet deadline might have catastrophic results
• For example, air traffic control
Real-Time Scheduling
• Static real-time scheduling
– Does not adjust priorities over time
– Low overhead
– Suitable for systems where conditions rarely change
• Hard real-time schedulers
– Rate-monotonic (RM) scheduling
• Process priority increases monotonically with the frequency with which it must execute
– Deadline RM scheduling
• Useful for a process that has a deadline that is not equal to its period
Real-Time Scheduling
• Dynamic real-time scheduling
– Adjusts priorities in response to changing conditions
– Can incur significant overhead, but must ensure that the overhead does
not result in increased missed deadlines
– Priorities are usually based on processes’ deadlines
• Earliest-deadline-first (EDF)
– Preemptive, always dispatch the process with the earliest deadline
• Minimum-laxity-first
– Similar to EDF, but bases priority on laxity, which is based on the process’s deadline and
its remaining run-time-to-completion
 Operations on Processes

Since processes can be created, operate concurrently, and terminated dynamically, certain mechanisms
should be available to perform these operations on processes.

Process Creation

1. During the lifetime of the process, it may create new processes using the create-process system call.

2. The creating process is the Parent Process and the created process is the Child Process.

3. The created child processes in turn may create other child processes, creating a hierarchical tree
structure of processes.

4. Most operating systems such as UNIX and the Windows family uniquely identify processes according to
a assigned unique process identifier (PID).

5. The PID is usually an integer.

 Synchronizing Communication

1. In message-passing systems, there can be different types or levels of synchronization.

1. Accordingly, message-passing can be either blocking (synchronous) or nonblocking

(asynchronous).

• Blocking Send : The sending process is blocked until the message is

received by the receiving process or by the mailbox.
• Nonblocking Send : The sending process sends the message and resumes
operation.
• Blocking Receive : The receiver blocks until a message is available.
• Nonblocking Receive : The receiver retrieves either a valid message or a
null.

3. Different combinations of send() and receive () are possible.

Synchronizing Communication

4. When both send() and receive() are blocking, we have a establish a direct
meeting between the sender and the receiver.
5. In this situation, the solution to the producer-consumer problem becomes
straightforward.

6. The producer merely executes the blocking send() call and waits until the
message is delivered to either the receiver or the mailbox.

7. Likewise, when the consumer invokes receive (), it blocks until a message is
available.
Ashen Gunawardena
MSc in Digital Marketing(Reading), MSc in Network and Information Security, BEng
(Hons) Computer Networking, Certificate in Cyber Security, HDCS, CCSK, CCNP, CCNA,
PCAP, CAP, CPP, NDG Linux Essentials.

Email :
ashen.g@saegis.onmicrosoft.com

Linkedin :
https://lk.linkedin.com/in/ashen
gunawardena

0768530641