Processes (con’t), Fork, I/O简介

1 . Recall: Four fundamental OS concepts CS162 •  Thread Operating Systems and –  Single unique execution context Systems Programming –  Program Counter, Registers, Execution Flags, Stack Lecture 3 •  Address Space w/ translation –  Programs execute in an address space that is distinct from the memory Processes (con’t), Fork, space of the physical machine Introduction to I/O •  Process –  An instance of an executing program is a process consisting of an address space and one or more threads of control August 30th, 2017 •  Dual Mode operation/Protection Prof. Ion Stoica –  Only the “system” has the ability to access certain resources http://cs162.eecs.Berkeley.edu –  The OS and the hardware are protected from user programs and user programs are isolated from one another by controlling the translation from program virtual addresses to machine physical addresses 8/30/17 CS162 ©UCB Fall 2017 Lec 3.2 Process Control Block Recall: give the illusion of multiple processors? (Assume single threaded processes for now) vCPU1 vCPU2 vCPU3 vCPU1 vCPU2 vCPU3 vCPU1 vCPU2 •  Kernel represents each process as a process control block (PCB) Shared Memory Time –  Status (running, ready, blocked, …) –  Registers, SP, … (when not running) •  Assume a single processor. How do we provide the illusion of –  Process ID (PID), User, Executable, Priority, … multiple processors? –  Multiplex in time! –  Execution time, … –  Multiple “virtual CPUs” –  Memory space, translation tables, … •  Each virtual “CPU” needs a structure to hold, i.e., PCB: –  Program Counter (PC), Stack Pointer (SP) –  Registers (Integer, Floating point, others…?) •  Kernel Scheduler maintains a data structure containing the PCBs •  How switch from one virtual CPU to the next? –  Save PC, SP, and registers in current PCB •  Scheduling algorithm selects the next one to run –  Load PC, SP, and registers from new PCB •  What triggers switch? –  Timer, voluntary yield, I/O, other things 8/30/17 CS162 ©UCB Fall 2017 Lec 3.3 8/30/17 CS162 ©UCB Fall 2017 Lec 3.4 Page 1 

2 . Simultaneous MultiThreading/Hyperthreading Scheduler •  Hardware technique –  Superscalar processors can if ( readyProcesses(PCBs) ) { execute multiple instructions nextPCB = selectProcess(PCBs); that are independent run( nextPCB ); –  Hyperthreading duplicates } else { run_idle_process(); register state to make a } second “thread,” allowing more instructions to run •  Can schedule each thread as if were separate CPU •  Scheduling: Mechanism for deciding which processes/threads receive the Colored blocks show –  But, sub-linear speedup! instructions executed CPU •  Lots of different scheduling policies provide … •  Original technique called “Simultaneous Multithreading” –  Fairness or –  http://www.cs.washington.edu/research/smt/index.html –  Realtime guarantees or –  SPARC, Pentium 4/Xeon (“Hyperthreading”), Power 5 –  Latency optimization or .. 8/30/17 CS162 ©UCB Fall 2017 Lec 3.5 8/30/17 CS162 ©UCB Fall 2017 Lec 3.6 Putting it together: web server Putting it together: web server 4. parse request 9. format reply Server request reply buffer buffer 1. network 3. kernel 10. network socket copy socket 5. file 8. kernel syscall read write syscall read copy Request Kernel wait RTU 11. kernel copy RTU from user buffer to network buffer interrupt interrupt 2. copy arriving 12. format outgoing 6. disk 7. disk data packet (DMA) packet and DMA request (DMA) Reply (retrieved by web server) Hardware Client Web Server Network interface Disk interface Request Reply 8/30/17 CS162 ©UCB Fall 2017 Lec 3.7 8/30/17 CS162 ©UCB Fall 2017 Lec 3.8 Page 2 

