Categories
UoPeople

Fast-food, Single-Queue versus Multi-Queue Scheduling

This text is an adaptation from a post in the Operating Systems 1 course discussion forum.

Let’s think about a simple fast-food restaurant with one counter attendant and one employee in the kitchen responsible for preparing the orders that arrive. The counter attendant is the scheduler, and the system is First-In, First-Out. The customer arrives, makes a request, pays for it, and waits for the food. If the orders are small, everything is prepared quickly, and the line runs smoothly. But sometimes there are big families that make huge orders. It is definitely not efficient to make the whole line wait in these situations.

The owner might decide to use a Shortest Job (or Order) First method, but I suspect that the customers (especially large families) would not be pleased with this option. Another option is to run a Round Robin process in the kitchen, where the cooker prepares each meal for a short time, rotating around all the orders and delivering as they are ready. I suspect that following this method can make everyone wait a long time, and the food will probably arrive cold.

It is obvious that a successful fast-food restaurant will need more employees at the counter and the kitchen (like more CPUs) and better schedulers, which mean more queues and/or solutions to take people’s orders and process them. For example, to visualize the single-queue versus multi-queue scheduling, picture a fast-food place with many workers in the kitchen, but only one counter. The speed is improved if compared against the “one counter and one kitchen” scenario, but if the place is crowded, we still have a huge line. This is not scalable.

As I am writing my fast-food analogy I can see that it is possible to even to think about caches. This, in fact, is a good advantage of fast-food restaurants. The options are predictable, and a smart manager knows which options are ordered often at certain times of the day (temporal locality). They can be prepared in advance to be heated at the right time, for example. If we talk about combos, such as a hamburguer with french fries, there is even a parallel with the spatial locality concept. Things that are ordered together can be prepared together.

Multi-queue scheduling is the obvious choice, and that is the reason why most fast-food chains have multiple counters. People tend to naturally follow an internal algorithm to avoid load imbalance between queues, changing from the crowded one to the empty one to order as fast as possible. Some restaurants also have special queues for small orders or just desserts. This is an example of Multilevel Feedback Queue (MLFQ) together with Multi-Queue scheduling, where different queues run different scheduling algorithms inside it.

I hope that this fast-food analogy is helpful to better understand this challenging Operating Systems topic. If not, at least it probably made you hungry.

Reference:

Arpaci-Dusseau, R. & Arpaci-Dusseau, A. (2012). Operating Systems: Three Easy Pieces. Madison, WI: University of Wisconsin-Madison. Available at http://pages.cs.wisc.edu/~remzi/OSTEP//

Categories
Tóin UoPeople

Family Scheduler

Unfortunately, this week the contribution is coming late. My personal scheduler (my brain) was unable to switch efficiently between processes during this week. The task of traveling on the weekend to meet my family took priority and starved all other processes on the queue. There was no First In, First Out algorithm applied, as I began to study last Thursday. Then this also got interrupted by work related tasks by the end of the week, together with the previously mentioned travel.

A smart personal scheduler would have allocated resources to the assignments appropriately, even under a long and time-consuming process such as going to another city. It could have used a Multi-level Feedback Queue (MLFQ) to clearly organize the competing processes and, eventually, run a Round-Robin algorithm to rotate the week assignments in the morning or late at night, when the CPU usage was reduced. This was not fully optimized, as I was only able to cover the reading assignments during the weekend. The result was that the discussion forum assignment went to the end of the queue and no priority boost was applied to level everything from time to time. Such a pity.

Despite the rush at the end, I was glad that no Shortest Job First (SJF) or Shortest Time to Completion First (STCF) was used instead. This could have made me lose the train, or even the dinner with my family. It is not a good idea to simplify too much and lose the context of the processes at hand. There are things that are priority no matter what, and for me family is one of them.

References

Arpaci-Dusseau, R. & Arpaci-Dusseau, A. (2012). Operating Systems: Three Easy Pieces. Madison, WI: University of Wisconsin-Madison. Available at http://pages.cs.wisc.edu/~remzi/OSTEP//

Categories
Política

Guernica e a Guerra do Iraque em 2003

