The Evolution of Memory Management

College of Computing and Informatics

Project
Deadline: Thursday 30/11/2025 @ 23:59
Student Details:
Name: Shahad Abdullah
Name: Amira Abdullah
Name: Rimaz alshehri

[Total Mark is 14]

CRN:
ID: s220027414
ID: S200030946
ID: s230031542

Instructions:

• You must submit two separate copies (one Word file and one PDF file) using the Assignment Template on
Blackboard via the allocated folder. These files must not be in compressed format.

• It is your responsibility to check and make sure that you have uploaded both the correct files.
• Zero mark will be given if you try to bypass the SafeAssign (e.g. misspell words, remove spaces between
words, hide characters, use different character sets, convert text into image or languages other than English
or any kind of manipulation).

• Email submission will not be accepted.
• You are advised to make your work clear and well-presented. This includes filling your information on the cover
page.

• You must use this template, failing which will result in zero mark.
• You MUST show all your work, and text must not be converted into an image, unless specified otherwise by
the question.

• Late submission will result in ZERO mark.
• The work should be your own, copying from students or other resources will result in ZERO mark.
• Use Times New Roman font for all your answers.

Description and Instructions

Pg. 01

Learning
Outcome(s):
Describe the OS
mechanism for
process
management,
threads, memory,

Description and Instructions
•

This project is a research group activity. Each group has up to 4 students.

•

Each group should choose a topic from the provided topics list.

•

The chosen topic and students’ names in each group must be sent to the course
instructor by 8 October 2025.

•

Students must use reputable sources and at least 2 scientific papers in their research.

•

Total Marks = 14

storage
management, I/O,

The deliverables of the project should include A report with the following sections:

file and

✓ Abstract: summary of chosen problem. (2 Marks)

concurrency

✓ Introduction: a brief introduction about the chosen topic. These should be
demonstrated using text and diagrams. (2 Marks)

management.

✓ Background: a brief of the chosen topic (provide any terms or theories the
reader should know about). (3 Marks)
✓ Discussion: discuss the chosen topic thoroughly. ( 4 Marks)
✓ Conclusion: summarize the findings of the discussion. (2 Marks)
✓ References: The citation should follow the APA style. (1 Marks)
✓ Your paper must be 10-12 pages, including references.
Topics:
1. Discuss the evolution of memory management?
2. Investigate techniques for optimizing system performance and resource utilization.
3. Explore emerging trends in operating system design and development
4. Research review for Scheduling algorithms in Android / iOS / any other mobile
operating system.
5. Research review for Deadlock prevention and avoidance in Modern Systems?

Description and Instructions

Pg. 02

The Evolution of Memory Management
Abstract
Memory management is a fundamental component of operating systems that ensures
efficient allocation, usage, and protection of memory resources. Over time, it has
evolved from basic static allocation techniques to complex mechanisms supporting
multitasking, virtual memory, and distributed processing. This paper summarizes the
key stages in the evolution of memory management, including contiguous allocation,
partitioning, paging, segmentation, and hybrid approaches such as paged segmentation.
It also highlights how advancements like cache hierarchy, virtual memory, and NonUniform Memory Access (NUMA) have reshaped performance and scalability in
modern computing systems. The evolution demonstrates the operating system’s role in
balancing resource optimization, process isolation, and user performance expectations.
Ultimately, this paper aims to outline these evolutionary stages to emphasize their
critical role in improving efficiency and stability within modern computing
environments (Silberschatz, Galvin, & Gagne, 2020; Stallings, 2018).
Introduction
Memory is a critical hardware component responsible for temporarily storing
instructions and data needed by the processor. Memory management refers to the set of
techniques and mechanisms an operating system uses to allocate, monitor, and
optimize the use of primary memory while ensuring that each process operates within
its allocated space safely and efficiently. In other words, it determines how the
system’s memory resources are distributed among running processes and how unused
portions are reclaimed for future use.
The operating system acts as a memory manager, ensuring that programs receive
adequate memory while maintaining overall system stability and performance. Without
effective memory management, systems can face inefficiencies such as memory

Description and Instructions

Pg. 03

fragmentation, performance degradation, or even complete system crashes (Tanenbaum
& Bos, 2015). Thus, memory management plays a vital role in enabling multitasking,
process protection, and efficient utilization of both hardware and software resources.
In early computing systems, memory allocation was simple and static, where programs
were loaded directly into fixed memory addresses. As computing demands increased
and multiple programs began executing concurrently, this approach became inefficient
and restrictive. To overcome these limitations, memory management evolved through
various models—each improving memory utilization, protection, and speed. The
following sections explore how these memory management techniques evolved over
time, beginning with early single-contiguous allocation methods and advancing toward
virtual memory systems used in modern architectures.
1. Early Memory Management
The earliest computers operated in a single-tasking mode, where the entire program
was loaded into a continuous block of memory. This technique, known as single
contiguous allocation, was straightforward but lacked flexibility. If a program exceeded
the available memory, it could not be executed. Moreover, any program error could
overwrite memory space used by other programs or the operating system itself, leading
to instability (Silberschatz et al., 2020).

