OPERATING SYSTEM STRUCTURES

OPERATING SYSTEM

CONTROLS AND COORDINATES THE USE OF THE HARDWARE AMONG THE VARIOUS APPLICATION PROGRAMS FOR THE VARIOUS USERS

A COMPUTER SYSTEM COMPONENTS:

HARDWARE
OPERATING SYSTEM
APPLICATIONS PROGRAMS
USERS

TYPE OF OPERATING SYSTEMS:

SIMPLE BATCH
MULTIPROGRAMMED BATCHED
TIME-SHARING
PERSONAL-COMPUTER
PARALLEL SYSTEM
DISTRIBUTES SYSTEMS
REAL TIME SYSTEMS

A MODERN COMPUTER SYSTEM

I/O STRUCTURE

I/O INTERRUPTS (SYNCHRONOUS AND ASYNCHRONOUS)

DMA STRUCTURE

STORAGE

CACHE
REGISTERS
MAIN MEMORY
MAGNETIC DISKS
MAGNETIC TAPES

OPERATING SYSTEM COMPONENTS

PROCESS MANAGEMENT

MAIN-MEMORY MANAGEMENT

FILE MANAGEMENT

I/O SYSTEM MANAGEMENT

SECONDARY-STORAGE MANAGEMENT

NETWORKING

PROTECTION SYSTEM

COMAND-INTERPRETER SYSTEM

SYSTEM CALLS

PROVIDE THE INTERFACE BETWEEN A PROCESS AND THE OPERATING SYSTEM

CATEGORIES:

PROCESS CONTROL
FILE MANIPULATION
DEVICE MAIPULATION
INFORMATION MAINTENANCE
COMMUNICATIONS

SYSTEM PROGRAMS

FILE MANIPULATION AND MODIFICATION

STATUS INFORMATION

PROGRAMMING-LANGUAGE SUPPORT

PROGRAM LOADING AND EXECUTION

COMMUNICATIONS

OPERATING SYSTEM STRUCTURES:

MONOLITHIC STRUCTURE
LAYERED STRUCTURE
CLIENT/SERVER MODEL
VIRTUAL MACHINE

OPERATING SYSTEM SERVICES:

PROGRAM EXECUTION
I/O OPERATIONS
FILE SYSTEM MANIPULATION HELPING USER
COMMUNICATIONS
ERROR DETECTION
RESOURCE ALLOCATION
ACCOUNTING HELPING SYSTEM
PROTECTION AND SECURITY

METHODOLOGY FOR OPERATING SYSTEM IMPLEMENTATION

DESIGN GOALS
MECHANISMS AND POLICIES
IMPLEMENTATIONS

PROCESSES

A PROCESS IS A PROGRAM EXECUTING A GIVEN SEQUENTIAL COMPUTATION

PROCESS ELEMENTS:

PROGRAM CODE
PROGRAM COUNTER
CONTENTS OF THE PROCESSOR’ REGISTERS
STACK
DATA SECTION

OPERATIGN SYSTEMS AND PROCESSES

OPERATIONS ON PROCESSES

SCHEDULING OF PROCESSES

MECHANISMS FOR:

SYNCHRONIZATION

COMMUNICATION

DEADLOCK HANDLING

STATE OF A PROCESS

Running Process loses CPU:

It executes a system call

An interrupt occurs

The Process is exiting

Process Control Block

Process Identification
Process State
CPU Scheduling Information
Program Counter
Memory Management Information (memory limits, etc.)
Accounting Information (amount of CPU used, etc.)
I/O Status Information (list of I/O devices allocated, etc.)

Interruption Procedure

Save PCB in a stack
Load information about interruption program
Execute the interruption program
Move blocked process to ready queue
Select process to run (scheduler program)
Begin execution of the active program

SWAPPING (the system very loaded)

OPERATIONS ON PROCESSES

Process Creation

Process Deletion

Scheduling

Long-term Scheduler

Short-term Scheduler

Medium-term Scheduler

Long-term Scheduler

Must select a new process for the CPU quite frequently

Must be very fast

Execute at least one every 100 milliseconds

Short-term Scheduler:

Execute much less frequently

Control the degree of multiprogramming

May be absent

Medium-term Scheduler:

