CS计算机代考程序代写 x86 Java distributed system AI arm COPE-07 Operating Systems.indd

COPE-07 Operating Systems.indd

7
Operating Systems

Uwe R. Zimmer – The Australian National University

Computer Organisation & Program Execution 2021

Operating Systems

References for this chapter

[Patterson17]
David A. Patterson & John L. Hennessy
Computer Organization and Design – The Hardware/Software Interface
Chapter 4 “The Processor”,
Chapter 6 “Parallel Processors from Client to Cloud”
ARM edition, Morgan Kaufmann 2017

Operating Systems

What is an operating system?

Operating Systems

What is an operating system?

1. A virtual machine!

… offering a more comfortable and safer environment

(e.g. memory management and protection, hardware abstraction,
process management, inter-process communication, …)

Operating Systems

What is an operating system?

1. A virtual machine!

… offering a more comfortable and safer environment

Hardware

Tasks

Typ. general OS

Hardware
RT-OS

Tasks

Typ. real-time system

Hardware

Tasks

Typ. embedded system

run-time
environment

Operating Systems

What is an operating system?

2. A resource manager!

… coordinating access to hardware resources

Operating Systems

What is an operating system?

2. A resource manager!

… coordinating access to hardware resources

Operating systems deal with

• processors

• memory

• mass storage

• communication channels

• devices (timers, special purpose processors, peripheral hardware, …)

and tasks/processes/programs which are applying for access to these resources!

Operating Systems

The evolution of operating systems

• in the beginning: single user, single program, single task, serial processing – no OS

• 50s: System monitors / batch processing
the monitor ordered the sequence of jobs and triggered their sequential execution

• 50s-60s: Advanced system monitors / batch processing:
the monitor is handling interrupts and timers
fi rst support for memory protection
fi rst implementations of privileged instructions (accessible by the monitor only).

• early 60s: Multiprogramming systems:
employ the long device I/O delays for switches to other, runable programs

• early 60s: Multiprogramming, time-sharing systems:
assign time-slices to each program and switch regularly

• early 70s: Multitasking systems – multiple developments resulting in UNIX (besides others)

• early 80s: single user, single tasking systems, with emphasis on user interface or APIs.
MS-DOS, CP/M, MacOS and others fi rst employed ‘small scale’ CPUs (personal computers).

• mid-80s: Distributed/multiprocessor operating systems – modern UNIX systems (SYSV, BSD)

Operating Systems

Types of current operating systems

Personal computing systems, workstations, and workgroup servers:

• late 70s: Workstations starting by porting UNIX or VMS to ‘smaller’ computers.

• 80s: PCs starting with almost none of the classical OS-features and services,
but with a user-interface (MacOS) and simple device drivers (MS-DOS)

last 20 years: evolving and expanding into current general purpose OSs, like for instance:

• Solaris (based on SVR4, BSD, and SunOS)

• LINUX (open source UNIX re-implementation for x86 processors and others)

• current Windows (used to be partly based on Windows NT, which is ‘related’ to VMS)

• MacOS (Mach kernel with BSD Unix and a proprietary user-interface)

• Multiprocessing is supported by all these OSs to some extent.

• None of these OSs are suitable for embedded systems, although trials have been performed.

• None of these OSs are suitable for distributed or real-time systems.

Operating Systems

Types of current operating systems

Parallel operating systems

• support for a large number of processors, either:

• symmetrical: each CPU has a full copy of the operating system

• asymmetrical: only one CPU carries the full operating system, the others are
operated by small operating system stubs to transfer code or tasks.

• symmetrical: each CPU has a full copy of the operating system

•••••••••••• aaaaaaaaaaasssssssssssyyyyyyyyyyyyymmmmmmmmmmmeeeeeetttttttrrrrrrriiiiiicccccccaaaaaalllllll::::: oooooonnnnnlllllyyyyyyy ooooonnnnneeeee CCCCCCCCPPPPPUUUUU cccccaaaaaarrrrrrrrrriiiiiieeeeeessssss tttttthhhhhheeeeeee ffffffuuuuuullllllll oooopppppppeeeerrrrraaaaatttiiiiinnnggggg ssssyyyysssttteeemmm,, ttthhheee ooottttttthhhhhhhhhhhhhhheeeeeeeeeeeeerrrrrrrrrrrrrssssssssssssssss aaaaaaaaaaaaaarrrrrrrrrrrrrrrrrreeeeeee
ooooooooooppppppppppppeeeeeeeeeerrrrrrrrraaaaaattttttteeeeeeeddddd bbbbbbyyyyyy sssssmmmmmaaaaaallllllllll oooooppppppeeeeerrrrraaaaaatttttiiiiinnnnnngggggg sssssyyyyyssssssttttteeeemmmmmm sssssstuuuuuubbbbbbbssssss ttttttoooooo ttttttrrrrrraaaaannnnnnnssssssffffffeeeeeerrrrrr ccccccooooooddddddeeeeeeee oooorrr tttaaaaassskkkkksss…

