Object-Oriented Programming
Operating Systems
Lecture 7a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
Deadlocks
Methods for handling deadlocks
Deadlock prevention
Deadlock avoidance
Deadlock detection and recovery
1
Today
Memory management
Addressing and address spaces
Partitioning and segmentation
2
Recap: Process abstraction
Process: program in execution
Unit of resource management
Process image: code, heap, stack, les, I/O devices, . . .
Protection
Threads: unit for scheduling
Scheduling algorithms
Communication between processes
Shared memory, . . .
Synchronisation and deadlocks
3
Recap: Process abstraction
Multiprogramming
Multiple processes run concurrently
Each works under the assumption that it has sole access to the CPU and
unbounded memory resources
4
Recap: Memory Hierarchy 5
Recap: Virtual Memory Abstraction
Virtual Memory
Memory usage regardless of actual organisation and size of physical memory
Each process has its own address space
Operating system duties:
Address translation
Memory management:
CPU can only address main memory
Data is only partially in memory (paging, swapping)
Memory protection
Process can only access its “own” memory
Provision of shared memory
6
Memory addressing
CPU-Memory Interaction
Operations and data in registers
Data and instructions loaded from memory into CPU
Memory locations are accessed through addresses
Bit-width of addresses (e.g. 32 bits) determines the size of addressable memory
7
E.g. addresses assigned when compiling code:
if(x!=0)
x++;
0x04: MOV 0x90, AX
0x06: JMZ AX, 0x0C
0x08: INC AX
0x0A: MOV AX, 0x90
0x0C: …
Memory addressing 8
Absolute addressing
Relocation problem
Memory addressing 9
Dynamic relocation
Memory addressing 10
Logical addressing
Logical address
“Offset” relative w.r.t. a base address
Limit: for protection
Address Translation
E.g. by MMU:
Address binding 11
Bind instructions and data to memory addresses
Compile time
If memory location known a priori
Must recompile code if starting address changes
Load time
Must generate relocatable code
I.e. information (relocation pointers)
allowing the loader to adapt addresses
Execution time
Binding delayed until run time
Process can be moved during its execution within memory
Requires hardware support (MMU)
Static and dynamic linking 12
Static Linking
Libraries and program code combined into the executable
No OS support required
Dynamic Linking
Linking postponed until execution time
Useful for shared libraries (.so, .dll)
OS support by dynamic linker
Dynamic linker is invoked when a library function is called
Loads the library (if not loaded yet)
Maps library into the process’ address space
Binds addresses of calls to the library functions
Memory Management Unit 13
Hardware device that at run time maps logical to physical addresses
Performs execution-time binding of addresses
Many methods possible: Simplest scheme: base address + offset
Implements memory protection
Logical and Physical Address Spaces 14
Logical address space
Addresses in the code being executed
Addresses sent from CPU to MMU
Physical address space
Addresses output by MMU
Actual addresses in main memory
Memory Allocation 15
Addressing
Relocation
Logical addresses
Protection
Memory allocation
Partitioning: contiguous memory partition for each process
Segmentation: process memory subdivided into segments
Paging: process memory subdivided into pages
Aspects to consider:
Fragmentation
Swapping
Memory Partitioning 16
Fixed-size partitions
Memory divided into fixed-size partitions
A partition is a contiguous section of memory
Process image resides in memory as one single chunk
Process is assigned a free partition
Easy to implement with base address and offset
Disadvantages
Maximum number of processes in memory is fixed.
Maximum size of process images is limited.
Internal fragmentation: There may be unused memory in the assigned partitions.
Memory Partitioning 17
Variable-size partitions
Process image resides in memory as one single chunk
Process is allocated a free partition of required size
On termination the partition is freed and combined with adjacent free partitions
OS maintains information on allocated and free partitions
Memory Partitioning 18
Dynamic Storage-Allocation Problem
Which free partition to use for a process of size n?
First-fit
Allocate the first free section that is big enough
Best-fit
Allocate the smallest free section that is big enough
Must search entire list, unless ordered by size
Produces the smallest leftover free section
Worst-fit
Allocate the largest free section
Must search entire list, unless ordered by size
Produces in the largest leftover free section (Is this useful?)
Memory Partitioning 19
External fragmentation
Total memory space exists to fit a process, but it is not contiguous
Compaction:
Move processes to eliminate small free partitions
Requires execution-time address binding
I/O problem:
Keep job in memory while waiting for I/O
Use double-buffering to decouple I/O from process image
What happens when a process is to be run but there is insufficient memory available?
Swapping 20
Memory Partitioning 21
Summary
Advantages
Enables multiprogramming
Memory protection between processes
Easy to implement
Disadvantages
Limit maximum size of process image
No memory protection within processes
Suffers from internal/external fragmentation
Memory Segmentation 22
Process image subdivided in segments
Compiler can create separate segments
E.g., for
The code
Global variables
The heap, from which memory is allocated
The stacks used by each thread
Memory Segmentation 23
Segment table
Indexed by segment number s:
Segment base
Segment limit
Access bits (read, write, execute)
Memory Segmentation 24
Segment address translation
Memory Segmentation 25
Segment protection
Offset (d) encoded in the
logical address together with
the segment number (s)
Look up allowed limit (length)
for this segment in the
segment table
Proceed addressing if
offset (d) within limit bounds,
else addressing error
Memory Segmentation 26
Summary
Advantages
Non-contiguous allocation
Segments can be swapped in/out independently
Memory protection within segments of process memory
Less fragmentation
Disadvantage
Limit maximum size of segments
Summary
Memory management
Memory addressing
Absolute vs relative addresses
Physical vs logical addresses
Address translation
Memory allocation concepts
Partitioning
Segmentation
Paging (next lecture)
27
Aspects to consider
Relocation
Dynamic linking
Fragmentation
Swapping
Read
Tanenbaum & Bos., Modern Operating Systems
Chapter 3
Silberschatz et al., Operating System Concepts
Chapter 8
28
Next Lecture
Introduction
Operating System Architectures
Processes
Threads – Programming
Process Scheduling – Evaluation
Process Synchronisation
29
Deadlocks
Memory Management (continued)
File Systems
Input / Output
Security and Virtualisation