- Swap out and swap in a process from the memory

Normally, when the system is overloaded

CONTEXT SWITCH

Save the state of the old process

Load the saved state for the new process

CONCURRENT PROCESSES

Independent

Cooperating + Producer-Consumer

Producer à Buffer -> Consumer

+ Client-Server

Information Sharing

Computational Speedup

Modularity

Convenience

THREADS

It is a lightweight process that does not have its own address space but shares it with its parent and other peer threads, collectively known as a task. A conventional process (heavyweight process) is a task with a single thread

- A thread has: + A program counter

+ Set of registers

+ Own stack

- A thread share: + The code segment

+ The data segment

+ OS resources

+ Opened files

+ Address space

THREADS

IMPLEMENTATION

1. Kernel-Support threads + System Calls

+ One process table entry per thread

+ Complex Switch

2. User-level Threads + One process table entry per task

+ Thread library

+ Blocking Problems

THREADS

- SERVER/WORKERS

TEAMS

PIPELING

SCHEDULING

DECIDES HOW TO ALLOCATE THE CPU AND THE MAIN MEMORY TO THE PROCESSES

CPU SCHEDULER -> SHORT-TERM SCHEDULER

MAIN MEMORY SCHEDULER -> MEDIUM-TERM SCHEDULER

GENERAL OBJECTIVES

MINIMIZE THE REPONSE TIME OF INTERACTIVE PROCESSES

MINIMIZE THE TOURNAROUND TIME OF BATCH PROCESSES

MAXIMIZE THROUGHPUT

MAXIMIZE CPU UTILISATION

MINIMIZE WAITING TIME

FAIR TO ALL CLASSES OF PROCESSES

AVOID STARVATION

SCHEDULING

NON-PRE-EMPTIVE SCHEDULER: NEVER REMOVES A RESOURCE FROM A PROCESS THAT STILL NEEDS IT.

PRE-EMPTIVE SCHEDULER: CAN TEMPORARELY REMOVE A RESOURCE FROM A PROCESS IF ANOTHERE PROCESS REQUIRES IT MORE URGENTLY.

CPU SCHEDULING DECISION:

FROM THE RUNNING STATE à TO THE WAITING STATE

FROM THE RUNNING STATE à TO THE READY STATE

FROM THE WAITING STATE à TO THE READY STATE

PROCESS TERMINATES

NON-PREEMPTIVE POLICIES

FIRST COME – FIRST SERVED

+ Can be monopolized the CPU

SHORTEST JOB FIRST:

+ Minimal average delay

+ Starvation

PREEMPTIVE POLICIES

ROUND ROBIN

+ Similar to FCFS but processes only get the CPU for a

fixed amount of time (time quantum or time slice)

+ Performance of this policies F(length of the quantum)

GENERAL MULTI-LEVEL OR PRIORITY SCHEDULING:

+ A given priority by process

+ A queue per priority level (array of FCFS queues)

+ Preemptive policy between priorities queues

+ Starvation for low-priority processes

PREEMPTIVE POLICIES

Multi-level feedback queues

+ Dynamic priorities

+ Each queue has a different time quantum

+ A process that exceeds its time quantum is moved to a

lower priority queue

+ A process that has not used the CPU for too long time is

moved to a higher priority queue

Guaranted Scheduling

+ Goal: fair share

+ The highest priority to the process that has the lowest

actual-to planned CPU usage ratio

PREEMPTIVE POLICIES

MULTI-LEVEL QUEUES BY CHARACTERISTICS:

+ Partition the ready queue into several separate queues

+ Each queue has its own scheduling algorithm

+ Scheduling between the queues: * Priorities

* Time quantum

+ Each queue represents a property of the process to allow

a classification of the processes into different groups

Floating Priorities: + Increase when the process completes an I/O

+ Decrease when the process exceeds its quantum

Aging: + Solve starvation problem

+ Gradually increasing the priority of process that wait

INTERPROCESS COMMUNICATION

SET OF TOOLS PROVIDED BY THE OPERATING SYSTEM TO ALLOW PROCESSES THAT DO NOT SHARE COMMON MEMORY SEGMENTS TO COMMUNICATE WITH EACH OTHER

TWO BASIC OPERATIONS:

send

receive