3 . Recall: 3 types of Kernel Mode Transfer Recall: User/Kernel (Privileged) Mode •  Syscall –  Process requests a system service, e.g., exit User Mode –  Like a function call, but “outside” the process interrupt exception –  Does not have the address of the system function to call syscall –  Like a Remote Procedure Call (RPC) – for later rtn rfi –  Marshall the syscall ID and arguments in registers and execute syscall exit •  Interrupt exec Kernel Mode –  External asynchronous event triggers context switch –  e.g., Timer, I/O device –  Independent of user process •  Trap or Exception Limited HW access Full HW access –  Internal synchronous event in process triggers context switch –  e.g., Protection violation (segmentation fault), Divide by zero, … 8/30/17 CS162 ©UCB Fall 2017 Lec 3.9 8/30/17 CS162 ©UCB Fall 2017 Lec 3.10 Implementing Safe Kernel Mode Transfers Need for Separate Kernel Stacks •  Important aspects: •  Kernel needs space to work –  Separate kernel stack •  Cannot put anything on the user stack (Why?) –  Controlled transfer into kernel (e.g., syscall table) •  Two-stack model –  OS thread has interrupt stack (located in kernel memory) plus •  Carefully constructed kernel code packs up the user process state User stack (located in user memory) and sets it aside –  Syscall handler copies user args to kernel space before invoking –  Details depend on the machine architecture specific function (e.g., open) running ready to run waiting for I/O –  Interrupts (???) main main main User Stack proc1 proc1 proc1 proc2 proc2 proc2 •  Should be impossible for buggy or malicious user program to cause ... ... syscall the kernel to corrupt itself user CPU user CPU state state Kernel Stack syscall handler I/O driver top half 8/30/17 CS162 ©UCB Fall 2017 Lec 3.11 8/30/17 CS162 ©UCB Fall 2017 Lec 3.12 Page 3 

4 . Before During User-level Registers Kernel User-level Registers Kernel Process Process code: SS: ESP code: code: SS: ESP code: CS: EIP CS: EIP foo () { handler() { foo () { EFLAGS handler() { EFLAGS while(...) { pusha while(...) { other pusha other x = x+1; ... x = x+1; registers: ... registers: y = y-2; } y = y-2; EAX, EBX, } EAX, EBX, } } ... ... } } Exception Exception stack: stack: Stack Stack SS ESP EFLAGS CS EIP error 8/30/17 CS162 ©UCB Fall 2017 Lec 3.13 8/30/17 CS162 ©UCB Fall 2017 Lec 3.14 Kernel System Call Handler Hardware support: Interrupt Control •  Vector through well-defined syscall entry points! •  Interrupt processing not visible to the user process: –  Table mapping system call number to handler –  Occurs between instructions, restarted transparently •  Locate arguments –  No change to process state –  In registers or on user (!) stack –  What can be observed even with perfect interrupt processing? •  Copy arguments –  From user memory into kernel memory •  Interrupt Handler invoked with interrupts ‘disabled’ –  Protect kernel from malicious code evading checks –  Re-enabled upon completion •  Validate arguments –  Non-blocking (run to completion, no waits) –  Protect kernel from errors in user code –  Pack up in a queue and pass off to an OS thread for hard work •  Copy results back »  wake up an existing OS thread –  Into user memory 8/30/17 CS162 ©UCB Fall 2017 Lec 3.15 8/30/17 CS162 ©UCB Fall 2017 Lec 3.16 Page 4 

5 . Hardware support: Interrupt Control Interrupt Controller Interrupt Mask Priority Encoder •  OS kernel may enable/disable interrupts IntID –  On x86: CLI (disable interrupts), STI (enable) CPU Timer –  Atomic section when select next process/thread to run Interrupt Int Disable –  Atomic return from interrupt or syscall Software Control •  HW may have multiple levels of interrupt Interrupt NMI Network –  Mask off (disable) certain interrupts, eg., lower priority –  Certain Non-Maskable-Interrupts (NMI) •  Interrupts invoked with interrupt lines from devices •  Interrupt controller chooses interrupt request to honor »  e.g., kernel segmentation fault –  Mask enables/disables interrupts –  Priority encoder picks highest enabled interrupt –  Software Interrupt Set/Cleared by Software –  Interrupt identity specified with ID line •  CPU can disable all interrupts with internal flag •  Non-Maskable Interrupt line (NMI) can’t be disabled 8/30/17 CS162 ©UCB Fall 2017 Lec 3.17 8/30/17 CS162 ©UCB Fall 2017 Lec 3.18 How do we take interrupts safely? Can a process create a process ? •  Interrupt vector •  Yes! Unique identity of process is the “process ID” (or PID) –  Limited number of entry points into kernel •  fork() system call creates a copy of current process with a new PID •  Kernel interrupt stack –  Handler works regardless of state of user code •  Return value from fork(): integer •  Interrupt masking –  When > 0: –  Handler is non-blocking »  Running in (original) Parent process •  Atomic transfer of control »  return value is pid of new child –  “Single instruction”-like to change: –  When = 0: »  Program counter »  Running in new Child process »  Stack pointer –  When < 0: »  Memory protection »  Kernel/user mode »  Error! Must handle somehow •  Transparent restartable execution »  Running in original process –  User program does not know interrupt occurred •  All state of original process duplicated in both Parent and Child! –  Memory, File Descriptors (next topic), etc… 8/30/17 CS162 ©UCB Fall 2017 Lec 3.19 8/30/17 CS162 ©UCB Fall 2017 Lec 3.20 Page 5 

