1

Overview Sistemas Operativos

Sistemas Informáticos

SLIDES 6

Quem são estes Senhores?

Dennis Ritchie Ken Thompson

Steve Jobs

Bill Gates

Bill Joy

Linus Torvalds

Andrew Tanenbaum

Diferentes Tipos de Software

Device Drivers

Funções do Sistema Operativo

Esconder os detalhes do hardware subjacente ao sistema� Gestão de memória� Gestão de dispositivos genéricos� Gestão de dispositivos de armazenamento

(discos/etc.)� Segurança

“Virtualizar” a utilização do processador e dos recursos associados à máquina� Cada programa corre sobre a aparência de ser o

único no sistema� O sistema operativo fornece um interface unificado

aos dispositivos da máquina

Virtualização do Processador/Dispositivos

Processador Real

Processadores Virtuais (... máquinas virtuais...)

Virtualização da Máquina

Dois aspectos fundamentais...

Multiprogramação� Trata-se de uma técnica de manter múltiplos

programas em memória simultaneamente. Cada programa executa como se fosse o único existente na máquina.

Gestão de Memória� Em qualquer altura o Sistema Operativo tem de

saber que programas estão em memória e onde é que cada um deles reside

2

Conceito de Processo

Um programa em execução com...� Um identificador único� Recursos próprios (e.g. ficheiros abertos)� Um espaço de endereçamento (i.e. memória própria

protegida de todos os outros “processos”)

MS Excel(1 processo)

MS Word(1 processo)

Histórico: batch processing Timesharing

Timesharing system A system that allows multiple users to interact with a computer at the same time

Multiprogramming A technique that allows multiple processes to be active at once, allowing programmers to interact with the computer system directly, while still sharing its resources

In a timesharing system, each user has his or her own virtual machine, in which all system resources are (in effect) available for use

Comutação entre Processos

De alguns em alguns ms é gerada uma “interrupção”

Quanto existe uma interrupção, deixa-se de executar o código do utilizador e passa-se a executar o código do sistema operativoO sistema operativo pode então comutar para outro processo (escalonamento preemptivo)

total = 0;for (int i=0; i<20000; i++)

total = total + i;

printf(“total=%d\n”, total);

while (!feof(fd)){

if (fscanf(fd, “%d”, &d) == 1)printf(“%d\n”, d);

}

(...)Nível do Utilizador

Nível do KernelRTC Interrupt Handler

Comutação de Processos Ciclo de Vida de um Processo

New

Ready(to execute)

Blocked(waiting for something)

Running

Terminated

I/O orevent waiting

End of I/O orevent completed

Dispatch

Interrupt

3

Filas do Sistema Operativo

Ready Queue� Fila onde aguardam todos os processos que estão à

espera de executar

Blocked Queue� Fila onde aguardam todos os processos que estão à

espera que uma operação de entrada/saída complete ou de um “evento especial”

Running (não é uma fila)� Processo que se encontra a executar� Apenas este processo o Sistema Operativo ocupam

tempo de processador

Escalonamento de Processos

Suponhamos que existem vários processos na Ready Queue.... � Como é que se decide qual é que executa a seguir?

Existem diversos algoritmos.Um bastante conhecido é o Round-Robin

Round Robin

É decidido à priori qual a fatia de tempo a atribuir a cada processo.� Timeslice ou Quantum de Execução

A “Ready Queue” é um lista ordenada� Cada processo executa até se esgotar o seu timeslice. Quando

isso acontece, é colocado no final da ready queue

� O próximo processo a executar é o que está à frente na readyqueue

Ver Slides_6B: Escalonamento Processos

Gestão de Memória

Bootstrap process

4

Endereços de Memória Endereços Lógicos e Físicos

Endereço Lógico: especifica um endereço queé visto pelo programa que deverá ter algumacorrespondência com um endereço físico.

Endereço Físico: endereço real/absoluto namemória principal.

Endereço Virtual ���� Endereço Físico

Endereços Lógicos e Físicos Gestão de Memória

