程序代写代做 algorithm compiler assembler C concurrency assembly kernel Processes and Threads Implementation

004000b0 :
4000b0: 27bdfff8
4000b4: afbe0000
4000b8: 03a0f021
4000bc: afc40008
4000c0: afc5000c
4000c4: afc60010
4000c8: afc70014
4000cc: 8fc30008
4000d0: 8fc2000c
4000d4: 00000000
4000d8: 00621021
4000dc: 8fc30010
4000e0: 00000000
4000e4: 00431021
4000e8: 8fc30014
4000ec: 00000000
4000f0: 00431021
4000f4: 8fc30018
4000f8: 00000000
addiu sp,sp,-8
sw s8,0(sp)
move s8,sp
sw a0,8(s8)
sw a1,12(s8)
sw a2,16(s8)
sw a3,20(s8)
lw v1,8(s8)
lw v0,12(s8)
nop
addu v0,v1,v0
lw v1,16(s8)
nop
addu v0,v0,v1
lw v1,20(s8)
nop
addu v0,v0,v1
lw v1,24(s8)
nop
20

4000fc: 00431021 addu v0,v0,v1 400100: 8fc3001c lw v1,28(s8) 400104: 00000000 nop
400108: 00431021 addu v0,v0,v1 40010c: 03c0e821 move sp,s8 400110: 8fbe0000 lw s8,0(sp) 400114: 03e00008 jr ra 400118: 27bd0008 addiusp,sp,8
21

The Process Model
• Multiprogramming of four programs
• Conceptual model of 4 independent, sequential processes (with a single thread each)
• Only one program active at any instant
22

Process
• Minimally consist of three segments
• Text
• contains the code (instructions)
• Data
• Global variables
• Stack
• Activation records of procedure/function/method • Local variables
• Note:
• datacandynamicallygrowup • E.g., malloc()-ing
• The stack can dynamically grow down
• E.g., increasing function call depth or recursion
Process Memory Layout
Stack
Gap
Data
Text
23

Processes
Process’s user-level stack and execution state
User Mode
Process A Process B Process C
Kernel Mode
Scheduler
Process’s in-kernel stack and execution state

Processes
• User-mode
• Processes (programs) scheduled by the kernel
• Isolated from each other
• No concurrency issues between each other
• System-calls transition into and return from the kernel
• Kernel-mode
• Nearly all activities still associated with a process
• Kernel memory shared between all processes
• Concurrency issues exist between processes concurrently executing in a system call
25

Threads
The Thread Model
(a) Three processes each with one thread (b) One process with three threads
26

The Thread Model
• Items shared by all threads in a process • Items that exist per thread
27

The Thread Model
Each thread has its own stack
28

A Subset of POSIX threads API
int pthread_create(pthread_t *, const pthread_attr_t *, void *(*)(void *), void *);
void pthread_exit(void *);
int pthread_mutex_init(pthread_mutex_t *, const pthread_mutexattr_t *); int pthread_mutex_destroy(pthread_mutex_t *);
int pthread_mutex_lock(pthread_mutex_t *);
int pthread_mutex_unlock(pthread_mutex_t *);
int pthread_rwlock_init(pthread_rwlock_t *, const pthread_rwlockattr_t *);
int pthread_rwlock_destroy(pthread_rwlock_t *); int pthread_rwlock_rdlock(pthread_rwlock_t *); int pthread_rwlock_wrlock(pthread_rwlock_t *); int pthread_rwlock_unlock(pthread_rwlock_t *);
29

Where to Implement Application Threads?
Note: Thread API similar in both
cases
User Mode Kernel Mode
Device Device
Application
System Libraries
User-level threads implemented in a library?
OS
Kernel-level threads implemented in the OS?
Memory 30

Implementing Threads in User Space
A user-level threads library
31

User-level Threads
User Mode
Scheduler Scheduler
Scheduler
Process A Process B Process C
Kernel Mode
Scheduler

User-level Threads
• Implementation at user-level
• User-level Thread Control Block (TCB), ready queue, blocked queue, and dispatcher
• Kernel has no knowledge of the threads (it only sees a single process)
• If a thread blocks waiting for a resource held by another thread inside the same process, its state is saved and the dispatcher switches to another ready thread
• Thread management (create, exit, yield, wait) are implemented in a runtime support library
33

