Breve história dos computadores modernos
Anos 40
Nesta década, os primeiros computadores considerados "modernos" eram capazes de executar programas escritos em cartões perfurados, ou punched cards.
Os computadores executavam um programa por vez e, por causa das velocidades modestas (cerca de 100 operações por segundo), os programas demoravam dias ou semanas para serem executados até ao fim.
As pessoas que escreviam programas em cartões perfurados tinham, então, de esperar em longas filas para que seus respectivos programas pudessem ser inseridos nos computadores.
Anos 50
Uma década depois, os computadores foram evoluídos para que pudessem enfileirar vários programas de uma vez, assim as pessoas não teriam que esperar para inserir os programas: bastava colocar todos eles e o computador fazia o resto do trabalho.
Apesar de termos resolvido a questão das filas de pessoas que desenvolvem programas, ainda assim os programas eram executados em ordem, um de cada vez.
Para entendermos o problema existente nesta época, vamos lembrar que um computador moderno é composto por:
CPU (unidade central de processamento)
Memória de trabalho (espaço temporário utilizado pela CPU para executar as tarefas)
I/O: onde input pode ser por ex. o teclado, e output pode ser a impressora ou o screen (tela)
Tomemos por cenário 3 programas enfileirados: programa A, programa B e programa C. Enquanto o programa A utiliza o computador, os outros 2 ficam na fila à espera.
Tudo bem até aqui.
Mas vamos imaginar que, após utilizar a CPU para fazer seus cálculos, o programa A precisa imprimir o resultado na impressora. Esta saída (I/O) leva seu tempo, e enquanto o programa A espera no I/O, a CPU não está sendo utilizada.
Esta não-utilização da CPU é por si só um desperdício de recursos. Por quê não deixar outro programa na fila (por ex. o programa B) utilizar a CPU enquanto o programa A fica à espera de I/O? Seria um raciocínio sensato, correto?
Anos 60
Também conhecida como a era dos transistores ou third-generation computers, nesta década começamos a ver computadores cada vez menores e mais rápidos.
O objetivo aqui é justamente resolver o problema da ociosidade da CPU das décadas anteriores. Enquanto um programa espera por I/O, outro programa pode utilizar a CPU, fazendo então com que o número de programas executados dentro de um intervalo de tempo aumente. A esta taxa chamamos de troughput, ou apenas tput.
Concorrência
Isto significa que dois programas podem concorrer a recursos físicos do mesmo computador. Mas como isto é feito na prática?
Monitors
Os Monitors eram formas primitivas do que hoje conhecemos por Sistemas Operacionais. Eles eram capazes de controlar os programas enfileirados e garantir que cada um deles utilizasse uma quantia justa da CPU enquanto outros ficavam à espera de I/O.
Tal técnica se chama time-sharing multitasking.
70s
Esta é a década onde os Monitors foram evoluídos para Sistemas Operacionais (SO). Alguns rotulam como a era da explosão cambriana dos computadores, pois, a partir desta década, cada vez mais e mais SO's são criados.
Dentre os SO's criados nesta época, vamos dar destaque ao UNIX, que será utilizado como base neste guia.
UNIX foi um sistema muito importante para entendermos onde estamos hoje. Muitas distribuições de SO baseadas em Linux e BSD utilizam a filosofia UNIX, e portanto são chamados de sistemas UNIX-like.
Concorrência de recursos
SO's modernos baseados em UNIX utilizam a mesma técnica primitiva de time-sharing multitasking observada nos Monitors dos anos 50/60.
Tendo por base a concorrência de recursos, e pelo fato da memória de trabalho do computador ser global, é preciso garantir que dois processos concorrentes não utilizem o mesmo espaço de memória, caso contrário, tais programas entrariam numa condição de conflito de race condition chamada data race.
Isolamento dos programas
Para evitar data race, os SO's então têm de garantir algumas propriedades enquanto programas concorrem aos recursos físicos:
o programa precisa ser isolado, ou seja, ter seu espaço de memória reservado onde nenhum outro programa possa ver ou alterar
o programa pode eventualmente ter a necessidade de se comunicar com outros programas através do envio de mensagens
para atingir tal comunicação, os programas precisam ter identificadores únicos para serem reconhecidos no sistema operacional
Temos então o resumo das características para um programa existir dentro de um sistema operacional moderno:
Isolamento
Comunicação por mensagens
Identificador único
Estas propriedades formam o conceito de Processo.
Processos
Os processos do SO são uma representação dos programas, com identificador único (PID) e canais de comunicação padrão para envio de mensagens, também chamado de inter-process communication, ou IPC.
Vamos listar todos os processos no sistema operacional. No meu exemplo, estou dentro de um container Docker com Ubuntu (sim, depois teremos outro guia especial apenas pra falar sobre containers e Docker).
Utilizamos então o comando ps que faz parte do SO e lista todos os processos:
Agora, abrimos outro terminal e executamos o comando sleep 30, que bloqueia o processo e fica à espera do relógio durante 30 segundos:
Terminal 1
Em outro terminal, verificamos todos os processos:
Terminal 2
Okay, vamos aos detalhes:
-eé a opção para listar os processos utilizando a sintaxe standard do SO-o pid,pcpu,commé a opção para mostrar as colunas PID, CPU e CMDo processo de
PID 1é o programa bash aberto no primeiro terminal (TTY pts/0)o processo 16 é o programa bash aberto no segundo terminal (TTY pts/1)
o processo 103 é o programa sleep que está bloqueado a espera do relógio terminar. Este programa está rodando no primeiro terminal (TTY pts/0)
o processo 109 se refere ao próprio programa
psque mostrou a saída e terminou. Lembrando que todos os comandos são programas no SO.
Repara que o processo sleep, enquanto está à espera de terminar o relógio, não utiliza quase nada da CPU. Esta operação é puramente I/O!
Agora, vamos simular um processo que faça uso de CPU. No primeiro terminal, vamos utilizar um loop infinito (que em termos computacionais, utiliza um ciclo de CPU para cada interação do loop):
Em um segundo terminal:
E, finalmente, no terceiro terminal:
Podemos notar que o processo 1 do primeiro terminal (pts/0) utiliza 57% da CPU, enquanto o processo 77 (sleep) do segundo terminal (pts/2) está bloqueado no I/O sem utilizar a CPU.
Processos concorrentes!!!!!!1
Mas como o SO faz a gestão destes processos?
Escalonamento preemptivo de processos
O sistema operacional traz um programa especial chamado escalonador, mais conhecido como OS Scheduler.
Este programa é responsável por fazer todo o trabalho de time-sharing multitasking, garantindo que os processos concorram com a CPU de forma justa.
Quando um processo fica a espera de I/O, outro processo pode utilizar a CPU. Entretanto, o SO nem sempre deixa um processo utilizar a CPU até terminar seu trabalho. Na maioria das vezes, o escalonador interrompe o processo da CPU depois de um tempo, estipulado no próprio escalonador.
Assim que um processo é interrompido, ele é colocado numa fila de espera juntamente com outros processos, abrindo oportunidade de preempção para que o próximo processo na fila possa fazer uso da CPU.
Este trabalho feito pelo escalonador é chamado de troca de contexto, ou context switch.
Os critérios para interrupção podem variar, mas quando um SO traz escalonador que interrompe processos baseado no tempo de execução com preempção, é comum chamarmos de escalonador preemptivo, ou preemptive scheduler.
Escalonamento cooperativo de processos
Existe outra forma de fazer escalonamento, que é baseada na transferência de controle da troca de contexto do escalonador para o próprio processo, ou seja, o processo recebe a responsabilidade de saber quando a troca de contexto deve acontecer. A este tipo de escalonamento, chamamos de escalonamento cooperativo, ou cooperative scheduler.
A maioria dos SO's modernos fazem uso do escalonamento preemptivo. Mas algumas implementações chegaram a ter o modo cooperativo, como no caso do antigo MS-DOS.
Alguns runtimes de linguagens de programação também acabam por implementar um escalonamento cooperativo, sendo esta uma decisão de design de determinada linguagem de programação.
Okay, vimos até agora que os sistemas operacionais foram criados para que múltiplos programas pudessem concorrer aos recursos físicos do computador de forma justa, maximizando utilização dos recursos, evitando desperdícios e aumentando a taxa de conclusão dos programas (throughput).
Aprendemos também que processos de SO's são abstrações que encapsulam programas com um identificador e são escalonados no SO para concorrerem à CPU mediante troca de contexto.
Anos 70-90
Estas 3 décadas foram um marco na tecnologia, pois os sistemas operacionais permitiram que diversas linguagens de programação pudessem ser criadas, causando impacto direto na forma como diferentes empresas tomavam decisões estratégicas.
Com isto, novas formas de criar programas foram desenvolvidas, dentre elas a capacidade de escrevermos programas onde determinados trechos de código pudessem concorrer separadamente na CPU.
Ou seja, enquanto o processo principal concorre à CPU, um trecho dentro do mesmo processo pode também concorrer de forma independente, assim um único processo poderia permitir que múltiplos blocos de código utilizem a CPU de forma concorrente e justa.
Seria uma forma de dizer ao sistema operacional:
Hey, SO, sou o processo 42, mas tenho aqui um trecho de código numa estrutura que tem acesso à minha memória, mas que esta estrutura quer também ficar na fila de escalonamento para utilização da CPU.
Você poderia criar esta estrutura aí pra mim, ~senhor sistema operacional?
A esta estrutura chamamos de threads.
Threads
As threads podem ser vistas como unidades de concorrência assim como os processos, mas como estas vivem dentro de um processo, logo estão utilizando a mesma memória do processo, mas sem carregar todo o processo junto com elas.
Ou seja, threads são mais leves que processos. Assim, é possível escrever um programa com múltiplas threads concorrentes, também chamado de multi-threading.
Então quer dizer que uma thread, por ser mais leve, é melhor que um processo?
Não necessariamente, pois duas threads diferentes do mesmo processo compartilham da mesma memória do processo principal. Ou seja, estão sujeitas a race condition! (mas vamos falar de race conditions e formas de mitiga-las mais pra frente).
Para exemplificar que threads são criadas no sistema operacional, vamos expor a coluna TID no output do comando ps:
a coluna TID se refere a "thread ID"
no exemplo acima, TID = PID, pois cada processo tem uma thread principal. Os processos descritos acima não estão criando novas threads.
Isto mostra que o sistema operacional traz estas duas unidades primitivas de concorrência para nossa utilização: processos e threads.
Lei de Moore
Gordon Moore constatou com estudos, por volta de 1970, que em termos físicos, as CPU's iriam dobrar de performance a cada 18 meses. Ou seja, o número de ciclos que uma CPU faz por segundo iria dobrar a cada 1 ano e meio.
E isto foi uma verdade durante décadas. A indústria viu a explosão de sistemas criados por diversas linguagens de programação onde, mesmo que o sistema fosse escrito de forma não-performática, aquilo não seria um problema para os programadores pois podia-se colocar "mais CPU" para suportar escala.
Anos 2000
A partir dos anos 2000, os engenheiros de CPU's se depararam com um problema físico. Com clocks de CPU's chegando a mais de 4GHz, se os ciclos continuassem aumentando, isto ocorreria uma geração de energia enorme, podendo haver efeitos colaterais graves.
Isto colocou para trás a Lei de Morre, mas desafiou a indústria de CPU's a buscar uma solução. Os engenheiros então chegaram a uma solução onde, ao invés de aumentar a velocidade da CPU, construir-se-iam mais núcleos utilizando a mesma velocidade.
Começara então a era multi-core.
Era multi-core e paralelismo
Meados dos anos 2000 marcou muito o conceito de multi-core. Era comum vermos CPU dual-core, mais tarde quad-core, 8-core e assim por diante. Hoje é comum vermos CPU's com 8, 16, 32 ou até mesmo 128-cores!
Com multi-core, vem então a mudança de paradigma de desenvolvimento de sistemas. Para ter um máximo proveito da CPU, precisamos escrever programas que saibam utilizar todos os núcleos (cores) da CPU de forma eficiente.
Os processos do SO, devido ao seu isolamento por definição, são escalonados de forma paralela na CPU, onde 2 processos distintos concorrem ao mesmo tempo em dois núcleos dentro da mesma CPU.
Mas com as threads, que compartilham memória do mesmo processo e estão sujeitas a race condition, o desafio para quem escreve programa multi-threading é maior.
Desafios em sistemas concorrentes (multi-threading)
Vamos agora focar nos desafios e algumas soluções que a indústria tem por padrão no que tange a multi-threading.
Race condition
Como vimos anteriormente, os processos são por natureza isolados e portanto não estão sujeitos a race conditions, diferente das threads.
Mas em um cenário onde há risco de race condition em um sistema multi-threading, como evitar tal efeito colateral?
Thread Lock
O sistema operacional fornece um mecanismo onde, caso uma thread vá utilizar CPU e precise garantir que não há data race, esta pode pedir um lock ao SO. Assim, outras threads do mesmo processo ficarão à espera até que o lock seja liberado.
Quando uma thread é suspensa na troca de contexto, caso tenha um lock, este é liberado.
Definir se uma thread vai ou não utilizar um lock não é responsabilidade do SO, isto é totalmente delegado para quem escrever o sistema, no caso a pessoa que escreve o código multi-threading.
Utilizar locks mitiga race conditions, mas traz alguns efeitos colaterais que precisam ser levados em conta:
se uma thread tem o lock e entretanto por algum motivo ela é abruptamente terminada, outras threads que dependem do mesmo lock ficam bloqueadas, caindo em uma situação de deadlock
a utilização de muitos locks afeta a performance do sistema. Muitos locks acabam por tornar o multi-threading redundante, pois como criar lock no SO tem seu custo, há situações em que seria melhor nem usar multi-threading de todo.
Apesar dos efeitos colaterais, a utilização de locks com prudência tem seu valor em diversas ocasiões, dependendo do tipo de problema.
Lock otimista
Uma alternativa aos locks explícitos é a utilização de um lock otimista (optimistic locking), que basicamente é a criação de duas ou mais versões dos dados, que são então comparados antes do update por 2 threads concorrentes. Desta forma, como não há lock explícito, também não há o risco de deadlocks.
Modelo de atores
Outra alternativa aos locks é fazer com que a thread seja safe. Ou seja, que tenha seu próprio espaço na memória tal como um processo. Mas teoricamente é impossível uma vez que a thread compartilha o mesmo espaço físico do processo.
Então, técnicas de cópia dos dados para outro espaço disponível na memória aparecem. Mesmo dentro do mesmo processo, duas threads diferentes têm cada uma seu estado privado, e desta forma uma não consegue modificar o estado da outra.
Com o estado interno isolado, em um sistema complexo, uma thread precisa se comunicar com outras, tal como os processos comunicam entre si utilizando IPC (veremos este tema de IPC mais tarde). Esta comunicação entre threads também deve ser feita por envio de mensagens.
Estas 2 características são as principais que fazem com que tal thread seja denominada por ator. Com isto, modelo de atores é uma alternativa a lock explícito e lock otimista em sistemas multi-threading.
E o I/O?
Nesta seção focamos bastante na concorrência pela CPU e na sua evolução com técnicas e funcionalidades como Threads, locks e modelo de atores.
Mas pouco falamos daqueles processos que, lá atrás nos anos 60, ficavam bloqueados à espera de I/O, correto?
Ficar bloqueado a espera de I/O é algo inevitável, pois foge ao controle do programa e do sistema computacional. É exatamente esperar pelo teclado, pelo screen, pelo relógio, pela impressora ficar pronta, pelos dados chegarem na rede (sim, networking utiliza I/O), entre outros aspectos.
Mas, diferente da guinada que as CPU's tiveram para uma arquitetura multi-core, os mecanismos de armazenamento e rede tais como HD, SSH, largura de banda, fibra ótica, etc têm ficado cada vez mais rápidos e baratos.
Non-blocking I/O
Sistemas operacionais modernos fornecem funcionalidades onde podemos verificar se o recurso I/O está disponível para leitura ou escrita.
Esta verificação pode acontecer de forma assíncrona, e assim a thread ou processo que vai utilizar I/O não precisa ficar à espera. O processo fica então disponível para outras operações, e assim que o recurso ficar disponível, é notificado e pode portanto ter o resultado do I/O.
Para que isto seja possível, é necessária a implementação de um padrão de loop de eventos, e dentro desse loop são feitas as tais verificações de recursos I/O disponíveis com suas respectivas "threads interessadas".
Tal implementação não é feita por todos os runtimes, mas nas últimas décadas temos visto uma crescente nisto, principalmente depois do sucesso que o runtime NodeJS teve nesta área. Atualmente, outros runtimes e projetos começaram a ir pelo mesmo caminho de non-blocking I/O (ou I/O assíncrono, que são termos ligeiramente diferentes mas se convergem), tais como Java Loom, PHP Swoole e Ruby 3.
Escalonamento cooperativo
Vimos anteriormente que os sistemas operacionais têm, em sua maioria, um tipo de escalonamento preemptivo, e que a forma cooperativa (quando a própria thread ou processo controla a troca de contexto) pode ser utilizada em alguns casos .
Em arquitetura de I/O não bloqueante, este modelo cooperativo pode ter suas vantagens, uma vez que a responsabilidade de trocar o contexto fica por conta do processo que está a espera de I/O e é notificado quando o recurso está pronto.
Mas não é todo runtime que decide implementar modelo cooperativo de escalonamento. Por exemplo, o Ruby 3 traz uma interface de escalonador cooperativo, mas não implementa dentro do runtime. Fica a cargo de quem desenvolve implementar um seguindo a interface de chamadas aos recursos de I/O do sistema operacional.
Resumo
Esta jornada da breve história dos computadores foi um pouco extensa, mas bastante resumida face à quantidade de conteúdo que temos nesta área.
Vamos continuar com o guia e seu objetivo que é continuar dissecando as partes fundamentais da Web.
Na próxima seção abordaremos como diferentes processos se comunicam e quais as formas comuns de comunicação entre processos dentro de um sistema operacional.
Last updated
