Transcript UNIT III

Example of a Resource Allocation Graph
CS1252-OPERATING SYSTEM UNIT
III
1
Resource Allocation Graph With A Deadlock
CS1252-OPERATING SYSTEM UNIT
III
2
Resource Allocation Graph With A Cycle But No Deadlock
CS1252-OPERATING SYSTEM UNIT
III
3
Safe, Unsafe , Deadlock State
CS1252-OPERATING SYSTEM UNIT
III
4
Resource-Allocation Graph For Deadlock Avoidance
CS1252-OPERATING SYSTEM UNIT
III
5
Unsafe State In Resource-Allocation Graph
CS1252-OPERATING SYSTEM UNIT
III
6
Resource-Allocation Graph and Wait-for Graph
Resource-Allocation Graph
Corresponding wait-for graph
CS1252-OPERATING SYSTEM UNIT
III
7
Overlays for a Two-Pass Assembler
CS1252-OPERATING SYSTEM UNIT
III
8
Schematic View of Swapping
CS1252-OPERATING SYSTEM UNIT
III
9
Hardware Support for Relocation and Limit Registers
CS1252-OPERATING SYSTEM UNIT
III
10
Contiguous Allocation (Cont.)
• Multiple-partition allocation
– Hole – block of available memory; holes of various size are scattered
throughout memory.
– When a process arrives, it is allocated memory from a hole large
enough to accommodate it.
– Operating system maintains information about:
a) allocated partitions b) free partitions (hole)
OS
OS
OS
OS
process 5
process 5
process 5
process 5
process 9
process 9
process 8
process 2
process 10
process 2
process 2
CS1252-OPERATING SYSTEM UNIT
III
process 2
11
Dynamic Storage-Allocation Problem
How to satisfy a request of size n from a list of free holes.
• First-fit: Allocate the first hole that is big enough.
• Best-fit: Allocate the smallest hole that is big enough; must
search entire list, unless ordered by size. Produces the
smallest leftover hole.
• Worst-fit: Allocate the largest hole; must also search entire
list. Produces the largest leftover hole.
First-fit and best-fit better than worst-fit in terms of
speed and storage utilization.
CS1252-OPERATING SYSTEM UNIT
III
12
Fragmentation
• External Fragmentation – total memory space exists to satisfy a request,
but it is not contiguous.
• Internal Fragmentation – allocated memory may be slightly larger than
requested memory; this size difference is memory internal to a partition,
but not being used.
• Reduce external fragmentation by compaction
– Shuffle memory contents to place all free memory together in one
large block.
– Compaction is possible only if relocation is dynamic, and is done at
execution time.
– I/O problem
• Latch job in memory while it is involved in I/O.
• Do I/O only into OS buffers.
CS1252-OPERATING SYSTEM UNIT
III
13
Paging
• Logical address space of a process can be noncontiguous;
process is allocated physical memory whenever the latter is
available.
• Divide physical memory into fixed-sized blocks called frames
(size is power of 2, between 512 bytes and 8192 bytes).
• Divide logical memory into blocks of same size called pages.
• Keep track of all free frames.
• To run a program of size n pages, need to find n free frames
and load program.
• Set up a page table to translate logical to physical addresses.
• Internal fragmentation.
CS1252-OPERATING SYSTEM UNIT
III
14
Address Translation Scheme
• Address generated by CPU is divided into:
– Page number (p) – used as an index into a page
table which contains base address of each page in
physical memory.
– Page offset (d) – combined with base address to
define the physical memory address that is sent to
the memory unit.
CS1252-OPERATING SYSTEM UNIT
III
15
Address Translation Architecture
CS1252-OPERATING SYSTEM UNIT
III
16
Paging Example
CS1252-OPERATING SYSTEM UNIT
III
17
Paging Example
CS1252-OPERATING SYSTEM UNIT
III
18
Free Frames
Before allocation
CS1252-OPERATING SYSTEM UNIT
III
After allocation
19
Paging Hardware With TLB
CS1252-OPERATING SYSTEM UNIT
III
20
Valid (v) or Invalid (i) Bit In A Page
Table
CS1252-OPERATING SYSTEM UNIT
III
21
Two-Level Page-Table Scheme
CS1252-OPERATING SYSTEM UNIT
III
22
Address-Translation Scheme
• Address-translation scheme for a two-level 32-bit
paging architecture
CS1252-OPERATING SYSTEM UNIT
III
23
Hashed Page Table
CS1252-OPERATING SYSTEM UNIT
III
24
Inverted Page Table Architecture
CS1252-OPERATING SYSTEM UNIT
III
25
User’s View of a Program
CS1252-OPERATING SYSTEM UNIT
III
26
Logical View of Segmentation
1
4
1
2
3
2
4
3
user space
physical memory space
CS1252-OPERATING SYSTEM UNIT
III
27
Segmentation Hardware
CS1252-OPERATING SYSTEM UNIT
III
28
Example of Segmentation
CS1252-OPERATING SYSTEM UNIT
III
29
Sharing of Segments
CS1252-OPERATING SYSTEM UNIT
III
30
MULTICS Address Translation
Scheme
CS1252-OPERATING SYSTEM UNIT
III
31
Intel 30386 Address Translation
CS1252-OPERATING SYSTEM UNIT
III
32