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
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
UoPeople

Programming 2 concluído e uma dica

Após longa ausência volto para escrever sobre este que é considerado um dos cursos mais difíceis da UoPeople: Programming 2. O terror dos estudantes de Ciência de Computação e alvo constante de perguntas sobre o conteúdo das matérias, quanto tempo investir por semana e como se preparar. Vou tentar, como sempre, abordar tudo isso de forma resumida. Acho que detalhar demais não é produtivo, mesmo porque o conteúdo do curso pode mudar com o tempo. A ideia aqui é compartilhar o conceito do curso e como ele se encaixa no todo de Ciências da Computação.

Seguindo o modelo de Programming 1, trabalhamos com a linguagem Java. Este curso é basicamente uma continuação, um aprofundamento do que aprendemos desde Programming Fundamentals, usando progressivamente os conhecimentos adquiridos para seguir adiante. É nesse ponto que reforço o que falei em postagens anteriores: preste muita atenção nos conceitos básicos! Não há revisão dos fundamentos durante o curso. Pegue suas anotações dos cursos anteriores e revise, preferencialmente antes de começar a unidade 1. 

Em Programming 2 exploramos recursão, estruturas de dados e alguns frameworks disponíveis em Java. Dá para perceber que adoro analogias, e a que faço aqui é que deixamos aos poucos de focar no “trabalho de pedreiro”, executando tarefas focadas e específicas, e passamos para o de projetista, olhando o todo e procurando organizar as diferentes partes de um programa de forma mais robusta possível. Isso fica evidente já na escolha do IDE, migrando do Netbeans para o Eclipse, que possui muito mais recursos e funcionalidades. O uso de Javadoc é requisito básico em todos os exercícios, tornando o uso de comentários claros e compreensíveis uma obrigação e não mais uma recomendação. Logo nas primeiras unidades o foco em Exception Handling (try.. catch) é um aspecto tangível que reforça o que estou apontando.

Conforme as unidades avançam ocorrem várias epifanias, pelo menos foi assim para mim. É maravilhoso ver as peças dos aprendizados anteriores se encaixando em novas figuras, que por sua vez se tornam novas peças e são utilizadas em novos aprendizados. É tão bonito quanto desafiador, e aí está a parte complicada de Programming 2. É o primeiro curso que toca em Análise de Algoritmos, com a notação Big-O, análise assintótica, logaritmos e exponenciais. Para os enferrujados em matemática chegou a hora de tirar as apostilas do colegial da estante, ou mergulhar nos excelentes vídeos do Khan Academy para refrescar a memória.

Nenhum desses conceitos é dado de forma isolada. Recursão e análise de algoritmos tornam-se ferramentas importantes para explorar o conceito de estruturas de dados, tanto de forma abstrata (Abstract Data Types) como implementações específicas (BinarySearch, Linked Lists, Binary Tree). Para quê, quando, onde, como e porquê utilizá-las, assim como avaliar qual estrutura é mais adequada para resolver determinado problema. 

É claro que cada item citado acima dá um curso próprio, e de fato é isso o que teremos mais para frente. Análise de Algoritmos e Estrutura de Dados são tópicos que tomam apenas uma unidade em Programming 2, mas que são também cursos completos mais para frente. Isso porque tanta gente considera esse curso difícil: são vários assuntos complexos juntos e apresentados pela primeira vez. Nesse contexto tive a sorte de ter um ótimo instrutor, Sonnie Avenbuan, que participou ativamente do fórum do grupo, dando dicas valiosas e estimulando as discussões. Ter um bom instrutor fez muita diferença.

Se você está lendo isso com ansiedade, calma, que é só o começo. Agora vem a crítica ao curso, pelo menos em como ele estava estruturado no início de 2018. Ao longo das unidades tratamos das bibliotecas disponíveis em Java. A premissa é boa e faz todo o sentido: não reinventar a roda. Várias estruturas de dados são frequentemente utilizadas e funcionam bem. Devemos entendê-las, mas não é necessário reescrevê-las. Para isso temos classes como ArrayList, LinkedList, Sort, TreeSet, Hashtable e tantas outras, prontas para uso. A sua caixa de ferramentas aumenta consideravelmente durante o curso. Até aí, tudo bom, tudo bem. O problema real surge nas últimas três unidades.

Sou da opinião que poucos assuntos são realmente complicados. O problema costuma estar na didática. Muitas vezes professores, livros ou cursos são mal formulados e fazem pouco para aplicar conceitos abstratos de forma tangível. Em Prog 2 sinto que vivemos os dois mundos. Há exercícios excelentes que conectam perfeitamente o tópico da unidade num projeto prático. Um exemplo é o laboratório de Exception Handling, que nos faz refatorar um código simples para torná-lo mais robusto a erros por parte do usuário. Outro é o laboratório da unidade 4 sobre a Comparable Interface, que faz um uso inteligente do depurador do Eclipse para localizar e corrigir erros em um código de busca e ordenação. Excelente exemplo de exercício prático que simula tarefas realizadas no mundo real.

Infelizmente perde-se o ritmo quando entramos na unidade 6: Files and Networking, Advanced GUI Programming. O título da unidade fala por si. Como é possível trabalhar manipulação de arquivos, redes e interface gráfica em apenas uma semana? Spoiler: Não é possível. O resultado é uma unidade confusa, com excesso de leitura, laboratórios, discussões e learning journals desconectados um do outro e a sensação de que tudo foi organizado de última hora para preencher uma lista de tópicos. Vou citá-los aqui só pela poesia: close(), flush(), streams, ServerSocket, antialiasing, canvas, icons. Tudo. De. Uma. Vez.

