CS计算机代考程序代写 python mips compiler Java file system gui flex Fortran computer architecture cache Excel assembly assembler Slide 1

Slide 1

Operating Systems
CSCI-GA.2250-001

Introduction

Hubertus Franke

.edu

Components of a Modern Computer

– One or more processors

– Main memory

– Disks

– Printers

– Keyboard

– Mouse

– Display

– Network interfaces

– I/O devices

Media
Player

emails Games Word
Processing

Media
Player

emails Games Word
Processing

Does a programmer need to understand all this hardware
in order to write these software programs?

Media
Player

emails Games Word
Processing

Operating System

Components of a
Modern Computer

Figure 1-1. Where the operating system fits in.

The Operating System as an
Extended Machine

Operating systems turn ugly hardware
into beautiful abstractions (arguable).

Assembler
Bitmapping
Hardware

APIs
Documented
Man(ual)-pages

The Operating System as a
Resource Manager

• Top down view
– Provide abstractions to application programs

• Bottom up view
– Manage pieces of complex systems

(hardware and events)

• Alternative view
– Provide orderly, controlled allocation of

resources

The Two Main Tasks of OS

• Provide programmers (and programs) a
clean set of abstract resources and
services to manipulate these resources

• Manage the hardware resources

A Glimpse on Hardware

Simplified view: System Components are interlinked through a
shared bus and communicate over that bus.

This is done through bus transactions
(e.g. load/store to/from memroy, interprocessor notifications,
device accesses, … )

A Glimpse on Hardware

Reality Check:
In reality there are many buses between the components one set
relates to memory accesses (load/store) and one to I/O subsystems

A few conventions

• Computer Scientists think in 2^N

• Remember a few tricks

• Know:
2^0 .. 2^9
2^10 ~10^3 = 1KB

• and the rest is easy (e.g.):

– 2^20 ~10^6 = 1MB

– 2^30 ~10^9 = 1GB

– 2^32 = 2^(30+2) = 4GB

– 2^16 = 2^(10+6) = 64KB

Expected you can do 2^N math on the spot

A few assembler conventions used

• Occasionally we need to use some assembler
notation, I utilize a general fictious notation that
should be easily understood

• Loads and stores:
– basic means to obtain a data item from/to memory
– ld r3,addr for loading a piece of memory (addr) into a

register (r3) (will cover that in a bit)
– st r3,addr for storing a value in register (r3) back to

memory (addr)

• Arithmetic operations:
– takes operands and performs basic operations
– add r3, r4, r5 ( r3 = r4+r5)

What Is an OS?

Resources

• Allocation

• Protection

• Reclamation

• Virtualization

Services

• Abstraction

• Simplification

• Convenience

• Standardization

Makes computer usage simpler

CONTAINER

What Is an OS?

Resources

• Allocation

• Protection

• Reclamation

• Virtualization

Finite resources

Competing demands

Examples:

• CPU

• Memory

• Disk

• Network

Limited budget,
Land,
Oil,
Gas,

Government

What Is an OS?

Resources

• Allocation

• Protection

• Reclamation

• Virtualization

You can’t hurt me

I can’t hurt you

Implies some degree of
safety & security

Law and order

Government

What Is an OS?

Resources

• Allocation

• Protection

• Reclamation

• Virtualization

The OS gives

The OS takes away

Voluntary at run time

Implied at termination

Involuntary

Cooperative

Income Tax

Government

What Is an OS?

Resources

• Allocation

• Protection

• Reclamation

• Virtualization

illusion of infinite

private resources

Memory versus disk

Timeshared CPU

More extreme cases
possible (& exist)

Social security

Government

Operating System

• OS (kernel) is really just a program that
runs with special privileges to implement
the features of allocation, protection,
reclamation and virtualization

and

the services that are structured on top
of it.

Booting Sequence
• BIOS starts

– checks how much RAM
– keyboard
– other basic devices

• BIOS determines boot Device

• The first sector in boot device is read into memory and
executed to determine active partition

• Secondary boot loader is loaded from that partition.

• This loaders loads the OS from the active partition and
starts it.

POST (Power On Self Test)

• BIOS: Binary Input/Output System
• e.g. UEFI: Unified Extensible Firmware Interface (UEFI) is a specification