Pg. 04

Description and Instructions

Figure 1. Simple Early Memory Layout – Single Contiguous Allocation
2. Multiprogramming and Partitioning
The introduction of multiprogramming required dividing memory among multiple
running processes. This led to fixed and variable partitioning methods. Fixed
partitioning divided memory into pre-set blocks, which was simple but caused internal
fragmentation when program sizes were smaller than partition sizes. Variable
partitioning allowed memory to be allocated dynamically according to program size,
reducing internal fragmentation but creating external fragmentation over time. To
reduce this, compaction techniques were introduced to reorganize memory and merge
scattered free spaces (Tanenbaum & Bos, 2015).

Description and Instructions

Pg. 05

Figure 2. Partitioned Memory Layout – Fixed vs Variable Partitions
3. Paging and Segmentation
Paging revolutionized memory allocation by dividing logical and physical memory into
small, fixed-size blocks called pages and frames. This method eliminated external
fragmentation and enabled non-contiguous memory allocation, making process
management more efficient. However, paging ignored the logical structure of
programs, which segmentation addressed by dividing programs into meaningful
sections such as code, data, and stack segments. Modern operating systems combine
both approaches for improved flexibility (Stallings, 2018).

Description and Instructions

Pg. 06

Figure 3. Paging and Segmentation Mapping Illustration
4. Virtual Memory and Modern Systems
The concept of virtual memory introduced a new level of abstraction, allowing systems
to execute programs larger than the available physical memory. Inactive memory
segments are temporarily stored on disk and swapped in as needed — a process known
as demand paging. This innovation allowed for multitasking, process isolation, and
efficient utilization of hardware resources. Today’s systems integrate virtual memory
with advanced features such as cache hierarchies, multi-core memory distribution, and
NUMA architectures, which optimize performance across multiple processors and
memory modules.

Pg. 07

Description and Instructions

Figure 4. Virtual Memory and Address Translation Model

Description and Instructions

Pg. 08

Background:
Memory management represents one of the essential components of operating systems,
encompassing the mechanisms and techniques used to control and organize the main
memory (Main Memory). The main memory, or Random Access Memory (RAM), is a
critical hardware resource responsible for temporarily storing data and instructions
required by the Central Processing Unit (CPU). The primary objectives of memory
management are to ensure the efficient allocation of memory resources, maintain
process isolation so that no process can interfere with the memory space of another,
and preserve the overall stability and performance of the system. The entire evolution
of memory management has been driven by the need to efficiently support
multiprogramming and multitasking environments.

1. Basic Memory Concepts and Address Translation
To fully understand the evolution of memory management, it is crucial to be familiar
with several core concepts:
– Address Space: The address space refers to the set of logical memory addresses that a
process can generate. This logical view is distinct and separate from the physical
memory addresses used by the hardware.
– Address Binding Stages: The process of converting symbolic program addresses into
physical memory addresses evolves through three stages: compile time, load time, and
execution time. Modern, flexible memory management techniques (such as paging)
rely on execution-time binding, allowing processes to be moved or mapped
dynamically while running.

Description and Instructions

Pg. 09

– Memory Fragmentation: Fragmentation occurs when free memory becomes divided
into small, non-contiguous blocks, reducing the system’s ability to allocate memory
efficiently. It is categorized into:
– Internal Fragmentation: Occurs when a process is allocated a memory block larger
than its actual requirements.
– External Fragmentation: Occurs when free memory blocks exist but are scattered
across non-adjacent areas, preventing the allocation of a single, large continuous block.

2. Early Memory Systems and Primitive Protection
Early computer systems relied on basic models that lacked flexibility, limiting system
functionality and scalability:
– Single Contiguous Allocation: In the earliest systems, only one program executed at a
time, loaded entirely into a single, contiguous block of memory. This model strictly
prevented multitasking.
– Fixed and Variable Partitioning: With the emergence of multiprogramming,
partitioning techniques were introduced:
– Fixed Partitioning: Divided main memory into predefined partitions, leading to
internal fragmentation.
– Variable Partitioning: Memory was allocated dynamically based on process size,
which reduced internal fragmentation but resulted in accumulating external
fragmentation over time.
Early Memory Protection:
Before sophisticated virtual memory, protection was primarily enforced through
hardware registers:
– Base and Limit Registers: In contiguous memory schemes, a pair of these registers
defined a process’s legal address range. The Base Register held the smallest physical