6 . fork1.c fork2.c #include <stdlib.h> #include <stdio.h> #include <string.h> #include <unistd.h> int status; #include <sys/types.h> … #define BUFSIZE 1024 cpid = fork(); int main(int argc, char *argv[]) if (cpid > 0) { /* Parent Process */ { char buf[BUFSIZE]; mypid = getpid(); size_t readlen, writelen, slen; printf("[%d] parent of [%d]\n", mypid, cpid); pid_t cpid, mypid; tcpid = wait(&status); pid_t pid = getpid(); /* get current processes PID */ printf("Parent pid: %d\n", pid); printf("[%d] bye %d(%d)\n", mypid, tcpid, status); cpid = fork(); } else if (cpid == 0) { /* Child Process */ if (cpid > 0) { /* Parent Process */ mypid = getpid(); mypid = getpid(); printf("[%d] child\n", mypid); printf("[%d] parent of [%d]\n", mypid, cpid); } else if (cpid == 0) { /* Child Process */ } mypid = getpid(); … printf("[%d] child\n", mypid); } else { perror("Fork failed"); exit(1); } exit(0); } 8/30/17 CS162 ©UCB Fall 2017 Lec 3.21 8/30/17 CS162 ©UCB Fall 2017 Lec 3.22 Process Races: fork3.c UNIX Process Management int i; cpid = fork(); •  UNIX fork – system call to create a copy of the current if (cpid > 0) { process, and start it running mypid = getpid(); –  No arguments! printf("[%d] parent of [%d]\n", mypid, cpid); for (i=0; i<10; i++) { printf("[%d] parent: %d\n", mypid, i); •  UNIX exec – system call to change the program being run by // sleep(1); } the current process } else if (cpid == 0) { mypid = getpid(); printf("[%d] child\n", mypid); •  UNIX wait – system call to wait for a process to finish for (i=0; i>-10; i--) { printf("[%d] child: %d\n", mypid, i); // sleep(1); •  UNIX signal – system call to send a notification to another } process } •  Question: What does this program print? •  UNIX man pages: fork(2), exec(3), wait(2), signal(3) •  Does it change if you add in one of the sleep() statements? 8/30/17 CS162 ©UCB Fall 2017 Lec 3.23 8/30/17 CS162 ©UCB Fall 2017 Lec 3.24 Page 6 

7 . UNIX Process Management Administrivia: Getting started •  THIS Friday (9/1) is early drop day! Very hard to drop afterwards… fork pid = fork(); exec main () { if (pid == 0) ... exec(...); •  Work on Homework 0 due on Monday! else } –  Get familiar with all the cs162 tools wait(pid); pid = fork(); –  Submit to autograder via git if (pid == 0) exec(...); else •  Participation: Attend section! Get to know your TA! wait(pid); pid = fork(); if (pid == 0) wait •  Group sign up via autograder then TA form next week (after EDD) exec(...); –  Get finding groups of 4 people ASAP else wait(pid); –  Priority for same section; if cannot make this work, keep same TA 8/30/17 CS162 ©UCB Fall 2017 Lec 3.25 8/30/17 CS162 ©UCB Fall 2017 Lec 3.26 Volunteers for RISE Camp? •  RISE Camp 2017, September 7-8 –  Between 130-150 attendees –  Talks and training for the latest software developed by RISE Lab (successor if AMP Lab) •  You’ll get: 5 min break –  Amazon gift certificate for $25 –  An event T-Shirt and –  Free food ;-) –  Talk with people involved in the project •  If interested contact boban@eecs.berkeley.edu or me 8/30/17 CS162 ©UCB Fall 2017 Lec 3.27 Page 7 