Operating Systems

© 2021 Uwe R. Zimmer, The Australian National University page 398 of 489 (chapter 7: “Operating Systems” up to page 436)© 2021 Uwee R. Zimmer, The Austtrar liann NNatatioionanal l UnUniviverersisityty page 398 of yy 489 (chapter 7: “Operating Systems” up to page 436)9

Types of current operating systems

Distributed operating systems

• all CPUs carry a small kernel operating system for communication services.

• all other OS-services are distributed over available CPUs

• services may migrate

• services can be multiplied in order to

• guarantee availability (hot stand-by)

• or to increase throughput (heavy duty servers)

Operating Systems

Types of current operating systems

Real-time operating systems

• Fast context switches?

• Small size?

• Quick response to external interrupts?

• Multitasking?

• ‘low level’ programming interfaces?

• Interprocess communication tools?

• High processor utilization?

Operating Systems

Types of current operating systems

Real-time operating systems

• Fast context switches? should be fast anyway

• Small size? should be small anyway

• Quick response to external interrupts? not ‘quick’, but predictable

• Multitasking? often, not always

• ‘low level’ programming interfaces? needed in many operating systems

• Interprocess communication tools? needed in almost all operating systems

• High processor utilization? fault tolerance builds on redundancy!

Operating Systems

© 2021 Uwe R. Zimmer, The Australian National University page 401 of 489 (chapter 7: “Operating Systems” up to page 436)e R. Zimmer, The Australian National University page 401 of y 489 (chapter 7: “Operating Systems” up to page 436)9

Types of current operating systems

Real-time operating systems need to provide…
the logical correctness of the results as well as

the correctness of the time, when the results are delivered

Predictability!
(not performance!)

All results are to be delivered just-in-time – not too early, not too late.

Timing constraints are specifi ed in many different ways …

… often as a response to ‘external’ events
reactive systems

Photo: NASA

Operating Systems

Types of current operating systems

Embedded operating systems

• usually real-time systems, often hard real-time systems

• very small footprint (often a few kBytes)

• none or limited user-interaction

90-95% of all processors are working here!

Artwork by Q. Mehdi (cc attribution license)

Operating Systems

Types of current operating systems

Start-stop system

Artwork by Q. Mehdi (cc attribution license)

tSSt

Cylinder deactivation
Key identifi cation

ABS

ESC

HUD

Lane holding

Adaptive cruise control

Cross traffi c detection

Navigation system

Adaptive dampers

Displays

Dashboard

Airbags

Alarm system

A/C

Driver monitoring
Automated Wipers

Automated Lights

Black Box

Power management

Seat adjustments

Hill start assist

Transmission control

Window control Interior lights

Engine/motor management

hb d

Speech recognition

Night vision

Mirror dimming

Tail gate

Seat heating

Emergency brakes

d WiWi

Steering

Power regeneration

Entertainment system

Radar/Lidar sensing

Image processing

Automated parking

Traction control

Tire pressure sensors

Emergency services call

Blindspot detection

Operating Systems

Types of current operating systems

Embedded operating systems

• usually real-time systems, often hard real-time systems

• very small footprint (often a few kBytes)

• none or limited user-interaction

90-95% of all processors are working here!

Artwork by Q. Mehdi (cc attribution license)

Often over 100 MPUs per car
(and some of them quite high performant)

Operating Systems

What is an operating system?

Is there a standard set of features for operating systems?

Operating Systems

What is an operating system?

Is there a standard set of features for operating systems?

no:

the term ‘operating system’ covers 4 kB microkernels,

as well as > 1 GB installations of desktop general purpose operating systems.

Operating Systems

What is an operating system?

Is there a standard set of features for operating systems?

no:

the term ‘operating system’ covers 4 kB microkernels,

as well as > 1 GB installations of desktop general purpose operating systems.

Is there a minimal set of features?

Operating Systems

What is an operating system?

Is there a standard set of features for operating systems?

no:

the term ‘operating system’ covers 4 kB microkernels,