User-Level Threads • Pros
• Thread management and switching at user level is much faster than doing it in kernel level
• No need to trap (take syscall exception) into kernel and back to switch
• Dispatcher algorithm can be tuned to the application
• E.g. use priorities
• Can be implemented on any OS (thread or non-thread aware)
• Can easily support massive numbers of threads on a per-application basis
• Use normal application virtual memory
• Kernel memory more constrained. Difficult to efficiently support wildly differing numbers of threads for different applications.
34

User-level Threads • Cons
• Threads have to yield() manually (no timer interrupt delivery to user- level)
• Co-operative multithreading
• A single poorly design/implemented thread can monopolise the available CPU time
• There are work-arounds (e.g. a timer signal per second to enable pre- emptive multithreading), they are course grain and a kludge.
• Does not take advantage of multiple CPUs (in reality, we still have a single threaded process as far as the kernel is concerned)
35

User-Level Threads • Cons
• If a thread makes a blocking system call (or takes a page fault), the process (and all the internal threads) blocks
• Can’t overlap I/O with computation
User Mode
Scheduler Scheduler
Scheduler
Process Process Process ABC
Kernel Mode
Scheduler
36

Implementing Threads in the Kernel
A threads package managed by the kernel
37

Kernel-provided Threads
User Mode
Process A Process B Process C
Kernel Mode
Scheduler

Kernel-provided Threads • Also called kernel-level threads
• Even though they provide threads to applications • Threads are implemented by the kernel
• TCBs are stored in the kernel
• A subset of information in a traditional PCB • The subset related to execution context
• TCBs have a PCB associated with them
• Resources associated with the group of threads (the process)
• Thread management calls are implemented as system calls • E.g. create, wait, exit
39

Kernel-provided Threads • Cons
• Thread creation and destruction, and blocking and unblocking threads requires kernel entry and exit.
• More expensive than user-level equivalent
40

Kernel-provided Threads
• Pros
• Preemptive multithreading • Parallelism
• Can overlap blocking I/O with computation • Can take advantage of a multiprocessor
User Mode
Process A Process B Process C
Kernel Mode
Scheduler

Multiprogramming Implementation
Skeleton of what lowest level of OS does when an interrupt occurs – a context switch
42

Context Switch Terminology • A context switch can refer to
• A switch between threads
• Involving saving and restoring of state associated with a thread
• A switch between processes
• Involving the above, plus extra state associated with a process.
• E.g. memory maps
43

Context Switch Occurrence
• A switch between process/threads can happen any time the OS is invoked
• On a system call
• Mandatory if system call blocks or on exit();
• On an exception
• Mandatory if offender is killed
• On an interrupt
• Triggering a dispatch is the main purpose of the timer interrupt
A thread switch can happen between any two instructions
Note instructions do not equal program statements
44

Context Switch
• Context switch must be transparent for processes/threads
• When dispatched again, process/thread should not notice that something else was running in the meantime (except for elapsed time)
OS must save all state that affects the thread
• This state is called the process/thread context
• Switching between process/threads consequently results in a context switch.
45

Thread a
thread_switch(a,b)
{
}
thread_switch(a,b)
{
Thread b
}
thread_switch(b,a)
{
}
Simplified Explicit Thread Switch
46

Assume Kernel-Level Threads
User Mode
Process A Process B Process C
Kernel Mode
Scheduler

Example Context Switch
• Running in user mode, SP points to user-level stack (not shown on slide)
Representation of
Kernel Stack SP
(Memory)
48

Example Context Switch
• Take an exception, syscall, or interrupt, and we switch to the kernel stack
SP
49

Example Context Switch
• We push a trapframe on the stack
• Also called exception frame, user-level context…. • Includes the user-level PC and SP
SP
trapframe
50

Example Context Switch
• Call ‘C’ code to process syscall, exception, or interrupt • Results in a ‘C’ activation stack building up
SP
‘C’ activation stack
trapframe
51