for a software program that connects a computer’s firmware to its operating system (OS)
and functions as nowadays BIOS

OS

Types Concepts
Different

Structures

Different aspects of
looking at an
operating system

OS

Types Concepts

• Mainframe/supercomputer OS
•batch
•transaction processing
•timesharing
•e.g. OS/390

•Server OS
•Multiprocessor OS
•PC OS
•Embedded OS
•Sensor node OS
•RTOS
•Smart card OS

Different
Structures

OS

Types Concepts

• Mainframe OS/supercomputer
•batch
•transaction processing
•timesharing
•e.g. OS/390

•Server OS
•Multiprocessor OS
•PC OS
•Embedded OS
•Sensor node OS
•RTOS
•Smart card OS

•Processes
•Its address space
•Its resources
•Process table

•Address space
•File system
•I/O
•Protection

Different
Structures

OS

Types
Different

StructuresConcepts

• Mainframe OS/supercomputer
•batch
•transaction processing
•timesharing
•e.g. OS/390

•Server OS
•Multiprocessor OS
•PC OS
•Embedded OS
•Sensor node OS
•RTOS
•Smart card OS

•Processes
•Its address space
•Its resources
•Process table

•Address space
•File system
•I/O
•Protection

•Monolithic
•Layered systems
•Microkernels
•Client-server
•Virtual machines

OS

Types
Different

StructuresConcepts

• Mainframe OS
•batch
•transaction processing
•timesharing
•e.g. OS/390

•Server OS
•Multiprocessor OS
•PC OS
•Embedded OS
•Sensor node OS
•RTOS
•Smart card OS

•Processes
•Its address space
•Its resources
•Process table

•Address space
•File system
•I/O
•Protection

•Monolithic
•Layered systems
•Microkernels
•Client-server
•Virtual machines

Main objectives of an OS:

• Convenience

• Efficiency

• Ability to evolve

OS Services

• Program development

• Program execution

• Access I/O devices

• Controlled access to files

• System access

• Error detection and response

• Accounting

Hardware and Software
Infrastructure

Figure 2.1 Computer Hardware and Software Infrastructure

In a nutshell

• OS is really a manager:
– programs, applications, and processes are the

customers

– The hardware provide the resources

• OS works in different environments and
under different restrictions
(supercomputers, workstations, notebooks,
tablets, smartphones, real-time, …)

History of Operating Systems

• “We can chart our future clearly and wisely only when we know the
path which has led to the present.”
– Adlai E. Stevenson, Lawyer and Politician

• First generation 1945 – 1955
– vacuum tubes, plug boards (no OS)

• Second generation 1955 – 1965
– transistors, batch systems

• Third generation 1965 – 1980
– ICs and multiprogramming

• Fourth generation 1980 – present
– server computers
– personal computers

– Fifth generation 2005 – present
– hand-held devices, sensors

History of Operating Systems (1945-55)

• Programming and Control tied to the Computer

Source: wikipedia

History of Operating Systems
(1945-1955)

• Vacuum tubes, plug boards (no OS)
– ENIAC (UPenn 1944)

• 30 tons, 150m, 5000calcs/sec

– Zuse’s Z3 (1941)
• 2000 relays

• 22 bit words

• 5-10 Hz

• What’s a bug?

History of Operating Systems
(1955-65)

• Structure of a typical JCL job – 2nd generation
• Single user
• Programmer/User as the operator
• Secure, but inefficient use of expensive resources
• Low CPU utilization-slow mechanical I/O devices

• Emergence of the Mainframe
• Programmers isolated from machine
• Programming Languages emerge

• Fortran
• Cobol

History of Operating System
(1955-65)

Early batch system
– bring cards to 1401
– read cards to tape
– put tape on 7094 which does computing
– put tape on 1401 which prints output

History of Operating Systems
(1965-80)

• Multiprogramming systems
– Multiple jobs in memory – 3rd generation
– Allow overlap of CPU and I/O activity
– Polling/Interrupts, Timesharing
– Spooling

• Different types
– Epitomized by the IBM 360 machine
– MFT (IBM OS/MFT) Fixed Number of Tasks
– MVT (IBM OS/MVT) Variable Number of Tasks

• Birth of Modern Operating System Concepts
– Time Sharing: when and what to run → scheduling
– Resource Control: memory management, protection