INTERPROCESS COMMUNICATION

TYPES:

+ DIRECT COMMUNICATION

SEND AND RECEIVE PRIMITIVES ALWAYS SPECIFY

PROCESS AS DESTINATION OR SOURCE

send(P, message) <-SYMMETRIC send(P, message)

receive(Q, message) receive(Q, message)

+ INDIRECT COMMUNICATION

SEND AND RECEIVE PRIMITIVES ALWAYS SPECIFY INTERMEDIARY ENTITY (THE MAILBOX OR PORT)

THE MAILBOX IS A SYSTEM OBJECT CREATE BY THE KERNEL

MAILBOX CAN BE: PRIVATE OR PUBLIC

send(A, message)

receive(A, message)

INTERPROCESS COMMUNICATION

TYPES:

+ BLOCKING (SYNCHRONOUS)

A BLOCKING SEND DOES NOT RETURN UNTIL THE MESSAGE HAS BEEN RECEIVED BY THE RECEIVING PROCESS

A BLOCKING RECEIVE DOES NOT RETURN UNTIL A MESSAGE HAS BEEN RECEIVED

+ NON-BLOCKING (ASYNCHRONOUS)

A NON-BLOCKING SEND RETURN AS SOON AS THE MESSAGE HAS BEEN ACCEPTED FOR DELIVERY BY THE OPERATING SYSTEM

A NON-BLOCKING RECEIVE RETURN AS SOON AS IT HAS EITHER RETRIEVED A MESSAGE OR LEARNED THAT THE MAILBOX IS EMPTY

INTERPROCESS COMMUNICATION

- BUFFERS + ZERO CAPACITY => RENDEZVOUS

+ BOUNDED CAPACITY

+ THEORETICALLY UNLIMITED CAPACITY

REMOTE PROCEDURE CALLS

USER PROGRAM

USER STUB: PACKS ARGUMENT

UNPACK REPLY

PERFORMS REQUIRED DATA CONVERSION

SEND A REQUEST AND WAIT

COMMUNICATION PACKAGE

SERVER STUB UNPACKS REQUEST

PACK RESULTS

PERFORMS REQUIRED DATA CONVERSION

WAIT FOR INCOMING REQUESTS AND SENDS

THE REPLY

SERVER PROCEDURE

EXCEPTIONS

PROCESS TERMINATES

LOST MESSAGES

SCRAMBLED MESSAGES

INTERPROCESS SYNCHRONIZATION

PROBLEM: WHENEVER TWO OR MORE PROCESSES SHARE COMMON DATA (WHICH CAN BE STORED IN A FILE, OR SHARED MEMORY SEGMENT), UNPREDICTABLE RESULTS ARE LIKELY TO HAPPEN IF TWO OF THE PROCESS ATTEMPT TO ACCESS THE SARED DATA AT THE SAME TIME

INTERPROCESS SYNCHRONIZATION

CRITICAL SECTION

EACH PROCESS HAS A SEGMENT CODE, CALLED A CRITICIAL SECTION, TO SHARE DATA WITH OTHER PROCESSES. WHEN ONE PROCESS IS EXECUTING IN ITS CRITICAL SECTION, NO OTHER PROCESS IS TO BE ALLOWED TO EXECUTE IN ITS CRITICAL SECTION

SOLUTIONS

DISABLE INTERRUPTS

MUTUAL EXCLUSION

CRITERIA TO SATISFY

NO TWO PROCESSES MAY BE SIMULTANEOUSLY INTO THEIR CRITICAL SECTIONS FOR THE SAME SHARED DATA

NO ASSUMPTIONS MAY BE MADE ABOUT THE SPEEDS AT WHICH THE PROCESSES WILL EXECUTE

NO PROCESS SHOULD BE PREVENTED TO ENTER ITS CRITICAL SECTION WHEN NO OTHER PROCESS IS INSIDE ITS OWN CRITICAL SECTION FOR THE SAME SHARED DATA

NO PROCESS SHOULD HAVE TO WAIT FOREVER TO ENTER ITS CRITICAL SECTION

SOFTWARE SOLUTION

LOCK VARIABLES

STRIC ALTERNATION

PETERSON’S ALGORITHMS

HARDWARE SOLUTION

