1Lecture 2ProcessesSeptember 30, 2003Prof. Joe PasqualeDepartment of Computer Science and EngineeringUniversity of California, San Diego© 2003 by Joseph PasqualeCSE 120: Principles of Operating Systems2Before We Begin …Read Chapters 4 and 5 (on Processes and Threads)• for background and overview, read Chapters 1-3Discussion section: Wednesdays 12-1, HSS 13303IntroductionMost fundamental kernel function: run a programUsers want ability to run multiple programs at onceHow is this achieved given single CPU and memory?4What is a Process?Abstraction of a running program• “a program in execution”Dynamic• has state, changes over time• whereas a program is staticBasic operations• start/end, suspend/resume,send/receive messages5Goal: Support Multiple ProcessesUsers would like multiple programs running at same time• some are more important, foreground/background• not all actively using the CPU• some waiting for input, devices (e.g., disk), …How to do this given single CPU (or small number)?browser editor email calendar6MultiprogrammingGiven a running process• at some point, it needs a resource, e.g., I/O device• say resource is busy, process can’t proceed• so, “voluntarily” gives up CPU to another processYield (p)• let process p run (voluntarily give up CPU to p)• requires context switching7Process Memory StructureText• code: program instructionsData• global variables• heap (dynamic allocation)Stack• activation records• automatic growth/shrinkageTextDataStack8Process StackStack of activation records• one per pending procedureEach activation record stores• where to return to• link to previous record• automatic (local) variablesStack pointer points to last record• RETURN instruction relies on itLocal var n...Local var 1Return addressPrevious recordLocal var n...Local var 1Return addressPrevious record...9Context SwitchingAllocating CPU to a process requires context switching• first, save context of currently running process• next, load context of next process to runLoading the context• load general registers, stack pointer, etc.• load the program counter (must be last instruction)10Simple Context SwitchingTwo processes: P1 and P2P1 calls yield () to voluntarily give up CPU to P2Save and restore registers• general-purpose, stack pointer, program counterSwitch text and data (not necessary if shared: threads)Switch stacks: note that PC is in the middle of yield ()!11The Magic of yield ()magic = 0Save P1’s context• GP (general purpose) registers, SP (stack pointer)• Lastly, PC (program counter); note, inside yield!If (magic == 1) return, else magic = 1Restore P2’s context• GP registers, SP• Lastly, restore PC12In this example, P1 is about to set x to 7 and yield to P2.P2 had already yielded to P1: note P2’s saved PC and SP.return topreviousmagic: 1stackmain (){ x = 7 yield () ... }yield (){ magic = 0 save p1.context if magic == 1 ret else magic = 1 restore p2.context }PCSPP1textdatastackX: ?Not shown are declarations:x is a global variable (in eachprocess), and magic is a localvariable in yield ().main (){ x = 11 yield () ... }yield (){ magic = 0 save p2.context if magic == 1 ret else magic = 1 restore p1.context }P2textdataX: 11return topreviousmagic: 1stack(why is this 1?)p1.context: ... PC SPp2.context: ... PC SPshared memory13P1 has just set x to 7 and is about to call yield. The PCalways points to the instruction to be executed next.main (){ x = 7 yield () ... }yield (){ magic = 0 save p1.context if magic == 1 ret else magic = 1 restore p2.context }PCSPP1textdatastackX: 7main (){ x = 11 yield () ... }yield (){ magic = 0 save p2.context if magic == 1 ret else magic = 1 restore p1.context }P2textdataX: 11return topreviousmagic: 1stackp1.context: ... PC SPp2.context: ... PC SPshared memory14Upon entering yield, an activation record is pushed onthe stack. It contains links, and local variable magic.return topreviousmagic: ?stackmain (){ x = 7 yield () ... }yield (){ magic = 0 save p1.context if magic == 1 ret else magic = 1 restore p2.context }PCSPP1textdataX: 7main (){ x = 11 yield () ... }yield (){ magic = 0 save p2.context if magic == 1 ret else magic = 1 restore p1.context }P2textdataX: 11return topreviousmagic: 1stackp1.context: ... PC SPp2.context: ... PC SPshared memory15Magic, an automatic variable because it is dynamicallyallocated on the stack, is set to 0. Next: save context.return topreviousmagic: 0stackmain (){ x = 7 yield () ... }yield (){ magic = 0 save p1.context if magic == 1 ret else magic = 1 restore p2.context }PCSPP1textdataX: 7main (){ x = 11 yield () ... }yield (){ magic = 0 save p2.context if magic == 1 ret else magic = 1 restore p1.context }P2textdataX: 11return topreviousmagic: 1stackp1.context: ... PC SPp2.context: ... PC SPshared memory16P1’s context is now saved. The saved PC points just afterthe save context. Compare this to P2’s saved context.return topreviousmagic: 0stackmain (){ x = 7 yield () ... }yield (){ magic = 0 save p1.context if magic == 1 ret else magic = 1 restore p2.context }PCSPP1textdataX: 7main (){ x = 11 yield () ... }yield (){ magic = 0 save p2.context if magic == 1 ret else magic = 1 restore p1.context }P2textdataX: 11return topreviousmagic: 1stackp1.context: ... PC SPp2.context: ... PC SPshared memory17P1 just checked whether magic equals 1, which was false,and so, on to the else clause to set magic to 1.return topreviousmagic: 0stackmain (){ x = 7 yield () ... }yield (){ magic = 0 save p1.context if magic == 1 ret else magic = 1 restore p2.context }PCSPP1textdataX: 7main (){ x = 11 yield () ... }yield (){ magic = 0 save p2.context if magic == 1 ret else magic = 1 restore p1.context }P2textdataX: 11return topreviousmagic: 1stackp1.context: ... PC SPp2.context: ... PC SPshared memory18P1 sets magic to 1, and is about to restore P2’s context(just like P2’s situation when it restored P1’s context).return topreviousmagic: 1stackmain (){ x = 7 yield () ... }yield (){ magic = 0 save p1.context if magic == 1 ret else magic = 1 restore p2.context }PCSPP1textdataX: 7main (){ x = 11 yield () ... }yield (){ magic = 0 save p2.context if magic == 1 ret else magic = 1 restore p1.context }P2textdataX: 11return topreviousmagic: 1stackp1.context: ... PC SPp2.context: ... PC SPshared memory19P2’s
View Full Document
Unlocking...