网络、(进程和线程)并发的简介

1 . So what happens when you fgetc? CS162 Application / Service Operating Systems and Systems Programming High Level I/O streams handles Lecture 5 Low Level I/O registers Syscall descriptors Introduction to Networking, File System Concurrency (Processes and Threads) I/O Driver Commands and Data Transfers Disks, Flash, Controllers, DMA September 11th, 2017 Prof. Ion Stoica http://cs162.eecs.Berkeley.edu 9/11/17 CS162 ©UCB Fall 2017 Lec 5.2 Communication between processes Communication Across the world looks like file IO •  Can we view files as communication channels? write(wfd, wbuf, wlen); write(wfd, wbuf, wlen); n = read(rfd,rbuf,rmax); n = read(rfd,rbuf,rmax); •  Producer and Consumer of a file may be distinct processes –  May be separated in time (or not) •  Connected queues over the Internet –  But what’s the analog of open? •  However, what if data written once and consumed once? –  What is the namespace? –  Don’t we want something more like a queue? –  How are they connected in time? –  Can still look like File I/O! 9/11/17 CS162 ©UCB Fall 2017 Lec 5.3 9/11/17 CS162 ©UCB Fall 2017 Lec 5.4 Page 1 

2 . Request Response Protocol Request Response Protocol Client (issues requests) Server (performs operations) Client (issues requests) Server (performs operations) write(rqfd, rqbuf, buflen); write(rqfd, rqbuf, buflen); requests requests n = read(rfd,rbuf,rmax); n = read(rfd,rbuf,rmax); wait service request wait service request write(wfd, respbuf, len); write(wfd, respbuf, len); responses responses n = read(resfd,resbuf,resmax); n = read(resfd,resbuf,resmax); 9/11/17 CS162 ©UCB Fall 2017 Lec 5.5 9/11/17 CS162 ©UCB Fall 2017 Lec 5.6 Client-Server Models Sockets •  Socket: an abstraction of a network I/O queue –  Mechanism for inter-process communication Client 1 –  Embodies one side of a communication channel »  Same interface regardless of location of other end »  Local machine (“UNIX socket”) or remote machine (“network socket”) Client 2 Server –  First introduced in 4.2 BSD UNIX: big innovation at time »  Now most operating systems provide some notion of socket *** •  Data transfer like files –  Read / Write against a descriptor Client n •  Over ANY kind of network –  Local to a machine –  Over the internet (TCP/IP, UDP/IP) •  File servers, web, FTP, Databases, … –  OSI, Appletalk, SNA, IPX, SIP, NS, … •  Many clients accessing a common server 9/11/17 CS162 ©UCB Fall 2017 Lec 5.7 9/11/17 CS162 ©UCB Fall 2017 Lec 5.8 Page 2 

3 . Silly Echo Server – running example Echo client-server example void client(int sockfd) { Client (issues requests) Server (performs operations) int n; char sndbuf[MAXIN]; char rcvbuf[MAXOUT]; getreq(sndbuf, MAXIN); /* prompt */ gets(fd,sndbuf, …); while (strlen(sndbuf) > 0) { write(sockfd, sndbuf, strlen(sndbuf)); /* send */ memset(rcvbuf,0,MAXOUT); /* clear */ requests n=read(sockfd, rcvbuf, MAXOUT-1); /* receive */ write(fd, buf,len); write(STDOUT_FILENO, rcvbuf, n); /* echo */ n = read(fd,buf,); getreq(sndbuf, MAXIN); /* prompt */ } } wait print void server(int consockfd) { write(fd, buf,); char reqbuf[MAXREQ]; responses int n; while (1) { memset(reqbuf,0, MAXREQ); n = read(consockfd,reqbuf,MAXREQ-1); /* Recv */ n = read(fd,rcvbuf, ); if (n <= 0) return; n = write(STDOUT_FILENO, reqbuf, strlen(reqbuf)); print n = write(consockfd, reqbuf, strlen(reqbuf)); /* echo*/ } } 9/11/17 CS162 ©UCB Fall 2017 Lec 5.9 9/11/17 CS162 ©UCB Fall 2017 Lec 5.10 Prompt for input Socket creation and connection •  File systems provide a collection of permanent objects in structured name space char *getreq(char *inbuf, int len) { –  Processes open, read/write/close them /* Get request char stream */ –  Files exist independent of the processes printf("REQ: "); /* prompt */ memset(inbuf,0,len); /* clear for good measure */ return fgets(inbuf,len,stdin); /* read up to a EOL */ } •  Sockets provide a means for processes to communicate (transfer data) to other processes. •  Creation and connection is more complex •  Form 2-way pipes between processes –  Possibly worlds away 9/11/17 CS162 ©UCB Fall 2017 Lec 5.11 9/11/17 CS162 ©UCB Fall 2017 Lec 5.12 Page 3 

