代写 algorithm Scheme compiler operating system security Operating Systems Lecture 7a

Operating Systems Lecture 7a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018

Previously 1 Deadlocks
 Methods for handling deadlocks  Deadlock prevention
 Deadlock avoidance
 Deadlock detection and recovery

Today 2 Memory management
 Addressing and address spaces  Partitioning and segmentation

Recap: Process abstraction 3 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

Recap: Process abstraction 4 Multiprogramming
 Multiple processes run concurrently
 Each works under the assumption that it has sole access to the CPU and unbounded memory resources

Recap: Memory Hierarchy 5

Recap: Virtual Memory Abstraction 6
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

Memory addressing 7 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
E.g. addresses assigned when compiling code:
if(x!=0) 0x04: MOV 0x90, AX x++; 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
27
Memory management
 Memory addressing
 Absolute vs relative addresses  Physical vs logical addresses  Address translation
 Memory allocation concepts  Partitioning
 Segmentation
 Paging (next lecture)
 Aspects to consider  Relocation
 Dynamic linking  Fragmentation  Swapping

Read 28  Tanenbaum & Bos., Modern Operating Systems
 Chapter 3
 Silberschatz et al., Operating System Concepts  Chapter 8

Next Lecture
29
 Introduction
 Operating System Architectures  Processes
 Threads – Programming
 Process Scheduling – Evaluation  Process Synchronisation
 Deadlocks
 Memory Management (continued)  File Systems
 Input / Output
 Security and Virtualisation