TEST AND SET INSTRUCTION

SWAP

PROBLEMS:

THEY RELY ON BUSY WAITS (IT WASTES CPU CYCLES)

THEY GENERATE UNNECESSARY CONTEXT SWITCHES

SEMAPHORES

TWO ATOMIC OPERATIONS

APPLICATIONS:

+ MUTUAL EXCLUSION

INITIAL VALUE OF SEMAPHORE = 0

ONE SEMAPHORE FOR EACH CRITICAL SECTION

P(&MUTEX) V(&MUTEX)

+ FORCING A PROCESS TO WAIT FOR ANOTHER:

INITIAL VALUE OF SEMAPHORE = 1

THE PROCESS THAT WAITS => P(&sem)

THE PROCESS THAT TELLS IT IS READY => V(&sem)

SEMAPHORES

+ FORCING TWO PROCESSES TO WAIT FOR EACH OTHER:

INITIAL VALUE OF SEMAPHORE = 1

THE FIRST PROCESS

V(&1-READY)

P(&2-READY)

THE SECOND PROCESS

P(&1-READY)

V(&2-READY)

EXAMPLE (Producer-Consumer)

MONITORS

A MONITOR IS A PACKAGE ENCAPSULATING PROCEDURES, VARIABLES AND DATA STRUCTURES

MONITOR PROCEDURES ARE ALWAYS EXECUTED ONE AT A TIME SO MUTUAL EXCLUSION IS ALWAYS GUARANTEED

MONITORS PROCEDURES CAN:

+ WAIT ON A CONDITION => COND.WAIT

+ GET A SIGNAL => COND.SIGNAL

THE MONITOR BODY IS EXECUTED WHEN A MONITOR IS STARTED (INITIALIZATION CODE)

MONITORS

EVENTCOUNTS

- 3 OPERATIONS: + READ (E)

+ ADVANCE (E)

+ AWAIT (E, V)

MESSAGE PASSING

CLASSICAL SYNCHRONIZATION PROBLEMS

PRODUCER AND CONSUMER

2 PROCESSES SHARE A COMMON BUFFER WHOSE SIZE IS FIXED

PRODUCER PRODUCES ITEMS AND STORES THEM IN BUFFER

CONSUMER REMOVES ITEMS FROM BUFFER AND CONSUMES THEM

PRODUCER AND CONSUMER MUST BE PREVENT FROM ACCESSING THE BUFFER AT THE SAME TIME

B) THE READERS-WRITERS PROBLEM

2 TYPES OF PROCESSES:

+ THE READERS THAT NEED TO ACCESS FILES

+ THE WRITERS THAT NEED TO UPDATE THEM

READERS PROCESSES MUST BE PREVENT FROM ACCESING FILE WHILE SOME WRITER PROCESS UPDATE THEM.

WRITERS PROCESSES MUST BE PREVENT FROM ACCESING FILE WHILE ANY OTHER PROCESS ACCESSES THEM.

C) THE DINING PHILOSOPHERS

FIVE PHILOSOPHERS SIT AT A TABLE. THEY SPEND THEIR TIME THINKING AND EATING SPAGHETTI; THE PROBLEM IS THAT THERE ARE ONLY 5 FORKS.

THE SLEEPING BARBER

A BARBER SHP HAS ONE BARBER CHAIR AND ONE BARBER WHO SLEEP WHEN THERE ARE NO COSTUMERS

COSTUMERS DO NOT WAIT IF THE SHOP IS FULL

DEADLOCK

A SET OF PROCESSES IS IN A DEADLOCK STATE WHEN EVERY PROCESS IN THE SET IS WAITING FOR AN EVENT THAT CAN BE CAUSED BY ONLY ANOTHER PROCESS IN THE SET

WHEN SEVERAL PROCESSES ARE BLOCKED AND EACH OF THESE PROCESSES IS WAITING FOR A RESOURCE THAT CAN ONLY BE RELEASED BY ANOTHER BLOCKED PROCESS

TYPE OF RESOURCE + SERIALLY REUSABLE RESOURCE

+ CONSUMABLE RESOURCE

MODE OF OPERATION + REQUEST

+ USE

+ RELEASE

DEADLOCK MANAGEMENT

+ IGNORE THE PROBLEM