as well as > 1 GB installations of desktop general purpose operating systems.

Is there a minimal set of features?

almost:

memory management, process management and inter-process communication/synchronisation

will be considered essential in most systems

Operating Systems

What is an operating system?

Is there a standard set of features for operating systems?

no:

the term ‘operating system’ covers 4 kB microkernels,

as well as > 1 GB installations of desktop general purpose operating systems.

Is there a minimal set of features?

almost:

memory management, process management and inter-process communication/synchronisation

will be considered essential in most systems

Is there always an explicit operating system?

Operating Systems

What is an operating system?

Is there a standard set of features for operating systems?

no:

the term ‘operating system’ covers 4 kB microkernels,

as well as > 1 GB installations of desktop general purpose operating systems.

Is there a minimal set of features?

almost:

memory management, process management and inter-process communication/synchronisation

will be considered essential in most systems

Is there always an explicit operating system?

no:

some languages and development systems operate with standalone runtime environments

Operating Systems

Typical features of operating systems

Process management:
• Context switch

• Scheduling

• Book keeping (creation, states, cleanup)

context switch:

needs to…

• ‘remove’ one process from the CPU while preserving its state

• choose another process (scheduling)

• ‘insert’ the new process into the CPU, restoring the CPU state

Some CPUs have hardware support for context switching, otherwise:

use interrupt mechanism

Operating Systems

Typical features of operating systems

Memory management:
• Allocation / Deallocation

• Virtual memory: logical vs. physical addresses, segments, paging, swapping, etc.

• Memory protection (privilege levels, separate virtual memory segments, …)

• Shared memory

Synchronisation / Inter-process communication
• semaphores, mutexes, cond. variables, channels, mailboxes, MPI, etc. (chapter 4)

tightly coupled to scheduling / task switching!

Hardware abstraction
• Device drivers

• API

• Protocols, fi le systems, networking, everything else…

Operating Systems

Typical structures of operating systems

Monolithic
(or ‘the big mess…’ )

• non-portable

• hard to maintain

• lacks reliability

• all services are in the kernel (on the same privilege level)

but: may reach high effi ciency

e.g. most early UNIX systems,

MS-DOS (80s), Windows (all non-NT based versions)

MacOS (until version 9), and many others…

Hardware

Tasks

Monolithic

APIs

Operating Systems

Typical structures of operating systems

Monolithic & Modular

• Modules can be platform independent

• Easier to maintain and to develop

• Reliability is increased

• all services are still in the kernel (on the same privilege level)

may reach high effi ciency

e.g. current Linux versions

Hardware

Tasks

Modular

APIs

M1 M1 Mn…

Operating Systems

Typical structures of operating systems

Monolithic & layered

• easily portable

• signifi cantly easier to maintain

• crashing layers do not necessarily stop the whole OS

• possibly reduced effi ciency through many interfaces

• rigorous implementation of the stacked virtual machine

perspective on OSs

e.g. some current UNIX implementations (e.g. Solaris) to a certain de-
gree, many research OSs (e.g. ‘THE system’, Dijkstra ‘68)

Hardware

Tasks

Layered

Mn
OS

APIs

…

layers

Operating Systems

Typical structures of operating systems

µKernels & virtual machines

• µkernel implements essential process,
memory, and message handling

• all ‘higher’ services are dealt with outside the
kernel ☞ no threat for the kernel stability

• signifi cantly easier to maintain

• multiple OSs can be executed
at the same time

• µkernel is highly hardware dependent
☞ only the µkernel needs to be ported.

• possibly reduced effi ciency through
increased communications

e.g. wide spread concept: as early as the CP/M, VM/370 (‘79)
or as recent as MacOS X (mach kernel + BSD unix), …

Hardware

µkernel, virtual machine

µkernel

Tasks

Mn
OS

APIs

…

layers
OS

Tasks

APIs

M1 M1 Mn…OS

Tasks

APIs

Operating Systems

Typical structures of operating systems

µKernels & client-server models

• µkernel implements essential process,
memory, and message handling

• all ‘higher’ services are user level servers

• signifi cantly easier to maintain

• kernel ensures reliable message passing
between clients and servers

• highly modular and fl exible

• servers can be redundant and easily replaced

• possibly reduced effi ciency through
increased communications

e.g. current research projects, L4, etc.

Hardware

µkernel, client server structure

µkernel

service mservice 1task 1 task n

Operating Systems

Typical structures of operating systems

µKernels & client-server models