Base register A register that holds the beginning address of the current partition

Bounds register A register that holds the length of the current partition

Particionamento de Memória

Fixed partitions Main memory is divided into a particular number of partitions.

Dynamic partitions Partitions are created to fit the needs of the programs.

5

Fixed Partitioning

Equal-size partitions

� any process whose size is less than or equal to the partition size can be loaded into an available partition.

� if all partitions are full, the operating system can swap a process out of a partition.

� a program may not fit in a partition. The programmer must design the program with overlays.

The use of main memory is inefficient. No program occupies an entire partition. This is called internal fragmentation.

Placement Algorithms with Partitions

Equal-size partitions

� because all partitions are of equal size, it does not matter which partition is used

Unequal-size partitions

� can assign each process to the smallest partition within which it will fit

� queue for each partition

� processes are assigned in such a way as to minimize wasted memory within a partition

Dynamic Partitioning

Partitions are of variable length and number.Process is allocated exactly as much memory as required.

Eventually get holes in the memory. This is called external fragmentation.

Must use compaction to shift processes so they are contiguous and all free memory is in one block.

6

Memory Compaction

To merge the memory blocks and reduce memory holes caused by external fragmentation.

Time-consuming task....

Dynamic Partitioning: Placement Algorithms

Operating system must decide which free block to allocate to a process.

Four algorithms: Best-Fit; First-Fit; Next-Fit; Worst-Fit

Placement Algorithm: Best-Fit

Best-fit algorithm

� Chooses the block that is closest in size to the request.

� Worst performance.� Since it finds the smallest block it produces the

smallest amount of fragmentation.� Memory compaction must be done more often.

Placement Algorithm: Worst-Fit

Worst-fit algorithm

� Chooses the largest available block.

� The fragmentation area can be used for another request.

Placement Algorithm: First-Fit

First-fit algorithm

� Begins to scan memory from the beginning and chooses the next available block that is largest enough.

� Fastest.� May have many process loaded in the front end of

memory that must be searched over when trying to find a free block.

Analysis of First-Fit Algorithm:

For every N allocated blocks, there are another 0.5N blocks that will be lost due to fragmentation -> 1/3 of memory will be unusable...

7

Placement Algorithm: Next-Fit

Next-fit

� Begins to scan memory from the location of the last placement and chooses the next available block that is largest enough.

Worst-Fit

Buddy System

Entire space available is treated as a single block of 2U.

If a request of size s such that 2U-1 < s <= 2U, entire block is allocated.� Otherwise block is split into two equal buddies.� Process continues until smallest block greater than

or equal to s is generated.

Exercícios Gestão Memória

8

Considere que tem um sistema de memória com as seguintes partições pela seguinte ordem:

100kb, 500kb, 200kb, 300kb, 600kb, 400kb.

Qual o resultado de execução dos algoritmos Best-Fit, First-Fit, Worst-Fit para a seguinte ordem de pedidos:

212kb, 417kb, 112kb, 526kb, 12kb- Para cada um dos algoritmos indique o total de fragmentação.

E se tivesse uma memória de 2Mb e o algoritmo Buddy-system, qual seria o resultado da execução para aquela ordem de pedidos?

Exercício

Considere a técnica de Buddy System para gestão de memória. Admitindo quea memória total é de 512kbytes. Apresente a simulação do algoritmo, “step-by-step” e indique a valor total defragmentação interna em cada passo, considerando a seguinte lista de pedidos:

Em caso de inexistência de espaço na memória principal considere aexistência de swapping para memória virtual e a aplicação do algoritmo LRU.

A: request 88kB: request 156kC: request 22kD: request 54kE: request 312k--- release C,AF: request 136k--- release DG: request 206k

Exercício Protecção de Memória

É absolutamente fundamental que cada processo não possa aceder à memória dos outros processos� Questão de segurança de dados� Protecção contra “ponteiros” perdidos e bugs de

software

� Grande problema dos Windows 95, 98 e Macsantigos!