Ressignificar o passado é algo que fazemos constantemente. Revisitar momentos históricos identificando suas consequências e desdobramentos é não só o papel de historiadores, políticos e propagandistas, mas de todos nós, coletivamente.

Hoje, sábado chuvoso, estava lendo um artigo sobre história da arte e topei com esse episódio: dia 5 de fevereiro de 2003, o secretário de Estado norte-americano Colin Powell apresentou no Conselho de Segurança das Nações Unidas as justificativas para ir à guerra contra o Iraque.

Tapeçaria de Guernica de Picasso, de Jacqueline de la Baume Dürrbach, na Whitechapel Gallery em Londres

A reprodução de Guernica, de Pablo Picasso, pendurada do lado de fora da sala de reuniões, foi coberta. A justificativa dos funcionários da ONU foi a necessidade de criar um plano de fundo adequado para as câmeras de televisão.

De vez em quando parece até que a história é consciente. Se fosse inventado acharíamos exagero.

Categories
UoPeople

Por que Databases 1 é essencial?

Muito da motivação humana vem da curiosidade. Percebemos o mundo e tentamos entendê-lo. Por que as coisas caem? Por que o sol brilha? Objetos visualmente chamativos costumam atrair a atenção. Lembro de ter fascínio pela água desde criança, especialmente os reflexos da luz do sol na superfície. Uma das minhas primeiras memórias é pulando na piscina sem ninguém ver e simplesmente afundar. No meio do susto e do turbilhão de bolhas surge o rosto da minha mãe me segurando nos braços e falando: “é fundo!”.

Minha consciência infantil não levou em consideração que eu não sabia nadar, muito menos que minha mãe me observava atentamente, prevendo meus movimentos inconsequentes e preparada para reagir ao primeiro sinal de perigo. Isso permitiu que eu explorasse o mundo, oferecendo redes de proteção quase invisíveis para garantir minha segurança.

Conectar essa história com a matéria de base de dados parece dramático, mas acredito em associação livre e foi a memória que surgiu quando comecei a escrever. Bases de dados são fundamentais para o mundo e elementos-chave para manter sistemas importantíssimos funcionando. São estruturas que trabalham pesado para armazenar dados e garantir a integridade dos milhões de sistemas essenciais para a manutenção frenética da sociedade moderna. Os detalhes que compartilharei a seguir demonstram de forma inconteste que Databases 1 é essencial no curso de Ciência da Computação.

Na University of the People temos aqui a introdução dos conceitos fundamentais envolvendo o design, uso e implementação de sistemas de base de dados. O foco é em base de dados relacionais e na linguagem SQL (Structured Query Language). Para mim esse é um dos cursos mais práticos do currículo. Quem já leu minhas avaliações anteriores conhece minhas críticas sobre a organização de alguns cursos. Databases 1 é uma exceção positiva.

A distribuição do peso das notas segue um modelo mais distribuído. Os Learning Journals têm 10%; Discussion Assignments com 20%; Programming Assignments 20%; Graded Quiz com 20%; e o Exame Final nos 30%. Isso reforça a importância de participar ativamente em todas as unidades, mas também em distribuir o esforço adequadamente em todas as tarefas. Faz bastante diferença na nota final, mas principalmente em como absorvemos o conteúdo.

O curso não exige uma solução de base de dados específica, sendo aberto para o uso do OpenOffice Database, DB2, MySQL, Oracle Express, ou outro da sua escolha. Ainda assim, o OpenOffice é diretamente citado em alguns materiais e, por ser mais acessível, costuma ser o escolhido pela maioria dos colegas. Outro fator importante e que sempre reforço aqui, é o fato do OpenOffice ser software livre. Familiarizar-se com soluções de software livre é essencial para realizar projetos escaláveis e acessíveis, então costumo priorizá-los. A única crítica dentre os programas recomendados é sobre o Dia, ferramenta para criar gráficos de relacionamento de entidades (ER). É um programa antigo, desatualizado e para usuários de Mac a compatibilidade é sofrível. Mesmo assim, acabei utilizando o programa sob o mesmo argumento do OpenOffice (software livre). Dá pro gasto.