8 . Shell Signals – infloop.c •  A shell is a job control system #include <stdlib.h> #include <stdio.h> –  Allows programmer to create and manage a set of programs to top? #include <sys/types.h> do some task #include <unistd.h> G ot –  Windows, MacOS, Linux all have shells #include <signal.h> void signal_callback_handler(int signum) •  Example: to compile a C program { printf("Caught signal %d - phew!\n",signum); cc –c sourcefile1.c HW1 exit(1); cc –c sourcefile2.c } ln –o program sourcefile1.o sourcefile2.o int main() { ./program signal(SIGINT, signal_callback_handler); while (1) {} } 8/30/17 CS162 ©UCB Fall 2017 Lec 3.29 8/30/17 CS162 ©UCB Fall 2017 Lec 3.30 Recall: UNIX System Structure How Does the Kernel Provide Services? •  You said that applications request services from the operating system via syscall, but … Applications User Mode •  I’ve been writing all sort of useful applications and I never ever Standard Libs saw a “syscall” !!! •  That’s right. Kernel Mode •  It was buried in the programming language runtime library (e.g., libc.a) •  … Layering Hardware 8/30/17 CS162 ©UCB Fall 2017 Lec 3.31 8/30/17 CS162 ©UCB Fall 2017 Lec 3.32 Page 8 

9 . OS Run-Time Library A Kind of Narrow Waist Word Processing Proc Proc Proc Compilers Web Browsers 1 2 … n Email Databases Web Servers Application / Service OS Appln login Window Portable OS Library OS Manager User System Call Interface … System Portable OS Kernel OS library OS library OS library Software Platform support, Device Drivers OS Hardware x86 PowerPC ARM PCI Ethernet (1Gbs/10Gbs) 802.11 a/g/n/ac SCSI Graphics Thunderbolt 8/30/17 CS162 ©UCB Fall 2017 Lec 3.33 8/30/17 CS162 ©UCB Fall 2017 Lec 3.34 Key Unix I/O Design Concepts I/O & Storage Layers •  Uniformity –  file operations, device I/O, and interprocess communication through Application / Service open, read/write, close streams –  Allows simple composition of programs High Level I/O »  find | grep | wc … Low Level I/O handles •  Open before use Syscall registers –  Provides opportunity for access control and arbitration File System descriptors –  Sets up the underlying machinery, i.e., data structures •  Byte-oriented I/O Driver Commands and Data Transfers –  Even if blocks are transferred, addressing is in bytes Disks, Flash, Controllers, DMA •  Kernel buffered reads –  Streaming and block devices looks the same –  read blocks process, yielding processor to other task •  Kernel buffered writes –  Completion of out-going transfer decoupled from the application, allowing it to continue •  Explicit close 8/30/17 CS162 ©UCB Fall 2017 Lec 3.35 8/30/17 CS162 ©UCB Fall 2017 Lec 3.36 Page 9 

10 . Summary The File System Abstraction •  Process: execution environment with Restricted Rights •  High-level idea –  Files live in hierarchical namespace of filenames –  Address Space with One or More Threads •  File –  Owns memory (address space) –  Named collection of data in a file system –  Owns file descriptors, file system context, … –  File data –  Encapsulate one or more threads sharing process resources »  Text, binary, linearized objects –  File Metadata: information about the file •  Interrupts »  Size, Modification Time, Owner, Security info –  Hardware mechanism for regaining control from user »  Basis for access control –  Notification that events have occurred •  Directory –  User-level equivalent: Signals –  “Folder” containing files & Directories •  Native control of Process –  Hierachical (graphical) naming »  Path through the directory graph –  Fork, Exec, Wait, Signal »  Uniquely identifies a file or directory •  Basic Support for I/O • /home/ff/cs162/public_html/fa16/index.html –  Standard interface: open, read, write, seek –  Links and Volumes (later) –  Device drivers: customized interface to hardware 8/30/17 CS162 ©UCB Fall 2017 Lec 3.37 8/30/17 CS162 ©UCB Fall 2017 Lec 3.38 Page 10