Announcements!Project Session #1– video on-line, slides will be posted!Assignment #1 out today– due Tue., July 8th, 10 p.m.start now (tricky sync. debugging)Andrew Birrell Paper (cs140/info)!C/NC? allowed, but not advisable– - you’ll do the same amount of work– - tell your teammates if C/NC!1More OS motivation!ISCA keynote, Justin Rattner (intel)- processors at (3GHz) wall- emphasis on “meaningful” performance- processor architecture -> system architecture- BL: OS affects responsiveness- when you do things matters: scheduling!Chrysler: 30 GB hard drive, WiFi hot spot- cars contain many embedded computers- reboot? slowdown? crash?- different time/reliability requirements vs. PC- protection, scheduling2Today’s adventure!What are threads, processes?!What are they for?!How do they work?!Threads vs. processes?!Concurrency (will continue Monday)!Readings: 7th ed: Silberschatz/Galvin: Ch. 3 (skip 3.{4-6}), 4, 66th ed: Silberschatz/Galvin: Ch. 4 (skip 4.{5,6}), 5, 7!Hundreds of things going on in system!How to make simple? – Separate each in isolated process. OS deals with one thing at a time, they just deal with OS– *THE* universal trick for managing complexity: decomposition (“reductionism”)Why processes? SimplicitygccemacsnfsdlprlswwwemacsnfsdlprlswwwOSOS!I/O parallelism:– Overlap execution: make 1 CPU into many– (Real parallelism: > 1 CPU (multiprocessing))!Completion time:– B’s completion time = 100s (A + B) So overlapWhy processes? Speedemacs(Wait for input)(Wait for input)gccABAB20 s80 sCompletion time for B? A?10 sProcesses in the real world!Processes, parallelism fact of life much longer than OSes have been around– Companies use parallelism for more throughput: 1 worker = 100 widgets? hire 100 to make 10,000.!Can you always partition work to speed up job?– Ideal: N-fold speedup– Reality: bottlenecks + coordination overhead– Example: CS140 group project– (More abstractly: easy to increase throughput, reducing latency more difficult)CS 140 - Summer 2008 - Handout #2What is a thread?!In theory: Turing machine– tape (state), tape head (position)!In practice: What’s needed to run code on CPU– “execution stream in an execution context” – Execution stream: sequential seq. of instructions!CPU execution context (1 thread)– State: stack, heap, registers – Position: program counter register!OS execution context (n threads):– identity + open file descriptors, page table, … add r1, r2, r3 sub r2, r3, r10st r2, 0(r1)… What is a process?!Process: thread + address space– or, abstraction representing what you need to run thread on OS (open files, etc)!Address space: encapsulates protection– address state passive, threads active!Why separate thread, process?– Many situations where you want multiple threads per address space (servers, OS, parallel app, user app?)Firefox int c; int main() { printf(“hello”);}Process != Program!Program: code + data– passive!Process: running program– state: registers, stack, heap…– position: Program counter!We both run Firefox:– same program, different processstackheapdatacodeint a;main()How to make one?!Creation:– Load code and data into memory; create empty call stack.– Initialize state to same as after a process switch.– Put on OS’s list of processes.!Clone:– Stop current process and save state.– Make copy of current code,– data, stack and OS state. – Add new process to OS’s list of processesgccgcc gccExample: Unix!How to make processes:– Fork clones a process.– Exec overlays the current process.– No create! Fork then exec.!Pros: Simple, clean. Con: duplicate operationsif((pid = fork()) == 0) { /* child process */ exec(“foo”); /* exec does not return */else /* parent */ wait(pid); /* wait for child to finish */Examples: WindowsBOOL CreateProcess( LPCTSTR lpApplicationName, // pointer to name of executable module LPTSTR lpCommandLine, // pointer to command line string LPSECURITY_ATTRIBUTES lpProcessAttributes, // process security attr. LPSECURITY_ATTRIBUTES lpThreadAttributes, // thread security attr. BOOL bInheritHandles, // handle inheritance flag DWORD dwCreationFlags, // creation flags LPVOID lpEnvironment, // pointer to new environment block LPCTSTR lpCurrentDirectory, // pointer to current directory name LPSTARTUPINFO lpStartupInfo, // pointer to STARTUPINFO LPPROCESS_INFORMATION lpProcessInformation // pointer to PROCESS_INFORMATION );Process environments!Uniprogramming: 1 process at a time– “Cooperative timesharing”: mostly PCs, vintage OSes– Easy for OS, hard for user (generally).– Violates isolation: Infinite loops?– When should process yield?!Multiprogramming: > 1 process at time– Time-sharing: CTSS, Multics, Unix, VMS, NT, ...– Multiprogramming != multiprocessing OSOSThe multithreading illusion!Each thread has its illusion of own CPU– yet on a uni-processor all threads share the same physical CPU!– How does this work?!Two key pieces:– thread control block (in Pintos: thread class): one per thread, holds execution state– dispatching loop:CPUwhile(1) interrupt thread save state get next thread load state, jump to itThe multiprogramming problems!Track state? PCB (process control block)– Thread state, plus OS state: identify, accounting, …!N processes? Whom to run? (“Scheduling”)– Need to schedule whenever 1 resource & many “things” (disk, net, CPU, classroom, …) !Protection? Need two things: – Prevent process from getting at another’s state – Fairness: make sure each process gets to run– (No protection? system crashes ~ O(# of processes)Priority registers open file descriptors, ...pcbProcess states!Processes in three states: – Running: executing now– Ready: waiting for CPU– Blocked: waiting for another event (I/O, lock)!Which ready process to pick?– 0 ready processes: run idle loop– 1 ready process: easy!– > 1: what to do? running readyblockedPicking a process to run!Scan process table for first runnable?– Expensive. Weird priorities (small pid’s better)– Divide into runnable and blocked processes!FIFO?– Put threads on back of list, pull them off from front– (pintos does this: thread.c)!Priority?– Give some threads a better shot at the CPU– problem?Scheduling policies!Scheduling issues– Fairness: don’t starve process– Prioritize: more important first– Deadlines:
View Full Document
Unlocking...