Chapter 5

Memory and Process

Management
 MEMORY MANAGEMENT

 Memory management is concerned with managing:

– The computer’s available pool of memory
– Allocating space to application routines and making
sure that they do not interfere with each other
MEMORY MANAGER FUNCTIONS

 To keep track of which parts of memory are in use

and which parts are not in use
 Coordinates how memory hierarchy is used
MEMORY HIERARCHY

 Main memory
 Should store currently needed program instructions and
data only
 Secondary storage
 Stores data and programs that are not actively needed
 Cache memory
 Extremely high speed
 Usually located on processor itself
 Most-commonly-used data copied to cache for faster access
 Small amount of cache still effective for boosting
performance
MEMORY HIERARCHY

FIGURE 1: Hierarchical memory organization.

MEMORY MANAGEMENT STRATEGIES

 Strategies divided into several categories

 Fetch strategies
• Decides which piece of data to load next

 Placement strategies
• Decides where in main memory to place incoming
data
 Replacement strategies
 Decides which data to remove from main memory
to make more
space
RESIDENT ROUTINE VS
TRANSIENT ROUTINE

RESIDENT ROUTINE TRANSIENT ROUTINE

Refers to routine that stays in Refers to a routine that is loaded
memory; the part of program as needed
must remain in memory all the
times
Instructions and data that Stored on disk and read into
remains in memory can be memory only when needed
accessed instantly
Example: Windows operating Example: database programs,
system web browser, drawing
application, paint application, 7
image editing programs and etc
MEMORY SWAPPING TECHNIQUE

 Not necessary to keep inactive processes in memory

 Swapping
• Only put currently running process in main
memory
• Others temporarily moved to secondary storage
• Maximizes available memory
• Significant overhead when switching processes
 Better yet: keep several processes in memory at
once
•Less available memory
•Much faster response times
CONTIGUOUS VS NONCONTIGUOUS
MEMORY ALLOCATION

 Ways of organizing programs in memory

 Contiguous allocation
• Program must exist as a single block of contiguous
addresses
• Sometimes it is impossible to find a large enough block
• Low overhead
 Noncontiguous allocation
• Program divided into chunks called segments
• Each segment can be placed in different part of memory
• Easier to find “holes” in which a segment will fit
10
• Increased number of processes that can exist
simultaneously
• in memory offsets the overhead incurred by this technique
MEMORY ALLOCATION

CONTIGOUS
 FIXED-PARTITION
 DYNAMIC
NON-CONTIGOUS
 PAGING
 SEGMENTATION
 FIXED-PARTITIONS
The simplest approach

 to managing memory for multiple concurrent process.

• Divides the available space into fixed- length

partitions,

• each of which holds one process.

When a partition is free,

 a process is selected from the input queue and

12 is
loaded into a free partition
Best-fit? First-fit? Worst-fit?
FIXED-PARTITIONS

 Best-fit? First-fit? Worst-fit?

FIXED-PARTITIONS

Partition can be of equal size or unequal size

Any process whose size is less than or equal to a
partition size,

 can be loaded into the partition

If all partitions are occupied,

 the OS can swap a process out of a partition

 FIXED-PARTITIONS
A process is either entirely in main memory or entirely on
backing store
A program may be too large to fit in partition. The
programmer must then design the program with overlays
 When the module needed is not present the user program
must load the module into the program’s partition,
overlaying whatever program or data are there
Main memory use inefficient. Any program, no matter how
15
small, occupies an entire position. This is called internal
fragmentation
FIXED-PARTITIONS: PLACEMENT ALGORITHM

Unequal-size partitions lessens this problem but it is still

remains.
Equal-size partitions
 If there is an available partition, a process can be
loaded into that partition
•Because all partitions are of equal size, it does not
matter which partitions is used
 If all partition are occupied by blocked processes,
choose one process to swap out to 16 make room for
the new process.
FIXED-PARTITIONS: PLACEMENT ALGORITHM

Unequal-size partitions: use

of multiple queues

 Assign each process to the

smallest partition within
which it will fit
 A queue for each partition
size

 Tries to minimize internal

fragmentation

 Problem: some queues will

be empty if no processes
within a size range is
present
FIXED-PARTITIONS:PLACEMENT ALGORITHM

• Unequal-size partitions: use

of single queue
– When its time to load a
process into main memory
the smallest available that
will hold the process is
selected

– Increases the level of

multiprogramming at the
expense of internal
fragmentation
 VIRTUAL MEMORY

 Real, or physical, memory exists on RAM chips inside

