What does a linker do?
   address resolution
      calls to functions that you have created?
      calls to functions in external libraries
   
Addresses generated relative to start of a segment (code, data, etc...)

Microsoft (R) Macro Assembler Version 8.00.50727.42       09/08/08 19:57:44
INCLUDE Irvine32.inc ;includes textbook ASM lib
00000000          .data
                  ; String to print
00000000 48 65 6C 6C 6F  Msg BYTE "Hello World",0dh,0ah,0
         20 57 6F 72 6C
         64 0D 0A 00
00000000          .code
00000000                 main PROC
00000000  E8 00000000 E  call Clrscr        ; Lib Call to clear the screen
00000005  BA 00000000 R  mov edx,OFFSET Msg ; Stores pointer to edx
0000000A  E8 00000000 E  call WriteString   ; Lib Call to print string
0000000F  B8 FFFFFFFF    mov  eax, -1       ; Stores -1 in eax      
00000014  E8 00000000 E  call dumpregs      ; Dumps CPU Registers to screen
                         exit               ; Ends Program and returns to OS
00000020                 main ENDP
                         END main


If we look at an assembly language in the debugger...
If we look at the disassembly...

   How do we know the addresses  given that RAM is huge and dynamic and
   different programs are loaded in differen places at different times?
   (on-line book chapter 5)


Logical vs. Physical address (RAM)

*
. Level of indirection allows delay of translation = "pointer"
*

. Logical address is translated to physical address at 
  EXECUTION time by *Memory Manager*

. Address translation TRANSPARENT to program and programmer

. Logical address is limited by address register (32 bits) 
  NOT by physical RAM 






Libraries
=========
   Originally library exe code became part of the exe code
   Makes exe BIG
      uses more disk (no biggie)
      uses more RAM (biggie)
   If a library changes, you need to re-link (how would you know that?)

Shared or  Dynamic libraries (DLL)
==================================
   One copy of library that all the exes link to
      code area shared
      may have separate data areas per process
      if shared data area, => IPC
   Only loaded when needed
   Exe much smaller
   Code must be carefully written 
      no statics that another process might mess up
      no changes to interfaces that would break everyone using it
   Updates to DLL 
      are automatically evident to exe
      exes do NOT have to be re-built
   DLL Hell
      conflicts between DLL versions
      difficulty in obtaining required DLLs
      having many unnecessary DLL copies

Big idea:
=========
  page size  =  frame size  =   block size

  A comon size is 4k, but some smaller and larger

Disadvantages of early schemes:
   Required storing entire program in memory
   Fragmentation
   Overhead due to relocation

Paging Scheme:
   Allows non-contiguous program storage
   Demand paging allows partial program loading
   Elimintaes virtually all fragmentation
   Eliminates need for relocation

   Divides each incoming job into pages of equal size
   Works well if the following are SAME SIZE:
      page size
      memory block size (page frames)
      size of disk section (sector, block)

   Before executing a program, Memory Manager:
      Determines number of pages in program
      Locates enough empty page frames in main memory
      Loads all of the program’s pages into them
         (or loads as needed if demand paging)

MEMORY MANAGER FOR PAGING
=========================
   Needs THREE tables to keep track of the job’s pages:
    1.  Job Table (JT) contains information about
          Size of the job
          Memory location where its PMT is stored
    2.  Page Map Table (PMT) contains information about
          Page number and its 
          Corresponding page frame memory address
    3.  Memory Map Table (MMT) contains
          Location for each page frame
          Free/busy status


JOB TABLE
=========

  A Typical Job Table (page size = 100)
    (a) initially has three entries, one for each job in process
    (b) when second job ends, its entry in the table is released
    (c) empty entry replaced by info about next job that's processed

PAGE MAP TABLE
==============
This is the page map table from Job1 above
Note that it is 4 pages, although only needing 350 units


MEMORY MAP TABLE
================
This is showing the same job with memory map


Displacement (offset) of a line: 
   Determines how far away a line is from the beginning of its page
   Used to locate that line within its page frame


TRANSLATE A LOGICAL ADDRESS to a PHYSICAL RAM ADDRESS
=====================================================
  1. Determine page number and displacement of a line   
       Page number = quotient from division of program size by page size
       Displacement = remainder from the page number division
  2. Use job’s PMT & find page frame containing required page
  3. Get page frame start address in RAM
       Page frame address = page frame number * page frame size
  4. Add the displacement (from step 1) to page frame start address



