CS代写 IEEE 802.3, IEEE 802.11

Design philosophy of operating systems (I)

Recap: von Neumman Architecture
05f0900cbbd273

Instructions Data
Instructions Data

What happens when creating a process
Dynamic allocated data: malloc()
static data
Virtual memory
Local variables, arguments
Linux contains a .bss section for uninitialized global variables
static data
The operating system needs to track all of these for each process!

Recap: Restricted operations
Most operations can directly execute on the processor without OS’s
intervention
The OS only takes care of protected resources, change running processes
or anything that the user program cannot handle properly
Divide operations into two modes
• Usermode
• Restricted operations
• User processes
Kernel mode
• Can perform privileged operations
• The operating system kernel
Requires architectural/hardware supports 4

Recap: Architectural support: privileged instructions
The processor provides
normal instructions and privileged instructions
Ring 3 Ring 2
Ring 1 Ring 0
Device Drivers
Device Drivers
Applications
LMSW, SIDT, ARPL, and etc…
Normal instructions: ADD, SUB, MUL, and etc …
The processor provides different modes
• Userprocessescanusenormalinstructions
• Privilegedinstructioncanonlybeusedifthe processor is in proper mode — otherwise, it incurs an exception and the OS handler needs to deal with it
Privileged instructions: HLT, CLTS, LIDT,
Least privileged Most privileged

Recap: How applications can use privileged operations?
Through the API: System calls
Implemented in “trap” instructions
• Raiseanexceptionintheprocessor
• Theprocessorsavestheexception PC and jumps to the corresponding exception handler in the OS kernel
user program
sbb %ecx,0x13(%rcx)
and %cl,(%rbx)
xor $0x19,%al
add %edx,(%rbx)
add %al,(%rax)
add %al,(%rbx)
Preserve register values/
add 0x1bad(%eax),%dh
add %al,(%eax)
decb PC0x5in2(t%oedmi)emory
in $0x8d,%al
mov %eax,0x101c
lea -0x2bb84(%ebx),%eax
mov %eax,-0x2bb8a(%ebx)
lgdtl -0x2bb8c(%ebx)
lea -0x2bf3d(%ebx),%eax
push $0x10
Restore register values/
…… PC from memory
return-from-trap
kernel/privileged mode

The OS kernel only get involved when necessary • Systemcalls
• Hardwareinterrupts
• Exceptions
The OS kernel works on behave of the requesting process — not a
Somehow like a function call to a dynamic linking library
The the process’ PC set to the invoked kernel code and enters kernel mode Kernel code preserve the current architectural states and update the PCB
As a result — overhead of copying registers, allocating local variables for kernel code and etc…
Recap: Kernel

Kernel (cont.) Outline
How to read research papers
The Structure of the ‘THE’-Multiprogramming System The Nucleus of a Multiprogramming System

The overhead of kernel

Latency Numbers Every Programmer Should Know (2020 Version)
Operations
Latency (ns)
Latency (us)
Latency (ms)
L1 cache reference
~ 1 CPU cycle
Branch mispredict
L2 cache reference
14x L1 cache
Mutex lock/unlock
Send 2K bytes over network
Main memory reference
20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy
Read 1 MB sequentially from memory
Read 4K randomly from SSD*
Read 1 MB sequentially from SSD*
Round trip within same datacenter
500,000 ns
Read 1 MB sequentially from disk
825,000 ns
2,000,000 ns
4x datacenter roundtrip
Send packet CA-Netherlands-CA
150,000,000 ns
150,000 us
https://colin-scott.github.io/personal_website/research/interactive_latency.html

Poll close in
The overhead of kernel switches/system calls
On a 3.7GHz intel Core i5-9600K Processor, please make a guess of the overhead of switching from user-mode to kernel mode.
A. asingledigitofnanoseconds B. tensofnanoseconds
C. hundreds of nanoseconds
D. asingledigitofmicroseconds E. tensofmicroseconds
Operations
Latency (ns)
L1 cache reference
Branch mispredict
L2 cache reference
Mutex lock/unlock
Send 2K bytes over network
Main memory reference
Compress 1K bytes with Zippy
Read 1 MB sequentially from memory
Read 4K randomly from SSD*
Read 1 MB sequentially from SSD*
Round trip within same datacenter
500,000 ns
Read 1 MB sequentially from disk
825,000 ns
2,000,000 ns
Send packet CA-Netherlands-CA
150,000,000 ns