the computer
 Virtual memory, as its name suggests, doesn’t
physically exist on a memory chip
 It is an optimization technique and is implemented by
the operating system, which creates a file on the hard
drive to expand the memory, in order to give the user
the impression that he has more memory than there
rally is
 Virtual memory is implemented by various operating
systems such as Windows, Mac OS X, and Linux.
HOW VIRTUAL MEMORY WORKS

 Let’s say that an operating system needs 120 MB of memory in

order to hold all the running programs, but there’s currently
only 50 MB of available physical memory stored on the RAM
chips
 The operating system will then set up 120 MB of virtual
memory, and will use a program called the virtual memory
manager (VMM) to manage that 120 MB
 The VMM will create a file on the hard disk that is 70 MB (120 –
50) in size to account for the extra memory that’s needed
 The O.S. will now proceed to address memory as if there were
actually 120 MB of real memory stored on the RAM, even
though there’s really only 50 MB
HOW VIRTUAL MEMORY WORKS

 So, to the O.S., it now appears as if the full 120 MB

actually exists

 It is the responsibility of the VMM to deal with the

fact that there is only 50 MB of real memory.
VIRTUAL MEMORY: PAGING
 The VMM creates a file on the hard disk that holds the
extra memory that is needed by the O.S., for example 70
MB in size

 This file is called a paging file (also known as a swap file),

and plays an important role in virtual memory

 The paging file combined with the RAM accounts for all of
the memory.

 Whenever the O.S. needs a ‘block’ of memory that’s not in

the real (RAM) memory, the VMM takes a block from the
real memory that hasn’t been used recently, writes it to
the paging file, and then reads the block of memory that
the O.S. needs from the paging file.
VIRTUAL MEMORY: PAGING
 The VMM then takes the block of memory from the paging file, and
moves it into the real memory – in place of the old block.
 This process is called swapping (also known as paging), and the
blocks of memory that are swapped are called pages.

 There are two reasons why virtual memory is important

 to allow the use of programs too large to fit physically in memory
 to allow multitasking – multiple programs running at once

 Before virtual memory existed, a word processor, e-mail program,

and browser couldn’t be run at the same time unless there was
enough memory to hold all three programs at once

 This would mean that one would have to close one program in order
to run the other, but now with virtual memory, multitasking is
possible even when there is not enough memory to hold all
executing programs at once.
PAGING

 Main memory is partition into equal-fixed sized

 Each process is also divided into partition of the same
size called pages
 The process page can thus be assigned to the available
partition in main memory called frames
 Consequence: a process does not need to occupy a
contiguous portion of memory
PAGING

Now suppose that Process B is swapped out

PAGING
 When Process A and C are
blocked, the pager loads a new
Process D consisting of 5 pages
 Process D does not occupied a
contiguous portion of memory
 There is no external
fragmentation
 Internal fragmentation consist
only of the last page of each
process
PAGING

 The OS now needs to maintain (in main memory) a

page table for each process
 Each entry of a page table consist of the frame number
where the corresponding page is physically located
 The page table is indexed by the page number to
obtain the frame number
 A free frame list, available for pages, is maintained
PAGING: LOGICAL ADDRESS &
PHYSICAL ADDRESS
 Within each program, each logical address must consist of
a page number and an offset within the page
 Page number: used as an index into a page table which
contains base address of each page in physical memory
 Page offset: combined with base address to define the
physical memory address that is sent to the memory
unit

 A CPU register always holds the starting physical address

of the page table of the currently running process

 Presented with logical address (page number, page offset)

the processor access the page table to obtain the physical
address (frame number, offset)
PAGING: LOGICAL ADDRESS &
PHYSICAL ADDRESS
PAGING: LOGICAL ADDRESS &
PHYSICAL ADDRESS
PAGING
PAGING

 When we use a paging scheme, there is no external

fragmentation:

 Any free frame can be allocated to a process that

needs it

 However, there is internal fragmentation

 Example: if a page size is 2048 bytes, a process of

72766 bytes would need 35 pages plus 1086 bytes
SEGMENTATION

 Each segment is subdivided into blocks of non-equal

size called segments
 When a process gets loaded into main memory, its
different segments can be located anywhere
 Each segment is fully packed with instruction/data:
no internal fragmentation
SEGMENTATION

 There is external fragmentation; it is reduced when

using small segments

 The OS maintain a segment table for each process.

Each entry may contains:
 The starting physical address of that segment (base)
 The length of that segment (limit)