The Operating System Jungle / Zoo
(1980-present)

• Mainframe operating systems

• Server operating systems

• Multiprocessor operating systems

• Personal computer operating systems

• Real-time operating systems

• Embedded operating systems

• Smart card operating systems

• Cellphone/tablet operating systems

• Sensor operating systems

Computer Architecture

( a closer look )

We must know and understand
what is actually managed by an OS

Processors

• Each CPU has a specific set of instructions

– ISA (Instruction Set Architecture) largely epitomized in the assembler

• RISC: Sparc, MIPS, PowerPC

• CISC: x86, zSeries

• All CPUs contain

– General registers inside to hold key variables and temporary results

– Special registers visible to the programmer

• Program counter contains the memory address of the next instruction to be

fetched

• Stack pointer points to the top of the current stack in memory

• PSW (Program Status Word) contains the condition code bits which are set by

comparison instructions, the CPU priority, the mode (user or kernel) and

various other control bits.

How Processors Work
• Execute instructions

– CPU cycles
• Fetch (from mem) → decode → execute

• Program counter (PC)
– When is PC changed?

• Pipeline: fetch n+2 while decode n+1 while execute n

(a) A three-stage pipeline. (b) A superscalar CPU.

Memory-Storage Hierarchy

• Other metrics:
– Bandwidth (e.g. MemBandwidth 30GB/s → 200GB/s, Disk ~70-200MB/s)

• What can an OS do to increase its “performance”
– Active management where to place data !!!

< - 4MB -1GB 2GB- 1TB -TB Latency Capacity 1ns 32+32 10ns 8KB – 2MB (L1 – L3) 100ns GBs - TBs 10msec 10s * TBs 10secs 500s * TBs CPU Caches • Principle: – Data/Instruction that were recently used are “likely” used again in short period – Caching is principle used in “many” subsystems ( I/O, filesystems, … ) [ hardware and software] • Cache hit: – no need to access memory • Cache miss: – data obtained from mem, possibly update cache • Issues – Operation MUST be correct – Cache management for Memory done in hardware – Data can be in read state in multiple caches but only in one cache when in write state CPU Cache CPU Cache Mem CPU Cache Example of real cache/memory access times • Modern systems have multiple CPUs with their own attached memory and multiple level of caches. • Non-uniform memory access. http://software.intel.com/en-us/forums/showthread.php?t=77966 CPU1 Core1 Core1 L1 L2 L1 Ram CPU2 Core1 Core1 L1 L2 L1 Ram CPU3 Core1 Core1 L1 L2 L1 Ram CPU4 Core1 Core1 L1 L2 L1 Ram CPU-0 Cache CPU-1 Cache Mem A=5 A[s]=5 C0 loads A ( A on C0 in shared mode [s]) Scenarios of Cache Coherency Scenario 1 Scenario 2 CPU-0 Cache CPU-1 Cache Mem A=5 A[x]=9 C0 stores A=9 ( A on C0 is now in exclusive mode [x] ) CPU-0 Cache CPU-1 Cache Mem A=5 A[s]=5 CPU-0 Cache CPU-1 Cache Mem A=5 A[s]=5A[s]=5 C0 loads A ( A on C0 in shared mode [s]) C1 now loads A (cache line is copied) ( A on C0 and C1 in shared mode [s]) C1 stores A=12 ( A on C1 in exclusive mode ) cache line is just moved CPU-0 Cache CPU-1 Cache Mem A=5 A[s]=5 C0 loads A ( A on C0 in shared mode [s]) Scenarios of Cache Coherency Scenario 3 CPU-0 Cache CPU-1 Cache Mem A=5 A[x]=9 C0 stores A=9 ( A on C0 is now in exclusive mode [x] ) CPU-0 Cache CPU-1 Cache Mem A=5 A[x]=12 (1) (2) C1 loads A Forces C0 to write back A to mem (or lowest level of shared cache) and put A into shared mode for C0/C1 Scenarios of Cache Coherency Scenario 4 CPU-0 Cache CPU-1 Cache Mem A=5 A[x]=2 CPU-0 Cache CPU-1 Cache Mem A=2 A[s]=2 A[s]=2 • A can be in [s] across several CPUs • A can be at most in ONE CPU in [x] and nowhere else in [s] Imperative at all times Now C0 sets A=9 All cache lines on other cpus must be invalidated and A on C0 in [x] Scenarios of Cache Coherency Scenario 5 Both thread C0, C1, C2 load A ( A on C0, C1, C2 in shared mode )CPU-0 Cache CPU-1 Cache Mem A=5 A[s]=5A[s]=5 CPU-2 Cache A[s]=5 CPU-0 Cache CPU-1 Cache Mem A=5 A[x]=9 CPU-2 Cache Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Eighth Edition ", Chapter 12 Example of Device (resource and operation) • Disk: – Multiple-subdevices – Translations • Block -> sector