Example Context Switch
• The kernel decides to perform a context switch • It chooses a target thread (or process)
• It pushes remaining kernel context onto the stack
SP
Kernel State
‘C’ activation stack
trapframe
52

Example Context Switch
• Any other existing thread must
• be in kernel mode (on a uni processor),
• and have a similar stack layout to the stack we are currently using
Kernel stacks of other threads/processes
SP
Kernel State
‘C’ activation stack
trapframe
Kernel State
‘C’ activation stack
trapframe
Kernel State
‘C’ activation stack
trapframe
53

Example Context Switch
• We save the current SP in the PCB (or TCB), and load the SP of the target thread.
• Thus we have switched contexts
SP
Kernel State
‘C’ activation stack
trapframe
Kernel State
‘C’ activation stack
trapframe
Kernel State
‘C’ activation stack
trapframe
54

Example Context Switch
• Load the target thread’s previous context, and return to C
SP
Kernel State
‘C’ activation stack
trapframe
‘C’ activation stack
trapframe
Kernel State
‘C’ activation stack
trapframe
55

Example Context Switch
• The C continues and (in this example) returns to user mode.
SP
Kernel State
‘C’ activation stack
trapframe
trapframe
Kernel State
‘C’ activation stack
trapframe
56

Example Context Switch • The user-level context is restored
SP
Kernel State
‘C’ activation stack
trapframe
Kernel State
‘C’ activation stack
trapframe
57

Example Context Switch • The user-level SP is restored
SP
Kernel State
‘C’ activation stack
trapframe
Kernel State
‘C’ activation stack
trapframe
58

The Interesting Part of a Thread Switch • What does the “push kernel state” part do???
SP
Kernel State
‘C’ activation stack
trapframe
Kernel State
‘C’ activation stack
trapframe
59

Simplified OS/161 thread_switch
static
void
thread_switch(threadstate_t newstate, struct wchan *wc) {
struct thread *cur, *next;
cur = curthread;
do {
next = threadlist_remhead(&curcpu->c_runqueue); if (next == NULL) {
cpu_idle();
}
} while (next == NULL);
/* do the switch (in assembler in switch.S) */ switchframe_switch(&cur->t_context, &next->t_context);
}
Lots of code removed – only basics of pick next thread and
run it remain 60

OS/161 switchframe_switch
switchframe_switch:
/*
* a0 contains the address of the switchframe pointer in the old thread.
* a1 contains the address of the switchframe pointer in the new thread. *
* The switchframe pointer is really the stack pointer. The other
* registers get saved on the stack, namely: *
* s0-s6, s8
* gp, ra *
* The order must match . *
* Note that while we’d ordinarily need to save s7 too, because we
* use it to hold curthread saving it would interfere with the way
* curthread is managed by thread.c. So we’ll just let thread.c
* manage it. */
61

OS/161 switchframe_switch
/* Allocate stack space for saving 10 registers. 10*4 = 40 */ addi sp, sp, -40
/* Save the registers */ sw ra, 36(sp)
sw gp, 32(sp)
sw s8, 28(sp)
sw s6, 24(sp) sw s5, 20(sp) sw s4, 16(sp) sw s3, 12(sp) sw s2, 8(sp) sw s1, 4(sp) sw s0, 0(sp)
/* Store the old stack pointer in the old thread */ sw sp, 0(a0)
Save the registers that the ‘C’ procedure calling convention expects preserved
62

OS/161 switchframe_switch
/* Get the new stack pointer from the new thread */ lw sp, 0(a1)
nop /* delay slot for load */
/* Now, restore the registers */
lw lw lw lw lw lw lw lw lw lw nop
s0, 0(sp) s1, 4(sp) s2, 8(sp) s3, 12(sp) s4, 16(sp) s5, 20(sp) s6, 24(sp) s8, 28(sp) gp, 32(sp) ra, 36(sp)
/* delay slot for load */
63

OS/161 switchframe_switch
/* and return. */
j ra
addi sp, sp, 40 /* in delay slot */
64

Thread a
switchframe_switch(a,b) {
}
Thread b
}
Revisiting Thread Switch
switchframe_switch(b,a) {
switchframe_switch(a,b) {
}
65