SEGMENTATION: USER VUE
OF A PROGRAM
SEGMENTATION: LOGICAL VIEW OF
SEGMENTATION
SEGMENTATION
SEGMENTATION
 MAJOR SYSTEM RESOURCE
 A resource, or system resource, is any physical or virtual component
of limited availability within a computer system.
 Every device connected to a computer system is a resource.
 Every internal system component is a resource
 System resource including:
– CPU time
– Memory
– Hard disk space
– Network throughput
– Electrical power
– External devices
– I/O operations
*Explain in your own word how system resource types function in computer system.
PROCESS STATES

 As a process executes, it changes state:

 New: the process is being created

 Running: instructions are being executed

 Waiting: the process are waiting for some event to occur

 Ready: the process is waiting to be assigned to a process

 Terminated: the process has finished execution

LIFE CYCLE
 INTERRUPTS
 An interrupt is an electronic signal.
 Hardware senses the signal, saves key control
information for the currently executing program, and
starts the operating system’s interrupt handler
routine. At that instant, the interrupt ends.
 The operating system then handles the interrupt.
 Subsequently, after the interrupt is processed, the
dispatcher starts an application program.
 Eventually, the program that was executing at the time
of the interrupt resumes processing.
Example of how interrupt work

Step 1:
Example of how interrupt work

Step 2 :
Example of how interrupt work

Step 3:
Example of how interrupt work

Step 4:
Example of how interrupt work

Step 5:
Example of how interrupt work

Step 6:
CPU Scheduling

 Types of scheduling:
 Short-term scheduling;
• which determines which of the ready processes can
have CPU resources, and for how long.
• Invoked whenever event occurs that interrupts current
process or provides an opportunity to preempt
current one in favor of another
• Events: clock interrupt, I/O interrupt, OS call, signal
CPU Scheduling

 Types of scheduling:
 Medium-term scheduling;
•determines when processes are to be suspended and
resumed
•Part of swapping function between main memory and
disk
•based on how many processes the OS wants available
at any one time
•must consider memory management if no virtual
memory (VM), so look at memory requirements of
swapped out processes
CPU Scheduling

 Types of scheduling:
 Long-term scheduling;
•determines which programs are admitted to the system
for execution and when, and which ones should be
exited.
•Determine which programs admitted to system for
processing - controls degree of multiprogramming
•Once admitted, program becomes a process, either:
– added to queue for short-term scheduler
– swapped out (to disk), so added to queue for medium-
term scheduler
 SHORT TERM

MEDIUM TERM

LONG TERM
CPU Scheduler

 Selects from among the processes in memory that are

ready to execute, and allocates the CPU to one of
them
 CPU scheduling decisions may take place when a
process:
 Switches from running to waiting state (non-
preemptive)
 Switches from running to ready state (preemptive)
 Switches from waiting to ready (preemptive)
 Terminates (nonpreemptive)
 All other scheduling is preemptive
CPU Scheduler

• Preemptive scheduling policy interrupts processing of a

job and transfers the CPU to another job.
- The process may be pre-empted by the operating
system when:
- a new process arrives (perhaps at a higher priority),
or
- an interrupt or signal occurs, or
- a (frequent) clock interrupt occurs.
CPU Scheduler

• Non-preemptive scheduling policy functions without

external interrupts.
– once a process is executing, it will continue to execute
until it
terminates, or
– it makes an I/O request which would block the process,
or
– it makes an operating system call.
 PREEMPTIVE VS NON-
PREEMPTIVE SCHEDULING
• Preemptive
– Preemptive Scheduling is when a computer process is interrupted
and the CPU's power is given over to another process with a higher
priority. This type of scheduling occurs when a process switches
from running state to a ready state or from a waiting state to a
ready state.
• Non-preemptive
– One the CPU has been allocated to a process, the process keep
the CPU until it release the CPU either by terminating or by
switching to waiting state

58
CPU Scheduling

• Types of scheduling algorithm: Basic strategies

- First In First Out (FIFO)
- Round Robin (RR)
- Shortest Job First (SJF)
- Priority

Combined strategies
- Multi-level queue
- Multi-level feedback queue
 CPU Scheduling

Turnaround time
The sum of time spent in the ready queue, execution time and I/O
time.
tat = t(process completed) – t(process submitted)
minimize, time of submission to time of completion.
Waiting time
minimize, time spent in ready queue - affected solely by scheduling
policy
Response time
The amount of time it takes to start responding to a request. This
criterion is important for interactive systems.
rt = t(first response) – t(submission of request)
minimize
First In First Out (FIFO)

• Non-preemptive. Also known as FCFS

• Handles jobs according to their arrival time;
– the earlier they arrive, the sooner they’re served.
• Simple algorithm to implement -- uses a FIFO queue.
• Good for batch systems;
– not so good for interactive ones.
• Turnaround time is unpredictable.
First In First Out (FIFO)
Process Burst time

P1 24

P2 3

P3 3

Suppose that the processes arrive in the order: P1, P2, P3.
The Gantt Chart for the schedule is:
P1 P2 P3

0 24 27 30

Waiting time for P1=0; P2=24; P3=27

Average waiting time = (0+24+27)/3 =17s
Round Robin (RR)

• FCFS with Preemption.

• Used extensively in interactive systems because it’s
easy to implement.
• Isn’t based on job characteristics but on a predetermined slice
of time that’s given to each job.
– Ensures CPU is equally shared among all active processes
and
isn’t monopolized by any one job.
• Time slice is called a time quantum
– size crucial to system performance (100 ms to 1- 2 secs)
Round Robin (RR)

Process Burst time

P1 53

P2 17

P3 68

P4 24

Suppose that the processes arrive in the order: P1, P2, P3, P4.
Given time quantum, Q=20s. The Gantt Chart for the
schedule is:
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 37 57 77 97 117 121 134 154 162

20
Waiting time for P1=?; P2=?; P3=?; P4=?,
Average waiting time = (wt P1 + wt P2 + wt P3 + wt P4 )/4
=?s
Shortest Job First (SJF)

 Non-preemptive or Preemptive
 Handles jobs based on length of their CPU cycle time.
 Use lengths to schedule process with shortest time.
 Optimal
 gives minimum average waiting time for a given set of
processes.
 optimal only when all of jobs are available at same
time and the CPU estimates are available and
accurate.
 Doesn’t work in interactive systems because users don’t
estimate in advance CPU time required to run their jobs.
Shortest Job First (SJF) Preemptive

Process Arrival Time Burst time

P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4

Suppose that the processes arrive in the order: P1, P2, P3,
P4. The Gantt Chart for the schedule is:
0 2 4 5 7 11 16

P1 P2 P3 P2 P4 P1

Waiting time for P1=?; P2=?; P3=?; P4=?,

Average waiting time = (wt P1 + wt P2 + wt P3 + wt P4 )/4 =?s
Shortest Job First (SJF) Non-Preemptive

Process Arrival Time Burst time

P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4

Suppose that the processes arrive in the order: P1, P2, P3, P4.
The Gantt Chart for the schedule is:

0 7 8 12 16

P1 P3 P2 P4

Waiting time for P1=?; P2=?; P3=?; P4=?,

Average waiting time = (wt P1 + wt P2 + wt P3 + wt P4 )/4 =?s
Priority
• Non-preemptive.
• Gives preferential treatment to important jobs.
– Programs with highest priority are processed first.
– Aren’t interrupted until CPU cycles are completed or a
natural wait occurs.
• If 2+ jobs with equal priority are in READY queue,
processor is allocated to one that arrived first
– (first come first served within priority).
• Many different methods of assigning priorities by system
administrator or by Processor Manager.
 Priority

Process Burst time Priority Arrival Time

P1 10 3 0.0
P2 1 1 1.0
P3 2 4 2.0
P4 1 5 3.0
P5 5 2 4.0

The Gantt Chart for the schedule is:

0 10 11 16 18 19

P1 P2 P5 P3 P4

Waiting time for P1=?; P2=?; P3=?; P4=?,

Average waiting time = (wt P1 + wt P2 + wt P3 + wt P4 )/5 =?s
 Priority

Process Burst time Priority

P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

The Gantt Chart for the schedule is:

P2 P5 P1 P3 P4
0 1 6 16 18 19

Waiting time for P1=?; P2=?; P3=?; P4=?,

Average waiting time = (wt P1 + wt P2 + wt P3 + wt P4 )/4
=?s
Multi-level queue
Multi-level queue
Multi-level queue
Multi-level feedback queue (MLFQ)
THREADS

 A thread is a separate part of a process.

 A process can consist of several threads, each of which
execute separately.
 For example,

 one thread could handle screen refresh and drawing,

another thread printing, another thread the mouse and
keyboard.

 This gives good response times for complex programs.

 Windows NT is an example of an operating system which

supports multi-threading.
 MULTITHREADING
 A thread is a way for program to fork or split itself into two or