+ DEADLOCK PREVENTION DEADLOCK

+ DEADLOCK AVOIDANCE NEVER OCCURS

+ DEADLOCK DETECTION

RESOURCE ALLOCATION GRAPH

VERTICES + RESOURCES EDGES + REQUEST

+ PROCESSES + ASSIGNEMENT

NECESSARY CONDITION FOR A DEADLOCK

FOUR NECESSARY CONDITION THAT MUST BE SIMULTANEOUSLY IN EFFECT

MUTUAL EXCLUSION (AT LEAST ONE RESOURCE)

HOLD AND WAIT CONDITION

NON PREEMPTION

CIRCULAR WAIT

DEADLOCK PREVENTION (DENYING ONE OF THE CONDITIONS)

DENYING MUTUAL EXCLUSION

DENYING THE WAIT FOR CONDITION

OBTAIN ALL THE RESOURCES BEFORE USING ANY OF THEM, OR

BEFORE IT CAN REQUEST ANY ADDITIONAL RESOURCES, HOWEVER IT MUST RELEASE ALL THE RESOURCE CURRENTLY ALLOCATED

DENYING THE NON PREEMPTION CONDITION

ABORT PROCESSES

APPLIED TO RESOURCES WHOSE STATE CAN BE EASILY SAVED AND RESTORED LATER

PREVENTING CIRCULAR WAITS

IMPOSE A TOTAL ORDER ON ALL RESOURCES TYPE

ALL PROCESS MUST FOLLOW THAT ORDER WHEN THEY ACQUIRE NEW RESOURCES

DEADLOCK AVOIDANCE

- INFORMATION

+ THE RESOURCES CURRENTLY AVAILABLE

+ THE RESOURCES CURRENTLY ALLOCATED

+ THE FUTURE REQUESTS AND RELEASES

SAFE STATE: THE SYSTEM CAN ALLOCATE RESOURCES TO EACH PROCESS (UP TO ITS MAXIMUN) IN SOME ORDER AND STILL AVOID A DEADLOCK

FREE=3 T0 T1 T2 T3 T4 T0 T1

9 A 3 3 3 3 3 3 5

4 B 2 4 - - - 2 2

7 C 2 2 2 7 - 2 2

RESOURCE ALLOCATION GRAPH => CLAIM EDGE

THE REQUEST CAN BE GRANTED ONLY IF CONVERTING A GIVEN CLAIM EDGE TO ASSIGNMENT EDGE DOES NOT RESULT IN THE FORMATION OF A CYCLE

DEADLOCK AVOIDANCE

BANKER’S ALGORITHMS

RESOURCES ALLOCATION NEED

4 2 3 1 0 0 1 0 2 0 0 1

AVAILABLE 2 0 0 1 1 0 1 0

2 1 0 0 0 1 2 0 2 1 0 0

RULES: A<B IFF Ai<=Bi

S _i=1^mALLOCATIONij + AVAILABLEj = RESOURCEj

REPEAT WHILE THERE IS A PROCESS Pi WITHOUT MARK

WHERE NEEDi <= AVAILABLE

AVAILABLE = AVAILABLE + NEEDi

MARK PROCESS Pi

IF THERE ARE PROCESSES WITHOUT MARK

UNSAFE STATE

ELSE

SAFE STATE

DEADLOCK PREVENTION

DETECTION MECHANISM

SIMPLE INSTANCE OF EACH RESOURCE TYPE

- MULTIPLE INSTANCE OF EACH RESOURCE TYPE

IF THERE ARE PROCESSES WITHOUT MARK

PROCESSES BLOCKED

RECOVERY MECHANISM

MANUALLY

- ABORT: + ABORT ALL DEADLOCKED PROCESSES

+ ABORT ONE PROCESS AT A TIME UNTIL THE

DEADLOCK CYCLE IS TERMINATED

PREEMPT SOME RESOURCES FROM ONE OR MORE OF THE DEADLOCK PROCESSES

SELECTING A VICTIM
ROLLBACK
STARVATION

MEMORY MANAGEMENT

MEMORY: LARGE ARRAY OF WORDS OR BYTES, EACH WITH ITS OWN ADDRESS