4 . Namespaces for communication over IP Using Sockets for Client-Server (C/C++) •  Hostname •  On server: set up “server-socket” –  www.eecs.berkeley.edu –  Create socket; bind to protocol (TCP), local address, port –  Call listen(): tells server socket to accept incoming requests •  IP address –  Perform multiple accept() calls on socket to accept incoming –  128.32.244.172 (IPv4 32-bit) connection request –  fe80::4ad7:5ff:fecf:2607 (IPv6 128-bit) –  Each successful accept() returns a new socket for a new connection; can pass this off to handler thread •  Port Number –  0-1023 are “well known” or “system” ports •  On client: »  Superuser privileges to bind to one –  Create socket; bind to protocol (TCP), remote address, port –  1024 – 49151 are “registered” ports (registry) –  Perform connect() on socket to make connection »  Assigned by IANA for specific services –  If connect() successful, have socket connected to server –  49152–65535 (215+214 to 216−1) are “dynamic” or “private” »  Automatically allocated as “ephemeral Ports” 9/11/17 CS162 ©UCB Fall 2017 Lec 5.13 9/11/17 CS162 ©UCB Fall 2017 Lec 5.14 Socket Setup over TCP/IP Example: Server Protection and Parallelism Server Client Server Socket Create Server Socket tion nnec u e st Co new Req socket Create Client Socket Bind it to an Address (host:port) socket connection socket Connect it to server (host:port) Listen for Connection Client Server Accept connection •  Server Socket: Listens for new connections child Connection Parent –  Produces new sockets for each unique connection Close Listen Socket Socket Close Connection •  Things to remember: write request read request Socket –  Connection involves 5 values: read response write response [ Client Addr, Client Port, Server Addr, Server Port, Protocol ] Close Server Socket –  Often, Client Port “randomly” assigned by OS during client socket setup Close Client Socket Close Connection Socket –  Server Port often “well known” (0-1023) »  80 (web), 443 (secure web), 25 (sendmail), etc 9/11/17 CS162 ©UCB Fall 2017 Lec 5.15 9/11/17 CS162 ©UCB Fall 2017 Lec 5.16 Page 4 