Memória Segmentada “Real”

A cada processo corresponde um endereço base e um limite (registos especiais no processador)Sempre que existe um acesso a memória, o processador verifica se o processo se encontra a aceder à sua memória ou não

0

ProcessoA

ProcessoB

50060

60530

70000

71433

MOV AX, [50124]

MOV AX, [60000]

OK, dentro do espaço

de endereçamento

ERRO, Acesso proibido!

GPF e Segmentation Faults! ☺☺☺☺ Memória Virtual

Actualmente, todos os sistemas utilizam o conceito de memória virtual� Cada processo vê toda a memória do computador, como

sendo dele� Quando um processo gera um endereço, esse endereço é

virtual. O processador, com a ajuda do sistema operativo transforma-o num endereço físico

0 0

4Gb 4Gb

Espaço de endereçamento do processo A

Espaço de endereçamento do processo B

1000 1000

Memória física0

256Mb5000

Tabela(s) de Tradução deEndereços

Disco

9

Memória Virtual Paginada

O sistema mais utilizado nas máquinas actuaisFunciona tal como o esquema indicado anteriormente, com os seguinte pormenores� A memória física é dividida em pequenos pedaços

chamados páginas (e.g. 4Kbytes)� A memória de cada processo também é dividida em

páginas� Existe uma tabela de páginas por cada processo,

que é gerida pelo sistema operativo. É utilizando esta tabela que é feita a tradução dos endereços virtuais em endereços físicos

� Sempre que é colocado outro processo em execução, a sua tabela de páginas é carregada.

Paginação de Memória

Paged memory technique A memory management technique in which processes are divided into fixed-size pages and stored in memory frames when loaded into memory� Frame A fixed-size portion of main memory that

holds a process page� Page A fixed-size portion of a process that is stored

into a memory frame� Page-map table (PMT) A table used by the

operating system to keep track of page/frame relationships

Paginação de Memória

To produce a physical address, you first look up the page in the PMT to find the frame number in which it is stored

Then multiply the frame number by the frame size and add the offset to get the physical address

Figure 10.7 A paged memory management approach

Address Translation Scheme

Address generated by CPU is divided into:� Page number (p) – used as an index into a page

table which contains base address of each page in physical memory.

� Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit.

Paging: Address Translation

Page number (p) – used as an index into a page table which contains base address of each page in physical memory.Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit.

Paging Example

10

Free Frames

Page Tables for Example Logical-to-Physical Address Translation

Exercícios Paginação

11

Considere um computador com 256Mbytes de memória real, que usa um esquema de memória virtual de 2Gbytes, baseado em Paginação, e onde o número das páginas ocupam os 20 bits mais significativos do endereço virtual.

(a) Qual o total máximo de páginas?

(b) Qual o tamanho de cada página?

(c) Se uma PTE (Page Table Entry) ocupar 8 bytes quantas páginas ocupa a Tabela de Páginas? Qual será o tamanho máximo dessa Tabela.

Exercício Page Swapping

Demand paging An important extension of paged memory management� Not all parts of a program actually have to be in

memory at the same time� In demand paging, the pages are brought into

memory on demand

Page swap The act of bringing in a page from secondary memory, which often causes another page to be written back to secondary memory

Swapping

Swapping

A process can be swapped temporarily out of memory to disk, and then brought back into memory for continued execution.

Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped.

Example: disk: transfer rate 5Mb/secmemory to swap: 1 MbTime it takes to swap out: 1/5 sec = 200 msecAverage disk latency: 8 msecTime to swap-out/swap-in: 416 msec

Memória Virtual Need for Page Replacement

12

Basic Page Replacement

1. Find the location of the desired page on disk.

2. Find a free frame:- If there is a free frame, use it.- If there is no free frame, use a page replacement

algorithm to select a victim frame.- If victim is dirty write back to disk

3. Read the desired page into the (newly) free frame. Update the page and frame tables.

4. Restart the process.

Example Trashing