CPU FETCHES INSTRUCTIONS FROM MEMORY ACCORDING TO THE VALUE OF THE PROGRAM COUNTER

EACH PROGRAM HAD ACCESS/MANAGED TO WHOLE MAIN MEMORY

UNIPROGRAMMING

+ MEMORY-RESIDENT MONITOR

+ MEMORY PROTECTION HARDWARE

MULTIPROGRAMMING WITH FIXED PARTITION

+ FIXED NUMBER OF MEMORY PARTITIONS WITH FIXED BOUNDARIES

+ PROGRAMS RUNNING IN DIFFERENT MEMORY PARTITION

DIFFERENT STARTING ADDRESS
FORCE PROGRAMS TO BE ALWAYS LOADED IN THE SAME PARTITION
HAVE A LOADER TO MODIFY THE STARTING ADDRESS OF A PROGRAM AT THE MOMENT IT IS LOADED INTO MAIN MEMORY

MEMORY MANAGEMENT

+ MEMORY PROTECTION

MULTIPROGRAMMING WITH VARIABLE PARTITION

+ EACH PROCESS IS GIVEN EXACTLY THE MEMORY SPACE IT REQUIRES

+ MEMORY MANAGER LOADS ALL THE PROCESS UNTIL MAIN MEMORY IS FULL => FREE LIST

MEMORY MANAGEMENT

+ EXTERNAL FRAGMENTATION: FREE MEMORY FRAGMENT INTO A LARGE NUMBER OF SMALL BLOCKS

COMPACTION
DYNAMIC ADDRESS RELOCATION (MMU)

+ MEMORY ALLOCATION:

FIRST FIT
BEST FIT
WORST FIT
FAST FIST

PAGING AND SEGMENTATION STRATEGIES

+ BINDING OF INSTRUCTION AND DATA TO MEMORY ADDRESS

COMPILE TIME
LOAD TIME
EXECUTION TIME

MEMORY MANAGEMENT

+ DYNAMIC LOADING AND LINKING

+ OVERLAYS => TO KEEP IN MEMORY ONLY THE CODE

THAT IS NEED

+ SWAPPING

VIRTUAL MEMORY

NON-CONTIGUOUS ALLOCATION OF MEMORY

+ PROCESS ADRESS SPACES à DISJOINTS BLOCKS OF

PHYSICAL MEMORY

(CALLED PAGES OR

SEGMENTS)

Virtual address Real address

+ CPU à MMU à RAM

DEMAND FETCH

+ PROCESS CAN BE EXECUTED WOTHOUT FETCHING INTO MEMORY IST WHOLE APRESS SPACE

+ PROCESS ADDRESS SPACE WILL BE FETCHED ON DEMAND

+ IF THE MEMORY IS FULL AND A PAGE NEEDS TO BE FETCHED => EXPEL SOME OTGER PAGE

+ FAULTS CAN SLOW DOWN A PROCESS

Taccess = (1-f)*Tmem + f*Tdisk

VIRTUAL MEMORY

KINDS OF VIRTUAL MEMORIES

+ PAGING SYSTEMS

PHYSICAL MEMORY=FIXED-SIZED BLOCKS

(FRAMES)

LOGICAL MEMORY=FIXED-SIZED BLOCKS

(PAGES)

PAGES = FRAMES

+ SEGMENTATION SYSTEMS

PROGRAMMER SPECIFIES HOW EACH PROGRAM WILL BE DIVIDED

ADDRESS TRANSLATION PROCESS

+ PROBLEM

VIRTUAL MEMORY

ADDRESS TRANSLATION PROCESS

+ EXAMPLE

1,024 = 10000000000

+ N LEAST SIGNIFICANT BITS = OFFSET

(N=LOG₂ (PAGE SIZE))

M-N MOST SIGNIFICANT BITS = PAGE NUMBER

VIRTUAL MEMORY

ADDRESS TRANSLATION PROCESS

5) MISSING PAGES => PAGE FAULTS => PROCESS TO

WAITING STATE

FIND EMPTY PAGE FRAME IN MEMORY
IF THERE ISN’T

2.1 EXPEL ONE PAGE FRAME FROM MEMORY

FETCH MISSING PAGE INTO THE MEMORY
UPDATE PAGE TABLE ENTRY