5 . Server Protocol (v3) Server Address - Itself struct sockaddr_in { listen(lstnsockfd, MAXQUEUE); short sin_family; while (1) { unsigned short sin_port; consockfd = accept(lstnsockfd, (struct sockaddr *) &cli_addr, struct in_addr sin_addr; &clilen); char sin_zero[8]; cpid = fork(); /* new process for connection */ } serv_addr; if (cpid > 0) { /* parent process */ close(consockfd); //tcpid = wait(&cstatus); memset((char *) &serv_addr,0, sizeof(serv_addr)); } else if (cpid == 0) { /* child process */ serv_addr.sin_family = AF_INET; close(lstnsockfd); /* let go of listen socket */ serv_addr.sin_addr.s_addr = INADDR_ANY; serv_addr.sin_port = htons(portno); server(consockfd); •  Simple form close(consockfd); exit(EXIT_SUCCESS); /* exit child normally */ •  Internet Protocol } } •  accepting any connections on the specified port close(lstnsockfd); •  In “network byte ordering” (which is big endian) 9/11/17 CS162 ©UCB Fall 2017 Lec 5.17 9/11/17 CS162 ©UCB Fall 2017 Lec 5.18 Client: Getting the Server Address Administrivia struct hostent *buildServerAddr(struct sockaddr_in *serv_addr, •  TA preferences due tonight at 11:59PM char *hostname, int portno) { struct hostent *server; –  We will try to accommodate your needs, but have to balance both over-popular and under-popular sections /* Get host entry associated with a hostname or IP address */ server = gethostbyname(hostname); if (server == NULL) { •  Attend section and get to know your TAs! fprintf(stderr,"ERROR, no such host\n"); exit(1); } /* Construct an address for remote server */ memset((char *) serv_addr, 0, sizeof(struct sockaddr_in)); serv_addr->sin_family = AF_INET; bcopy((char *)server->h_addr, (char *)&(serv_addr->sin_addr.s_addr), server->h_length); serv_addr->sin_port = htons(portno); return server; } 9/11/17 CS162 ©UCB Fall 2017 Lec 5.19 9/11/17 CS162 ©UCB Fall 2017 Lec 5.20 Page 5 

6 . Recall: Traditional UNIX Process •  Process: OS abstraction of what is needed to run a single program –  Often called a “Heavyweight Process” –  No concurrency in a “Heavyweight Process” •  Two parts: –  Sequential program execution stream [ACTIVE PART] »  Code executed as a sequential stream of execution (i.e., thread) »  Includes State of CPU registers BREAK –  Protected resources [PASSIVE PART]: »  Main memory state (contents of Address Space) »  I/O state (i.e. file descriptors) 9/11/17 CS162 ©UCB Fall 2017 Lec 5.21 9/11/17 CS162 ©UCB Fall 2017 Lec 5.22 How do we Multiplex Processes? CPU Switch From Process A to Process B •  The current state of process held in a process control block (PCB): –  This is a “snapshot” of the execution and protection environment –  Only one PCB active at a time •  Give out CPU time to different processes (Scheduling): –  Only one process “running” at a time –  Give more time to important processes •  Give pieces of resources to different processes (Protection): –  Controlled access to non-CPU resources •  This is also called a “context switch” –  Example mechanisms: •  Code executed in kernel above is overhead »  Memory Mapping: Give each process their own Process address space Control –  Overhead sets minimum practical switching time »  Kernel/User duality: Arbitrary multiplexing of I/O Block –  Less overhead with SMT/hyperthreading, but… contention for through system calls resources instead 9/11/17 CS162 ©UCB Fall 2017 Lec 5.23 9/11/17 CS162 ©UCB Fall 2017 Lec 5.24 Page 6 

7 . Lifecycle of a Process Process Scheduling •  As a process executes, it changes state: –  new: The process is being created –  ready: The process is waiting to run •  PCBs move from queue to queue as they change state –  running: Instructions are being executed –  Decisions about which order to remove from queues are Scheduling –  waiting: Process waiting for some event to occur decisions –  terminated: The process has finished execution –  Many algorithms possible (few weeks from now) 9/11/17 CS162 ©UCB Fall 2017 Lec 5.25 9/11/17 CS162 ©UCB Fall 2017 Lec 5.26 Ready Queue And Various I/O Device Queues Modern Process with Threads •  Process not running ⇒ PCB is in some scheduler queue –  Separate queue for each device/signal/condition •  Thread: a sequential execution stream within process –  Each queue can have a different scheduler policy (Sometimes called a “Lightweight process”) –  Process still contains a single Address Space Ready Head Link Link Link Queue Tail Registers Registers Registers –  No protection between threads Other Other Other Head State State State USB Unit 0 Tail PCB9 PCB6 PCB16 •  Multithreading: a single program made up of a number of different concurrent activities Disk Head Link Link Unit 0 –  Sometimes called multitasking, as in Ada … Tail Registers Registers Other Other Disk Head State State Unit 2 Tail PCB2 PCB3 •  Why separate the concept of a thread from that of a process? Link –  Discuss the “thread” part of a process (concurrency) Ether Head Netwk 0 Registers –  Separate from the “address space” (protection) Tail Other State –  Heavyweight Process ≡ Process with one thread PCB8 9/11/17 CS162 ©UCB Fall 2017 Lec 5.27 9/11/17 CS162 ©UCB Fall 2017 Lec 5.28 Page 7 

8 . Single and Multithreaded Processes Thread State •  State shared by all threads in process/address space –  Content of memory (global variables, heap) –  I/O state (file descriptors, network connections, etc) •  State “private” to each thread –  Kept in TCB ≡ Thread Control Block –  CPU registers (including, program counter) –  Execution stack – what is this? •  Threads encapsulate concurrency: “Active” component •  Execution Stack •  Address spaces encapsulate protection: “Passive” part –  Parameters, temporary variables –  Keeps buggy program from trashing the system –  Return PCs are kept while called procedures are executing •  Why have multiple threads per address space? 9/11/17 CS162 ©UCB Fall 2017 Lec 5.29 9/11/17 CS162 ©UCB Fall 2017 Lec 5.30 Shared vs. Per-Thread State Execution Stack Example Shared Per−Thread Per−Thread A(int tmp) { A: tmp=1 ret=exit Stack State State State if (tmp<2) Pointer B: ret=A+2 Thread Control Thread Control B(); Heap Block (TCB) Block (TCB) printf(tmp); C: ret=b+1 Stack Stack } A: tmp=2 Information Information ret=C+1 B() { Saved Saved Global Registers Registers C(); Variables Thread Thread } Stack Growth Metadata Metadata C() { •  Stack holds temporary results A(2); Stack Stack •  Permits recursive execution } Code •  Crucial to modern languages A(1); 9/11/17 CS162 ©UCB Fall 2017 Lec 5.31 9/11/17 CS162 ©UCB Fall 2017 Lec 5.32 Page 8 

9 . MIPS: Software conventions for Registers Motivational Example for Threads 0 zero constant 0 16 s0 callee saves 1 at reserved for assembler . . . (callee must save) •  Imagine the following C program: 2 v0 expression evaluation & 23 s7 3 v1 function results 24 t8 temporary (cont’d) main() { 4 a0 arguments 25 t9 ComputePI(̎pi.txt̎); 5 a1 26 k0 reserved for OS kernel PrintClassList(̎classlist.txt̎); 6 a2 27 k1 } 7 a3 28 gp Pointer to global area 8 t0 temporary: caller saves 29 sp Stack pointer •  What is the behavior here? ... (callee can clobber) 30 fp frame pointer –  Program would never print out class list 15 t7 31 ra Return Address (HW) –  Why? ComputePI would never finish •  Before calling procedure: •  After return, assume –  Save caller-saves regs –  Callee-saves reg OK –  Save v0, v1 –  gp,sp,fp OK (restored!) –  Save ra –  Other things trashed 9/11/17 CS162 ©UCB Fall 2017 Lec 5.33 9/11/17 CS162 ©UCB Fall 2017 Lec 5.34 Use of Threads Memory Footprint: Two-Threads •  Version of program with Threads (loose syntax): main() { •  If we stopped this program and examined it with a debugger, we would see ThreadFork(ComputePI, ̎pi.txt̎)); ThreadFork(PrintClassList, ̎classlist.txt̎)); –  Two sets of CPU registers Stack 1 } –  Two sets of Stacks •  What does ThreadFork() do? •  Questions: Stack 2 Address Space –  Start independent thread running given procedure –  How do we position stacks relative to •  What is the behavior here? each other? –  Now, you would actually see the class list –  What maximum size should we choose –  This should behave as if there are two separate CPUs for the stacks? Heap –  What happens if threads violate this? CPU1 CPU2 CPU1 CPU2 CPU1 CPU2 Global Data –  How might you catch violations? Code Time 9/11/17 CS162 ©UCB Fall 2017 Lec 5.35 9/11/17 CS162 ©UCB Fall 2017 Lec 5.36 Page 9 

