Operating Systems Processes Lecture Slides PDF | University of Guelph

Operating Systems: Processes CIS*3110: Operating Systems Dr. A. Hamilton-Wright School of Computer Science University of Guelph 2025-01-28 1 / 56 Parts of a Computer RAM CPU...

Operating Systems: Processes CIS*3110: Operating Systems Dr. A. Hamilton-Wright School of Computer Science University of Guelph 2025-01-28 1 / 56 Parts of a Computer RAM CPU I/O Devices 2 / 56  111110x??...?? 00000 00000 11111 00000 11111 Actual Physical Memory 00000 11111 00000 11111 00000 11111 00000 11111 00000 11111 RAM 00000 11111 00000 11111 "Zero Page" 00000 11111 − interrupt vector 00000 11111 00000 11111 − I/O 00000 11111 BIOS/ROMs (if present) 00000 11111 00000 11111 111 000 0000x00...00 111 3 / 56 Tools at the Hardware Architecture Level program counter (PC) stack pointer/frame pointer processor status register general purpose registers memory management unit (mapping, protection) kernel/user mode interrupts and interrupt vector 4 / 56 Interrupt vector links devices with service routines discintr(...) {... disc service... fn addr 3 } CD service fn addr 2 mouse service fn addr 1 mouseintr(...) kbd service { fn addr 0... } 5 / 56 basic instruction cycle of the ALU of the CPU: 1. fetch instruction pointed to by the PC   over and 2. increment PC  over again 3. execute instruction processor status (usually a special register on each CPU) user mode – can execute most instructions (but no I/O) kernel mode – can execute all user instructions, PLUS access special instructions and registers that control I/O, memory access (also called supervisor mode) interrupt vector (special range of locations in RAM) used to link hardware interrupts with... interrupt service routines 6 / 56  P1 P2 P3 P4 User Space shared memory crossed via process interrupt or trap table entry Hardware Kernel Space run queue interrupt service routines (UARport contr ard ("bottom half") oller T) interf ork ace alarm o disk... clock serial keyb netw 7 / 56 Program on an Example Machine Assembler Mach Code Virt Addr load R1, 0xA2 0x11A2 0x10 incr R1 0x3100 0x12 store R1, 0xA2 0x21A2 0x14 Op Codes jmp xx 0x5026 0x16 load 0x1 yy: decr R2 0x4200 0x18 store 0x2...... rsb 0x7000 0x24 incr 0x3 xx: zero R2 0x8200 0x26 decr 0x4 incr R2 0x3200 0x28 jmp 0x5 store R2, 0xA0 0x22A0 0x2A jsr 0x6 jsr yy 0x6018 0x2C rsb 0x7 incr R2 0x3200 0x2E zero 0x8 store R2, 0xA2 0x22A0 0x30...... Registers: R0, R1, R2, R3, SP, PC 8 / 56 Context Switch change from one running program to another “on the fly” need to be able to change back later to do this, we must save the “program state” program counter general purpose registers status register stack pointer each program must be resident in different parts of memory 9 / 56  Interrupt (disk) Interrupt (disk) Disk Interrupt (mouse) context context context Mouse switch switch switch context context Program switch context switch switch A B C D E F GH Time 10 / 56 Interrupts a hardware generated jump to subroutine (JSR) requested by an external hardware device (not the CPU) defined through the interrupt vector resides somewhere in physical memory is effectively an array of function pointers may be delayed (i.e.; disabled, possibly temporarily) by masking off 11 / 56 Interrupt Steps Interrupt → Return from Interrupt (RTI) save PC on stack ← switch CPU to kernel restore registers (supervisor) mode restore saved PC value load PC from vector set CPU to previous using hardware id (vector mode contains the start address of the interrupt service routine) save all registers continue execution 12 / 56 Critical Sections a critical section contains reference(s) to data shared between two or more “threads of control” one may be an interrupt this may be two or more processes this may be two or more threads must manage the data so all parties can rely on its value if we fail to do this, data may be wrong for one party, or even corrupted for all load R1, #i i++; ←→ incr R1 store R1, #i 13 / 56 A Critical Example c = ’A ’ ; f o r ( i = 0 ; i < MAX ; i ++) { a [ i ] = c ++; i f ( c > ’E ’ ) c = ’B ’ ; } Interrupt Service Routine set_to_a ( ) { c = ’A ’ ; } 14 / 56 Modern (UNIX-type) systems: 3 types of device drivers BLOCK devices that read/write blocks (disc, tapes, SD-cards, CD-ROM/DVD,... ) NETWORK local area network (Ethernet, token ring), remote connection network interface (PPP, ISDN,... ) CHARACTER everything that does not fit the above two cases (serial ports, display/keyboard, mouse, joystick, touchscreen,... ) 15 / 56 Device Driver Functions Top Half: communicate with user, kernel probe check for hardware at boot time open called when a process does an open of a device file (e.g., /dev/mouse, /dev/disk0, /dev/null etc.) mostly initializes variables and maybe hardware generates a file descriptor in user space close called when a process does a close() of the file de- scriptor created from open (usually just marks the de- vice closed) read called when a process does a read(fd) — transfers data from device to process write called when a process does a write(fd) — queues data for device to output Bottom Half: event handling interrupt service routine called when device generates an interrupt and does the I/O on the hardware 16 / 56 char g e t _ k e y b ( ) { while (???) { } return ???; } void k e y b _ i n t r ( ) { / * " magic " addresses f o r memory mapped I /O * / char * k e y b _ r e g = ( char * ) 0x2ff4200 ; char * k e y b _ s t a t u s = ( char * ) 0x 2 f f 4 2 0 1 ; while (* keyb_status ) ; ??? = * k e y b _ r e g ; } 17 / 56 Circular Queue (Ring Buffer) char Q[QSIZE]; int numQ, startQpos, endQpos; numQ = startQpos = endQpos = 0; 0 ’b’ Add into queue Q[endQpos] = value; 1 ’c’ endQpos = (endQpos + 1) % QSIZE; numQ++; Remove from queue 2 value = Q[startQpos]; startQpos = (startQpos + 1) % QSIZE; numQ–; 3 ’a’ 18 / 56 Critical Sections in Device Driver interrupts can be masked off: int state = spltty() masks interrupt(s) to prevent a second interrupt from over-writing the first int splx(int prevState) returns the interrupt mask to the previous state process can be “put to sleep” until there is space in a buffer: int tsleep(void *id, int flags, char *mesg, int timeo) causes the current thread (program counter) to be BLOCKED until someone calls wakeup() int wakeup(void *id) un-blocks all threads which are asleep and have the given identifier 19 / 56 Device Driver Skeleton – read static char Q[QSIZE]; static int numQ = 0, startQpos = 0, endQpos = 0; devread(char *ubuf) { int s; s = spltty(); while (numQ == 0) { splx(s); tsleep(devread,...); s = spltty(); } *ubuf = Q[ startQpos ]; startQpos = (startQpos + 1) % QSIZE; numQ–; splx(s); } 20 / 56 Device Driver Skeleton – intr devintr() { int s; s = spltty(); if (QSIZE == numQ) { splx(s); return; } Q[ endQpos ] = GET_CHAR_FROM_DEVICE(); endQpos = (endQpos + 1) % QSIZE; numQ++; splx(s); wakeup(devread); } 21 / 56 Running Programs The execution of a program (an “image”) is a process. The environment that the O/S provides for the execution of a program (i.e.; a process) is that of a simplified pseudo-computer. 0xFFFFFFFF k ac St ap G UNIX/Mach process environment: a at D virtual (simplified) address space process context xt Te no direct access to I/O ports 0x00000000 22 / 56 Process Table Entry (Process Context) the process table contains an entry for each current process if a process has more than one thread there is usually one process table entry per thread (ps(1) may or may not show it this way) each entry holds all the information about a process: process (thread) context program counter registers (general and special purpose) stack pointer virtual address space reference scheduling information BLOCKED -vs-RUNNABLE -vs-RUNNING priority time used 23 / 56 Process Status Listing % ps auxw USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND root 1 0.0 0.0 1368 84 ? S Jan11 0:04 init root 2 0.0 0.0 0 0 ? SW Jan11 0:00 [keventd] root 4 0.0 0.0 0 0 ? SWN Jan11 0:00 [ksoftirqd_CPU0] root 9 0.0 0.0 0 0 ? SW Jan11 0:00 [bdflush] root 5 0.0 0.0 0 0 ? SW Jan11 0:00 [kswapd] root 1609 0.0 0.0 1368 144 ? S Jan11 0:00 klogd -x root 1761 0.0 0.0 3508 480 ? S Jan11 0:00 /usr/sbin/sshd root 1920 0.0 0.2 2320 1380 ? S Jan11 0:00 [login] root 1921 0.0 0.0 1352 60 tty2 S Jan11 0:00 /sbin/mingetty t andrew 8506 0.0 0.2 4692 1448 tty1 S 09:33 0:00 -csh andrew 9373 0.0 0.5 8196 2980 pts/7 S 10:43 0:03 vim Processes.te andrew 9795 0.0 0.2 4680 1428 pts/8 S 11:20 0:00 -bin/csh andrew 10154 0.0 0.1 2728 780 pts/7 R 11:36 0:00 ps auxw 24 / 56 Synchronization Primitives Shared data can also be used between processes/threads → we need to manage critical sections at this level. The two most popular synchronization primitives are: mutex: bracket critical section so only 1 process allowed at a time: critical_begin();... code in critical section... critical_end(); semaphores: allow N-at-a-time Co-operating sequential processes can be envisioned as a separate, dedicated processor for each – with no guarantee which runs first/faster etc. 25 / 56 Mutex Synchronization: Producer void add_queue(char aNewChar) { int oldsize; do { critical_begin(); oldsize = numQ; critical_end(); } while (oldsize == QSIZE); critical_begin(); Q[ endQpos ] = aNewChar; endQpos = (endQpos + 1) % QSIZE; numQ++; critical_end(); 26 / 56 Mutex Synchronization: Consumer void del_queue(char aNewChar) { int oldsize, tmpBuf; do { critical_begin(); oldsize = numQ; critical_end(); } while (oldsize == 0); critical_begin(); tmpBuf = Q[ startQpos ]; startQpos = (startQpos + 1) % QSIZE; numQ–; critical_end(); return tmpBuf; 27 / 56 Implementing Mutual Exclusion (in Hardware) s t a t i c mutexFlag = 0 ; critical_begin () { i n t oldFlag ; do { / * * does o l d f l a g = f l a g , f l a g = 1 * / TEST_AND_SET(& o l d F l a g , &mutexFlag ) ; / * * as one i n d i v i s i b l e o p e r a t i o n * / } while ( oldFlag ) ; } critical_end () { mutexFlag = 0 ; } 28 / 56 Dekker’s Algorithm (2 processes) i n t need [ 2 ] = { 0 , 0 } ; int turn ; c r i t i c a l _ b e g i n ( i n t who ) { need [ who ] = 1 ; t u r n = ! who ; w h i l e ( need [ ! who ] && t u r n ! = who ) ; } c r i t i c a l _ e n d ( i n t who ) { need [ who ] = 0 ; } 29 / 56 Semaphores A semaphore is a synchronization primitive which has an internal integer counter supporting the following operations: signal increments the internal counter wait until the internal counter > 0... only then decrement the counter 30 / 56 Semaphore Implementation - Using Mutexes SEM_WAIT(semaphore_t *s) { SEM_SIGNAL(semaphore_t *s) { semaphore_t oldsem; critical_begin(); *s = *s + 1; critical_end(); do { } critical_begin(); oldsem = *s; if (*s > 0) *s = *s - 1; critical_end(); } while (oldsem == 0); commercial/professional implementations use tsleep() to block the process instead of a busy-loop 31 / 56 Semaphore Producer/Consumer available_sem = QSIZE; void del_queue(char aNewChar) { used_sem = 0; int tmpBuf; critical_sem = 1; SEM_WAIT( &used_sem ); SEM_WAIT( &critical_sem ); void add_queue(char aNewChar) { SEM_WAIT( &available_sem ); tmpBuf = Q[ startQpos ]; SEM_WAIT( &critical_sem ); startQpos = (startQpos + 1) Q[ endQpos ] = aNewChar; % QSIZE; endQpos = (endQpos + 1) % QSIZE; SEM_SIGNAL( &critical_sem ); SEM_SIGNAL( &critical_sem ); SEM_SIGNAL( &used_sem ); SEM_SIGNAL( &available_sem ); } return tmpBuf; } 32 / 56 Co-Operating Sequential Processes – Examples semaphore_t U = 1; semaphore_t D = 0; int sharedch = ’a’; up() { down() { while (1) { while (1) { printf("U-%c ", sharedch); printf("D-%c ", sharedch); if(++sharedch > ’z’) if(--sharedch < ’a’) sharedch = ’a’; sharedch = ’a’; } } } } 33 / 56 Co-Operating Sequential Processes – Example #1 semaphore_t U = 1; semaphore_t D = 0; int sharedch = ’a’; up() { down() { while (1) { while (1) { SEM_WAIT( &U ); SEM_WAIT( &D ); printf("U-%c ", sharedch); printf("D-%c ", sharedch); if(++sharedch > ’z’) if(--sharedch < ’a’) sharedch = ’a’; sharedch = ’a’; SEM_SIGNAL( &D ); SEM_SIGNAL( &U ); } } } } Output: U-a D-b U-a D-b U-a... 34 / 56 Co-Operating Sequential Processes – Example #2 semaphore_t U = 2; semaphore_t D = 0; int sharedch = ’a’; up() { down() { while (1) { while (1) { SEM_WAIT( &U ); SEM_WAIT( &D ); SEM_WAIT( &D ); printf("U-%c ", sharedch); printf("D-%c ", sharedch); if(++sharedch > ’z’) if(--sharedch < ’a’) sharedch = ’a’; sharedch = ’a’; SEM_SIGNAL( &D ); SEM_SIGNAL( &U ); SEM_SIGNAL( &U ); } } } } Output: U-a U-b D-c U-c U-d D-e U-d U-e D-f U-e U-f D-g U-f... 35 / 56 Co-Operating Sequential Processes – Example #3 semaphore_t U = 0; semaphore_t D = 2; int sharedch = ’a’; up() { down() { while (1) { while (1) { SEM_WAIT( &U ); SEM_WAIT( &D ); printf("U-%c ", sharedch); SEM_WAIT( &D ); if(++sharedch > ’z’) printf("D-%c ", sharedch); sharedch = ’a’; if(--sharedch < ’a’) SEM_SIGNAL( &D ); sharedch = ’a’; } SEM_SIGNAL( &U ); } SEM_SIGNAL( &U ); } } Output: D-a U-a U-b D-c U-c U-d D-e U-d U-e D-f U-e U-f D-g... 36 / 56 Semaphore Hints: all semaphores must be properly initialized always work from the definition of wait_sem() and signal_sem() normally, there will be a wait_sem with a corresponding signal_sem() on the same semaphore the order of wait_sem() operations is quite important; the order of signal less so 37 / 56 Deadlock deadlock occurs when processes hold resources and they require resources that other processes already hold shown by the presence of a cycle in the request allocation graph P1 R1 R2 P2 38 / 56 Deadlock deadlock occurs when processes hold resources and they require resources that other processes already hold shown by the presence of a cycle in the request allocation graph P1 R1 R2 P2 39 / 56 Deadlock deadlock occurs when processes hold resources and they require resources that other processes already hold shown by the presence of a cycle in the request allocation graph P1 R1 R2 P2 40 / 56 Deadlock deadlock occurs when processes hold resources and they require resources that other processes already hold shown by the presence of a cycle in the request allocation graph P1 R1 R2 P2 41 / 56 Deadlock deadlock occurs when processes hold resources and they require resources that other processes already hold shown by the presence of a cycle in the request allocation graph P1 R1 R2 P2 42 / 56 Deadlock deadlock occurs when processes hold resources and they require resources that other processes already hold shown by the presence of a cycle in the request allocation graph P1 R1 R2 P2 43 / 56 Java synchronized keyword The synchronized keyword can be used on a whole method or a block to provide a critical section method locking: public class SyncCount { private int count = 0; public synchronized void increment() { count++; }; public synchronized int getValue() { return count; }; } block locking: public void someMethod() { while(keepGoing()) { synchronized(someObject) { count++; } } } 44 / 56 IPC in General Shared Memory blocks of shared process image Semaphores/Mutexes integer data values for flow control Signals a software “interrupt” Pipes an imitation file shared by two processes 45 / 56 Signals used to indicate that some important event has happened sequence of events process A is running and performing some task process B sends a signal to process A process A interrupts whatever it is doing... call a signal handler (a function)... returns to whatever it was doing before there is no direct notification to process B that anything has been done 46 / 56 Signal Values Signals are simply integer valued actions, similar to interrupts. Some common signals are: 1 HUP hangup 7 BUS bus error 2 INT interrupt 11 SEGV segmentation violation 3 QUIT quit 30 PWR power failure 4 ILL illegal instruction 15 TERM terminate process 5 TRAP trace trap 10 USR1 user defined #1 9 KILL kill process 12 USR2 user defined #2 The left column contains signals typically found at the indicated numbers. The right column contain common signals whose ID number may vary between platforms; the ID numbers for linux are provided. The numbers for a given platform may be found by running kill -l 47 / 56 Signal Example #i n c l u d e < s i g n a l. h> v o i d s i g n a l H a n d l e r ( i n t code ) { f p r i n t f ( stderr , " I n t e r r u p t caught −− c l e a n i n g up \ n " ) ; performCleanup ( ) ; exit ( 1 ) ; } v o i d main ( ) { s i g n a l ( SIGINT , s i g n a l H a n d l e r ) ;... 48 / 56 Pipes A pipe is a file descriptor pair shared between processes, attached to a buffer common to both processes. The buffer is not stored anywhere in a filesystem, only in memory. P1 P2 (fixed size) buffer 49 / 56 Scheduling Basic process scheduler loop: when a process can no longer run (exits, waiting for I/O or time-slice used up) mark process RUNNABLE or blocked (and why – blocked status) save process context in process table entry search process table for another RUNNABLE process mark this process running restore process context for this process the system now runs this process, picking up where it left off (just as with a hardware interrupt) 50 / 56 Scheduling Algorithm or “Queuing Discipline” FIFO SJF if jobs/process- shortest job first es/... repeatedly join the allow the job with the queue this is typically shortest running time to called “round robin.” go next (jump to the typically, round robin is head of the queue) preemptive not preemptive A preemptive discipline permits a job to be preempted before it completes 51 / 56 Scheduling Algorithms/Queuing Disciplines FIFO and round robin are generally considered to be fair, as jobs cannot be stuck waiting forever SJF is optimal w.r.t. throughput: iff you always run the job that will finish in the shortest time. will always finish more jobs in a given elapsed time than any other ordering it is unfair, and impractical for processes (can be approximated) 52 / 56 Scheduling Algorithms/Queuing Disciplines In general: preemptive schedulers will perform better (i.e.; smoother response) than non-preemptive schedulers and are required for interactive systems schedulers will normally bias towards short jobs, such as updating an editor after a keystroke operators/users will be able to set/adjust priorities for jobs, see nice(1) dynamic priority is updated during context switch based on last run time there will always be a trade-off between coarse -vs-fine granularity of the time-slices: coarse : low overhead/poor interactive response fine : higher overhead/better interactive response 53 / 56 Scheduling Algorithms/Queuing Disciplines if preemption occurs extremely frequently such that each job gets an infinitesimally small time each time it runs, the discipline is called “processor sharing” whereas, if the preemption time is infinitely large, the discipline is called FIFO 54 / 56 Scheduling Algorithms/Types of Tasks batch insensitive to gaps in runtime; get overall task done interactive sensitive to runtime gaps; typically lots of I/O real-time critically sensitive to runtime gaps demand fixed fraction of CPU/unit time 55 / 56 Priority Queues (VMS/Windows) Priority 1 Priority 2 Priority 3 Some systems vary the priority dynamically, others do not 56 / 56 Operating Systems: Memory CIS*3110: Operating Systems Dr. A. Hamilton-Wright School of Computer Science University of Guelph 2024-12-01 1 / 41 Unix-Style Process Image 0xFFFFFFFF Stack text – contains executable code other processes data – contains static data shared with Data Segment Dynamic Data Shared BSS Data symbol table – symbol (literal) definitions Symbols Static – strings, constants Data Segment Text Text (machine code) 0x00000000 2 / 41  0xFFFFFFFF Stack Process Image: Unique pro- Data Segment Dynamic cess image “contains” all data Data Shared Data Symbols Static Data Segment Text Text (machine code) 0x00000000 3 / 41  0xFFFFFFFF 0xFFFFFFFF Stack Stack Program may clone itself using fork(): most data copied Data Segment Data Segment Dynamic Dynamic Data Data shared (pointer) to shared Shared Shared libs, shared mem, readonly Data Data Symbols Symbols portions (text, symbols) Static Static Data Data Segment Segment Text Text Text Text (machine (machine code) code) 0x00000000 0x00000000 4 / 41  0xFFFFFFFF 0xFFFFFFFF Stack Stack If a new POSIX thread is cre- ated: most data is shared only the stack is copied → only local variables may be used without potential race conditions Data Segment Data Segment Dynamic Dynamic Data Data different thread Shared Shared implementation give Data Data Symbols Symbols different things Static Static fibres are threads that use Data Data co-operative Segment Segment multitasking instead of Text Text Text Text preemptive multitasking (machine (machine code) code) 0x00000000 0x00000000 5 / 41 Protected Virtual Addressing program sees only virtual addresses kernel sees/manages all address 0xFFFFFFFF spaces k ac ss 0 St one program cannot ‘see’ or Proce a ac Tex Dat 0xFFFFFFFF affect any other programs in k k t ac 0x00000000 0xFFFFFFFF s1 St St memory s Proce ap a at D G xt large space requirements to store Te 0x00000000 many programs a 0xFFFFFFFF k sN ac at St D s Proce a program may largely consist of at D xt xt Te 0x00000000 Te l rne Ke ory ts ‘empty space’ between stack and 0x00000000 m n me reme req ui data each program is divided into pages; only the pages currently needed are represented in (or loaded into) in real memory 6 / 41 Process image and logical pages 0xFFFFFFFF ck a St process image is “sliced” into pages independent of data ap unneeded pages arrangement on G pages “page + offset” → logical position of... 39 a... at byte D 4 10... 0 1 2 3...... 9 3 physical storage ↔ page 3, byte 2 2 @ 40 bytes/page logical? = absolute 3x40+2 xt 1 = 120 + 2 = 122 Te 0 0x00000000 7 / 41 MMU (Memory Management Unit) Translates virtual ⇒ physical addresses A virtual address: Page # Offset Translation Table (Page Table) 5 9 + Physical Address 7 Page Frame Main Memory OR I/O device registers 8 / 41 MMU - Address Translation Processes are divided into pages (analogies: book, also slice of a loaf of bread) VirtualAddress/PageSize = VirtualPageNumber VirtualAddress%PageSize = PageOffset Use virtual page number to look up the frame number for the page number in the page table. (FrameNumber × PageSize) + Offset = PhysicalAddress 9 / 41 Relationship between CPU and Memory CPU MMU Memory (ALU) (RAM chips) Virtual Physical Addresses Addresses 10 / 41 Valid and Invalid regions of Memory the hardware page table contains the following information for each page within a process whether the page is “valid”, meaning “in memory” (called the V bit) writeability: usually called RO or W dirty and used bits – more on this shortly page frame number additionally, the in-memory page table contains an associated disk address if paged out the valid bit indicates whether page is currently in memory; the bottom of the stack and top of the heap indicate whether the page is legally part of the process 11 / 41  Page Table Main Memory V RO D U Page Frame Disk Addr Example #1: F 0 0 C 0x16 P0−2 (RO) Given a page size of E D 1 0 0 11 6 0x14 0x12 P0−6 P2−0 P4−2 51210 bytes = ???16 C B 0 0 0x10 P1−4 0x0E PA−0 P1−E Read virtual address A 0 0x0C P0−A P1−3 (RO) 9 0 0x0A P5−1 PA−A 0x072E (for process 1) 8 0 0x08 P0−C P2−1 7 0 0 11 0x06 P0−4 P5−F 0x200 = 29 ⇒ 9 bits of 6 1 0 1 0x04 P1−2 (RO) P1−5 5 1 0 5 0x02 P5−4 P5−0 offset 4 1 0 10 0x00 P0−1 (RO) P1−6 3 1 1 D 4 0x072E / 0x200 = 0x3 2 1 1 4 (0x12E remainder) 1 0 0 0 1 1 B 5 page 0x3 ⇒ frame 0xD Paging Disk 0 0xD × 0x200 = 0x1A00 4 P0−D P0−1(RO) P0−8 P0−E P1−3 (RO) P0−B + 0x12E 8 P1−0 (RO) P1−E P1−1 (RO) = physical address C P1−F P0−5 P0−3(RO) P0−F 10 0x1B2E P1−7 P2−0 (RO) 12 / 41  Page Table Main Memory V RO D U Page Frame Disk Addr F 0 0 C 0x16 P0−2 (RO) Example #2: E 1 0 11 6 0x14 P0−6 P2−0 D 0 0x12 P4−2 Given a page offset of C 0 0x10 P1−4 P1−E 11 bits B A 0 0 0x0E PA−0 0x0C P0−A P1−3 (RO) 11 wires of bus used 9 0 0x0A P5−1 PA−A 8 0 0x08 P0−C P2−1 for offset; 7 0 0 11 0x06 P0−4 P5−F 211 =0x800 6 5 1 0 1 0 1 5 0x04 0x02 P1−2 (RO) P5−4 P1−5 P5−0 Read virtual address 4 1 0 10 0x00 P0−1 (RO) P1−6 3 1 1 D 4 0x77FF (for process 1) 2 1 1 4 1 0 1 B 0x77FF / 0x800 = 0xE 0 0 1 5 (0x7FF remainder) Paging Disk 0 P0−D page 0xE ⇒ frame 0x11 4 P1−3 (RO) P0−1(RO) P0−8 P0−E P0−B = physical address 8 P1−0 (RO) P1−E P1−1 (RO) C P0−5 P0−3(RO) 0x8FFF P1−F P0−F 10 P1−7 P2−0 (RO) 13 / 41  Page Table Main Memory Example #3: V RO D U Page Frame Disk Addr F 0 0 C 0x16 P0−2 (RO) Given a page offset of E 1 0 11 6 0x14 P0−6 P2−0 D 0 0x12 P4−2 11 bits (11 wires of bus C 0 0x10 P1−4 P1−E B 0 0x0E PA−0 used for off-set) A 0 0x0C P0−A P1−3 (RO) 211 = 0x800 9 8 0 0 0x0A P5−1 0x08 P0−C PA−A P2−1 7 0 0 11 0x06 P0−4 P5−F Read virtual address 6 5 1 0 1 0 1 5 0x04 0x02 P1−2 (RO) P5−4 P1−5 P5−0 0x77FF (for process 1) 4 1 0 10 0x00 P0−1 (RO) P1−6 3 1 1 D 4 2 1 1 4 1 0 1 B 0x77FF / 0x800 = 0x0E 0 0 1 5 (0x7FF remainder) page 0xE ⇒ frame 0x11 Paging Disk 0 P0−D 0x11 × 0x800 = 4 P1−3 (RO) P0−1(RO) P0−8 P0−E P0−B 0x8800 + 0x7FF 8 P1−0 (RO) P1−E P1−1 (RO) C P0−5 P0−3(RO) = physical address P1−F P0−F 10 0x8FFF P1−7 P2−0 (RO) 14 / 41 Example #4: Given a page offset of 11 bits Page Table Main Memory V RO D U Page Frame Disk Addr Read virtual address F E 0 0 1 0 11 C 6 0x16 0x14 P0−6 P0−2 (RO) P2−0 0x072E (for process 1) D C 0 0 0x12 0x10 P1−4 P4−2 P1−E 0x072E / 0x800 = 0 B A 0 0 0x0E PA−0 0x0C P0−A P1−3 (RO) (72E remainder) 9 0 0x0A P5−1 PA−A 8 0 0x08 P0−C P2−1 page 0x0 ⇒ page not 7 0 0 11 0x06 P0−4 P5−F 6 1 0 1 0x04 P1−2 (RO) P1−5 in memory 5 1 0 5 0x02 P5−4 P5−0 4 1 0 10 0x00 P0−1 (RO) P1−6 3 1 1 D 4 page fault 2 1 1 0 1 1 4 B page is on the paging 0 0 1 5 disk Paging Disk we schedule a read to 0 P0−D P0−E place the page in an 4 P1−3 (RO) P0−1(RO) P0−8 P0−B 8 P1−0 (RO) P1−E empty frame (let’s say C P0−5 P0−3(RO) P1−1 (RO) P1−F 0x16) 10 P0−F when I/O completes, we P1−7 P2−0 (RO) restart MMU access... 15 / 41  Page Table Main Memory V RO D U Page Frame Disk Addr Example #4b: F 0 0 C 0x16 P1−0 (RO) P0−2 (RO) Given a page offset of E D 1 0 0 11 6 0x14 P0−6 0x12 P2−0 P4−2 11 bits C B 0 0 0x10 P1−4 0x0E PA−0 P1−E Read virtual address A 0 0x0C P0−A P1−3 (RO) 9 0 0x0A P5−1 PA−A 0x072E (for process 1) 8 0 0x08 P0−C P2−1 7 0 0 11 0x06 P0−4 P5−F 0x072E / 0x800 = 0 6 1 0 1 0x04 P1−2 (RO) P1−5 5 1 0 5 0x02 P5−4 P5−0 (72E remainder) 4 1 0 10 0x00 P0−1 (RO) P1−6 3 1 1 D 4 page 0x0 (now in 2 1 1 4 memory) 1 0 0 1 1 1 16 B 5 page 0x0 ⇒ frame 0x16 Paging Disk 0 0x16 × 0x800 = 4 P0−D P0−1(RO) P0−8 P0−E P1−3 (RO) P0−B 0xB800 + 0x72E 8 P1−0 (RO) P1−E P1−1 (RO) = physical address C P1−F P0−5 P0−3(RO) P0−F 10 0xB72E P1−7 P2−0 (RO) 16 / 41 Page Fault Handling 1 IF address invalid ⇒ terminate process 2 ELSE IF page frame in process allocation is empty ⇒ use this frame 3 ELSE choose page to be replaced IF page is modified ⇒ save page on disk 4 IF required page is saved on paging area ⇒ read in from disk paging area 5 ELSE IF required page is a text page or an initialized data page ⇒ read in from executable program file 6 ELSE initialize page to zeros (for security) 7 set up page table to point to the new page 8 mark process RUNNABLE 17 / 41 Page Fault Timeline If address mapping in process X causes page fault: process X cannot be run – BLOCKED on I/O waiting for needed page to be loaded into page frame + possibly other steps other processes (Y, Z... ) may be run if RUNNABLE if no RUNNABLE process, system is idle all processes are waiting on I/O (no matter what), fault causes major interruption in runtime of process X equivalent to thousands of instructions.˙. worthwhile to spend some processor effort trying to manage and decrease the number of page faults 18 / 41 Paged Virtual Memory Paged Virtual Memory depends on the locality principle: a large program only uses a small portion of its virtual address space at a given time. The set of pages that make up this portion is called the working set The pages that are allocated page frames in physical memory is called the resident set. 19 / 41  ∗ ∗ Silberschatz et al, Operating System Concepts, 8th ed. John Wiley & Sons. Fig 9.19, pp. 388. 20 / 41 Page Replacement Policy A page replacement policy decides which page frames to replace The ideal page replacement policy would achieve: resident set ≡ working set To evaluate a page replacement policy, you must calculate its page fault rate for the page reference strings of real programs. 21 / 41