6) PAGE TABLE ENTRIES

EXTRA BITS

+ MODIFICATION BIT

+ PROTECTION BIT

+ PAGE REFERENCE BIT

VIRTUAL MEMORY

7) PAGE TABLE REPRESENTATION

+ EACH PROCESS PAGE TABLE IN CPU

SET OF DEDICATED REGISTERS

+ PAGE TABLE IN MEMORY

PAGE TABLE BASE REGISTER

+ TRANSLATION LOOK-ASIDE BUFFER (TLB)

Taccess = h*Tmem + (1-h)* Tmem

+ TWO LEVEL PAGES TABLE

VIRTUAL MEMORY

7) PAGE TABLE REPRESENTATION

+ INVERTED PAGE TABLE

< process-id, page-number, offset>

8) SHARED PAGES

PAGE REPLACEMENT POLICY

PAGING SYSTEM WITH SWAPPING

PRP: USED BY THE PAGE FAULT HANDLER TO SELECT THE PAGE TO BE EXPELLED FROM THE MAIN MEMORY

PAGE REPLACEMENT POLICY

- GOALS: + MINIMUM OVERHEAD

+ VICTIMS MUST NOT BE REFERENCED AGAIN IN

THE NEAR FUTURE

CODE:

FIND THE DESIRED PAGE ON THE DISK

IF THERE IS A FREE FRAME THEN

USE IT

ELSE

USE A PAGE-REPLACEMENT POLICY

WRITE THE VICTIM PAGE TO THE DISK

READ THE DESIRED PAGE INTO THE FREE FRAME AND UPDATE PAGE AND/OR FRAME TABLE.

RESTART THE USER PROCESS

GLOBAL VERSUS LOCAL ALLOCATION

PAGE REPLACEMENT POLICY

POLICIES:

+ FIFO (FIRST IN – FIRST OUT)

BELADY’S ANOMALY

Reference String: 0 1 2 3 0 1 4 0 1 2 3 4

+ LRU (LEAST RECENTLY USED)

+ SECOND CHANCE AND CLOCK

+ LFU (LEAST FREQUENTLY USED)

+ MFU (MOST FREQUENTLY USED)

PAGE REPLACEMENT POLICY

+ VARIABLE SIZE LOCAL POLICIES

