CS代考 CS162 ©UCB Spring 2022

Recall: Four Fundamental OS Concepts
• Thread: Execution Context
– Fully describes program state
– Program Counter, Registers, Execution Flags, Stack

• Address space (with or w/o translation)
– Set of memory addresses accessible to program (for read or write)
– May be distinct from memory space of the physical machine (in which case programs operate in a virtual address space)
• Process: an instance of a running program
– Protected Address Space + One or more Threads
• Dual mode operation / Protection
– Only the “system” has the ability to access certain resources
– Combined with translation, isolates programs from each other and the OS from programs
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Recall: OS Bottom Line: Run Programs
instructions
Executable
Program Source
int main() { …;
instructions
Create OS “PCB”, address space, stack and heap
Load instruction and data segments of executable file into memory
“Transfer control to program” Provide services to program While protecting OS and program
Joseph & Kubiatowicz CS162 ©UCB Spring 2022
Load & Execute

Recall: Protected Address Space
• Program operates in an address space that is distinct from the physical memory space of the machine
translator
Page Table

Joseph & Kubiatowicz CS162 ©UCB Spring 2022
“virtual address”
“physical address”

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: Simple address translation with Base and Bound
Addresses translated on-the-fly
Static Data
Static Data
Base Address
Static Data
0010… Program
0010… address
• Can the program touch OS? • Can it touch other programs?
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Simple B&B: User => Kernel
Static Data
Static Data
Static Data
Proc 1 2…n
sysmode Base
Bound uPC PC regs
0000… FFFF…
• How to return to system?
1100… 3000…
3080… FFFF…
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Simple B&B: Interrupt
Static Data
Static Data
Static Data
Proc 1 2…n
sysmode Base
Bound uPC PC regs
0000… FFFF…
IntrpVector[i]
How to save registers and set up system stack?
1100… 3000…
3080… FFFF…
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Simple B&B: Switch User Process
Static Data
Static Data
Static Data
Proc 1 2…n
sysmode Base
Bound uPC PC regs
0000… FFFF…
1100… 3000…
3080… FFFF…
How to save registers and set up system stack?
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Simple B&B:“resume”
Static Data
Static Data
Static Data
Proc 1 2…n
sysmode Base
Bound uPC PC regs
0000… FFFF…
1100… 3000…
3080… FFFF…
How to save registers and set up system stack?
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Running Many Programs
• We have the basic mechanism to
– switch between user processes and the kernel,
– the kernel can switch among user processes,
– Protect OS from user processes and processes from each other
• Questions ???
– How do we represent user processes in the OS? – How do we decide which user process to run?
– How do we pack up the process and set it aside? – How do we get a stack and heap for the kernel? – Aren’t we wasting are lot of memory?
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

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

CPU Switch From Process A to Process B
Kernel/System Mode
1/25/22 Joseph & Kubiatowicz CS162 ©UCB Spring 2022 Lec 3.12

if ( readyProcesses(PCBs) ) {
nextPCB = selectProcess(PCBs);
run( nextPCB );
run_idle_process();
• Scheduling: Mechanism for deciding which processes/threads receive the CPU
• Lots of different scheduling policies provide … – Fairness or
– Realtime guarantees or
– Latency optimization or ..
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

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!
Colored blocks show instructions executed
• Original technique called “Simultaneous Multithreading” – http://www.cs.washington.edu/research/smt/index.html – SPARC, Pentium 4/Xeon (“Hyperthreading”), Power 5
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Also recall:The World Is Parallel: Intel SkyLake (2017)
• Up to 28 Cores, 56 Threads
– 694 mm2 die size (estimated)
• Many different instructions – Security, Graphics
• Caches on chip:
– L2: 28 MiB
– Shared L3: 38.5 MiB (non-inclusive)
– Directory-based cache coherence • Network:
– On-chip Mesh Interconnect
– Fast off-chip network directlry supports 8-chips connected
• DRAM/chips
– Up to 1.5 TiB
– DDR4 memory
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Is Base and Bound a Good-Enough Protection Mechanism?
• NO:Too simplistic for real systems
• Inflexible/Wasteful:
– Must dedicate physical memory for potential future use – (Think stack and heap!)
• Fragmentation:
– Kernel has to somehow fit whole processes into contiguous block of memory
– After a while, memory becomes fragmented! • Sharing:
– Very hard to share any data between Processes or between Process and Kernel
– Need to communicate indirectly through the kernel…
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Better: x86 – segments and stacks
Static Data
Static Data
Processor Registers
CS EIP SS ESP
Start address, length and access rights associated with each segment
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Better Alternative:Address Mapping
OS heap & Stacks
Virtual Address Space 1
Translation Map 1
Virtual Address Space 2
Translation Map 2
Physical Address Space
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Recall: 3 types of Kernel Mode Transfer
– Process requests a system service, e.g., exit
– Like a function call, but “outside” the process
– Does not have the address of the system function to call
– Like a Remote Procedure Call (RPC) – for later
– Marshall the syscall id and args in registers and exec syscall
• Interrupt
– External asynchronous event triggers context switch – eg.Timer, I/O device
– Independent of user process
• Trap or Exception
– Internal synchronous event in process triggers context switch
– e.g., Protection violation (segmentation fault), Divide by zero, …
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Recall: User/Kernel (Privileged) Mode
Kernel Mode
Limited HW access
Full HW access
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Implementing Safe Kernel Mode Transfers
Important aspects:
– Controlled transfer into kernel (e.g., syscall table) – Separate kernel stack!
Carefully constructed kernel code packs up the user process state and sets it aside
– Details depend on the machine architecture – More on this next time
Should be impossible for buggy or malicious user program to cause the kernel to corrupt itself!
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Hardware support: Interrupt Control
• Interrupt processing not visible to the user process:
– Occurs between instructions, restarted transparently
– No change to process state
– What can be observed even with perfect interrupt processing?
• Interrupt Handler invoked with interrupts ‘disabled’
– Re-enabled upon completion
– Non-blocking (run to completion, no waits)
– Pack up in a queue and pass off to an OS thread for hard work » wake up an existing OS thread
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

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

Interrupt Vector
interrupt number (i)
Address and properties of each interrupt handler
Joseph & Kubiatowicz CS162 ©UCB Spring 2022
• Where else do you see this dispatch pattern? – System Call
– Exceptions
intrpHandler_i () {

How do we take interrupts safely?
• Interrupt vector
– Limited number of entry points into kernel • Kernel interrupt stack
– Handler works regardless of state of user code • Interrupt masking
– Handler is non-blocking • Atomic transfer of control
– “Single instruction”-like to change: » Program counter
» Stack pointer
» Memory protection
» Kernel/user mode
• Transparent restartable execution
– User program does not know interrupt occurred
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Need for Separate Kernel Stacks
• Kernel needs space to work
• Cannot put anything on the user stack (Why?)
• Two-stack model
– OS thread has interrupt stack (located in kernel memory) plus User stack (located in user memory)
– Syscall handler copies user args to kernel space before invoking specific function (e.g., open)
– Interrupts (???)
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

1/25/22 Joseph & Kubiatowicz CS162 ©UCB Spring 2022 Lec 3.27

During Interrupt/System Call
1/25/22 Joseph & Kubiatowicz CS162 ©UCB Spring 2022 Lec 3.28

Recall: UNIX System Structure
Applications Standard Libs
Kernel Mode
Joseph & Kubiatowicz CS162 ©UCB Spring 2022 Lec 3.29

A Narrow Waist
Compilers Word Processing Web Browsers Email
Web Servers
Application / Service
User Mode System Mode
Portable OS Library OS
Portable OS Kernel Platform support, Device Drivers
PowerPC ARM
System Call
Software Hardware
x86 Ethernet (1Gbs/10Gbs)
802.11 a/g/n/ac/ax SCSI
PCI Thunderbolt
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Kernel System Call Handler
• Vector through well-defined syscall entry points!
– Table mapping system call number to handler • Locate arguments
– In registers or on user (!) stack • Copy arguments
– From user memory into kernel memory
– Protect kernel from malicious code evading checks
• Validate arguments
– Protect kernel from errors in user code
• Copy results back
– Into user memory
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Putting it together: web server
Server Process
4. parse request
9. format reply
5. file 8. kernel read() copy
request buffer
reply buffer
1.network socket
3. kernel copy
10. network socket
2. copy arriving packet (DMA)
syscall wait
11. kernel copy
from user buffer to network buffer
12. format outgoing packet and DMA
6. disk request
7. disk data (DMA)
Network interface
Disk interface
Request Reply
Joseph & Kubiatowicz CS162 ©UCB Spring 2022 Lec 3.33

Recall: Processes
• How to manage process state? – How to create a process?
– How to exit from a process?
• Remember: Everything outside of the kernel is running in a process!
– Including the shell! (Homework 2)
• Processes are created and managed… by processes!
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Bootstrapping
• If processes are created by other processes, how does the first process start?
• First process is started by the kernel
– Often configured as an argument to the kernel before the kernel boots – Often called the “init” process
• After this, all processes on the system are created by other processes
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Process Management API
• exit – terminate a process
• fork – copy the current process
• exec – change the program being run by the current process
• wait – wait for a process to finish
• kill – send a signal (interrupt-like notification) to another process • sigaction – set handlers for signals
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

#include
#include
#include
#include
#include
int main(int argc, char *argv[])
/* get current processes PID */
pid_t pid = getpid();
printf(“My pid: %d\n”, pid);
Q:What if we let main return
without ever calling exit?
• The OS Library calls exit() for us!
• The entrypoint of the executable is in
the OS library
• OS library calls main
• If main returns, OS library calls exit • You’ll see this in Project 0: init.c
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Creating Processes
• pid_t fork() – copy the current process – New process has different pid
– New process contains a single thread
• Return value from fork(): pid (like an integer)
– When > 0:
» Running in (original) Parent process » return value is pid of new child
– When = 0:
» Running in new Child process
– When < 0: » Error! Must handle somehow » Running in original process • State of original process duplicated in both Parent and Child! – Address Space (Memory), File Descriptors (covered later), etc... Joseph & Kubiatowicz CS162 ©UCB Spring 2022 Joseph & Kubiatowicz CS162 ©UCB Spring 2022 #include
#include
#include
#include
int main(int argc, char *argv[]) {
pid_t cpid, mypid;
pid_t pid = getpid();
printf(“Parent pid: %d\n”, pid);
cpid = fork();
/* get current processes PID */
if (cpid > 0) { /* Parent Process */ mypid = getpid();
printf(“[%d] parent of [%d]\n”, mypid, cpid);
} else if (cpid == 0) { /* Child Process */ mypid = getpid();
printf(“[%d] child\n”, mypid);
perror(“Fork failed”);

#include
#include
#include
#include
int main(int argc, char *argv[]) {
pid_t cpid, mypid;
pid_t pid = getpid();
printf(“Parent pid: %d\n”, pid);
cpid = fork();
/* get current processes PID */
if (cpid > 0) { /* Parent Process */ mypid = getpid();
printf(“[%d] parent of [%d]\n”, mypid, cpid);
} else if (cpid == 0) { /* Child Process */ mypid = getpid();
printf(“[%d] child\n”, mypid);
perror(“Fork failed”);
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

if (cpid > 0) { /* Parent Process */ mypid = getpid();
printf(“[%d] parent of [%d]\n”, mypid, cpid);
} else if (cpid == 0) { /* Child Process */ mypid = getpid();
printf(“[%d] child\n”, mypid);
perror(“Fork failed”);
#include
#include
#include
#include
int main(int argc, char *argv[]) {
pid_t cpid, mypid;
pid_t pid = getpid();
printf(“Parent pid: %d\n”, pid);
cpid = fork();
/* get current processes PID */
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

pid_t cpid = fork();
if (cpid > 0) {
for (i = 0; i < 10; i++) { printf("Parent: %d\n", i); // sleep(1); } else if (cpid == 0) { for (i = 0; i > -10; i–) {
printf(“Child: %d\n”, i);
// sleep(1);
Recall: a process consists of one or more threads executing in an address space
• Here, each process has a single thread
• These threads execute concurrently
fork_race.c
• What does this print?
• Would adding the calls to sleep() matter?
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

Running Another Program
With threads, we could call pthread_create to create a new thread executing a separate function
With processes, the equivalent would be spawning a new process executing a different program
How can we do this?
Joseph & Kubiatowicz CS162 ©UCB Spring 2022

cpid = fork();
if (cpid > 0) {

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts