Today: Four Fundamental OS Concepts
• Thread: Execution Context
– Fully describes program state
– Program Counter, Registers, Execution Flags, Stack
Copyright By PowCoder代写 加微信 powcoder
• 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
OS Bottom Line: Run Programs
instructions
Executable
Program Source
int main() { …;
• Write them and compile them
instructions
• Load instruction and data segments of executable file into memory
• Create stack and heap
• “Transfer control to program”
• Provide services to program
• While protecting OS and program
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Load & Execute
Recall (61C): Instruction Fetch/Decode/Execute
The instruction cycle
Instruction fetch Decode
instruction
Joseph & Kubiatowicz CS162 © UCB Spring 2022
First OS Concept:Thread of Control
• Thread: Single unique execution context
– Program Counter, Registers, Execution Flags, Stack, Memory State
• A thread is executing on a processor (core) when it is resident in the processor registers
• Resident means: Registers hold the root state (context) of the thread:
– Including program counter (PC) register & currently executing instruction » PC points at next instruction in memory
» Instructions stored in memory
– Including intermediate values for ongoing computations
» Can include actual values (like integers) or pointers to values in memory
– Stack pointer holds the address of the top of stack (which is in memory)
– The rest is “in memory”
• A thread is suspended (not executing) when its state is not loaded (resident) into the processor – Processor state pointing at some other thread
– Program counter register is not pointing at next instruction from this thread
– Often: a copy of the last value for each register stored in memory
1/20/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall (61C):What happens during program execution?
Addr 232-1
… Data1 Data0 Inst237 Inst236 … Inst5 Inst4 Inst3 Inst2 Inst1 Inst0
R0 … R31 F0 … F30 PC
Fetc h Exec
• Execution sequence:
– Execute (possibly using registers) – Write results to registers/mem – PC = Next Instruction(PC)
PC PC PC PC
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Registers: RISC-V ⇒ x86
Load/Store Arch (RISC-V) with software conventions
Complex mem-mem arch (x86) with specialized registers and “segments”
• cs61C does RISC-V. Will need to learn x86… • Section will cover this architecture
Joseph & Kubiatowicz CS162 © UCB Spring 2022
vCP vCP vCP U1 U2 U3
Shared Memory
Programmer’s View
Illusion of Multiple Processors
Assume a single processor (core). How do we provide the illusion of multiple processors?
– Multiplex in time! Threads are virtual cores
Contents of virtual core (thread): – Program counter, stack pointer
– Registers
Where is “it” (the thread)?
– On the real (physical) core, or
– Saved in chunk of memory – called the Thread Control Block (TCB)
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 2.7
Illusion of Multiple Processors (Continued)
vCP vCP vCP U1 U2 U3
Shared Memory
Programmer’s View
• Consider:
– At T1: vCPU1 on real core, vCPU2 in memory – At T2: vCPU2 on real core, vCPU1 in memory
• What happened?
– OS Ran [how?]
– Saved PC, SP, … in vCPU1’s thread control block (memory) – Loaded PC, SP, … from vCPU2’s TCB, jumped to PC
• What triggered this switch?
– Timer, voluntary yield, I/O, other things we will discuss
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Multiprogramming – Multiple Threads of Control
Static Data
Static Data
Static Data
Proc 1 2…n
• Thread Control Block (TCB)
– Holds contents of registers when thread not running – What other information?
• Where are TCBs stored? – For now, in the kernel
• PINTOS? – read thread.h and thread.c
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Second OS Concept:Address Space
• Address space ⇒ the set of accessible addresses + state associated with them:
– For 32-bit processor: 232 = 4 billion (109) addresses
– For 64-bit processor: 264 = 18 quintillion (1018) addresses
• What happens when you read or write to an address? – Perhaps acts like regular memory
– Perhaps ignores writes
– Perhaps causes I/O operation » (Memory-mapped I/O)
– Perhaps causes exception (fault)
– Communicates with another program – ….
Static Data
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Address Space: In a Picture
Static Data
instruction
Code Segment
Processor registers
• What’s in the code segment? Static data segment?
• What’s in the Stack Segment?
– How is it allocated? How big is it?
• What’s in the Heap Segment? – How is it allocated? How big?
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Previous discussion of threads:Very Simple Multiprogramming
• All vCPU’s share non-CPU resources – Memory, I/O Devices
• Each thread can read/write memory – Perhaps data of others
– can overwrite OS ?
• Unusable?
• This approach is used in
– Very early days of computing
– Embedded applications
– MacOS 1-9/Windows 3.1 (switch only with voluntary yield) – Windows 95-ME (switch with yield or timer)
• However it is risky…
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Simple Multiplexing has no Protection!
• Operating System must protect itself from user programs
– Reliability: compromising the operating system generally causes it to crash
– Security: limit the scope of what threads can do
– Privacy: limit each thread to the data it is permitted to access
– Fairness: each thread should be limited to its appropriate share of system resources (CPU time, memory, I/O, etc)
• OS must protect User programs from one another
– Prevent threads owned by one user from impacting threads owned by another user
– Example: prevent one user from stealing secret information from another user
Joseph & Kubiatowicz CS162 © UCB Spring 2022
What can the hardware do to help the OS protect itself from programs???
1/20/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 2.14
Simple Protection: Base and Bound (B&B)
Static Data
0100… Base
Static Data
Static Data
Program address
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Simple Protection: Base and Bound (B&B)
Static Data
0100… Base
Static Data
Static Data
Program address
Addresses translated when program loaded
• Still protects OS and isolates program
• Requires relocating loader
• No addition on address path
Joseph & Kubiatowicz CS162 © UCB Spring 2022
61C Review: Relocation
• Compiled .obj file linked together in an .exe
• All address in the .exe are as if it were loaded at memory address 00000000
• File contains a list of all the addresses that need to be adjusted when it is “relocated” to somewhere else.
Joseph & Kubiatowicz CS162 © UCB Spring 2022
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?
• Hardware relocation
Joseph & Kubiatowicz CS162 © UCB Spring 2022
x86 – segments and stacks
static data
code static data
heap stack
Processor Registers
CS EIP SS ESP
Start address, length and
access rights associated with SS: each segment register
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Another idea:Address SpaceTranslation
• Program operates in an address space that is distinct from the physical memory space of the machine
translator
Joseph & Kubiatowicz CS162 © UCB Spring 2022
“virtual address”
“physical address”
Paged Virtual Address Space
• What if we break the entire virtual address space into equal size chunks (i.e., pages) have a base for each?
• All pages same size, so easy to place each page in memory!
• Hardware translates address using a page table
– Each page has a separate base
– The “bound” is the page size
– Special hardware register stores pointer to page table
– Treat memory as page size frames and put any page into any frame …
• Another cs61C review…
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Paged Virtual Address
Page Table
instruction
• Instructions operate on virtual addresses
– Instruction address, load/store data address
Page (eg, 4 kb)
• Translated to a physical address through a Page Table by the hardware
• Any Page of address space can be in any (page sized) frame in memory – Or not-present (access generates a page fault)
• Special register holds page table base address (of the process)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Third OS Concept: Process
• Definition: execution environment with Restricted Rights – (Protected) Address Space with One or More Threads
– Owns memory (address space)
– Owns file descriptors, file system context, …
– Encapsulate one or more threads sharing process resources • Application program executes as a process
– Complex applications can fork/exec child processes [later!] • Why processes?
– Protected from each other!
– OS Protected from them
– Processes provides memory protection
• Fundamental tradeoff between protection and efficiency – Communication easier within a process
– Communication harder between processes
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Single and Multithreaded Processes
• Threads encapsulate concurrency: – “Active” component
• Address spaces encapsulate protection:
– “Passive” component
– Keeps buggy programs from crashing the system
• Why have multiple threads per address space?
– Parallelism: take advantage of actual hardware parallelism (e.g. multicore)
– Concurrency: ease of handling I/O and other simultaneous events
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 2.24
Protection and Isolation
• Why Do We Need Processes??
– Reliability: bugs can only overwrite memory of process they are in
– Security and privacy: malicious or compromised process can’t read or write other process’ data
– (to some degree) Fairness: enforce shares of disk, CPU • Mechanisms:
– Address translation: address space only contains its own data
– BUT: why can’t a process change the page table pointer? » Or use I/O instructions to bypass the system?
– Hardware must support privilege levels
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Fourth OS Concept: Dual Mode Operation
• Hardware provides at least two modes (at least 1 mode bit):
1. Kernel Mode (or “supervisor” mode)
2. User Mode
• Certain operations are prohibited when running in user mode
– Changing the page table pointer, disabling interrupts, interacting directly w/ hardware, writing to kernel memory
• Carefully controlled transitions between user mode and kernel mode – System calls, interrupts, exceptions
Joseph & Kubiatowicz CS162 © UCB Spring 2022
For example: UNIX System Structure
Applications Standard Libs
Kernel Mode
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 2.27
User/Kernel (Privileged) Mode
Kernel Mode
Limited HW access
Full HW access
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Additional Layers of Protection for Modern Systems
• Additional layers of protection through virtual machines or containers
– Run a complete operating system in a virtual machine
– Package all the libraries associated with an app into a container for execution
• More on these ideas later in the class
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Tying it together: Simple B&B: OS loads process
Static Data
Static Data
Static Data
Proc 1 2…n
sysmode Base
Bound uPC PC regs
0000… FFFF…
1100… 3000…
3080… FFFF…
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Simple B&B: OS gets ready to execute process
Proc 1 2…n
Static Data
Static Data
Static Data
sysmode Base
0000… FFFF…
Privileged Inst: set special registers
RTU (Return To Usermode)
1100… 3000…
3080… FFFF…
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Simple B&B: User Code Running
Static Data
Static Data
Static Data
Proc 1 2…n
sysmode Base
Bound How does kernel switch uPC
0000… FFFF…
between processes?
First question: How to return to system?
1100… 3000…
3080… FFFF…
Joseph & Kubiatowicz CS162 © UCB Spring 2022
3 types of User ⇒ 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 – e. g.,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, …
• All 3 are an UNPROGRAMMED CONTROL TRANSFER – Where does it go?
Joseph & Kubiatowicz CS162 © UCB Spring 2022
How do we get the system target address of the “unprogrammed control transfer?”
1/20/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 2.34
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?
intrpHandler_i () {
Simple B&B: User => Kernel
Static Data
Static Data
Static Data
Proc 1 2…n
sysmode Base
Bound uPC PC regs
0000… FFFF…
So: How to return to system?
– Timer Interrupt – I/O requests
– Other things
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
1100… 3000…
3080… FFFF…
0000… 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 decide which user process to run?
• How do we represent user processes in the OS? • 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
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 • Scheduling algorithm selects the next one to run
Joseph & Kubiatowicz CS162 © UCB Spring 2022
if ( readyProcesses(PCBs) ) {
nextPCB = selectProcess(PCBs);
run( nextPCB );
run_idle_process();
1/20/2022 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 2.42
Conclusion: 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
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com