Description and Instructions

Pg. 10

address, while the Limit Register specified the size of the range, ensuring that a process
could not access memory outside its allocated partition.

3. Advanced Techniques and the Hardware Shift
As computing requirements grew, sophisticated non-contiguous techniques were
developed to separate logical and physical memory and permanently mitigate external
fragmentation:
– Paging: Paging divides logical memory into fixed-size pages and physical memory
into equally sized frames. Processes can be stored in non-contiguous frames, entirely
eliminating external fragmentation and simplifying allocation.
– Segmentation: Segmentation divides programs into logically meaningful units
(segments) of variable size, such as code, data, and stack segments. This method aligns
more closely with how programmers structure applications but remains susceptible to
external fragmentation.
– Paged Segmentation: Modern systems often implement a hybrid model where each
segment is further divided into pages, combining the logical organization of
segmentation with the efficient allocation of paging.

4. Virtual Memory Evolution and Modern Systems
The introduction of Virtual Memory (VM) marked a major turning point, allowing
processes to run even when their total size exceeds the available physical memory:
– Demand Paging: Memory pages are loaded into RAM only when they are actively
needed, reducing initial loading time and optimizing memory usage.
– Swapping: This is the underlying mechanism used by VM to temporarily transfer
entire processes or inactive pages out of main memory onto a backing store (disk) and
bring them back when needed, a crucial step for managing memory overcommitment.

Description and Instructions

Pg. 11

– Page Replacement Algorithms: Algorithms such as Least Recently Used (LRU) and
First-In, First-Out (FIFO) determine which pages should be removed from physical
memory when space is required for new pages.
– Memory Management Unit (MMU) and TLB: The implementation of VM is
fundamentally supported by a hardware component called the MMU. The MMU
performs the dynamic translation of logical addresses to physical addresses at runtime.
To accelerate this critical operation, a high-speed cache known as the Translation
Look-Aside Buffer (TLB) stores recent page-to-frame translations, drastically reducing
the Effective Access Time (EAT) of memory.
– Modern Memory Architectures: Contemporary systems integrate VM with advanced
hardware features for performance and scalability:
– Cache Memory Hierarchy: Multi-level caches (L1, L2, L3) reduce access time by
storing frequently used data closer to the CPU.
– Non-Uniform Memory Access (NUMA): Used in multiprocessor systems where each
processor has local memory, enabling faster access to local data compared to memory
associated with other processors.
– Memory Mapping: Modern OSs like Linux and Windows implement advanced
mapping techniques to efficiently manage the virtual address space, optimize file
access, and control memory allocation.

Pg. 12

Discussion – Evolution of Memory Management

Discussion – Evolution of Memory
Management
The evolution of memory management mirrors the rapid growth of computer systems
from simple, single-task environments to complex, multi-layered, and virtualized
platforms. Each stage of development responded to performance needs, program
complexity, and hardware constraints. In the earliest systems, memory management
was extremely simple due to the limitations of hardware and the absence of
multitasking. Programs were loaded into a single contiguous memory block, allowing
straightforward execution but preventing more than one process from running at a time.
This model lacked protection and frequently caused system crashes when a program
accessed memory outside its boundaries (Silberschatz, Galvin, & Gagne, 2020).
As computing demands increased, the need for running multiple programs
simultaneously led to the development of multiprogramming and more efficient
allocation strategies. This shift introduced fixed and variable partitioning techniques,
which allowed memory to be divided among several processes. Fixed partitioning was
easier to implement but caused internal fragmentation, whereas variable partitioning
improved space utilization but suffered from external fragmentation, eventually
requiring compaction to reorganize scattered free memory. These improvements laid
the foundation for more sophisticated memory handling and demonstrated the growing
role of the operating system in resource optimization (Tanenbaum & Bos, 2015).
To overcome the limitations of partitioning, operating systems introduced paging, a
technique that eliminated external fragmentation by dividing memory into equal-sized
pages and frames. Paging supported non-contiguous allocation, making better use of
physical memory and simplifying management. However, paging ignored the logical
structure of programs, which prompted the development of segmentation.
Segmentation divided programs into meaningful parts such as code, data, and stack,
aligning with the programmer’s logical view. Despite its logical advantages,
segmentation reintroduced external fragmentation, leading modern systems to adopt
paged segmentation, which merges the flexibility of paging with the structural clarity
of segmentation (Stallings, 2018).

Pg. 13