É quando você está exausto, na reta final da maratona, e os últimos cinco quilômetros são uma subida íngreme, que a técnica se perde e o único objetivo é chegar vivo e tropeçando até a linha de chegada. Assim são as duas últimas unidades sobre Graphic User Interface (GUI), o que é uma pena, pois o tópico é importante e conecta muito do que aprendemos desde Programming Fundamentals. Ainda assim os aprendizados profundos continuam: relação entre Programação Orientada a Objetos e GUI; composição de imagens (frame buffer) e sua manipulação pela placa de vídeo; Action, Toolbar, Buttons; o padrão Model-View-Controller (MVC) que estrutura os componentes gráficos na biblioteca Java Swing; padrões de design e sua aplicação em classes de interface.

O que salva as últimas unidades são os labs (exercícios de programação) que exploram a modificação de programas já criados. Para mim foram os primeiros exercícios de programação representando efetivamente trabalho prático na área. Isso ficam ainda mais evidente por serem exercícios sobre interface gráfica, onde observamos visualmente os resultados das mudanças e aprimoramentos no código. O exercício da unidade 6 foi um dos mais complicados do curso. A parte positiva de cobrir tantos assuntos diferentes foi a oportunidade de avaliar quais assuntos despertam mais ou menos meu interesse. Interface gráfica, por exemplo, não é minha praia. Foi bom reconhecer isso através de exercícios práticos.

Mas deixei o principal aprendizado, sob a perspectiva dos estudos, para este penúltimo parágrafo. Ao revisar minhas anotações fica claro que meu método de estudo na época era pouco efetivo. Anotei muita coisa sem saber o que é prioridade. Alguns fichamentos têm mais de 25 páginas numa unidade com 100 páginas de leitura! Isso não é razoável. O maior problema sem dúvida foi seguir os materiais de forma “linear”. Começar pelo Learning Guide, seguir para os Reading Assignments, e assim por diante. Faz muito mais sentido seguir para o Self-Quiz logo após terminar os Reading Assignments, anotar os tópicos do Discussion e do Programming Assignment e usar isso para fichar os materiais apenas nos pontos que realmente importam.

Programming 2 é um curso desafiador, mas é efetivamente o curso-base de Ciência da Computação que toca superficialmente nos tópicos centrais que serão revisitados em vários cursos avançados. É normal não entender tudo de uma vez e fazer vários exercícios sem muita ideia do que está acontecendo. Absorva tudo o que for possível, mas saiba que esses assuntos serão tratados com mais calma adiante. Não se afobe! Para facilitar, recomendo fazer Prog2 sozinho, a não ser que você estude na UoPeople de forma integral. Faça com calma e atenção que sem dúvida seu aprendizado será efetivo.

Qualquer dúvida é só comentar ou entrar em contato. Bons estudos!

Categories
UoPeople

Abstract Data Types and Program Modularity

We have been on a long journey through abstraction since the Programming 1 course. Object oriented programming (OOP), Interfaces and Polymorphism. Abstraction (in the general concept) can be something hard to understand initially because it requires the ability to generalize a behavior and break a process down into its building blocks, detached from a specific problem or content.

The task is hard, the concept is relatively simple and the consequences are huge. We are learning that a significant part of what makes computers so powerful and one of the driving forces that are changing our modern society is this abstraction capability. Abstract data types (ADTs) come to add another tool to our understanding of how these machines function and how they adapt so quickly and seamless to the multitude of programs that we use in our everyday life.

As the book beautifully summarizes, an ADT “refers to a set of possible values and a set of operations on values, without any specification of how the values are to be represented or how the operations are to be implemented” (Eck, 2016, p.444). When I first read this sentence it did not help much because it felt too abstract. Funny. It is hard to grasp because of what I mentioned in the beginning: it requires the ability to generalize a behavior. A lot of things that we learn in our lives are given as “natural rules” and then it is hard to deconstruct them later. One good example is the Postfix Expressions subchapter. It was the first time that I saw the possibility to write an simple mathematical expression in a different order like 2+(15-12)*17 to 2 15 12 – 17 *. It is not just about having fun with the numbers, it is actually an easier way to work with them from a computational perspective. They do not require parentheses or precedence rules!

This subchapter complements the Stack and Queues concept. We might be tempted to focus on how Stacks and Queues are implemented in Java, but actually this is all about the behavior (semantics) of the data. A Stack can be thought of as a pile of dishes to clean. After dinner you keep adding dirty plates on top of another. When you start cleaning you do not remove from the bottom or the middle, you start by the top (I do like that, do not want to risk breaking all my plates by doing in a different order). It follows a policy, defined as last in, first out (LIFO). The Queue can also be simply thought of as a queue to enter a club. First in (the line), First out (in the club). Imagining using a Stack policy in a club? Not fair at all!

Everything presented above comes together in the context of programming by the fact that you separate the data structure from the policy to handle it. This is very powerful for program modularity, because you can then change and optimize the way that you handle the actual data without affecting the data itself and without having to know the details of the ADT implementation (a.k.a. encapsulation). This also gives flexibility to use and apply with ease specific ADTs in specific contexts where they might work better (Akhtar, 2011). Some algorithms work well with some data structures while others work better with the rest. Stacks for example are used in subroutine calls; Queues for others, like web server requests, processing each one in order.

References:

Akhtar, A. (2011, September 11). Data Structure & Application. Retrieved December 05, 2017, from http://datastructure-application.blogspot.de/2011/09/advantages-of-adt.html

Eck, D. J. (2016). Programming: introduction to programming using Java(7.0.2 ed.). San Francisco, Calif: Sohobooks