Transcript Operating Systems

Operating Systems
软件学院
高海昌
[email protected]
Operating Systems
Contents
 1.
Introduction
**
 2.
Processes and Threads
*******
 3.
Deadlocks
**
 4.
Memory Management
*****
 5.
Input/Output
***
 6.
File Systems
****
 8.
Multiple Processor Systems
*
 9.
Security
**
Gao Haichang , Software School, Xidian University
2
Operating Systems
Chapter 4: Memory Management
 4.1
Basic memory management
 4.2
Swapping (交换）
 4.3
Virtual memory （虚拟内存）
 4.4
Page replacement algorithms
 4.5
Design issues for paging systems
 4.6
Implementation issues
 4.7
Segmentation （分段）
Gao Haichang , Software School, Xidian University
3
Operating Systems
Memory Management
 Ideally programmers want memory that is



large
fast
non volatile
 Memory hierarchy （层次）



small amount of fast, expensive memory – cache
some medium-speed, medium price main memory
gigabytes of slow, cheap disk storage
 Memory manager handles the memory hierarchy
Gao Haichang , Software School, Xidian University
4
Operating Systems
Basic Memory Management
 Memory Management Systems can be divided into two
classes:
 That move processes back and forth between main memory
and disk during execution (swapping and paging).
 That do not.
 Program expand to fill the memory available to hold them
Gao Haichang , Software School, Xidian University
5
Operating Systems
Monoprogramming without Swapping or Paging
Three simple ways of organizing memory
-
an operating system with one user process
(a) Formally used on mainframes and minicomputers but is really used
any more.
(b) used on some palmtop computers and embedded systems.
(c) used by early PC (MS-DOS), where the portion of the system in the
ROM is called the BIOS.
Gao Haichang , Software School, Xidian University
6
Operating Systems
Multiprogramming with Fixed Partitions
 Fixed memory partitions
 separate input
queues for each partition
 single input queue
Gao Haichang , Software School, Xidian University
7
Operating Systems
Modeling Multiprogramming
Degree of multiprogramming
CPU utilization as a function of number of processes in memory
Gao Haichang , Software School, Xidian University
8
Operating Systems
Modeling Multiprogramming
 Suppose a computer has 32MB of memory, with the OS
taking up 16MB and each user program taking up 4MB.

These sizes allow 4 programs to be in memory at once. With an 80%
average I/O wait, we have a CPU utilization of 1-0.8^4≈60%.

Adding another 16MB of memory allow 8 programs, thus raising the
CPU utilization to 83%.

Adding yet another 16MB of memory allow 12 programs, only increase
CPU utilization to 93%.

…97%

…
Gao Haichang , Software School, Xidian University
9
Operating Systems
Analysis of Multiprogramming System Performance
 (a) Arrival and work requirements of 4 jobs
 (b) CPU utilization for 1 – 4 jobs with 80% I/O wait
 (c) Sequence of events as jobs arrive and finish

note numbers show amount of CPU time jobs get in each interval
Gao Haichang , Software School, Xidian University
10
Operating Systems
Relocation and Protection
 Cannot be sure where program will be loaded in memory

address locations of variables, code routines cannot be absolute

must keep a program out of other processes’ partitions
 Use base and limit values

address locations added to base value to map to physical addr

address locations larger than limit value is an error
Gao Haichang , Software School, Xidian University
11
Operating Systems
Base and Limit register
Gao Haichang , Software School, Xidian University
12
Operating Systems
Chapter 4: Memory Management
 4.1
Basic memory management
 4.2
Swapping (交换）
 4.3
Virtual memory （虚拟内存）
 4.4
Page replacement algorithms
 4.5
Design issues for paging systems
 4.6
Implementation issues
 4.7
Segmentation （分段）
Gao Haichang , Software School, Xidian University
13
Operating Systems
Swapping
 Sometimes there is not enough main memory to hold all the
currently active processes.
 Two general approaches to memory management:

Swapping, bringing in each process in its entirety, running it for a while,
then putting it back on the disk.

Virtual memory, allow programs to run even when they are only partially
in main memory.
Gao Haichang , Software School, Xidian University
14
Operating Systems
Swapping (1)
 Memory allocation changes as:

processes come into memory

leave memory
 Shaded regions are unused memory. Addresses A must be relocated
since it is now at a different location.
 Hole, memory compaction.
 Difference between fix and the variable partitions.
Gao Haichang , Software School, Xidian University
15
Operating Systems
Swapping (2)
 Allocating space for growing data segment
 Allocating space for growing stack & data segment
Gao Haichang , Software School, Xidian University
16
Operating Systems
Memory Management with Bit Maps
 (a) Part of memory with 5 processes, 3 holes


tick marks show allocation units
shaded regions are free
 (b) Corresponding bit map (Shortcoming: searching a
bitmap for a run of a given length is a slow operation).
 (c) Same information as a list.
Gao Haichang , Software School, Xidian University
17
Operating Systems
Memory Management with Linked Lists
Four neighbor combinations for the terminating process X
Gao Haichang , Software School, Xidian University
18
Operating Systems
Memory Management with Linked Lists
 Several algorithms can be used to allocate memory for a
newly created process:





First fit.
Next fit.
Best fit.
Worst fit.
Quick fit.
Gao Haichang , Software School, Xidian University
19
Operating Systems
Lesson 2
Operating Systems
Chapter 4: Memory Management
 4.1
Basic memory management
 4.2
Swapping (交换）
 4.3
Virtual memory （虚拟内存）
 4.4
Page replacement algorithms
 4.5
Design issues for paging systems
 4.6
Implementation issues
 4.7
Segmentation （分段）
Gao Haichang , Software School, Xidian University
21
Operating Systems
Virtual Memory
 The basic idea behind virtual memory is that the combined
size of the program, data, and stack may exceed the amount
of physical memory available for it.
 The operating system keeps those parts of the program
currently in use in main memory, and the rest on the disk.
Gao Haichang , Software School, Xidian University
22
Operating Systems
Paging (1)
MMU maps the virtual addresses onto the physical memory addresses
The position and function of the MMU
Gao Haichang , Software School, Xidian University
23
Operating Systems
Paging (2)
 The virtual address space is
divided up into units called
pages.
 The corresponding units in the
physical memory are called
page frames.
MOVE REG, 0
→ MOVE REG, 8192
MOVE REG, 8192
→ MOVE REG, 24576
MOVE REG, 20500 (20480+20)
→ MOVE REG, 12308
MOVE REG, 32780
→ page fault
Gao Haichang , Software School, Xidian University
24
Operating Systems
Address Translation Architecture
Gao Haichang , Software School, Xidian University
25
Operating Systems
Page Tables (1)
Internal operation of MMU with 16 4KB pages
MOVE REG, 8196
→ MOVE REG, 24580
Gao Haichang , Software School, Xidian University
26
Operating Systems
Page Tables (2)
 Purpose of the page table is to map virtual pages onto page frame.
Two major issues must be faced:

The page table can be extremely large. (232=220*4k)

The mapping must be fast.
 The simplest design is to have a single page table consisting of an array
of fast hardware registers, with one entry for each virtual page, indexed
by virtual page number.

Advantage: it is straightforward and requires no memory references
during mapping.

Disadvantage: it is potentially expensive, and hurts performance.
 Another extreme, the page table can be entirely in main memory. All the
hardware needs then is a single register that points to the start of the
page table.

Disadvantage: requiring one or more memory references to read page
Gao Haichang
, Software School, Xidian University
table entries during the execution of each
instruction.
27
Operating Systems
Multilevel Page Tables
Second-level
page tables
 32 bit address with 2 page table fields
 Two-level page tables (232=4G, 4M, 4K)
 0x00403004: PT1=1, PT2=3, Offset=4
PT1=1 → 4M~8M
PT2=3 → 12K~16K (+4M) → 4206592~4210687
Gao Haichang , Software School, Xidian University
28
Operating Systems
Page Tables (4)
Typical page table entry
Page frame number: most important field, the goal of the page mapping;
Present /absent: if this bit is 1, the entry is valid and can be used;
Protection: tell what kinds of access are permitted, R/W/X.
Modified: useable in reclaiming a page frame. If dirty, write back to disk.
Referenced: the bit is set whenever a page is referenced. Help the OS choose a page
to evict when a page fault occurs.
Caching disabled: useful for pages that map onto device register rather than memory.
Gao Haichang , Software School, Xidian University
29
Operating Systems
Page Tables (exercise)
In the paged memory management system, the address is composed of page
number and the offset within the page. In the address structure showed in
the following figure,
.
A．page size is 1K, 64 pages at most
B．page size is 2K, 32 pages at most
C．page size is 4K, 16 pages at most
D．page size is 8K, 8 pages at most
Gao Haichang , Software School, Xidian University
30
Operating Systems
Translation Lookaside Buffers
TLB, 转换检测缓冲区
 Most programs tend to make a large number of references to a small
number of pages.
 Solution: equip computers with a small hardware device for mapping
virtual addresses to physical addresses without going through the page
table. The device called TLB.
Gao Haichang , Software School, Xidian University
31
Operating Systems
TLBs
A TLB to speed up paging
Gao Haichang , Software School, Xidian University
32
Operating Systems
Inverted Page Tables
For 64-bit computers, things change.
There is one entry per page frame in
real memory, rather than one entry
per page of virtual address space.
Comparison of a traditional page table with an inverted page table
Downside: virtual-to-physical translation becomes much harder.
Solution: TLB, Hash table.
Gao Haichang , Software School, Xidian University
33
Operating Systems
Chapter 4: Memory Management
 4.1
Basic memory management
 4.2
Swapping (交换）
 4.3
Virtual memory （虚拟内存）
 4.4
Page replacement algorithms
 4.5
Design issues for paging systems
 4.6
Implementation issues
 4.7
Segmentation （分段）
Gao Haichang , Software School, Xidian University
34
Operating Systems
Page Replacement Algorithms 页面置换算法
 Page fault forces choice


which page must be removed
make room for incoming page
 Modified page must first be saved

unmodified just overwritten
 Better not to choose an often used page

will probably need to be brought back in soon
 “page replacement” occurs in other areas of
computer design as well


Memory cache
Web server
Gao Haichang , Software School, Xidian University
35
Operating Systems
Optimal Page Replacement Algorithm
 Replace page needed at the farthest point in future
 Optimal
but unrealizable
 Estimate by …
 logging
page use on previous runs of process
 although
this is impractical
Gao Haichang , Software School, Xidian University
36
Operating Systems
Not Recently Used (NRU, 最近未使用)
 Each page has Reference bit, Modified bit

bits are set when page is referenced, modified
 Pages are classified:
0. not referenced, not modified
1. not referenced, modified
2. referenced, not modified
3. referenced, modified

NRU removes page at random from lowest numbered non empty
class
Gao Haichang , Software School, Xidian University
37
Operating Systems
FIFO Page Replacement Algorithm
 Maintain a linked list of all pages
 in
order they came into memory
 Page at beginning of list replaced
 Disadvantage
 Page
being replaced may be often used
Gao Haichang , Software School, Xidian University
38
Operating Systems
Second Chance Page Replacement Algorithm
 Operation of a second chance


pages sorted in FIFO order
Looking for an old page that has not been referenced in the previous
clock interval
Gao Haichang , Software School, Xidian University
39
Operating Systems
The Clock Page Replacement Algorithm
Gao Haichang , Software School, Xidian University
40
Operating Systems
Lesson 3
Operating Systems
Least Recently Used (LRU, 最近最少使用)
 Assume pages used recently will used again soon

throw out page that has been unused for longest time
 Must keep a linked list of pages


most recently used at front, least at rear
update this list every memory reference !!
 Alternatively keep counter in each page table entry


choose page with lowest value counter
periodically zero the counter
Gao Haichang , Software School, Xidian University
42
Operating Systems
Simulating LRU in Hardware
LRU using a matrix – pages referenced in order
0, 1, 2, 3, 2, 1, 0, 3, 2, 3
LRU: 3, 3, 3, 0, 0,Gao
0, Haichang
3, 2, 1,, Software
1
School,
Xidian University
43
Operating Systems
Simulating LRU in Software
 The aging algorithm simulates LRU in software
 Note 6 pages for 5 clock ticks, (a) – (e)
Gao Haichang , Software School, Xidian University
44
Operating Systems
The Working Set
 Demand paging (请求调页): pages are loaded only on
demand, not in advance.
 Locality of reference: during any phase of execution, the
process references only a relatively small fraction of its
pages.
 Working set: the set of pages that a process is currently
using.

What to do when a process is brought back in again?

Working set model: Many paging system keep track of each process’
working set and make sure that it is in memory before letting the process
run.
Gao Haichang , Software School, Xidian University
45
Operating Systems
The Working Set Page Replacement Algorithm (1)
k
 The working set is the set of pages used by the k most recent
memory references
 w(k,t) is the size of the working set at time, t
Gao Haichang , Software School, Xidian University
46
Operating Systems
The Working Set Page Replacement Algorithm (2)
The working set algorithm
Gao Haichang , Software School, Xidian University
47
Operating Systems
The WSClock Page Replacement Algorithm
Operation of the WSClock algorithm
Gao Haichang , Software School, Xidian University
48
Operating Systems
Review of Page Replacement Algorithms
Gao Haichang , Software School, Xidian University
49
Operating Systems
Chapter 4: Memory Management
 4.1
Basic memory management
 4.2
Swapping (交换）
 4.3
Virtual memory （虚拟内存）
 4.4
Page replacement algorithms
 4.5
Design issues for paging systems
 4.6
Implementation issues
 4.7
Segmentation （分段）
Gao Haichang , Software School, Xidian University
50
Operating Systems
Local vs Global Allocation Policies
How memory should be allocated among the competing
runnable processes?
 (a) Original configuration
 (b) Local page replacement
 (c) Global page replacement
Gao Haichang , Software School, Xidian University
51
Operating Systems
Local vs Global Allocation Policies (2)
Another approach:
 allocate page frames to processes.


a. periodically determine the number of running processes and allocate
each process an equal share.
b. pages can be allocated in proportion to each process’ total size.
Gao Haichang , Software School, Xidian University
52
Operating Systems
Local vs Global Allocation Policies (3)
Page fault rate as a function of the number of page frames
assigned
Gao Haichang , Software School, Xidian University
53
Operating Systems
Lesson 4
Operating Systems
Load Control
 Despite good designs, system may still thrash (a program
causing page faults every few instructions)
 When PFF (page fault frequency 页面失效频率) algorithm
indicates


some processes need more memory
but no processes need less
 Solution :
Reduce number of processes competing for memory


swap one or more to disk, divide up pages they held
reconsider degree of multiprogramming (CPU bound or I/O bound)
Gao Haichang , Software School, Xidian University
55
Operating Systems
Page Size
Argue for small page size (typically 4k or 8k).
 Advantages
 less
internal fragmentation
 better fit
 less
for various data structures, code sections
unused program in memory
 Disadvantages
 programs
need many pages, hence a larger page tables
 transfer
a small page takes almost as much time as
transferring a large page
Gao Haichang , Software School, Xidian University
56
Operating Systems
Separate Instruction and Data Spaces
 One address space
 Separate I and D spaces
Gao Haichang , Software School, Xidian University
57
Operating Systems
Shared Pages
Two processes sharing the same program sharing its page table
(not all pages are sharable)
Gao Haichang , Software School, Xidian University
58
Operating Systems
Cleaning Policy
 Need for a background process, paging daemon （分页守护进
程）

periodically inspects state of memory, to insure a plentiful supply of free
page frames.
 When too few frames are free

selects pages to evict using a replacement algorithm
 It can use same circular list (clock)
Gao Haichang , Software School, Xidian University
59
Operating Systems
Chapter 4: Memory Management
 4.1
Basic memory management
 4.2
Swapping (交换）
 4.3
Virtual memory （虚拟内存）
 4.4
Page replacement algorithms
 4.5
Design issues for paging systems
 4.6
Implementation issues
 4.7
Segmentation （分段）
Gao Haichang , Software School, Xidian University
60
Operating Systems
Operating System Involvement with Paging
Four times when OS involved with paging
1.
Process creation time



determine program size
create page table
space has to be allocated in memory for the page table and it
has to be initialized
Process execution time
2.


MMU reset for new process
TLB flushed
Page fault time
3.


determine virtual address causing fault
swap target page out, needed page in
Process termination time
4.

release page table, pages, and the disk space that the pages
occupy when they are on disk.
Gao Haichang , Software School, Xidian University
61
Operating Systems
Page Fault Handling (in detail)
1.
Hardware traps to kernel, saving the program counter on
the stack.
2.
General registers saved
3.
OS determines which virtual page needed
4.
OS checks validity of address, seeks free page frame
5.
If selected frame is dirty, write it to disk
6.
OS schedules new page in from disk
7.
Page tables updated
8.
Faulting instruction backed up to when it began
9.
Faulting process scheduled
10.
Registers restored, Program continues
Gao Haichang , Software School, Xidian University
62
Operating Systems
Backing Store
(a) Paging to static swap area (always a shadow copy on disk)
(b) Backing up pages dynamically (no copy on disk)
Gao Haichang , Software School, Xidian University
63
Operating Systems
Chapter 4: Memory Management
 4.1
Basic memory management
 4.2
Swapping (交换）
 4.3
Virtual memory （虚拟内存）
 4.4
Page replacement algorithms
 4.5
Design issues for paging systems
 4.6
Implementation issues
 4.7
Segmentation （分段）
Gao Haichang , Software School, Xidian University
64
Segmentation 分段
Operating Systems
A compiler has many
tables that are built up
as compilation
proceeds
 One-dimensional address space with growing tables
 One table may bump into another
Gao Haichang , Software School, Xidian University
65
Operating Systems
Segmentation (2)
Segmentation: many completely independent address spaces.
Allows each table to grow or shrink, independently
Gao Haichang , Software School, Xidian University
66
Operating Systems
Segmentation (3)
Advantages:
 Simplify the handling of data structures that are growing or
shrinking
 The linking up of procedures compiled separately is greatly
simplified
 Facilitates sharing procedures or data between several
processes
 Different segments can have different kinds of protection
Gao Haichang , Software School, Xidian University
67
Operating Systems
Segmentation (4)
Comparison of paging and segmentation
Gao Haichang , Software School, Xidian University
68
Operating Systems
Implementation of Pure Segmentation
(a)-(d) Development of checkerboarding
(e) Removal of the checkerboarding by compaction
Gao Haichang , Software School, Xidian University
69
Operating Systems
Segmentation with Paging
 If the segments are large, it may be inconvenient, or even
impossible, to keep them in main memory in their
entirety.
 MULTICS, combine the advantage of paging (uniform
page size and not having to keep the whole segment in
memory if only part of it is being used) with the advantages
of segments (ease of programming, modularity, protection,
and sharing).
Gao Haichang , Software School, Xidian University
70
Operating Systems
Segmentation with Paging: MULTICS (1)
 Descriptor segment points to page tables
 Segment descriptor – numbers are field lengths
Gao Haichang , Software School, Xidian University
71
Operating Systems
Segmentation with Paging: MULTICS (2)
A 34-bit MULTICS virtual address (consists of two parts: the segment
and the address within the segment. The address within the segment is further
divided into a page number and a word within the page)
1.
2.
3.
the segment number is used to find the segment descriptor.
Check if the segment’s page table is in memory. Located it if YES, fault occurs if
NO.
Examine if the page table entry in memory. Extract it if YES, page fault occurs if
NO.
4.
Add offset to give the real memory address.
5.
Read or store finally takes places.
Gao Haichang , Software School, Xidian University
72
Operating Systems
Segmentation with Paging: MULTICS (3)
Conversion of a 2-part MULTICS address into a main memory address
Gao Haichang , Software School, Xidian University
73
Operating Systems
Segmentation with Paging: MULTICS (4)
 Simplified version of the MULTICS TLB
 Existence of 2 page sizes makes actual TLB more complicated
Gao Haichang , Software School, Xidian University
74
Operating Systems
Gao Haichang , Software School, Xidian University
75
Operating Systems
Segmentation with Paging
 MULTICS has 256K independent segments, each up to 64K 36-bit words.
 Intel Pentium has 16K independent segments, each up to 1 billion 32-bit
words.
 Few programs need more than 1000 segments, but many programs
need large segments.
 The heart of the Pentium virtual memory consists of two
tables, the LDT (Local Descriptor Table 局部描述符表)
and the GDT (Global Descriptor Table 全局描述符表).
 Each program has its own LDT, but there is a single GDT, shared by all
the programs.
 LDT describes segments local to each program, including its code, data,
stack, and so on. GDT describes system segments, including the OS itself.
Gao Haichang , Software School, Xidian University
76
Operating Systems
Segmentation with Paging: Pentium (1)
A Pentium selector选择符
Gao Haichang , Software School, Xidian University
77
Operating Systems
Segmentation with Paging: Pentium (2)
 Pentium code segment descriptor
 Data segments differ slightly
Gao Haichang , Software School, Xidian University
78
Operating Systems
Segmentation with Paging: Pentium (3)
Conversion of a (selector, offset) pair to a linear address
Gao Haichang , Software School, Xidian University
79
Operating Systems
Segmentation with Paging: Pentium (4)
Mapping of a linear address onto a physical address
Gao Haichang , Software School, Xidian University
80
Operating Systems
Segmentation with Paging: Pentium (5)
Level
Protection on the Pentium
Gao Haichang , Software School, Xidian University
81
Operating Systems
Homework
 P250, No.14
 P251, No.24
 P251, No.28
Gao Haichang , Software School, Xidian University
82