10 . Actual Thread Operations Dispatch Loop •  thread_fork(func, args) •  Conceptually, the dispatching loop of the operating system –  Create a new thread to run func(args) looks as follows: –  Pintos: thread_create •  thread_yield() Loop { –  Relinquish processor voluntarily RunThread(); –  Pintos: thread_yield ChooseNextThread(); SaveStateOfCPU(curTCB); •  thread_join(thread) LoadStateOfCPU(newTCB); –  In parent, wait for forked thread to exit, then return } –  Pintos: thread_join •  thread_exit •  This is an infinite loop –  Quit thread and clean up, wake up joiner if any –  One could argue that this is all that the OS does –  Pintos: thread_exit •  Should we ever exit this loop??? •  pThreads: POSIX standard for thread programming –  When would that be? [POSIX.1c, Threads extensions (IEEE Std 1003.1c-1995)] 9/11/17 CS162 ©UCB Fall 2017 Lec 5.37 9/11/17 CS162 ©UCB Fall 2017 Lec 5.38 Running a thread Internal Events Consider first portion: RunThread() •  Blocking on I/O –  The act of requesting I/O implicitly yields the CPU •  How do I run a thread? •  Waiting on a “signal” from other thread –  Load its state (registers, PC, stack pointer) into CPU –  Thread asks to wait and thus yields the CPU –  Load environment (virtual memory space, etc) •  Thread executes a yield() –  Jump to the PC –  Thread volunteers to give up CPU •  How does the dispatcher get control back? computePI() { –  Internal events: thread returns control voluntarily while(TRUE) { –  External events: thread gets preempted ComputeNextDigit(); yield(); } } 9/11/17 CS162 ©UCB Fall 2017 Lec 5.39 9/11/17 CS162 ©UCB Fall 2017 Lec 5.40 Page 10 