Discussion – Evolution of Memory Management
A major turning point in memory management came with the emergence of virtual
memory, which allowed programs larger than the available physical memory to execute
by storing inactive portions on secondary storage. Demand paging became a crucial
technique, loading only necessary pages into memory while keeping the rest on disk.
This innovation enabled true multitasking, increased system responsiveness, and
improved user experience. It also introduced new challenges, particularly the need for
efficient page replacement algorithms such as FIFO, LRU, and Clock, which determine
which pages should be evicted during memory shortages (Silberschatz et al., 2020).
As hardware evolved, memory management incorporated new components to support
performance demands. One of the most important advancements was the Memory
Management Unit (MMU), which translated logical addresses to physical addresses
and enforced memory protection. The MMU’s performance was enhanced by the
Translation Lookaside Buffer (TLB), a high-speed cache that stored recent address
translations. The introduction of TLBs significantly reduced the effective access time
of memory and improved the efficiency of virtual memory systems, especially in
multitasking and multi-process environments (Tanenbaum & Bos, 2015).
The increasing speed of processors compared to memory led to another innovation: the
cache hierarchy. Modern systems rely on multiple levels of cache (L1, L2, and L3) to
reduce access latency and align memory speed with CPU requirements. Cache
management became tightly integrated with memory management policies, especially
in operating systems that optimize for high-performance computing, multimedia
processing, and real-time tasks. These developments reflect the rising importance of
integrating hardware and software strategies to achieve efficient memory handling
(Stallings, 2018).
Further advancements occurred with the rise of multi-core and large-scale systems.
Non-Uniform Memory Access (NUMA) architectures were introduced to reduce
latency by giving each processor local memory regions that could be accessed faster
than remote regions. Operating systems adapted by implementing NUMA-aware
scheduling and memory allocation techniques to ensure workload balance and
minimize memory contention. These changes significantly improved the scalability and
efficiency of modern servers and high-performance computing platforms (Silberschatz
et al., 2020).

In recent years, the rise of virtualization, cloud computing, and containerization created
new demands for flexible and secure memory management. Operating systems now

Pg. 14

Discussion – Evolution of Memory Management
manage memory not only for applications but for entire virtual machines. Techniques
such as memory ballooning, copy-on-write, and memory overcommitment became
essential for cloud providers, enabling them to host multiple users efficiently without
sacrificing performance or security. These advanced memory strategies underscore the
increasing complexity of modern computing environments (Tanenbaum & Bos, 2015).
Finally, contemporary operating systems continue to evolve memory management
through intelligent policies, predictive algorithms, and deep integration with hardware.
Machine-learning-based caching, adaptive page replacement, and hybrid memory
models involving SSDs and persistent memory technologies are becoming more
common. These innovations reflect a shift toward adaptive and hardware-aware
memory management techniques that accommodate modern workloads such as AI, big
data, and edge computing (Stallings, 2018).
Overall, the evolution of memory management demonstrates continuous progress
toward improved efficiency, protection, and performance. From simple contiguous
allocation to fully virtualized and predictive systems, each stage contributed to the
robust and flexible memory management frameworks present in today’s operating
systems (Silberschatz et al., 2020).

Module 1
Chapter 1: Introduction
Chapter 2: Operating-System Services

WHAT IS AN OPERATING SYSTEM?
An operating system is ……
Is it only for Computers? How about these machines?
Car
Airplane
Printer
Washing Machine
Toaster
Compiler
Etc.

WHAT OPERATING SYSTEM DO
• A program that acts as an intermediary between a user of a
computer and the computer hardware
• Operating system goals:
• Execute user programs and make solving user problems easier
• By providing abstraction to application programs.
• Make the computer system convenient to use
• By turning ugly hardware into beautiful abstractions.
• Use the computer hardware in an efficient manner
• By orderly controlled allocation of resources.

COMPUTER SYSTEM STRUCTURE
Users
(People, Machines, and other computers)

OPERATING SYSTEM DEFINITION
• No universally accepted definition
• “Everything a vendor ships when you order an operating system” is a good
approximation but varies wildly
• “The one program running at all times on the computer” is the kernel, part of the
operating system. Everything else is either
• A system program (ships with the operating system, but not part of the kernel) , or
• An application program, all programs not associated with the operating system
• Today’s OSes for general purpose and mobile computing also include middleware –
a set of software frameworks that provide addition services to application
developers such as databases, multimedia, graphics

COMPUTER SYSTEM ORGANIZATION
• Computer-system consists of one or more CPUs, device controllers
connect through common bus providing access to shared memory
• Operating systems (OS) have a device driver for each device controller
which facilitate communication between OS and the device.