Demo: Kernel Switch Overhead
Measure kernel switch overhead using lmbench http://
www.bitmover.com/lmbench/

The overhead of kernel switches/system calls
On a 3.7GHz intel Core i5-9600K Processor, please make a guess of the overhead of switching from user-mode to kernel mode.
A. asingledigitofnanoseconds B. tensofnanoseconds
D. asingledigitofmicroseconds E. tensofmicroseconds
C. hundreds of nanoseconds
Operations
Main memory reference
Compress 1K bytes with Zippy
Read 1 MB sequentially from memory
Latency (ns)
L1 cache reference
Branch mispredict
L2 cache reference
Mutex lock/unlock
Send 2K bytes over network
Read 4K randomly from SSD*
Read 1 MB sequentially from SSD*
Round trip within same datacenter
Read 1 MB sequentially from disk
500,000 ns
825,000 ns
Send packet CA-Netherlands-CA
2,000,000 ns
150,000,000 ns

How does the processor knows where to jump to?
kernel mode
power on/boot
install trap tables using privileged instructions
system call user mode
system call handlers
user process
system call
user process

How to read research papers

For each paper, you should identify the followings:
How to read research papers
Why? The most important thing when you’re reading/writing a paper
• Why should we care about this paper?
• What’s the problem that this paper is trying to address?
What? The second most important thing when you’re reading/writing a paper
• What has been proposed? and again, why the proposed idea makes
What’s new about the paper: contributions of the paper
They are important only if you want to implement the proposed idea
How does the paper accomplish the proposed idea? How does the result perform?

Recap & Brainstorm
What are those related papers that you read before?
Compare with those related papers and re-exam their whys, whats and how’s
Treating the idea presented in each paper as arguments rather than What will you propose if you’re solving the same “why”?
“absolute truth”
Why different papers solving the same problems with different
approaches?

Why is reading papers important
As a researcher
• Youwanttoidentifyimportantproblems
• Youwanttoknowwhathasbeenaccomplished
your systems, applications
You want to know if you can apply the proposed mechanism You want to know how to do it
As an engineer
• Youwanttoknowifthereisasolutionofthedesignproblemsof

The Structure of the ‘THE’-
Multiprogramming System
Edsger W. Dijkstra
Technological University, Eindhoven, The Netherlands

• • • • • •
Edsger W. Dijkstra
11 May 1930 – 6 August 2002
Dijkstra’s algorithm (single-source shortest path problem)
Synchronization primitive, Mutual exclusion, Critical sections — appendix of this paper
Dining philosophers problem Program verification Multithreaded programming Concurrent programming Dijkstra–Scholten algorithm ……

Poll close in
How many of the following statements fulfill the reasons of having
“THE” system in addition to the computer and the application
! Improvestheresponsetimeofexecutingaprogram ” Improvestheutilizationofperipherals
# Providesamultiaccesssystem
$ Supportsdatasharingamonguserprograms
A. 0 B. 1 C. 2 D. 3 E. 4

Where is why? Usually, you should be able to identify the why in the
very beginning part of a paper

How many of the following statements fulfill the reasons of having ! Improvestheresponsetimeofexecutingaprogram
“THE” system in addition to the computer and the application
” Improvestheutilizationofperipherals
# Providesamultiaccesssystem
$ Supportsdatasharingamonguserprograms A. 0
response time: submission until start execution turn-around time: submission until the end

Performance Metrics
CPU utilization — how busy we keep the CPU to be — CPU is busy does not Latency — the time between start execution and completion
mean it’s making progress for the user program
Wait time — the time between the job is ready (not including the overhead of queuing, command processing) and the first time when the job is scheduled
Fairness — every process should get a fair chance to make progress 26
the job is scheduled
Throughput — the amount of “tasks/processes/threads” that we can finish within a given amount of time
Turnaround time — the time between submission/arrival and completion Response time — the time between submission and the first time when