If page size = 100, what's physical address of instruction at line 225 of job1?
  1. 225 / 100: Q = 2  R = 25, means page = 2, displacement = 25 
  2. Goto PMT: page frame for page 2 is 7: 
  3. 7 x 100 (page frame size)
  4. Add displacement (25) = 725 is physical address of code! 

If page size=100, what's physical address of instruction at line 189 of job 4?

Paging Advantages:
   Allows jobs to be allocated in noncontiguous memory locations
   Memory used more efficiently; more jobs can fit
Paging Disadvantages:
   Address resolution causes increased overhead
   Internal fragmentation still exists
      only in last page & usually not a large amount
   Requires the entire job to be stored in memory location
      only if no demand paging
   Size of page is crucial (not too small, not too large)

Demand Paging
=============
   Pages  brought into memory only as they are needed, 
   Allows jobs to be run with less main memory (working set)
   Takes advantage that programs written so not all pages needed at once
      Error handling modules processed only when specific error is detected
      Mutually exclusive modules
      Certain program options are not always accessible

   Demand paging made virtual memory widely available
     Can give appearance of an almost infinite amount of physical memory
     Allows user to run jobs with less RAM than required in paged memory
     Requires use of a high-speed DASD that can work directly with CPU
     Which pages are “swapped” depends on predefined policies

Page Map Table - UPDATED
========================
Need 3 new fields in PMT to determine which pages should be swapped in or out.

   Page Map Table with 3 new fields to determine
      1. If requested page is already in memory
      2. If page contents have been modified (dirty bit)
      3. If the page has been referenced recently



Swapping Process:
=================
   To move in a new page, a resident page must be swapped back to SS
      Copy resident page to the disk (IF it was modified)
      Write the new page into the empty page frame

   Page fault: a failure to find a page in memory
   ==========
   Page fault handler: section of the MM that handles paging 
    If there are empty page frames in RAM
      requested page is copied from secondary storage to RAM
    Else
      Choose page(s) to remove
      Algorithm determines which page: FCFS, LRU

   Advantages:
     Job no longer constrained by the size of physical memory (VM)
     Utilizes memory more efficiently than the previous schemes
   
   Disadvantages:
     Increased overhead caused by the tables and the page interrupts

VIRTUAL ADDRESS
===============
Virtual address includes index into page table AND offset within page

Example: 32 bit address, 4k page
========
  20 bit index - how many page frames? 
  12 bit offset - how big is page?
  
  so 1 megabye of 4k pages = 1meg x 4k = 4gig


 

PAGE REPLACEMENT
================
Policy that selects the page to be removed crucial to system efficiency. 
   Types include:
      (FIFO) First-in first-out  policy: 
             Removes page that has been in memory the longest
      (LRU)  Least-recently-used  policy: 
             Removes page that has been least recently accessed
      (MRU)  Most recently used  policy
      (LFU)  Least frequently used  policy

Scenario:   2 empty page frames
=========   4 pages to swap in and out
            2 algorithms illustrated

FIFO
====


 Begin with all 4 pages on disk
 Pages brought in as accessed => demand paging
   11 page requests  
    9 page faults (request for page not in memory)
 Failure rate = 9/11 = 82%
 Remove page that was "first in"

LRU
===

 Begin with all 4 pages on disk
 Pages brought in as accessed => demand paging
   11 page requests  
    8 page faults (request for page not in memory)
 Failure rate = 8/11 = 73%
 Remove page that was "least recently used"
 

Memory Problems: buffer overflow
   enter 6 characters ("mypass")
   enter any 6 characters
   enter any 9 characters
   enter any 10 characters
   
   [run on jupiter]
   a at ffbefa2f and
   x at ffbefa38
   Enter a short word: mypass
   x = 1
   Password is correct!

#include <stdio.h>

int checkpass(void);

int main(void) {
   int x;
   x = checkpass();
   fprintf(stderr, "x = %d\n", x);
   if (x)
      fprintf(stderr, "Password is correct!\n");
   else
      fprintf(stderr, "Password is not correct!\n");
   return 0;
}

     ------------SEPARATE FILE -------------------

#include <stdio.h>
#include <string.h>

int checkpass(void){
   int x;
   char a[9];
   x = 0;
   fprintf(stderr,"a at %p and\nx at %p\n", (void *)a, (void *)&x);
   printf("Enter a short word: ");
   scanf("%s", a);
   if (strcmp(a, "mypass") == 0)
      x = 1;
   return x;
}