I/O OPERATION OVERVIEW
• A program request an I/O operation
• Device driver load appropriate registers in device controller
• The device controller, in turn, examines the contents of these registers to determine what
action to take (such as “read a character from the keyboard”).
• The controller starts the transfer of data from the device to its local buffer. Once the
transfer of data is complete, the device controller informs the device driver that it has
finished its operation.
• The device driver then gives control to other parts of the operating system, possibly
returning the data or a pointer to the data if the operation was a read. For other
operations, the device driver returns status information such as “write completed
successfully” or “device busy”.
• But how does the controller inform the device driver that it has finished its operation? This
is accomplished via an interrupt.

INTERRUPT
• Hardware may trigger an interrupt at any time by sending a signal to the CPU,
usually by way of the system bus.
• Interrupts are used for many other purposes as well and are a key part of how
operating systems and hardware interact.
• Interrupts are an important part of a computer architecture.
• Each computer design has its own interrupt mechanism, but several functions
are common.

INTERRUPT

INTERRUPT HANDLING
• The operating system preserves the state of the CPU by storing the
registers and the program counter
• Determines which type of interrupt has occurred:
• Separate segments of code determine what action should be taken for
each type of interrupt

COMPUTER SYSTEM OPERATION
• I/O devices and the CPU can execute concurrently
• Each device controller is in charge of a particular device type
• Each device controller has a local buffer
• Each device controller type has an operating system device driver to
manage it
• CPU moves data from/to main memory to/from local buffers
• I/O is from the device to local buffer of controller
• Device controller informs CPU that it has finished its operation by
causing an interrupt

COMMON FUNCTIONS OF INTERRUPTS
• Interrupt transfers control to the interrupt service routine generally,
through the interrupt vector, which contains the addresses of all the
service routines
• Interrupt architecture must save the address of the interrupted
instruction
• A trap or exception is a software-generated interrupt caused either by
an error or a user request
• An operating system is interrupt driven

I/O STRUCTURE
• After I/O starts, control returns to user program only upon I/O completion
• Wait instruction idles the CPU until the next interrupt
• Wait loop (contention for memory access)
• At most one I/O request is outstanding at a time, no simultaneous I/O processing
• After I/O starts, control returns to user program without waiting for I/O completion
• System call – request to the OS to allow user to wait for I/O completion
• Device-status table contains entry for each I/O device indicating its type, address,
and state
• OS indexes into I/O device table to determine device status and to modify table
entry to include interrupt

COMPUTER STARTUP
• Bootstrap program is loaded at power-up or reboot
• Typically stored in ROM or EPROM, generally known as firmware
• Initializes all aspects of system
• Loads operating system kernel and starts execution

STORAGE STRUCTURE
• Main memory – only large storage media that the CPU can access
directly
• Random access
• Typically volatile
• Typically random-access memory in the form of Dynamic Randomaccess Memory (DRAM)
• Secondary storage – extension of main memory that provides large
nonvolatile storage capacity

STORAGE STRUCTURE (CONT.)
• Hard Disk Drives (HDD) – rigid metal or glass platters covered with
magnetic recording material
• Disk surface is logically divided into tracks, which are subdivided into
sectors
• The disk controller determines the logical interaction between the
device and the computer
• Non-volatile memory (NVM) devices– faster than hard disks, nonvolatile
• Various technologies
• Becoming more popular as capacity and performance increases, price
drops

STORAGE HIERARCHY
• Storage systems organized in hierarchy
• Speed
• Cost
• Volatility
• Caching – copying information into faster storage system; main memory
can be viewed as a cache for secondary storage
• Device Driver for each device controller to manage I/O
• Provides uniform interface between controller and kernel

STORAGE-DEVICE HIERARCHY

HOW A MODERN COMPUTER WORKS

A von Neumann architecture

DIRECT MEMORY ACCESS STRUCTURE
• Used for high-speed I/O devices able to transmit information at close
to memory speeds
• Device controller transfers blocks of data from buffer storage directly
to main memory without CPU intervention
• Only one interrupt is generated per block, rather than the one
interrupt per byte

OPERATING-SYSTEM OPERATIONS
• Bootstrap program – simple code to initialize the system, load the kernel
• Kernel loads
• Starts system daemons (services provided outside of the kernel)
• Kernel interrupt driven (hardware and software)
• Hardware interrupt by one of the devices
• Software interrupt (exception or trap):
• Software error (e.g., division by zero)
• Request for operating system service – system call
• Other process problems include infinite loop, processes modifying each other or
the operating system

MULTIPROGRAMMING (BATCH SYSTEM)
• Single user cannot always keep CPU and I/O devices busy
• Multiprogramming organizes jobs (code and data) so CPU always has
one to execute
• A subset of total jobs in system is kept in memory
• One job selected and run via job scheduling
• When job has to wait (for I/O for example), OS switches to another
job

