Recall: Connection Setup over TCP/IP
Client Side
Connection request:
1. Client IP addr
Copyright By PowCoder代写 加微信 powcoder
2. Client Port
3. Protocol (TCP/IP)
Server Socket
Server Side
Server Listening:
1. Server IP addr
2. well-known port,
3. Protocol (TCP/IP)
connection
new socket
• 5-Tuple identifies each connection:
1. Source IP Address
2. Destination IP Address
3. Source Port Number
4. Destination Port Number
5. Protocol (always TCP here)
• Often, Client Port “randomly” assigned – Done by OS during client socket setup
• Server Port often “well known”
– 80 (web), 443 (secure web), 25 (sendmail), etc
– Well-known ports from 0—1023
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 6.1
Request Connection
Recall: Server Protocol (v3)
// Socket setup code elided…
while (1) {
// Accept a new client connection, obtaining a new socket int conn_socket = accept(server_socket, NULL, NULL);
if (pid == 0) { close(server_socket); serve_client(conn_socket); close(conn_socket); exit(0);
} else { close(conn_socket); // wait(NULL);
close(server_socket);
listen(server_socket, MAX_QUEUE);
pid_t pid = fork();
2/3/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 6.2
Recall: Multiplexing Processes:The Process Control Block
• Kernel represents each process as a process control block (PCB)
– Status (running, ready, blocked, …)
– Register state (when not ready)
– Process ID (PID), User, Executable, Priority, … – Execution time, …
– Memory space, translation, …
• Kernel Scheduler maintains a data structure containing the PCBs
– Give out CPU to different processes – This is a Policy Decision
• Give out non-CPU resources – Memory/IO
– Another policy decision
Process Control Block
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: CPU Switch From Process A to Process B
Kernel/System Mode
2/3/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 6.4
Recall: Lifecycle of a Process or Thread
• As a process executes, it changes state:
– new: The process/thread is being created
– ready: The process is waiting to run
– running: Instructions are being executed
– waiting: Process waiting for some event to occur – terminated: The process has finished execution
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Single and Multithreaded Processes
• Threads encapsulate concurrency:“Active” component
• Address spaces encapsulate protection:“Passive” part – Keeps buggy program from trashing the system
• Why have multiple threads per address space?
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Shared vs. Per-Thread State
2/3/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 6.7
The Core of Concurrency: the Dispatch Loop
• Conceptually, the scheduling loop of the operating system looks as follows:
RunThread();
ChooseNextThread();
SaveStateOfCPU(curTCB);
LoadStateOfCPU(newTCB);
• This is an infinite loop
– One could argue that this is all that the OS does
• Should we ever exit this loop??? – When would that be?
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Running a thread
Consider first portion: RunThread()
• How do I run a thread?
– Load its state (registers, PC, stack pointer) into CPU – Load environment (virtual memory space, etc)
– Jump to the PC
• How does the dispatcher get control back?
– Internal events: thread returns control voluntarily – External events: thread gets preempted
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Internal Events
• Blocking on I/O
– The act of requesting I/O implicitly yields the CPU
• Waiting on a “signal” from other thread
– Thread asks to wait and thus yields the CPU
• Thread executes a yield()
– Thread volunteers to give up CPU
computePI() {
while(TRUE) {
ComputeNextDigit();
yield(); }
Joseph & Kubiatowicz CS162 © UCB Spring 2022
kernel_yield
run_new_thread
Trap to OS
• How do we run a new thread?
run_new_thread() {
newThread = PickNewThread();
switch(curThread, newThread);
ThreadHouseKeeping(); /* Do any cleanup */
• How does dispatcher switch to a new thread?
– Save anything next thread may trash: PC, regs, stack pointer – Maintain isolation for each thread
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Stack growth
What Do the Stacks Look Like?
• Consider the following code blocks:
proc A() {
proc B() {
while(TRUE) {
yield(); }
• Suppose we have 2 threads:
– Threads S and T
run_new_thread
run_new_thread
Thread S’s switch returns to Thread T’s (and vice versa)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Stack growth
Saving/Restoring state (often called “Context Switch)
Switch(tCur,tNew) {
/* Unload old thread */
TCB[tCur].regs.r7 = CPU.r7;
TCB[tCur].regs.r0 = CPU.r0;
TCB[tCur].regs.sp = CPU.sp;
TCB[tCur].regs.retpc = CPU.retpc; /*return addr*/
/* Load and execute new thread */
CPU.r7 = TCB[tNew].regs.r7;
CPU.r0 = TCB[tNew].regs.r0;
CPU.sp = TCB[tNew].regs.sp;
CPU.retpc = TCB[tNew].regs.retpc;
return; /* Return to CPU.retpc */
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Switch Details (continued)
• What if you make a mistake in implementing switch?
– Suppose you forget to save/restore register 32
– Get intermittent failures depending on when context switch occurred and whether new thread uses register 32
– System will give wrong result without warning
• Can you devise an exhaustive test to test switch code?
– No! Too many combinations and inter-leavings • Cautionary tale:
– For speed,Topaz kernel saved one instruction in switch()
– Carefully documented! Only works as long as kernel size < 1MB
– What happened?
» Time passed, People forgot
» Later, they added features to kernel (no one removes features!) » Very weird behavior started happening
– Moral of story: Design for simplicity
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Are we still switching contexts with previous examples?
• Yes, but much cheaper than switching processes – No need to change address space
• Some numbers from Linux:
– Frequency of context switch: 10-100ms – Switching between processes: 3-4 μsec. – Switching between threads: 100 ns
• Even cheaper: switch threads (using “yield”) in user-space!
Many-to-One 2/3/2022 Threading Model Joseph & Kubiatowicz CS162 © UCB Spring 2022
Many-to-Many
What we are talking about in Today’s lecture
Simple One-to-One
What happens when thread blocks on I/O?
kernel_read
run_new_thread
Trap to OS
• What happens when a thread requests a block of data from the file system?
– User code invokes a system call – Read operation is initiated
– Run new thread/switch
• Thread communication similar – Wait for Signal/Join
– Networking
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Stack growth
External Events
• What happens if thread never does any I/O, never waits, and never yields control?
– Could the ComputePI program grab all resources and never release the processor?
» What if it didn’t print to console?
– Must find way that dispatcher can regain control!
• Answer: utilize external events
– Interrupts: signals from hardware or software that stop the running code and jump to kernel
– Timer: like an alarm clock that goes off every some milliseconds
• If we make sure that external events occur frequently enough, can ensure dispatcher runs
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Interrupt Controller
Int Disable
• Interrupts invoked with interrupt lines from devices
• Interrupt controller chooses interrupt request to honor
– Interrupt identity specified with ID line
– Mask enables/disables interrupts
– Priority encoder picks highest enabled interrupt – Software Interrupt Set/Cleared by Software
• CPU can disable all interrupts with internal flag
• Non-Maskable Interrupt line (NMI) can’t be disabled
Software Interrupt
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Priority Encoder Interrupt Mask
Example: Network Interrupt
Raise priority
(set mask)
Reenable All Ints
Save registers
Dispatch to Network Packet
from hardware
to Kernel Buffers
Restore registers
Clear current Int
Disable All Ints
Restore priority
(clear Mask)
• An interrupt is a hardware-invoked context switch – No separate step to choose what to run next
– Always run the interrupt handler immediately
add $r1,$r2,$r3 subi $r4,$r1,#4 slli $r4,$r4,#2
Pipeline Flush
lw $r2,0($r4)
lw $r3,4($r4) add $r2,$r2,$r3 sw 8($r4),$r2
Joseph & Kubiatowicz CS162 © UCB Spring 2022
PC saved Disable All Ints Kernel Mode
Restore PC Enable all Ints User Mode
External Interrupt
“Interrupt Handler”
Use of Timer Interrupt to Return Control
• Solution to our dispatcher problem
– Use the timer interrupt to force scheduling decisions
Some Routine
TimerInterrupt
run_new_thread
• Timer Interrupt routine:
TimerInterrupt() {
DoPeriodicHouseKeeping();
run_new_thread();
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Stack growth
ThreadFork(): Create a
• ThreadFork() is a user-level procedure that creates a new
thread and places it on ready queue
• Arguments to ThreadFork()
– Pointer to application routine (fcnPtr)
– Pointer to array of arguments (fcnArgPtr) – Size of stack to allocate
• Implementation
– Sanity check arguments
– Enter Kernel-mode and Sanity Check arguments again – Allocate new Stack and TCB
– Initialize TCB and place on ready list (Runnable)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
How do we initialize TCB and Stack?
• Initialize Register fields of TCB
– Stack pointer made to point at stack
– PC return address ⇒ OS (asm) routine ThreadRoot()
– Two arg registers (a0 and a1) initialized to fcnPtr and fcnArgPtr, respectively
• Initialize stack data?
– Minimal initialization ⇒setup return to go to beginning of ThreadRoot() » Important part of stack frame is in registers for RISC-V (ra)
» X86: need to push a return address on stack
– Think of stack frame as just before body of ThreadRoot() really gets started ThreadRoot stub
Initial Stack
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Stack growth
How does Thread get started?
Other Thread
ThreadRoot
run_new_thread
ThreadRoot stub
• Eventually, run_new_thread() will select this TCB and return into beginning of ThreadRoot()
– This really starts the new thread
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Stack growth
How does a thread get started?
Other Thread
SetupNewThread(tNew) {
TCB[tNew].regs.sp = newStackPtr;
TCB[tNew].regs.retpc = &ThreadRoot;
TCB[tNew].regs.r0 = fcnPtr
TCB[tNew].regs.r1 = fcnArgPtr
ThreadRoot stub
ThreadRoot
run_new_thread
• How do we make a new thread?
– Setup TCB/kernel thread to point at new user stack and ThreadRoot code – Put pointers to start function and args in registers or top of stack
» This depends heavily on the calling convention (i.e. RISC-V vs x86)
Eventually, run_new_thread() will select this TCB and return into beginning of ThreadRoot() – This really starts the new thread
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Stack growth
What does ThreadRoot() look like? • ThreadRoot() is the root for the thread routine:
ThreadRoot(fcnPTR,fcnArgPtr) {
DoStartupHousekeeping();
UserModeSwitch(); /* enter user mode */
Call fcnPtr(fcnArgPtr);
ThreadFinish();
• Startup Housekeeping
– Includes things like recording start time of thread – Other statistics
• Stack will grow and shrink with execution of thread
Running Stack
ThreadRoot
Thread Code
• Final return from thread returns into ThreadRoot() which calls ThreadFinish() – ThreadFinish() wake up sleeping threads
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 6.25
Stack growth
Processes vs.Threads: One Core
Process 1 threads
Process N threads
• Switch overhead:
– Same process: low – Different proc.: high
• Protection
– Same proc: low
– Different proc: high
• Sharing overhead
– Same proc: low
– Different proc: high
• Parallelism:no
CPU sched.
1 thread at
a time CPU
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Processes vs.Threads: MultiCore
Process 1 threads
Process N threads
• Switch overhead:
– Same process: low – Different proc.: high
• Protection
– Same proc: low
– Different proc: high
• Sharing overhead
– Same proc: low
– Different proc,
simultaneous core: medium
– Different proc, offloaded core: high
• Parallelism:yes
CPU sched.
Joseph & Kubiatowicz CS162 © UCB Spring 2022
4 threads at a time
Recall: Simultaneous MultiThreading/Hyperthreading
• Hardware scheduling technique
– Superscalar processors can execute multiple instructions that are independent.
– Hyperthreading duplicates register state to make a second “thread,” allowing more instructions to run.
• Can schedule each thread as if were separate CPU – But, sub-linear speedup!
• Original technique called “Simultaneous Multithreading” – http://www.cs.washington.edu/research/smt/index.html
– SPARC, Pentium 4/Xeon (“Hyperthreading”), Power 5
Colored blocks show instructions executed
2/3/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022
Processes vs.Threads: Hyper-Threading
Process 1 Process N threads threads
• Switch overhead between hardware-threads: very-low (done in hardware)
• Contention for ALUs/FPUs may hurt performance
CPU sched.
hardware-threads (hyperthreading)
8 threads at a time
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Threads vs Address Spaces: Options
# threads Per AS:
MS/DOS, early Macintosh
Traditional UNIX
Embedded systems (Geoworks,VxWorks, JavaOS,etc)
JavaOS, Pilot(PC)
Mach, OS/2, Linux Windows 10
Win NT to XP, Solaris, HP-UX, OS X
• Most operating systems have either
– One or many address spaces
– One or many threads per address space
2/3/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 6.30
# of addr spaces:
Multiprocessing vs Multiprogramming
• Some Definitions:
– Multiprocessing ≡ Multiple CPUs
– Multiprogramming ≡ Multiple Jobs or Processes – Multithreading ≡ Multiple threads per Process
• What does it mean to run two threads “concurrently”?
– Scheduler is free to run threads in any order and interleaving: FIFO, Random, ...
– Dispatcher can choose to run each thread to completion or time-slice in big chunks or small chunks
Multiprocessing
Multiprogramming
A B C A B C B
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Correctness for systems with concurrent threads
• If dispatcher can schedule threads in any way, programs must work under all circumstances
– Can you test for this?
– How can you know if your program works?
• IndependentThreads:
– No state shared with other threads
– Deterministic ⇒ Input state determines results
– Reproducible ⇒ Can recreate Starting Conditions, I/O
– Scheduling order doesn’t matter (if switch() works!!!)
• CooperatingThreads:
– Shared State between multiple threads – Non-deterministic
– Non-reproducible
• Non-deterministic and Non-reproducible means that bugs can be intermittent – Sometimes called “Heisenbugs”
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Interactions Complicate Debugging
• Is any program truly independent?
– Every process shares the file system, OS resources, network, etc
– Extreme example: buggy device driver causes thread A to crash “independent thread” B
• You probably don’t realize how much you depend on reproducibility:
– Example: Evil C compiler
» Modifies files behind your back by inserting errors into C program unless you insert debugging code
– Example: Debugging statements can overrun stack • Non-deterministic errors are really difficult to find
– Example: Memory layout of kernel+user programs
» depends on scheduling, which depends on timer/other things » Original UNIX had a bunch of non-deterministic errors
– Example: Something which does interesting I/O
» User typing of letters used to help generate secure keys
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Why allow cooperating threads?
• People cooperate; computers help/enhance people’s lives, so computers must cooperate
– By analogy, the non-reproducibility/non-determinism of people is a notable problem for “carefully laid plans”
• Advantage 1: Share resources – One computer, many users
– One bank balance, many ATMs
» What if ATMs were only updated at night?
– Embedded systems (robot control: coordinate arm & hand)
• Advantage 2: Speedup
– Overlap I/O and computation
» Many different file systems do read-ahead
– Multiprocessors – chop up program into parallel pieces
• Advantage 3: Modularity
– More important than you might think
– Chop large problem up into simpler pieces
» To compile, for instance, gcc calls cpp | cc1 | cc2 | as | ld » Makes system easier to extend
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: High-level Example:Web Server
• Server must handle many requests • Non-cooperating version:
serverLoop() {
con = AcceptCon();
ProcessFork(ServiceWebPage(),con);
• What are some disadvantages of this technique?
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Thread Pools: Bounded Concurrency
• Problem with previous version: Unbounded Threads
– When web-site becomes too popular – throughput sinks
• Instead, allocate a bounded “pool” of worker threads, representing the maximum level of multiprogramming
Maste r Threa d
master() {
allocThreads(worker,queue);
while(TRUE) {
con=AcceptCon();
Enqueue(queue,con);
wakeUp(queue);
Thread Pool
worker(queue) {
while(TRUE) {
con=Dequeue(queue);
if (con==null)
sleepOn(queue);
Joseph & Kubiatowicz CS162 © UCB Spring 2022
ServiceWebPage(con);
Recall:Threaded Web Server
• Now, use a single process
• Multithreaded (cooperating) version:
serverLoop() {
connection = AcceptCon();
ThreadFork(ServiceWebPage(),connection);
• Looks almost
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com