• µkernel implements essential process,
memory, and message handling

• all ‘higher’ services are user level servers

• signifi cantly easier to maintain

• kernel ensures reliable message passing
between clients and servers:
locally and through a network

• highly modular and fl exible

• servers can be redundant and easily replaced

• possibly reduced effi ciency through increased communications

e.g. Java engines,
distributed real-time operating systems, current distributed OSs research projects

µkernel, distributed systems

task 1 task n service 1

µkernel µkernel

service m

µkernel

Hardware

Network

Operating Systems

UNIX

UNIX features

• Hierarchical fi le-system (maintained via ‘mount’ and ‘unmount’)

• Universal fi le-interface applied to fi les, devices (I/O), as well as IPC

• Dynamic process creation via duplication

• Choice of shells

• Internal structure as well as all APIs are based on ‘C’

• Relatively high degree of portability

UNICS, UNIX, BSD, XENIX, System V, QNX, IRIX, SunOS, Ultrix, Sinix, Mach,
Plan 9, NeXTSTEP, AIX, HP-UX, Solaris, NetBSD, FreeBSD, Linux, OPEN-
STEP, OpenBSD, Darwin, QNX/Neutrino, OS X, QNX RTOS, … … .

Operating Systems

Introduction to processes and threads

1 CPU per
control-fl ow

Specifi c confi gurations
only, e.g.:

• Distributed µcontrollers.

• Physical process
control systems:

1 cpu per task,
connected via a
bus-system.

Process management
(scheduling) not required.

Shared memory access
need to be coordinated.

CPU
stack

code

CPU
stack

code

CPU
stack

code

address space 1

shared memory

CPU
stack

code

CPU
stack

code

CPU
stack

code

address space n

shared memory

…

Operating Systems

Introduction to processes and threads

1 CPU for all
control-fl ows

• OS: emulate one CPU
for every control-fl ow:

Multi-tasking
operating system

Support for memory
protection essential.

Process management
(scheduling) required.

Shared memory access
need to be coordinated.

stack
code

address space 1

shared memory

stack
code

CPU

stack
code

address space n

shared memory

…

Operating Systems

Introduction to processes and threads

Processes

Process ::=

Address space
+ Control fl ow(s)

Kernel has full
knowledge about all
processes as well as their
states, requirements and
currently held resources.

stack
code

address space 1

shared memory

stack
code

CPU

stack
code

address space n

shared memory

…

p
ro

ce
ss

p
ro

ce
ss

Operating Systems

Introduction to processes and threads

Threads
Threads (individual control-
fl ows) can be handled:

• Inside the OS:

Kernel scheduling.

• Thread can easily
be connected to
external events (I/O).

• Outside the OS:

User-level scheduling.

• Threads may need
to go through their
parent process
to access I/O.

stack
thread

address space 1

shared memory

stack
thread

CPU

stack
thread

address space n

shared memory

…

p
ro

ce
ss

p
ro

ce
ss

Operating Systems

Introduction to processes and threads

Symmetric
Multiprocessing

(SMP)
All CPUs share the same
physical address space
(and access to resources).

Any process / thread
can be executed on
any available CPU.

stack
thread

address space 1

shared memory

stack
thread

address space n

shared memory

…

p
ro

ce
ss

p
ro

ce
ss

CPU CPU CPUCPU …

shared memory

p
h

ys
ic

al
a

d
d

re
ss

s
p

ac
e

Operating Systems

Introduction to processes and threads

Processes ) Threads

Also processes can share memory and the specifi c defi nition of threads
is different in different operating systems and contexts:

Threads can be regarded as a group of processes, which
share some resources ( process-hierarchy).

Due to the overlap in resources, the attributes attached to
threads are less than for ‘fi rst-class-citizen-processes’.

Thread switching and inter-thread communication can be
more effi cient than switching on process level.

Scheduling of threads depends on the actual thread implementations:

• e.g. user-level control-fl ows, which the kernel has no knowledge about at all.

• e.g. kernel-level control-fl ows, which are handled as processes with some restrictions.

Operating Systems

Introduction to processes and threads

Process Control Blocks

• Process Id

• Process state:
{created, ready, executing, blocked, suspended, bored …}

• Scheduling attributes:
Priorities, deadlines, consumed CPU-time, …

• CPU state: Saved/restored information while context
switches (incl. the program counter, stack pointer, …)

• Memory attributes / privileges:
Memory base, limits, shared areas, …

• Allocated resources / privileges:
Open and requested devices and fi les, …