MULTITASKING (TIMESHARING)
• A logical extension of Batch systems– the CPU switches jobs so
frequently that users can interact with each job while it is running,
creating interactive computing
• Response time should be 1 hardware threads.
• If one thread has a memory stall, switch to another thread!

MULTITHREADED MULTICORE SYSTEM
• Chip-multithreading (CMT) assigns each core
multiple hardware threads. (Intel refers to this as
hyperthreading.)
• On a quad-core system with 2 hardware threads
per core, the operating system sees 8 logical
processors.

MULTITHREADED MULTICORE SYSTEM
Two levels of scheduling:
 The operating system deciding which
software thread to run on a logical
CPU
 How each core decides which
hardware thread to run on the
physical core.

MULTIPLE-PROCESSOR SCHEDULING – LOAD BALANCING
If SMP, need to keep all CPUs loaded for efficiency
• Load balancing attempts to keep workload evenly distributed
• Push migration – periodic task checks load on each processor, and if
found pushes task from overloaded CPU to other CPUs
• Pull migration – idle processors pulls waiting task from busy processor

MULTIPLE-PROCESSOR SCHEDULING – PROCESSOR
AFFINITY
• When a thread has been running on one processor, the cache contents of that
processor stores the memory accesses by that thread.
We refer to this as a thread having affinity for a processor (i.e., “processor affinity”)
• Load balancing may affect processor affinity as a thread may be moved from one
processor to another to balance loads, yet that thread loses the contents of what
it had in the cache of the processor it was moved off.
• Soft affinity – the operating system attempts to keep a thread running on the
same processor, but no guarantees.
• Hard affinity – allows a process to specify a set of processors it may run on.

NUMA AND CPU SCHEDULING
If the operating system is NUMA-aware, it will assign memory closes to the CPU
the thread is running on.

Operating Systems
Module 4

Chapter 6: Synchronization Tools

INTRODUCTION
• Processes can execute concurrently
• May be interrupted at any time, partially completing execution
• Concurrent access to shared data may result in data inconsistency
• Maintaining data consistency requires mechanisms to ensure the
orderly execution of cooperating processes
• We illustrated in chapter 4 the problem when we considered the
Bounded Buffer problem with use of a counter that is updated
concurrently by the producer and consumer,. Which lead to race
condition.

CRITICAL SECTION PROBLEM
• Consider system of n processes {p0, p1, … pn-1}
• Each process has critical section segment of code
• Process may be changing common variables, updating table, writing
file, etc.
• When one process in critical section, no other may be in its critical
section
• Critical section problem is to design protocol to solve this
• Each process must ask permission to enter critical section in entry
section, may follow critical section with exit section, then remainder
section

CRITICAL SECTION
• General structure of process Pi

REQUIREMENT FOR CRITICAL SECTION
1. Mutual Exclusion – If process Pi is executing in its critical section, then no other
processes can be executing in their critical sections
2. Progress – If no process is executing in its critical section and there exist some
processes that wish to enter their critical section, then the selection of the
process that will enter the critical section next cannot be postponed
indefinitely
3. Bounded Waiting – A bound must exist on the number of times that other
processes are allowed to enter their critical sections after a process has made
a request to enter its critical section and before that request is granted
4. Assume that each process executes at a nonzero speed
5. No assumption concerning relative speed of the n processes

RACE CONDITION
• Processes P0 and P1 are creating child processes using the fork() system call
• Race condition on kernel variable next_available_pid which represents the next
available process identifier (pid)

• Unless there is a mechanism to prevent P0 and P1 from accessing the variable
next_available_pid the same pid could be assigned to two different processes!

PETERSON’S SOLUTION
• Two process solution
• Assume that the load and store machine-language instructions are
atomic; that is, cannot be interrupted
• The two processes share two variables:
• int turn;
• boolean flag[2]
• The variable turn indicates whose turn it is to enter the critical section
• The flag array is used to indicate if a process is ready to enter the critical
section.
• flag[i] = true implies that process Pi is ready!

ALGORITHM FOR PROCESS
while (true){
flag[i] = true;
turn = j;
while (flag[j] && turn = = j)
;

/* critical section */
flag[i] = false;
/* remainder section */
}

CORRECTNESS OF PETERSON’S SOLUTION
Provable that the three CS requirement are met:
1. Mutual exclusion is preserved
Pi enters CS only if:
either flag[j] = false or turn = i
2. Progress requirement is satisfied
3. Bounded-waiting requirement is met

PETERSON’S SOLUTION
• Although useful for demonstrating an algorithm, Peterson’s Solution
is not guaranteed to work on modern architectures.
• To improve performance, processors and/or compilers may reorder
operations that have no dependencies
• Understanding why it will not work is useful for better
understanding race conditions.
• For single-threaded this is ok as the result will always be the same.
• For multithreaded the reordering may produce inconsistent or
unexpected results!