– Head Movement
– Seek Time
– Data Placement

– Power Management

OS Major Components

• Process and thread management

• Resource management
– CPU
– Memory
– Device (I/O)

• File system

• Bootstrapping

Process: a running program

• A process includes
– Address space

– Process table entries (state, registers)
• Open files, thread(s) state, resources held

• A process tree
– A created two child processes, B and C

– B created three child processes, D, E, and F

Address Space
• Defines where sections of data and

code are located in 32 or 64
address space

• Defines protection of such
sections
– ReadOnly, ReadWrite, Execute

• Confined “private” addressing
concept
– ➔ requires form of address

virtualization

#include

#include

#define NUMS (4)

int a;

int b = 2;

int x;

int y = 3;

int main(int argc, char* argv[])

{

int *values;

int i;

values = (int*) malloc(NUMS*sizeof(int));

for (i=0 ; i KernelMode

– Trap

– Interrupt (also Kernel2Kernel)

– Execption (also Kernel2Kernel)

KernelMode -> UserMode

– rfi (return from interrupt)
(also kernel to kernel)

Interrupt / Exception / Traps
• Understand similarity and differences between these 3 “events”

• Interrupts:
– asynchronous :Triggered by an event from a “device” (device needs attention)

• Exceptions:
– Synchronous: triggered by a “fault condition” of an instruction condition

• Traps (instruction, aka sc [ system call ] ) == special kind of exception
– Synchronous: triggered by “trap instruction” for syscall

• They all end up in the so called “interrupt handler”:

assembler code aka __entry in the kernel

from there the assembler identifies whether an interrupt, execption,
or trap and jumps to their respective handlers.

Protected Hardware register is initialized in OS bootstrap with the
address of __entry so the hardware knows where to jump to when an
Interrupt or Trap or Exception is raised.

Attention all Personnel

• __entry is the ONLY means to enter
into the operating system kernel

either by
– hw-interrupt
– exception
– trap

A peek into Unix/Linux

Application

Portable OS Layer

Libraries

Machine-dependent layer

User space/level

Kernel space/level

• User/kernel modes are

supported by hardware

•Some systems do not have

clear user-kernel boundary

Unix: Application

Application

(E.g., emacs)

Portable OS Layer

Libraries

Machine-dependent layer

Written by programmer

Compiled by programmer

Uses function calls

Unix: Libraries

Application

Portable OS Layer

Libraries (e.g., stdio.h)

Machine-dependent layer

Provided pre-compiled

Defined in headers

Input to linker (compiler)

Invoked like functions

May be “resolved” when

program is loaded

Typical Unix OS Structure

Application

Portable OS Layer

Libraries

Machine-dependent layer

system calls (read, open..)

All “high-level” code

Typical Unix OS Structure

Application

Portable OS Layer

Libraries

Machine-dependent layer

Bootstrap

System initialization

Interrupt and exception

I/O device driver

Memory management

Kernel/user mode

switching

Processor management

Service Requests
from user to kernel (OS)

• Basic means to request services from the
operating system kernel is to make
system calls
(which end up in a “trap / sc” event)

• It’s a well architected and “secure” API
between kernel and userspace

Some System Calls For Process Management

Signal

Call Description

kill(pid, signal) Deliver signal to the process pid

signal( signal, function ) Define which function to call for signal

System Calls (POSIX)
• System calls for process management

• Example of fork()used in simplified shell program

#define TRUE 1

while(TRUE) {

type_prompt();

read_command(command, parameters);

if (fork()!=0) {

/* some code*/

waitpid(-1,&status, 0);}

else {

/* some code*/

execve(command, parameters,0);

}

}

Portable Operating System Interface for Unix (IEEE standard 90’s)

System Calls (POSIX)

• System calls for file/directory
management
– fd = open(file,how,….)
– n = write(fd,buffer,nbytes)
– e = rmdir(name)

• Miscellaneous
– e = kill(pid,signal)
– e = chmod(name,mode)

List of important syscalls

System Call == OS kernel service request

• Invoked via non-priviliged instruction ( trap / sc)
– Treated often like an interrupt, but its “somewhat” different

• Synchronous transfer control from user to kernel

• Side-effect of executing a trap in userspace is that
an “exception” is raised and program execution
continues at a prescribed instruction in the kernel
see __entry -> syscall_handler

How are syscalls implemented
• First one has to understand how arguments in any regular function call are passed.

• For this a calling code convention is defined.

• Typically arguments are passed through registers
(sometimes as offsets on the stack)

• Those registers can be modified by the function called, any other registers most be
saved and restored by the callee function

– Volatile register (args,stackptr) and non-volative registers (callee must save and restore)

• Generally referred to as ABI: Application Binary Interface

• Syscalls are simply an extension on this. All compilers need to agree on this or code
will no cooperate/work.

Excellent writeup: https://lwn.net/Articles/604287/

Trap/SC instruction

syscall implementation (user side)
/usr/include/asm-generic/unistd.h
unistd.h:extern ssize_t pread64 (int __fd, void *__buf, size_t __nbytes)

ABI: Application Binary Interface

Definition agreed upon by libc and kernel
➔ ABI is known. Compiler assembles args

#define __SYSCALL(number) syscall(number…)

syscall is implemented as assembler largely

taking the arguments already in the right

registers and TRAP-ing into the kernel.

• Kernel defines a table (using the compiler help )

int syscall_table [ __NR_SYSCALL_MAX ] = {

:

[ __NR_READ] = sys_read,

[ __NR_WRITE] = sys_write,

:

}

• On system trap, architecture automatically and immediately
enters kernel mode and runs a small piece of assembler code that is
stored at a machine register address set by the OS at boot time.

• Said trap assembler code (aka interrupt handler) does the following:
– Checks the syscall number in well known register ( see ABI ) to be in range
– Assembler equivalent:

• Change stack to kernel ( more on this in a bit )
• All arguments are already in right place thanks to the ABI and the compiler’s help
• “Call/jmp” to syscall_table[ registers.syscall_number ]; // see ABI definition
• After return from ^^^^, switch back from kernel stack to user stack and RFI

(return from kernel mode).

syscall implementation (kernel side)

The compiler does the magic
and associates the syscall
number with the kernel
internal function

Putting it all together (based on ARM/EABI)

r0 = fd

r1 = buf

r2 = 64

r7 = __NR_READ

Your app.c

libc.so

Regular function call

assembler based on compiler

Function expects args in r0,r1,r2,…

Regular function call
All argument registers must stay intact:

r0,r1,r2,…

User
kernel

System Call with args passed
over the stack (different ABI)

Example:

read (fd, buffer,nbytes)

In this example the ABI
dictates that function arguments
are pushed on the stack not through
registers

(older architectures)

System Calls (Windows Win32 API)

• Process Management
– CreateProcess- new process (combined work of fork and

execve in UNIX)
• In Windows – no process hierarchy, event concept implemented

– WaitForSingleObject – wait for an event (can wait for
process to exit)

• File Management
– CreateFile, CloseHandle, CreateDirectory, …
– Windows does not have signals, links to files, …, but has a

large number of system calls for managing GUI

Other implicit/explicit
OS Services Examples

• Services that can be provided at user level
(because they only read unprotected data)

– Read time of the day

• Services that need to be provided at kernel level
– System calls: file open, close, read and write

– Control the CPU so that users won’t stuck by running
while ( 1 ) ;

– Protection:
• Keep user programs from crashing OS

• Keep user programs from crashing each other

Is Any OS Complete?
(Criteria to Evaluate OS)

Portability

Security

Fairness

Robustness

Efficiency

Interfaces

When you look at these criteria you should see that
they can’t all be satisfied at the same time.

Recap: What is an OS ?

• Code that:
– Sits between programs & hardware
– Sits between different programs
– Sits betweens different users

• Job of OS:
– Manage hardware resources

• Allocation, protection, reclamation, virtualization

– Provide services to app. How ? → system call
• Abstraction, simplification, standardization

Application

OS

Hardware

Monolithic systems – basic structure

1. A main program that invokes the
requested service procedure.

2. A set of service procedures that carry
out the system calls.

3. A set of utility procedures that help
the service procedures.

Operating Systems Structure
(Chapter 1)

Monolithic Systems

By far the most common OS organization

A simple structuring model for a
monolithic system.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639

Layered Systems

• Layer-n services are comprised of services provided by Layer-(n-1)..
• Structure of the THE operating system (Dijkstra 1968)

• THE used this approach as a design AID
• Multics Operating System relied on Hardware Protection to enforce

layering

• Microkernels move the layering boundaries between kernel and
userspace

• Move only most rudimentary services to kernel

• Move other services to Userspace

• Higher Overhead, but more flexibility, higher robustness
– Minix (Tanenbaum is only 3200 lines of C and 800 lines assembler)

– L4, K42,

Microkernels

• Assumes generic network model (network, bus)

• Communication via message passing

Client-Server Model

• VM/370: Timesharing system should be comprised of:
– Multiprogramming

– extended machine with more interface than bare HW

– Completely separate these two functions

• Provides ability to “self-virtualize”

• Beginning of “modern day” virtualization technology

Virtual Machines (1)

• A type 1 hypervisor
(like virtual machine monitor)

– Priviliged instructions are trapped and “emulated”

• A type 2 hypervisor (runs on top of a host OS)
– Unmodified ( trapped )

– Modified ( paravirtualization )

Virtual Machines (2)

Other areas of virtual machines
usage

• Java virtual machines

• Dynamic scripting languages (e.g. Python)

• Typically define a instruction set that is
“interpreted” by the associate virtual
machine
– JVM, PVM

– Modern system then JIT (Just In Time)
compile the VM instructions into native code.

History of the UNIX Operating System
(source: wikipedia)

Bell Labs: Thomson, Richie, Kernigan et.al

DLL
DLL

Loader

Source Code to Execution

Assembly
Assembler Object File

Object File
Object File

Assembly
Assembly

Executable

Linker
Library
Library
Library

Assembly
Assembly

C source
Compiler

DLL

DLL
DLL

Loader

Source Code to Execution

Object File
Object File

Object File

Executable

Linker
Library
Library
Library

DLL

What happens to your program
after it is compiled but before
it can be executed?

The OS Expectation

• The OS expects executable files to have a
specific format

– Header info
• Code locations and size
• Data locations and size

– Code & data

– Symbol Table
• List of names of things defined in your program and

where they are defined
• List of names of things defined elsewhere that are

used by your program, and where they are used.

Example of Things

#include

extern int errno;

int main () {

printf (“hello,

world\n”)

}

• Symbol defined in
your program and
used elsewhere

• main

• Symbol defined
elsewhere and used
by your program

• printf

• errno

Two Steps Operation:
Parts of OS

Linking
• Stitches independently

created object files into
a single executable file
(i.e., a.out)

• Resolves cross-file
references to labels

• Listing symbols needing
to be resolved by loader

Loading
• copying a program image

from hard disk to the main
memory in order to put
the program in a ready-to-
run state

• Maps addresses within file
to memory addresses

• Resolves names of dynamic
library items

• schedule program as a new
process

Libraries (I)

• Programmers are expensive.

• Applications are more sophisticated.
– Pop-down menus, streaming video, etc

• Application programmers rely more on
library code to make high quality apps
while reducing development time.
– This means that most of the executable is

library code

Libraries (II)

• A collection of subprograms

• Libraries are distinguished from
executables in that they are not
independent programs

• Libraries are “helper” code that provides
services to some other programs

• Main advantages: reusability and
modularity

Large Programming Projects

The process of compiling C and header
files to make an executable.

#include

#include

#define NUMS (4)

int a;

int b = 2;

int x;

int y = 3;

extern int myfunc(int);

int main(int argc, char* argv[])

{

int *values;

int i;

values = (int*)

malloc(NUMS*sizeof(int));

for (i=0 ; i