I/O Management and Disk Scheduling

Wykład 2

Fizyczna reprezentacja

danych

Opracowanie Zbigniew Sołtys
na podstawie :
Systemy operacyjne – William Stallings
Podstawy systemów operacyjnych – A. Silberschatz,

Budowa Systemu Operacyjnego Unix - M.Bach

Rodzaje urządzeń I/O

•

Do komunikacji z
użytkownikami

–

Drukarki

–

Terminale

•

Klawiatury

•

Myszki

Rodzaje urządzeń I/O

•

Do komunikacji z innymi
urządzeniami

–

Dyski, urządzenia taśmowe

–

CD, RW

–

Czujniki

–

Kontrolery

Rodzaje urządzeń I/O

•

Do komunikacji

–

Z innymi urządzeniami

–

Modemy

Różnice pomiędzy

urządzeniami I/O

•

Szybkość transmisji danych

Różnice pomiędzy

urządzeniami I/O

•

Z punktu widzenia oprogramowania

–

Dysk używany do przechowywania
plików wymaga odpowiedniej
organizacji – system plików

–

Dysk używany do przechowywania
stron pamięci wymaga specjalnego
programu (część jądra)

–

Terminal używany przez
administratora wymaga wyższego
priorytetu

Różnice pomiędzy

urządzeniami I/O

•

Sposób transmisji

–

Strumień bajtów lub bloki

•

Reprezentacja danych

–

Różne sposoby kodowania

•

Obsługa błędów

–

Urządzenia różnie reagują na
błędy

Buforowanie I/O

•

Powody buforowania

–

Proces musi czekać na
zakończenie operacji I/O przed
rozpoczęciem wykonywania.

–

Niektóre strony pamięci muszą
pozostać zablokowane do czasu
zakończenia operacji I/O.

Buforowanie I/O

•

Block-oriented

–

Information is stored in fixed sized

blocks

–

Transfers are made a block at a time

–

Used for disks and tapes

•

Stream-oriented

–

Transfer information as a stream of bytes

–

Used for terminals, printers,

communication ports, mouse and other

pointing devices, and most other devices

that are not secondary storage

Parametry wydajnościowe

dysków

•

Pozycjonowanie głowicy

•

Opóźnienie rotacyjne

–

Czas ustawienia odpowiedniego
sektora pod głowicą

Parametry wydajnościowe

dysków

•

Czas dostępu

–

Suma czasów seek time i
opóźnienia rotacyjnego

•

Transfer danych następuje
podczas przesuwania się
odpowiedniego sektora pod
głowicą

Strategie szeregowania

dysku

•

Czas wyszukiwania (seek time)
ma istotny wpływ na wydajność

•

W czasie pracy systemu
występuje wiele żądań dostępu

•

Jeśli obsługiwać je będziemy
według FIFO (losowość żądań) –
mała wydajność

Strategie szeregowania

dysku

•

First-in, first-out (FIFO)

–

Żądania obsługiwane sekwencyjnie

–

Sprawiedliwe podejście

–

Ruchy głowicy losowe przy wielu procesach

•

http://gaia.ecs.csus.edu/
%7ezhangd/oscal/oscal.htm

Strategie szeregowania

dysku

•

Priorytet

–

Celem jest optymalizacja
wykonania zadań a nie dostępu do
danych.

–

Mniejsze zadania – większy
priorytet

–

Dobry czas reakcji

Strategie szeregowania

dysku

•

Shortest Service Time First SSTF

–

Wybierane jest żądanie wymagające
minimalnego ruchu głowicy w stosunku
do jej aktualnego położenia

–

Minimalizacja czasu wyszukiwania

Strategie szeregowania

dysku

•

SCAN

–

Ramię porusza się w jednym kierunku,
obsługując żądania aż do osiągnięcia
skrajnej ścieżki

–

Kierunek jest odwracany

Strategie szeregowania

dysku

•

C-SCAN

–

Ogranicza skanowanie tylko do jednego
kierunku

–

Po osiągnięciu ostatniej ścieżki, ramię
wraca na początek

Strategie szeregowania

dysku

•

N-step-SCAN

–

Tworzenie kilku kolejek

–

Kolejki obsługiwane są kolejno przy

użyciu SCAN

–

Nowe żądania dodawane są do

nieobsługiwanej kolejki

•

FSCAN

–

Dwie kolejki

–

Jedna zawsze wolna dla nowych

żądań

RAID

•

Redundant Array of Independent
Disks

•

Zbiór dysków fizycznych
widzianych przez system
operacyjny jako jedno logiczne
urządzenia

•

Dane są rozproszone na dyskach.

•

Można uzyskać redundancje
danych

Disk Cache

•

Buffer in main memory for disk
sectors

•

Contains a copy of some of the
sectors on the disk

Least Recently Used

•

The block that has been in the

cache the longest with no

reference to it is replaced

•

The cache consists of a stack of

blocks

•

Most recently referenced block is

on the top of the stack

•

When a block is referenced or

brought into the cache, it is

placed on the top of the stack

Least Recently Used

•

The block on the bottom of the
stack is removed when a new
block is brought in

•

Blocks don’t actually move
around in main memory

•

A stack of pointers is used

Least Frequently Used

•

The block that has experienced the

fewest references is replaced

•

A counter is associated with each block

•

Counter is incremented each time

block accessed

•

Block with smallest count is selected

for replacement

•

Some blocks may be referenced many

times in a short period of time and the

reference count is misleading

UNIX SCR4 I/O

•

Each individual
device is
associated with
a special file

•

Two types of I/O

–

Buffered

–

Unbuffered

Linux I/O

•

Elevator scheduler

–

Maintains a single queue for disk
read and write requests

–

Keeps list of requests sorted by
block number

–

Drive moves in a single direction
to satisy each request

Linux I/O

•

Deadline scheduler

–

Uses three queues

•

Incoming requests

•

Read requests go to the tail of a FIFO
queue

•

Write requests go to the tail of a FIFO
queue

–

Each request has an expiration
time

Linux I/O

•

Anticipatory I/O scheduler

–

Delay a short period of time after
satisfying a read request to see if
a new nearby request can be
made

Windows I/O

•

Basic I/O modules

–

Cache manager

–

File system drivers

–

Network drivers

–

Hardware device drivers

Document Outline