SYNCHRONIZATION HARDWARE
• Many systems provide hardware support for implementing the
critical section code.
• Uniprocessors – could disable interrupts
• Currently running code would execute without preemption
• Generally too inefficient on multiprocessor systems
• Operating systems using this not broadly scalable
• We will look at three forms of hardware support:
1. Hardware instructions
2. Atomic variables

HARDWARE INSTRUCTIONS
• Special hardware instructions that allow us to either test-andmodify the content of a word, or to swap the contents of two words
atomically (uninterruptedly.)
• Test-and-Set instruction
• Compare-and-Swap instruction

The test_and_set Instruction
Definition
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = true;
return rv:
}
Properties
Executed atomically
Returns the original value of passed parameter
Set the new value of passed parameter to true

Solution Using test_and_set()
Shared boolean variable lock, initialized to false
Solution:

do {
while (test_and_set(&lock))
; /* do nothing */
/* critical section */
lock = false;

/* remainder section */
} while (true);
Does it solve the critical-section problem?

ATOMIC VARIABLES
• Typically, instructions such as compare-and-swap are used as
building blocks for other synchronization tools.
• One tool is an atomic variable that provides atomic (uninterruptible)
updates on basic data types such as integers and booleans.
• For example:
• Let sequence be an atomic variable
• Let increment() be operation on the atomic variable sequence
• The Command:
• increment(&sequence);
•
ensures sequence is incremented without interruption:

MUTEX LOCK
• Previous solutions are complicated and generally inaccessible to application
programmers
• OS designers build software tools to solve critical section problem
• Simplest is mutex lock
• Boolean variable indicating if lock is available or not

• Protect a critical section by
• First acquire() a lock
• Then release() the lock

• Calls to acquire() and release() must be atomic
• Usually implemented via hardware atomic instructions such as compare-and-swap.
• But this solution requires busy waiting

• This lock therefore called a spinlock

SOLUTION USING MUTEX LOCK
while (true) {
acquire lock
critical section

release lock
remainder section
}