TRASHING: THERE ARE TOO MANY PROCESS IN MAIN MEMORY AND MOST PROCESS IN WAITING STATE BECAUSE THE PAGING DEVICE CANNOT KEEP UP WITH ALL PAGE REQUEST (A PROCESS IS TRASHING IF IT IS SPENDING MORE TIEM PAGIN THAN EXECUTING

WORKING SET: KEEPS IN MAIN MEMORY ALL PAGES THAT HAVE BEEN REFERENCED DURING THE LAST D REFERENCED ISSUED BY THE PROCESS. Conversely, all pages that were not referenced during this time interval are inmediately expelled.

ALLOCATION OF FRAMES

+ EQUAL ALLOCATION:

m/n FRAMES PER PROCESS

m: number of frames

n: number of process

+ PROPORTIONAL ALLOCATION

s_i /S*m FRAMES PER PROCESS

S=å s_i S: size of virtual memory

s_i: size of virtual memory for process i

SEGMENTATION

SEGMENTATION WITH PAGING

PROCESSES -> SEGMENT TABLES

SEGMENT -> PAGE TABLE

NUMBER OF SEGMENT

NUMBER OF PAGE

OFFSET

SEGMENTATION

FILE SYSTEMS

IT IS THE PART OF THE OPERATING SYSTEM THAT PROVIDES LONG TERM STORAGE OF INFORMATION. THE OPERATING SYSTEM PROVIDES A UNIFORM LOGICAL VIEW OF THIS INFORMATION STORAGE

- ELEMENTS: + COLLECTION OF FILES

+ DIRECTORY STRUCTURE

FILES:

+ IS A SET OF RELATED INFORMATION THAT IS STORAGE ON SECONDARY STORAGE.

+ IS A LOGICAL STORAGE UNIT THAT THE OPERATING SYSTEM ABSTRACTS FROM THE PHYSYCAL PROPERTIES OF ITS STORAGE DEVICES

+ SEQUENCE OF BITS WHOSE IS DEFINED BY THE FILE’S CREATOR

FILES TYPES

+ ORDINARY FILES (ASCII, BINARY, EXECUTABLE) LIKE SOURCE CODE, TEXT FILE, ETC.

+ DIRECTORIES

+ SPECIAL FILES: DEVICES, SYSTEM OBJECTS

FILE SYSTEMS

FILE STRUCTURE

+ SET OF RECORDS => SET OF FIELDS

+ BLOCK OF RECORDS => PACKING THECNIQUES

+ TREE OF RECORDS

+ SEQUENCE OF BYTES

ACCESS METHODS

+ SEQUENCIAL ACCESS

+ DIRECT ACCESS

+ USING A KEY

FILE SYSTEMS

FILE ATRIBUTES

+ NAME

+ TYPE

+ LOCATION

+ FILE PROTECTION: owner, password, access control list

+ HISTORIAL INFORMATION: creation date, last access date

+ ACCOUNTING INFORMATION: file size

+ FLAGS: hidden flag, backup flag

OPERATIONS

+ OPEN

+ READ

start from the current position

+ WRITE

+ SEEK => direct access

+ CLOSE

+ CREATE

+ DELETE

+ OTHERS: APPEND, RENAME, ETC.

MAPPED FILES

IT IS A FILE THAT IS MAPPED INTO THE VIRTUAL MEMORY SPACE OF A GIVEN PROCESS

LESS CONTEXT SWITCHES

SHARED A FILE AMONGS PROCESS IS HARD

ALLOCATION METHODS

SEQUENTIAL ALLOCATION

+ SIMPLE AND LOW ACCESS TIME

+ FRAGMENTATION AND PREDICTION OF THE SIZE

ALLOCATION METHODS

LINKED ALLOCATION

+ EACH DISK BLOCK CONTAINS THE ADDRESS OF THE

NEXT ONE

+ NO EXTERNAL FRAGMENTATION AND FILE GROWTH

EASY

ALLOCATION METHODS

INDEXED ALLOCATION

+ A FILE INDEX WITH THE ADDRESS OF ALL THE BLOCKS

IN THE FILE

MS-DOS SOLUTION

LINKED ALLOCATION METHOD WITH A FILE ALLOCATION TABLE

FILE 1 => BLOCKS: 0 3 6 7 8 9 10

FILE 2 => BLOCKS: 1 2 4 5

UNIX SOLUTION

SUPERBLOCK

DIRECTORIES

OPERATION

+ CREATE

+ DELETE

+ RENAME

+ LINK

+ LIST

+ SEARCH (PATH NAME: ABSOLUTE OR RELATIVE)

DIRECTORY STRUCTURE

+ SINGLE STRUCTURE

+ TWO-LEVEL

DIRECTORY STRUCTURE

+ TREE-STRUCTURE

+ ACYCLIC STRUCTURE

UNIX SOLUTION

FREE-SPACE MANAGEMENT

BIT VECTOR
LINKED LIST
GROUPING
COUNTING

DISK SCHEDULING

FIFO

SSTF (SHORTEST-NEXT-TIME-FIRST)

DISK SCHEDULING

SCAN

C-SCAN

LOOK

PROTECTION
TO CONTROL ACCESS TO RESOURCES

TECHNIQUES:

+ ACCESS CONTROL LIST <user name, type-access>

+ TICKETS OR CAPABILIITES => password

I/O HARDWARE

- STORAGE DEVICES: DISKS, TAPES

- TRANSMISSION DEVICES: NETWORK CARDS, MODEMS

- HUMAN-INTERFACE DEVICES: SCREEN, KEYBOARD, MOUSE

- SPECIAL DEVICES: PORT, BUS, CONTROLLERS

I/O HARDWARE

INTERRUP-DRIVEN I/O CYCLE

I/O INTERFACE

I/O HARDWARE

DEVICE CHARACTERISTICS

+ CHARACTER-STREAM OR BLOCK

+ SEQUENTIAL OR RANDOM-ACCESS

+ SYNCHRONOUS OR ASYNCHRONOUS

+ SHARABLE OR DEDICATED

+ SPEED OF OPERATION

+ READ-WRITE, READ ONLY, WRITE ONLY

I/O REQUEST