A primeira tarefa de programação começa com a criação de um banco de dados para uma biblioteca. Os trabalhos vão evoluindo a partir daí, relativamente conectados com a unidade anterior. Acho que a universidade deveria explorar mais esse modelo de projeto contínuo nos cursos. O Learning Journal, por sua vez, é simples: O que você aprendeu, o que surpreendeu, desafios e quais são as aplicações práticas do que está sendo visto. Essa parte foi fácil já que no meu dia-a-dia na Houzz usava bastante Metabase e Sequel Pro, então sempre dava pano pra manga.

Databases 1 não exige preparo específico, nem é especialmente desafiador em termos teóricos. De qualquer forma, para dar uma ideia mais detalhada do conteúdo, destaco abaixo em forma de lista os principais assuntos mais ou menos na ordem em que aparecem ao longo das semanas, dessa forma cada um pode julgar por si:

  • Modelo informacional: o nível abstrato das entidades, suas propriedades e relações.
  • Atributos, conceito de valor atômico (impossível de decompor), propriedades dos bancos de dados relacionais, Tuples, IDs, chave-primária, chave-secundária, chave-substituta e chave artificial.
  • Álgebra relacional: união, intersecção, diferença, seleção, junção (join). Sugiro o tutorial SQL na W3Schools para explorar esses conceitos.
  • Entity integrity constraint, referential integrity constraint, semantic integrity constraint, domain constraint, null constraint, unique constraint etc. Série de limitações teóricas importantes de entender para configurar uma base de dados relacional.
  • Normalização (1-3 Normal-Forms) e Boyce-Codd Normal Formal. Procedimento com o objetivo de tornar bases relacionais mais robustas e menos redundantes, evitando anomalias de inserção, remoção e atualização.
  • Definição de DDL (Data Definition Language), DML (Data Manipulation Language), e DCL (Data Control Language) em SQL.
  • Em SQL: Select, Group By, Cursor, Delete, Where, Join, Union, Set, operadores lógicos, operadores de strings, operadores comparativos, agregadores (Count, Sum, Average, Minimum, Maximum), Having, Between, Order By, In, Like, Wildcards.

Essa lista dá apenas uma ideia geral dos tópicos abordados. O interessante é que eles são bem organizados ao longo do curso, então as 8 unidades são fluídas. Diria que o ritmo de estudo fica mais intenso a partir da unidade 4, mergulhando fundo na teoria de bases relacionais e rapidamente seguindo por SQL nas unidades seguintes. É a partir da unidade 5 que começam as primeiras questões sobre SQL nos Self e Graded Quizzes. Para mim, os tópicos mais difíceis nos exames foram os “Normal Forms”, algumas questões de álgebra relacional e outras muito específicas sobre ODBC ou queries complexas de SQL que exigem atenção especial.

Para concluir, Databases 1 não é um curso difícil. Para quem não tem familiaridade com o tópico, ele será extremamente importante para abrir novas perspectivas e aprofundar significativamente o conhecimento de como diferentes elementos de um programa se conectam e trabalham em conjunto. Reforço a recomendação dos cursos de SQL da W3Schools ou do Khan Academy para evitar sobrecarga de novidades. Tirando isso, é fazer as tarefas com calma e atenção. Não espere conteúdo atualizado com tecnologias mais recentes ou alternativas. O curso não cobre NoSQL, por exemplo. Claro que isso não impede a proatividade dos alunos nos fóruns de discussão e em usar o instrutor do curso para recomendar recursos adicionais.

Espero ter dado um norte. Qualquer dúvida ou sugestão é só comentar.

Categories
Tóin

Desculpas ao símbolo

Não é pessoal. Ou melhor, é totalmente pessoal. Rejeito em você o que rejeito em mim. Rolou essa coisa de sermos muito parecidos. Para alguns isso é sorte, para mim é doloroso. Feridas abertas sendo tratadas.

Hoje usei todas as minhas forças. Eliminei. Expurguei. Espremi. O pus está saindo. O inchaço cedendo. Dor tolerável. Tratável. Compreensível. Para mim é e isso me basta.

Estou leve.