SEMAPHORE
• Synchronization tool that provides more sophisticated ways (than Mutex locks) for processes to synchronize their
activities.
• Semaphore S – integer variable
• Can only be accessed via two indivisible (atomic) operations
• wait() and signal()
• Originally called P() and V()
• Definition of the wait() operation
• wait(S) {

•

while (S satisfies
safety criteria

EXAMPLE: P1 REQUEST (1,0,2)
Check that Request Available (that is, (1,0,2) (3,3,2) true
Allocation Need Available
ABC
ABC
ABC
P0
010
743
230
P1
302
020
P2
302
600
P3
211
011
P4
002
431
Executing safety algorithm shows that sequence satisfies safety
requirement
Can request for (3,3,0) by P4 be granted?
Can request for (0,2,0) by P0 be granted?

DEADLOCK DETECTION
• Allow system to enter deadlock state
• Detection algorithm
• Recovery scheme

SINGLE INSTANCE OF EACH RESOURCE TYPE
• Maintain wait-for graph
• Nodes are processes
• Pi Pj if Pi is waiting for Pj

• Periodically invoke an algorithm that searches for a cycle in the graph.
If there is a cycle, there exists a deadlock
• An algorithm to detect a cycle in a graph requires an order of n2 operations,
where n is the number of vertices in the graph

RESOURCE-ALLOCATION GRAPH AND WAIT-FOR GRAPH

Resource-Allocation Graph

Corresponding wait-for graph

SEVERAL INSTANCES OF A RESOURCE TYPE
Available: A vector of length m indicates the number of available resources of each
type
Allocation: An n x m matrix defines the number of resources of each type currently
allocated to each process
Request: An n x m matrix indicates the current request of each process. If Request
[i][j] = k, then process Pi is requesting k more instances of resource type Rj.

DETECTION ALGORITHM
1. Let Work and Finish be vectors of length m and n, respectively Initialize:
2. Work = Available
3. For i = 1,2, …, n, if Allocationi 0, then
Finish[i] = false; otherwise, Finish[i] = true
4. Find an index i such that both:
5. Finish[i] == false
6. Requesti Work
7. If no such i exists, go to step 4

DETECTION ALGORITHM (CONT.)
Work = Work + Allocationi
Finish[i] = true
go to step 2
If Finish[i] == false, for some i, 1 i n, then the system is in deadlock state.
Moreover, if Finish[i] == false, then Pi is deadlocked
Note: Algorithm requires an order of O(m x n2) operations to detect whether the
system is in deadlocked state

EXAMPLE OF DETECTION ALGORITHM
Five processes P0 through P4; three resource types
A (7 instances), B (2 instances), and C (6 instances)
Snapshot at time T0:
Allocation Request
Available
ABC
ABC
ABC
P0
010
000
000
P1
200
202
P2
303
000
P3
211
100
P4
002
002
Sequence will result in Finish[i] = true for all i

EXAMPLE (CONT.)
P2 requests an additional instance of type C

Request
ABC
P0

000

P1

202

P2

001

P3

100

P4

002

State of system?

Can reclaim resources held by process P0, but insufficient resources to fulfill other processes; requests
Deadlock exists, consisting of processes P1, P2, P3, and P4

DETECTION-ALGORITHM USAGE
When, and how often, to invoke depends on:
• How often a deadlock is likely to occur?
• How many processes will need to be rolled back?
• one for each disjoint cycle
If detection algorithm is invoked arbitrarily, there may be many cycles in
the resource graph and so we would not be able to tell which of the
many deadlocked processes “caused” the deadlock.

RECOVERY FROM DEADLOCK: PROCESS TERMINATION
Abort all deadlocked processes
Abort one process at a time until the deadlock cycle is eliminated
In which order should we choose to abort?
• Priority of the process
• How long process has computed, and how much longer to
completion
• Resources the process has used
• Resources process needs to complete
• How many processes will need to be terminated
Is process interactive or batch?

RECOVERY FROM DEADLOCK: RESOURCE PREEMPTION
 Selecting a victim – minimize cost
 Rollback – return to some safe state, restart process for that state
 Starvation – same process may always be picked as victim, include

number of rollback in cost factor

Operating Systems
Module 7

Chapter 9: Main Memory

INTRODUCTION
• Program must be brought (from disk) into memory and placed within a process
for it to be run
• Main memory and registers are only storage CPU can access directly
Memory unit only sees a stream of:
addresses + read requests, or
address + data and write requests
 Register access is done in one CPU clock (or less)
 Main memory can take many cycles, causing a stall
 Cache sits between main memory and CPU registers
 Protection of memory required to ensure correct operation

PROTECTION
• Need to censure that a process can access only access those addresses in its
address space.
• We can provide this protection by using a pair of base and limit registers define
the logical address space of a process

HARDWARE ADDRESS PROTECTION
• CPU must check every memory access generated in user mode to be sure
it is between base and limit for that user

• the instructions to loading the base and limit registers are privileged

MEMORY BINDING
Address binding of instructions and data to memory addresses can happen at
three different stages
• Compile time: If memory location known a priori, absolute code can be
generated; must recompile code if starting location changes
• Load time: Must generate relocatable code if memory location is not known at
compile time
• Execution time: Binding delayed until run time if the process can be moved
during its execution from one memory segment to another
Need hardware support for address maps (e.g., base and limit registers)

PROCESSING OF USER PROGRAM

ADDRESS SPACE
The concept of a logical address space that is bound to a separate physical
address space is central to proper memory management
• Logical address – generated by the CPU; also referred to as virtual address
• Physical address – address seen by the memory unit
• Logical and physical addresses are the same in compile-time and load-time
address-binding schemes; logical (virtual) and physical addresses differ in
execution-time address-binding scheme
• Logical address space is the set of all logical addresses generated by a program
• Physical address space is the set of all physical addresses generated by a
program

MEMORY MANAGEMENT UNIT (MMU)
• Hardware device that at run time maps virtual to physical address

MEMORY MANAGEMENT UNIT (MMU)
Consider simple scheme. which is a generalization of the base-register scheme.
• The base register now called relocation register
• The value in the relocation register is added to every address generated by a
user process at the time it is sent to memory
• The user program deals with logical addresses; it never sees the real physical
addresses
• Execution-time binding occurs when reference is made to location in memory
• Logical address bound to physical addresses

MEMORY MANAGEMENT UNIT (MMU)

CONTIGUOUS ALLOCATION
• Main memory must support both OS and user processes
• Limited resource, must allocate efficiently
• Contiguous allocation is one early method
Main memory usually into two partitions:
• Resident operating system, usually held in low memory with
interrupt vector
• User processes then held in high memory
Each process contained in single contiguous section of memory

CONTIGUOUS ALLOCATION
 Relocation registers used to
1. protect user processes from each other
2. and from changing operating-system code and data
 Base register contains value of smallest physical address
 Limit register contains range of logical addresses – each logical
address must be less than the limit register
 MMU maps logical address dynamically
Can then allow actions such as kernel code being transient and kernel
changing size

HARDWARE SUPPORT

VARIABLE PARTITION
• Multiple…
Purchase answer to see full
attachment