11 . Stack for Yielding Thread What Do the Stacks Look Like? ComputePI •  Consider the following code blocks: Stack growth yield Trap to OS proc A() { Thread S Thread T kernel_yield B(); A A Stack growth run_new_thread switch } B(while) B(while) •  How do we run a new thread? proc B() { yield yield run_new_thread() { while(TRUE) { yield(); run_new_thread run_new_thread newThread = PickNewThread(); switch(curThread, newThread); } switch switch ThreadHouseKeeping(); /* Do any cleanup */ } } •  Suppose we have 2 •  How does dispatcher switch to a new thread? threads: –  Save anything next thread may trash: PC, regs, stack pointer –  Threads S and T –  Maintain isolation for each thread 9/11/17 CS162 ©UCB Fall 2017 Lec 5.41 9/11/17 CS162 ©UCB Fall 2017 Lec 5.42 Saving/Restoring state (often called “Context Switch) Switch Details (continued) Switch(tCur,tNew) { •  What if you make a mistake in implementing switch? /* Unload old thread */ –  Suppose you forget to save/restore register 32 TCB[tCur].regs.r7 = CPU.r7; –  Get intermittent failures depending on when context switch occurred and … whether new thread uses register 32 TCB[tCur].regs.r0 = CPU.r0; –  System will give wrong result without warning TCB[tCur].regs.sp = CPU.sp; •  Can you devise an exhaustive test to test switch code? TCB[tCur].regs.retpc = CPU.retpc; /*return addr*/ –  No! Too many combinations and inter-leavings •  Cautionary tale: /* Load and execute new thread */ –  For speed, Topaz kernel saved one instruction in switch() CPU.r7 = TCB[tNew].regs.r7; –  Carefully documented! Only works as long as kernel size < 1MB … CPU.r0 = TCB[tNew].regs.r0; –  What happened? »  Time passed, People forgot CPU.sp = TCB[tNew].regs.sp; »  Later, they added features to kernel (no one removes features!) CPU.retpc = TCB[tNew].regs.retpc; »  Very weird behavior started happening return; /* Return to CPU.retpc */ –  Moral of story: Design for simplicity } 9/11/17 CS162 ©UCB Fall 2017 Lec 5.43 9/11/17 CS162 ©UCB Fall 2017 Lec 5.44 Page 11 

12 . Summary •  Processes have two parts –  One or more Threads (Concurrency) –  Address Spaces (Protection) •  Concurrency accomplished by multiplexing CPU Time: –  Unloading current thread (PC, registers) –  Loading new thread (PC, registers) –  Such context switching may be voluntary (yield(), I/O operations) or involuntary (timer, other interrupts) 9/11/17 CS162 ©UCB Fall 2017 Lec 5.45 Page 12