Se um processo não tem páginas “suficientes”, o ritmo de faltas de página aumenta muito. Istoé caracterizado pelo comando vmstat:� Baixa taxa de ocupação do CPU.� Grande número de operações de I/O sobre o disco

de paginação.

� Poucas “frames”livres.

Thrashing ≡ o processo está praticamentesempre à espera que o SO carregue páginas(page-in) e a transferir páginas (page-out) de/para o disco.

Trashing Exercício

Considere que tem um sistema operativo com um determinado valor limite no grau de multiprogramação e que a taxa de utilização de CPU e disco foram medidas nos seguintes 3 cenários:

(a) CPU usage [11%]; Disk usage [98%](b) CPU usage [92%]; Disk usage [5%] (c) CPU usage [12%]; Disk usage [3%]

Para cada um dos três casos, indique o que poderá estar a acontecer, indique se pode aumentar o número de processos para ocupar mais a CPU e se o mecanismo de paginação deverá estar ou não a melhorar a performance.

Localidade Temporal e Espacial

Para evitar a ocorrência de trashing é preciso que os programas explorem bem a localidade

dos dados mantidos em cache.

Localidade Temporal

Localidade Espacial

13

Hierarquia de memória

Princípio da localidade espacial: � Se eu acedi a estes dados, é

provável que aceda aos dados que estão próximos (e.g. uma imagem)

Princípio da localidade temporal:� Se eu acedi à pouco tempo a estes

dados, é provável que lhes vá aceder dentro de pouco tempo

Registos

Cache

Memória Central (RAM)

Memória de Massa (Disco)

~128x 32bits

~512Kbyte

~512Mbyte

~60Gbyte

VelocidadePreço

Tamanho

int A[][] = new int[128][128];int i,j;

// page size = 512 bytes// each row is stored in one // page

// Programa Afor (j = 0; j < 128; j++)

for (i = 0; i < 128; i++)A[i][j] = 0;

int A[][] = new int[128][128];int i,j;

// page size = 512 bytes// each row is stored in one // page

// Programa Bfor (i = 0; i < 128; i++)

for (j = 0; j < 128; j++)A[i][j] = 0;

Exemplo: dois programas...

Quem escreveu o programa A?

E o programa B?

José Peseiro

int A[][] = new int[128][128];

// Programa Afor (j = 0; j < 128; j++)

for (i = 0; i < 128; i++)A[i][j] = 0;

int A[][] = new int[128][128];

// Programa Bfor (i = 0; i < 128; i++)

for (j = 0; j < 128; j++)A[i][j] = 0;

128 page faults128 x128 = 16,384 page faults

Page Faults

int A[][] = new int[128][128];

// Programa Afor (j = 0; j < 128; j++)

for (i = 0; i < 128; i++)A[i][j] = 0;

int A[][] = new int[128][128];

// Programa Bfor (i = 0; i < 128; i++)

for (j = 0; j < 128; j++)A[i][j] = 0;

128 page faults128 x128 = 16,384 page faults

Exercício

Considere que tem duas matrizes:- int A[4][400]; - int B[4][400]. O tamanho da página neste sistema é 800 bytes e um inteiro ocupa 4 bytes. O sistema tem N Page-Frames, mas o primeiro page-frame é usado pela página 0, que contém o código. Os outros (N-1) Page-framesestão vazios no ínicio. O sistema faz uso do algoritmo LRU e do Modify-Bit para troca de páginas.

Se o número de Page-Frames for igual a cinco (N=5) quantos Page-Faults e quantos Swap-Outs serão gerados pelo Programa A? e pelo Programa B?

// Programa A

for(i=0;i < 4; i++)

for(j=0; j < 400; j++)

A[i][j]=B[i][j];

// Programa B

for(j=0;j < 400; j++)

for(i=0; i < 4; i++)

A[i][j]=B[i][j];

14

Para saber mais...

Computer Science, An Overview� Capítulo 3 (3.1, 3.2, 3.3)

Computer Science Illuminated� Capítulo 10 (10.1, 10.2, 10.3, 10.4)