Why should people care about this paper in 1968? • Turn-aroundtimeofshortprograms
• Economicuseofperipherals
• Automaticcontrolofbackingstorage
• Economicuseofthemachine
• Designingasystemisdifficultin1968
• Difficult to verify soundness
• Difficult to prove correctness
• Difficult to deal with the complexities

The computer in the era of “THE”
cycle time: 0.5 ns (clock rate: 2 GHz)
the era of “THE”
Core memory
cycle time: 2.5 us (clock rate: 400KHz)
512KWords response time: 40ms 1000 chars/sec
response time: 20us – 10ms 100MB/sec-2.4GB/sec

processes Where is what?
ict layered design

virtualized peripherals
virtualized console
virtual memory
virtualized processor
What has been proposed?
layer 5: operators
layer 4: applications
layer 3: I/O & peripherals buffering
layer 2: message interpreter
layer 1: memory (segment/page) management
layer 0: processor allocation & scheduling
Each layer has a different privilege mode — your processor needs to provide 5 levels of execution modes

Poll close in
Why layered/hierarchical design?
How many the following is/are true regarding the proposed
hierarchical design
! Thehierarchicaldesignfacilitatesdebugging
” Thehierarchicaldesignmakesverificationofsystemcomponentseasier # Thehierarchicaldesignreducestheoverheadofrunningasingleprocess $ Thehierarchicaldesignallowsflexibleresourceallocation

Why layered/hierarchical design?
How many the following is/are true regarding the proposed
hierarchical design
! Thehierarchicaldesignfacilitatesdebugging
” Thehierarchicaldesignmakesverificationofsystemcomponentseasier
# Thehierarchicaldesignreducestheoverheadofrunningasingleprocess
$ Thehierarchicaldesignallowsflexibleresourceallocation
— what a potential problem is this?
— function calls/syscalls, memory copying, and etc…

What has been proposed?
virtualized peripherals
virtualized console
virtual memory
virtualized processor
layer 5: operators
layer 4: applications
layer 3: I/O & peripherals buffering
layer 2: message interpreter
layer 1: memory (segment/page) management
layer 0: processor allocation & scheduling
What if the program of processor allocation/scheduling needs more memory?
Careful layout of levels:
The peripherals always need to go through message interpreter. Why?

Where is how?

How they achieved these goals?
Built the layered system to facilitate debugging
Priority scheduling to improve turn-around time
Mutual synchronization for sharing resource among processes • Processorallocationforprocesses
• Accessofthephysicalconsoleamongvirtualconsoles
• Accessperipheralsamonguserprograms
• Keepthisinmind,wewilldiscussmutualexclusionindetaillater 38

Where else do you see hierarchical designs?
Application
TCP/UDP…
IPv4, IPv6
IEEE 802.3, IEEE 802.11
Application
Optical Fiber, Cooper wires, Air

Process abstraction Hierarchical system design Virtual memory
Mutual Synchronization
Impacts of THE

The Nucleus of a Multiprogramming
Per Brinch Hansen
A/S Regnecentralen, Copenhagen, Denmark

Poll close in
Why “Nucleus”
A. Feasibility
B. Performance C. Freedom
D. Hierarchy
E. Robustness
Which of the following words best described the why of “The
Nucleus of a Multiprogramming System”

C. Freedom
Why “Nucleus”
Which of the following words best described the why of “The
Nucleus of a Multiprogramming System”
A. Feasibility
B. Performance
D. Hierarchy E. Robustness
avoid this kind of pronoun

Office Hour links are inside Google Calendar events: https://calendar.google.com/calendar/u/0/r? oogle.com
Reading quizzes due this Thursday
We will make both midterm and final exams online this quarter
• AvoidtheuncertaintyofCOVID-19
• Avoidhigh-densityintheclassroom(onlysits60andwehave59 for now) during examines
Announcement

Engineering

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

Related Posts