… PCBs (links thereof) are commonly enqueued at a certain
state or condition (awaiting access or change in state)

Process Id

Process state

Saved registers

(complete CPU state)

Scheduling info

Memory spaces /

privileges

Allocated resources /

privileges

Process Control Blocks (PCBs)

Operating Systems

Process states

• created: the task is ready to run, but
not yet considered by any dispatcher

waiting for admission

• ready: ready to run
waiting for a free CPU

• running: holds a CPU and executes

• blocked: not ready to run
waiting for a resource

blockedblocked

ready running

blocked

dispatch

timeout

block

release

created

admit

terminated

finish

m
ai

n
m

e
m

o
ry

Operating Systems

Process states

• created: the task is ready to run, but
not yet considered by any dispatcher

waiting for admission

• ready: ready to run
waiting for a free CPU

• running: holds a CPU and executes

• blocked: not ready to run
waiting for a resource

• suspended states: swapped out of
main memory
(none time critical processes)

waiting for main memory
space (and other resources)

blockedblocked

ready running

blocked

dispatch

timeout

block

release

created

admit

terminated

finish

blockedblockedblocked, susp.

suspend (swap-out)

ready, susp.

suspend (swap out)

release

reload (swap in)

m
ai

n
m

e
m

o
ry

se
co

n
d

ar
y

m
e

m
o

Operating Systems

Process states

• created: the task is ready to run, but
not yet considered by any dispatcher

waiting for admission

• ready: ready to run
waiting for a free CPU

• running: holds a CPU and executes

• blocked: not ready to run
waiting for a resource

• suspended states: swapped out of
main memory
(none time critical processes)

waiting for main memory
space (and other resources)

dispatching and suspending can
now be independent modules

blockedblocked

ready running

blocked

dispatch

timeout

block

release

created

admit

terminated

finish

blockedblockedblocked, susp.

suspend (swap-out)

ready, susp.

suspend (swap out)

release

reload (swap in)

m
ai

n
m

e
m

o
ry

se
co

n
d

ar
y

m
e

m
o

Operating Systems

Process states

CPU
creation

ydaerhctab

ready, suspended

blocked, suspended

blocked

pre-emption or cycle done

terminationn

block or synchronize

executing
admitted dispatch

unblock suspend (swap-out)

swap-in

swap-out

unblock

suspend (swap-out)

Operating Systems

Defi nition of terms

Time scales of scheduling

CPU
creation

ydaerhctab

ready, suspended

blocked, suspended

blocked

pre-emption or cycle done

terminate.

block or synchronize

executingadmit
dispatch

suspend (swap-out)

swap-in

swap-out

unblock

suspend (swap-out)

Long-term

Short-term

Medium-term

Operating Systems

Performance scheduling

Requested resource times

time0 5 10 15 20 25 30 35 40 45
(Ti, Ci)

(4, 1)

(12, 3)

(16, 8)

Tasks have an average time between instantiations of Ti
and a constant computation time of Ci

Operating Systems

Performance scheduling

First come, fi rst served (FCFS)

time0 5 10 15 20 25 30 35 40 45
(Ti, Ci)

(4, 1)

(12, 3)

(16, 8)

Waiting time: 0..11, average: 5.9 – Turnaround time: 3..12, average: 8.4

As tasks apply concurrently for resources, the actual sequence of arrival is non-deterministic.
hence even a deterministic scheduling schema like FCFS can lead to different outcomes.

Operating Systems

Performance scheduling

First come, fi rst served (FCFS)

time0 5 10 15 20 25 30 35 40 45
(Ti, Ci)

(4, 1)

(12, 3)

(16, 8)

Waiting time: 0..11, average: 5.4 – Turnaround time: 3..12, average: 8.0

In this example:
the average waiting times vary between 5.4 and 5.9
the average turnaround times vary between 8.0 and 8.4

Shortest possible maximal turnaround time!

Operating Systems

Performance scheduling

Round Robin (RR)

time0 5 10 15 20 25 30 35 40 45
(Ti, Ci)

(4, 1)

(12, 3)

(16, 8)

Waiting time: 0..5, average: 1.2 – Turnaround time: 1..20, average: 5.8

Optimized for swift initial responses.

“Stretches out” long tasks.

Bound maximal waiting time! (depended only on the number of tasks)

Operating Systems

Operating Systems
• Operating Systems

• Concept

• Categories

• Architectures

• Processes

• Defi nition

• Relation to architectures

• Scheduling

Summary

Related Posts