Review Scheduling selecting a waiting process from the ready queue and allocating the CPU to it FCFS Scheduling CS162 Operating Systems and Systems Programming Lecture 11 Run threads to completion in order of submission Pros Simple Cons Short jobs get stuck behind long ones Protection Address Spaces Round Robin Scheduling Give each thread a small amount of CPU time when it executes cycle between all ready threads Pros Better for short jobs Cons Poor when jobs are same length March 5 2008 Prof Anthony D Joseph http inst eecs berkeley edu cs162 3 5 08 Review Joseph CS162 UCB Spring 2008 Lec 11 2 Goals for Today Shortest Job First SJF Shortest Remaining Time First SRTF Kernel vs User Mode What is an Address Space How is it Implemented Run whatever job has the least amount of computation to do least remaining amount of computation to do Pros Optimal average response time Cons Hard to predict future Unfair Multi Level Feedback Scheduling Multiple queues of different priorities Automatic promotion demotion of process priority in order to approximate SJF SRTF Lottery Scheduling Give each thread a priority dependent number of tokens short tasks more tokens Reserve a minimum number of tokens for every thread to ensure forward progress fairness Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and Gagne Evaluation of mechanisms Analytical Queuing Theory Simulation 3 5 08 Joseph CS162 UCB Spring 2008 3 5 08 Lec 11 3 Page 1 Joseph CS162 UCB Spring 2008 Lec 11 4 Virtualizing Resources Recall Single and Multithreaded Processes Physical Reality Different Processes Threads share the same hardware Need to multiplex CPU Just finished scheduling Need to multiplex use of Memory Today Need to multiplex disk and devices later in term Why worry about memory sharing The complete working state of a process and or kernel is defined by its data in memory and registers Consequently cannot just let different threads of control use the same memory Threads encapsulate concurrency Active component of a process Address spaces encapsulate protection Physics two different pieces of data cannot occupy the same locations in memory Probably don t want different threads to even have access to each other s memory protection 3 5 08 Joseph CS162 UCB Spring 2008 3 5 08 Lec 11 5 Important Aspects of Memory Multiplexing Lec 11 6 Choose addresses for instructions and data from the standpoint of the processor Separate state of threads should not collide in physical memory Obviously unexpected overlap causes chaos Conversely would like the ability to overlap when desired for communication data1 dw 32 start lw r1 0 data1 jal checkit loop addi r1 r1 1 bnz r1 r0 loop checkit Translation Ability to translate accesses from one address space virtual to a different one physical When translation exists processor uses virtual addresses physical memory uses physical addresses Side effects Can be used to avoid overlap Can be used to give uniform view of memory to programs 0x300 0x900 0x904 0x908 0x90C 0xD00 00000020 8C2000C0 0C000340 2021FFFF 1420FFFF Could we place data1 start and or checkit at different addresses Protection Yes When Compile time Load time Execution time Prevent access to private memory of other processes Different pages of memory can be given special behavior Read Only Invisible to user programs etc Kernel data protected from User programs Programs protected from themselves Joseph CS162 UCB Spring 2008 Joseph CS162 UCB Spring 2008 Binding of Instructions and Data to Memory Binding of instructions and data to addresses Controlled overlap 3 5 08 Keeps buggy program from trashing the system Passive component of a process Related which physical memory locations hold particular instructions or data 3 5 08 Lec 11 7 Page 2 Joseph CS162 UCB Spring 2008 Lec 11 8 Multi step Processing of a Program for Execution Administrivia Preparation of a program for execution involves components at Midterm 1 Solution with grading guidelines posted Midterms will be returned Thursday and Friday Regrade request deadline is next Friday 3 14 Compile time i e gcc Link Load time unix ld does link Execution time e g dynamic libs Addresses can be bound to final values anywhere in this path Depends on hardware support Also depends on operating system Project 2 started yesterday Design doc due next Monday 3 10 Code due Thursday 3 20 Dynamic Libraries Linking postponed until execution Small piece of code stub used to locate the appropriate memoryresident library routine Stub replaces itself with the address of the routine and executes routine 3 5 08 Joseph CS162 UCB Spring 2008 3 5 08 Lec 11 9 Recall Uniprogramming Must somehow prevent address overlap between threads Application always runs at same place in physical memory since only one application at a time Application can access any physical address Application Operating System 0xFFFFFFFF 0xFFFFFFFF Valid 32 bit Addresses Application2 Application1 0x00000000 0x00000000 Everything adjusted to memory location of program Translation done by a linker loader Was pretty common in early days With this solution no protection bugs in any program can cause other programs to crash or even the OS Of course this doesn t help us with multithreading Joseph CS162 UCB Spring 2008 0x00020000 Trick Use Loader Linker Adjust addresses while program loaded into memory loads stores jumps Application given illusion of dedicated machine by giving it reality of a dedicated machine 3 5 08 Lec 11 10 Multiprogramming First Version Multiprogramming without Translation or Protection Uniprogramming no Translation or Protection Operating System Joseph CS162 UCB Spring 2008 3 5 08 Lec 11 11 Page 3 Joseph CS162 UCB Spring 2008 Lec 11 12 Multiprogramming Version with Protection Can we protect programs from each other without translation Operating System Application2 Application1 Segmentation with Base and Limit registers Base Virtual Address CPU DRAM 0xFFFFFFFF LimitAddr 0x10000 Limit BaseAddr 0x20000 0x00020000 Alter address of every load store by adding base User allowed to read write within segment 0x00000000 Accesses are relative to segment so don t have to be relocated when program moved to different segment If user tries to access an illegal address cause an error User may have multiple segments available e g x86 During switch kernel loads new base limit from TCB User not allowed to change base limit registers Joseph CS162 UCB Spring 2008 3 5 08 Lec 11 13 Issues with simple
View Full Document
Unlocking...