Instructions must be loaded into  (physical)  memory befor execution.

一种方法是：整个进程放在内存中，program entire-->physical memory

虚拟内存技术允许执行进程不必完全在内存中。

Virtual Memory:

具有请求调页功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统

意义：将用户逻辑内存与物理内存分开

            separation of user logical memory from physical memory

logical size:内存容量+外存容量

1.only part of the program needs to be in memory for execution

2.logical address space much larger than physical

3.allows address spaces to be shared by several processes

4.allows for more processes creation

虚拟存储的特点:

多次性：一个作业被分成多次装入内存运行

对称性：允许在进程运行的过程中，（部分）换入换出

虚拟性：逻辑扩充

benefits:

1.Programmers need not care about memory limitations

2.More programs could be run simultaneously

3.Less I/O needed,each user program would run faster

swapper :manipulates the entire processes

pager :deal with individual pages 即以页为单位的lazy swapper

Page fault:

1.reference 

            invalid reference (引用非法）-->abort

            valid reference-->v  ok

                                    -->i   not in memory  -->2. Page fault ,trap

3.page is on backing store

4.bring in missing page  

            (get an empty frame from the free frame list

                -->swap page into frame,page out and page in

                -->modify the internal tables and set validation bit=v)

5.reset page table

6.restart instruction

distinguish:

illegal reference:the process is terminated (abort)

page fault:load in or pager in 

the modified page table mechanism

valid bit:v --in memory  i --not in memory    

            i-->page fault-->intepret-->换入

reference bit:标记页面访问情况

dirty/modified bit:记录页面是否被修改，如修改-->写回，没修改-->不写回

（提高效率，换出时看是否被修改，然后看是否写回）

Free page frame is managed by OS using free-frame-list

Basic Page Replacement

1.find the location of the desired page on disk

2.find a free frame:

        if there is a free frame,use it

        if there is no free frame,use a page replacement algorithm to select a victim frame

3.bring the desired page into the newly free frame

    update the page and frame tables

4.restart the process

1.use modify(dirty) bit to reduce overhead of page transfers,only modified pages are written to disk

2.page replacement completes separation between logical memory and physical memory

2 major problems:

frame-allocation algorithms 

page-replacement algorithms

Page replacement algorithms

A reference string: a sequence of addresses referenced by a program

page fault-page replacement=frame number

FIFO(first-in-first-out) Algorithm

The oldest page is chosen to be replaced

Data structure: a FIFO queue

·replace the page at the head of the queue

·insert a new page at the end of the queue

Belady's anomaly:more frames-->more page faults

(只有fifo有）

Optimal page-replacement algorithm:

Replace page that will not be used for longest period of time

lowest page-fault rate

difficult to implement,it is only used for measuring how well other algorithm performs

Least Recently Used (LRU) Algorithm

replace the page that has not been used for the longest period of time

implement:

1.counter implementation

    every page entry has a counter

2.stack implementation-keep a stack of page numbers in a double lin form

    when page referenced:move it to the top

LRU Approximation Algorithms

reference bit:initially=0,referenced-->1,replace the one which is 0

    additional-reference-bits algorithm：record each entry of page table entry with a 8-bit byte

    second chance(clock) algorithm:1 reference bit,modified FIFO

                   reference bit =0-->replace

                   reference bit =1-->set reference bit=0,leave page in memory(第二次机会）

Counting Algorithms

counter :the number of references that have been made to each page

LFU(Least frequently used) :replace the page with smallest count

MFU(Most frequently used):

Allocation of Frames

1.each process needs minimal number of pages

2.determined by 指令集的结构

2 major allocation schemes--fixed allocation

①equal allocation

frame number for any process=total memory frames/number of processes

②proportional allocation 

allocate according to the size of process

2 major allocation schemes--proority allocation

use a proportional allocation scheme using priorities rather than size

如果page fault-->replace policy

·local replacement 

·global replacement:replace the lower proority process's frame

Thranshing

thranshing=a process is busy swapping pages in and out

cause of thranshing:unreasonable degree of multiprogramming

page fault rate太高，处于阻塞状态，cpu利用率低，增加道数，越来越缺

page-fault frequency:helpful for controlling trashing

to establish "acceptable" page-fault rate:

if too low ,process loses frame

if too high,process gains frame

working-set strategy:进程的推进就是一个局部到另一个局部