more simultaneously running tasks
 A lot of software that run on modern desktop PCs are
multithreaded
 Example:
 Web browser – one thread to display images or text, another
thread retrieves data from the network
 Word processor – one thread for displaying graphics, another
thread is for responding to keystrokes from the user, another
thread for performing spelling and grammar checking.
SINGLE VS MULTITHREADED PROCESSES
SINGLE VS MULTITHREADED PROCESSES

 Web browser example:

 Web browser accepts client request for webpage,

image, sound and so on.

 A web browser server may have several clients

concurrently accessing it

 Ifthe web browser ran as a traditional single

threaded process, it would be able to service only
one client at a time. The amount of time the client
may have to wait is enormous.
SINGLE VS MULTITHREADED PROCESSES
 Solution 1
 When a server received a request, it creates a separate
process to service that request
 Old solution before threads become popular
 Disadvantage: time consuming and resource intensive, new
process will perform the same task as the existing process.

 Solution 2:
 It is more efficient to use one process with multiple
threads
 Multithreaded web server process
 Create a separate thread that would listen for client
requests
 When a request is made, rather than creating another
process, the server would create another thread to serve
that request
 Many OS are multithreaded. E.g: Linux.
BENEFITS OF MULTITHREADING

 Responsiveness - One thread may provide rapid response while other

threads are blocked or slowed down doing intensive calculations.
 Resource sharing - By default threads share common code, data, and other
resources, which allows multiple tasks to be performed simultaneously in a
single address space.
 Economy - Creating and managing threads ( and context switches between
them ) is much faster than performing the same tasks for processes.
 Utilization of multiprocessor architectures - A single threaded process can
only run on one CPU, no matter how many may be available, whereas the
80
execution of a multi-threaded application may be split amongst available
processors.
(Note that single threaded processes can still benefit from multi-processor architectures
when there are multiple processes contending for the CPU, i.e. when the load average is
above some certain threshold.)
DEADLOCK

 Process deadlock
 A process is deadlocked when it is waiting on an
event which will never happen
 System deadlock
 A system is deadlocked when one or more processes
are
deadlock
 Under normal operation, a resource allocations
proceed like this
 Request a resource
 Use the resource
 Release the resource
NECESSARY AND SUFFICIENT
DEADLOCK CONDITIONS

 Coffman (1971) identified four (4) conditions that must

hold simultaneously for there to be a deadlock.

 Mutual exclusion condition

 Hold and wait condition

 No-preemptive condition

 Circular wait condition

NECESSARY AND SUFFICIENT
DEADLOCK CONDITIONS

 Mutual exclusion condition

•the resource involved are non-sharable
•At least one resource (thread) must be held in a non-
shareable mode, that is, only one process at a time
claims exclusive control of the resource.
•If another process requests that resource, the
requesting process must be delayed until the resource
has been released.
NECESSARY AND SUFFICIENT
DEADLOCK CONDITIONS

 Hold and wait condition

 Requesting process hold already, resources while
waiting for requested resources.
 There must exist a process that is holding a resource
already allocated to it while waiting for additional
resource that are currently being held by other
processes.
NECESSARY AND SUFFICIENT
DEADLOCK CONDITIONS

 No-preemptive condition
 Resources already allocated to a process cannot be
preempted.
 Resources cannot be removed from the processes are
used to completion or released voluntarily by the
process holding it.
 Circular wait condition
 The processes in the system form a circular list or
chain where each process in the list is waiting for a
resource held by the next process in the list.
 METHODS FOR HANDLING DEADLOCKS

 Deadlock problem can be deal in 3 ways:

i. Use a protocol to prevent or avoid deadlocks,
ensuring that the system will never enter a
deadlock state
ii. Allowthe system to enter a deadlock state, detect
it, and
 recover
[Link] the problem, pretend that deadlock never
occur in the system. This solution used by most OS
including UNIX
DEADLOCK PREVENTION

 Deadlock prevention is a set of methods for ensuring that at least one of the
necessary conditions cannot hold.
 Deadlock prevention for:
 Mutual exclusion: allow multiple processes to access computer resource.
 Hold and wait: force each process to request all required resources at once
(in one shot). It cannot proceed until all resources have been acquired.
(process either acquires all resources or stops)
 No-preemption: allow a process to be aborted or its resources reclaimed by
another or by system, when competing over a resource
 Circular wait: all resource types are numbered by an integer resource 87
id.
Processes must request resources in numerical (decreasing) order of resource
id.