detalhes finais do relatorio

[3hU9fRjo95.git] / relatorio / relatorio.tex~

\documentclass[a4paper,10pt]{abnt} %
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[brazil]{babel}
\usepackage{listings}
\usepackage{color}

%opening
%\title{}
%\author{Kauê Silveira \\171671 \and Silveira Kauê \\ 671171}

\autor{Kaue Soares da Silveira \\ 171671} %\and
\instituicao{Universidade Federal do Rio Grande do Sul}
\orientador[Professor:]{Alexandre Carissimi}
\titulo{Trabalho Opcional 1: Estudo da Linguagem Golang}
\comentario{Disciplina INF01151 - Sistemas Operacionais II N}
\data{}

\definecolor{gray}{rgb}{0.5, 0.5, 0.5}
\definecolor{darkBlue}{rgb}{0.15,0.18,0.40}
\definecolor{darkGreen}{rgb}{0.15,0.40,0.18}
\lstset{extendedchars=true,
        inputencoding=utf8,
        basicstyle=\small\color{blue},
        keywordstyle=\color{red}\bfseries,
        keywordstyle= [2]\color{magenta}\bfseries,
        identifierstyle=\color{blue},
        commentstyle=\color{gray}\textit,
        stringstyle=\color{darkGreen},
        showstringspaces=false,
        tabsize=2
}

\lstset{
        numbers=left,         % Números na margem da esquerda
        numberstyle=\tiny\color{darkGreen},    % Números pequenos
        stepnumber=1,         % De 1 em 1
        numbersep=5pt         % Separados por 5pt
}
\lstdefinelanguage{Go}{%
      morekeywords=[1]{func, int, chan, package, import, int64, var, const, type, struct, byte},% blocks
      morekeywords=[2]{make, go, select, for, case, if, then, else, len, cap, break},%
      morekeywords=[3]{idvar,var,->,as},% variables
      morekeywords=[4]{lexical,sum,join},% aggregation/sorting
      morekeywords=[5]{},% regexps (s.moredelim below)
      morestring=[b]",%
      morecomment=[l]{\#},%
      morecomment=[l]{//},%
      morecomment=[s]{\\\#}{\#\\\\)},%
      morecomment=[s]{/*}{*/},%
      alsodigit={-},%
      literate= {->}{$\rightarrow$}{2},%
      sensitive%
    }[keywords,strings]

\lstdefinelanguage{Shell}{%
      morekeywords=[1]{sudo, apt-get, install, cd, export, hg, mkdir, mv, gedit, easy_install, clone, release, g, l, make},% blocks
      morekeywords=[2]{declare,some,position,pos,optional,opt,where,order-by,group-by,and,or,not},%
      morekeywords=[2]{variable,ns-default,ns-prefix,not,if,then,else,case,without,desc,descendant,in,identity},%
      morekeywords=[3]{idvar,var,->,as},% variables
      morekeywords=[4]{lexical,sum,count,join},% aggregation/sorting
      morekeywords=[5]{},% regexps (s.moredelim below)
      morestring=[b]",%
      morecomment=[l]{\#},%
      morecomment=[s]{\\\#}{\#\\\\)},%
      alsodigit={-},%
      literate= {->}{$\rightarrow$}{2},%
      sensitive%
    }[keywords,strings]

\begin{document}

%\maketitle
\folhaderosto
\sumario

%\begin{abstract}
%\begin{resumo}
%\end{abstract}
%\end{resumo}

\chapter{Introdução}
        \begin{quotation}
\emph{"Não comunique-se compartilhando memória, compartilhe
memória comunicando-se."}
        \end{quotation}

 O simples ato de comunicação garante a sincronização.

        Concorrência em muitos ambientes se torna difícil pelas sutilezas envolvidas
no acesso correto a variáveis compartilhadas. Go\cite{GO} encoraja uma abordagem
diferente, na qual variáveis compartilhadas são passadas através de canais e
nunca são de fato ativamente compartilhadas por threads de execução separadas.
Apenas uma gorotina tem acesso à variável num dado momento de tempo. Condições
de corrida relativas aos dados não podem ocorrer, por construção. Modelo de concorrência inspirado no CSP \cite{CSP}.
\chapter{Primeiros Passos}
        \section{Instalação}
        Passos que eu segui no Ubuntu 9.10:

\begin{lstlisting}[language=Shell, texcl=true, numbers=none, escapechar={\%}]
$ cd ~
$ gedit .bashrc &
# colar no final:
        export GOROOT=$HOME/go
        export GOARCH=386
        export GOOS=linux
# reiniciar o shell para que as alterações tenham efeito
$ sudo apt-get install bison gcc libc6-dev ed gawk %make%
$ sudo apt-get install python-setuptools python-dev build-essential gcc
$ sudo easy_install mercurial
$ hg clone -r release https://go.googlecode.com/%hg%/ $GOROOT
$ cd $GOROOT/src
$ mkdir $HOME/bin
$ ./all.bash
$ cd $HOME/bin
$ sudo mv * /bin
\end{lstlisting}

\section{Utilização}
\begin{lstlisting}[language=Shell, texcl=true, numbers=none, escapechar={\%}]
# criar o arquivo fonte num editor de sua preferência
$ gedit prog.go & # -> prog.go
# compilar
$ %\color{red}{8}%g prog.go # -> prog.8
# ligar
$ %\color{red}{8}%l -o prog prog.8 # -> prog
# executar
$ ./prog
\end{lstlisting}

\chapter{Mecanismos de Programação Concorrente}
        \section{Gorotinas}
                Go tem seu próprio modelo de processo / thread / corotina,
chamado gorotina (\emph{goroutines}). Gorotinas são divididas de acordo com o necessário em threads (de usuário) e processos do sistema. Quando uma goroutine executa uma chamada de sistema bloqueane, nenhuma outra gorotina é bloqueada. Para configurar o número máximo de processos criados podemos modificar a variável de ambiente \lstinline|\$GOMAXPROCS| ou utilizar a função runtime.GOMAXPROCS (n int) durante a execução. Seu valor default é 1, ou seja, todas as gorotinas são threads de usuário pertencentes ao mesmo processo.

        \section{Channel}
                Representa um canal de comunicação / sincronização que pode conectar duas
computações concorrentes. Na realidade são referências para um objeto que
coordena a comunicação.

                <- é o operador binário de comunicação (envio) <- também é o operador, desta vez unário, de recebimento. Ambos são atômicos.

                Operações de leitura (respesctivamente, escrita) em canais que não têm buffer ou que estão com o buffer vazio (respectivamente, cheio) bloqueiam, e o bloqueio se mantém até que haja aconteça uma operação de escrita (respectivamente, leitura). A linguagem também permite leitura (respectivamente, escrita) não bloqueante, a qual retorna imediatamente uma flag dizendo se a operação foi realizada com sucesso ou não.

                Na criação são sempre bidirecionais, mas quando são recebidos como parâmetro por uma função, além da declaração normal (chan T) podem ser declarados para apenas receber (<-chan T) e apenas enviar (chan<- T), com o objetivo garantir que serão utilizados corretamente no corpo da função.

                As funções len e cap, quando aplicadas a canal, retornam, repspectivamente, a quantidade de mensagens esperando e o tamanho do buffer do canal (caso este seja assíncrono), ou zero caso contrário. São úteis para determinar se o buffer de um canal assíncrono está cheio, o que permite evitar torná-lo síncrono.

                Exemplos:

\begin{lstlisting}[language=Go, texcl=true, escapechar={\%}]
// declaração:
        var canal_sincrono chan int // envia e recebe inteiros
        var canal_assincrono chan int // poderia ser qualquer outro tipo
// instanciação:
        canal_sincrono = make (chan int) 
        canal_assincrono = make (chan int, 10) // buffer de tamanho 10
// função que utiliza um canal apenas para leitura
        func so_leio (canal_leitura <-chan int) { ... }
// função que utiliza um canal apenas para escrita
        func so_escrevo (canal_escrita chan<- int) { ... }
// função que utiliza um canal bidirecional
        func leio_e_escrevo (canal chan int) { ... }
// tipos de leitura:
        v := <-canal_sincrono // sempre leitura sincrona
        v := <-canal_assincrono // leitura assincrona quando houver espaço no buffer, síncrona caso contrário
        v, ok := <-canal // sempre leitura assíncrona, ok é setado para true ou false de acordo com o sucesso
// tipos de escrita:
        canal_sincrono <- v // sempre escrita síncrona
        canal_assincrono <- v // escrita assíncrona quando houver espaço no buffer, síncrona caso contrário
        ok := canal <- v // sempre escrita assíncrona, ok é setado para true ou false de acordo com o sucesso
// axiomas:
        // 0 <= len(canal) <= cap(canal), para qualquer canal
        // cap(make(chan int)) = 0
        // cap(make(chan int, n)) = n
\end{lstlisting}

        \section{go}
                É o operador que inicia a execução concorrente de uma gorotina, sempre no mesmo espaço de endereçamento. Prefixe uma chamada de função ou de método com a palavra-chave go para executar a chamada numa nova gorotina. Quando a chamada termina, a gorotina também termina (silenciosamente). O efeito é similar a notação \& do shell Unix para rodar um comando em background.

                Exemplo:

\begin{lstlisting}[language=Go, texcl=true, escapechar={\%}]
...
func faz_algo () { ... }
...
func main () {
        ...
        // inicia a execução concorrente da função faz\_algo ...
        go faz_algo ()
        // ... e continua executando ...
        ...
}
\end{lstlisting}

        \section{select}
                É um estrutura de controle análoga a um switch, mas que age sempre sobre comunicações. Escolhe qual das comunicações listadas em seus casos pode prosseguir. Se todas estão bloqueadas, ele espera até que alguma desbloqueie. Se várias podem prosseguir, ele escolhe uma aleatoriamente.

                Exemplo:

\begin{lstlisting}[language=Go, texcl=true, escapechar={\%}]
// esta função envia zeros e uns aleatoriamente a cada iteração
func gerador_aleatorio_de_bits (canal chan<- int)
        for { // laço infinito
                select { // escolha não-determinística
                        case c <- 0: // nada no corpo do case, o break é implícito (diferente de c)
                        case c <- 1:
                }
        }
\end{lstlisting}

\chapter{Prática}
        \section{Compilando e executando os exemplos}

                Todos os exemplos, exceto o hello.go, implementam a solução do problema produtor-consumidor com buffer limitado e taxa de produção e consumo aleatórias, sendo que o pc\_channel\_multi.go implementa a versão com vários produtores e vários consumidores. Os outros implementam a versão singular apenas para manter a simplicidade, mas também são facilmente generalizáveis.

\begin{lstlisting}[language=Shell, texcl=true, numbers=none, escapechar={\%}]
$ cd src
$ make
$ ./programa_desejado
\end{lstlisting}
        \section{Hello, World!}
                \begin{description}
                        \item[Arquivo:] hello.go
                \end{description}
\lstinputlisting[language=Go, texcl=true, escapechar={\#}]{../hello.go}

        \section{Funções Auxiliares}
\lstinputlisting[firstline=11, lastline=17, language=Go, texcl=true, numbers=none, escapechar={\$}]{../pc_channel.go}
\lstinputlisting[firstline=18, lastline=22, language=Go, texcl=true, numbers=none, escapechar={\#}]{../pc_channel.go}
\lstinputlisting[firstline=23, lastline=27, language=Go, texcl=true, numbers=none, escapechar={\$}]{../pc_channel.go}
\lstinputlisting[firstline=28, lastline=32, language=Go, texcl=true, numbers=none, escapechar={\#}]{../pc_channel.go}
\lstinputlisting[firstline=33, lastline=40, language=Go, texcl=true, numbers=none, escapechar={\#}]{../pc_channel.go}
\lstinputlisting[firstline=42, lastline=45, language=Go, texcl=true, numbers=none, escapechar={\#}]{../pc_channel.go}
\lstinputlisting[firstline=47, lastline=51, language=Go, texcl=true, numbers=none, escapechar={\#}]{../pc_monitor_cond.go}
\lstinputlisting[firstline=32, lastline=46, language=Go, texcl=true, numbers=none, escapechar={\#}]{../pc_monitor_cond.go}
%\lstinputlisting[firstline=, lastline=, language=Go, texcl=true, escapechar={\#}]{../pc_channel.go}

        \section{Constantes}
\lstinputlisting[firstline=32, lastline=36, language=Go, texcl=true, numbers=none, escapechar={\#}]{../pc_mutex.go}

        \section{Destruição (de variáveis)}
                Como a linguagem tem coletor de lixo, não é necessário (nem possível) se preocupar com a destruição das variáveis.

        \section{Mutex}
                \begin{description}
                        \item[Criação]:
\begin{lstlisting}[language=Go, numbers=none]
import . "sync"
var mutex *Mutex = new(Mutex)
\end{lstlisting}
                        \item[Uso]:
\begin{lstlisting}[language=Go, texcl, numbers=none]
mutex.Lock()
        // seção crítica
mutex.Unlock()
\end{lstlisting}
                        \item[Arquivo:] pc\_mutex.go
                        \item[Implementação (parte principal)]:
\lstinputlisting[firstline=37, lastline=91, language=Go, texcl=true, escapechar={\#}]{../pc_mutex.go}
                \end{description}

        \section{Semáforo}
                \begin{description}
                        \item[Criação]:
\begin{lstlisting}[language=Go, texcl, numbers=none]
var semaforo chan int = make(chan int, MAX_VAL) // o semáforo sempre começa em 0
\end{lstlisting}
                        \item[Inicialização]:
\begin{lstlisting}[language=Go, texcl, numbers=none]
// atribui o valor inicial n para o semáforo
// com n = 1 simulamos um mutex
for i := 0; i < n; i++ {
        signal(semaforo)
}
\end{lstlisting}
                        \item[Uso]:
\begin{lstlisting}[language=Go, texcl, numbers=none]
wait(semaforo)
        // seção crítica
signal(semaforo)
\end{lstlisting}
                        \item[Arquivo:] pc\_sem.go
                        \item[Implementação (parte principal)]:
\lstinputlisting[firstline=36, lastline=110, language=Go, texcl=true, escapechar={\#}]{../pc_sem.go}
                \end{description}

        \section{Monitor}
                \begin{description}
                        \item[Criação]:
\begin{lstlisting}[language=Go, texcl, numbers=none]
type Monitor struct {
        mutex *Mutex
        // outros campos ...
}
\end{lstlisting}
                        \item[Inicialização]:
\begin{lstlisting}[language=Go, texcl, numbers=none]
func newMonitor () *Monitor {
        return &Monitor {
                new(Mutex),
                // inicializar outros campos ...
        }
}
var monitor *Monitor = newMonitor()
\end{lstlisting}
                        \item[Uso]:
\begin{lstlisting}[language=Go, texcl, numbers=none]
func (m *Monitor) metodo () {
        m.mutex.Lock()
                // fazer o que tem que fazer ...
        m.mutex.Unlock()
}
monitor.metodo()
\end{lstlisting}
                        \item[Arquivo:] pc\_monitor.go
                        \item[Implementação (parte principal)]:
\lstinputlisting[firstline=37, lastline=110, language=Go, texcl=true, escapechar={\#}]{../pc_monitor.go}
                        \item[Discussão]: semáforos são utilizados para simular as variáveis de condição. As diferenças entre ambos são:
                                \begin{description}
                                        \item[Memória:] semáforos têm memória, no sentido de que sinalização nunca são perdidas, pois permanecem armazenadas no semáforo. Variáveis de condição não tem memória, caso não haja ninguém esperando quando ocorre um sinal, o sinal se perde.
                                        \item[Atomicidade:] variáveis de condição destravam o mutex e entram em estado de espera de forma atômica. Isso é necessário pois, se houvesse uma troca de contexto entre estas duas ações, um outra thread poderia entrar no monitor e gerar um sinal que seria perdido, podendo causar um deadlock. Os semáforos, ao contrário, não realizam estas duas operações de forma atômica, mas isso não é um problema, já que os sinais não se perdem.
                                \end{description}
                \end{description}

        \section{Variável de Condição}
                \begin{description}
                        \item[Criação]:
\begin{lstlisting}[language=Go, texcl, numbers=none]
// canal sem buffer
var cond chan int = make(chan int)
\end{lstlisting}
                        \item[Uso]:
\begin{lstlisting}[language=Go, texcl, numbers=none]
wait_cond(cond, mutex)
trysignal(cond)
\end{lstlisting}
                        \item[Arquivo:] pc\_monitor\_cond.go
                        \item[Implementação (parte principal)]:
\lstinputlisting[firstline=57, lastline=130, language=Go, texcl=true, escapechar={\#}]{../pc_monitor_cond.go}
                        \item[Discussão]: a semântica das variáveis de condição diz que o destrancamento do mutex tem que acontecer de forma atômica com o início da espera pela variável (ver discussão na seção sobre Monitor). A melhor tentativa de simular esta atomicidade foi criar uma outra gorotina (waiter) e deixá-la esperando pelo variável de condição antes de destrancar o mutex, e então esperar pela resposta desta gorotina. Porém, mesmo esta implementação está incorreta, pois não há como garantir que a gorotina criada já esteja esperando pela variável de condição antes de destrancarmos o mutex. Portanto, não há como implementar variáveis de condição corretamente na linguagem, podemos apenas simular seu comportamente com semáforos, mas são coisas diferentes. Para se ter uma idéia da chance de ocorrência do deadlock, no meu computador pessoal o programa acima entrou em deadlock em média após 40000 iterações.
                \end{description}

        \section{The Go Way}
                Os canais de go são exatamente o que precisamos para comunicação entre as gorotinas. Veja como a solução é bem mais elegante:
                \begin{description}
                        \item[Arquivo]: pc\_channel.go
                        \item[Implementação (parte principal)]:
\lstinputlisting[firstline=52, lastline=130, language=Go, texcl=true, escapechar={\#}]{../pc_channel.go}
                \end{description}

        \section{Múltiplos Produtores e Consumidores}
                \begin{description}
                        \item[Arquivo]: pc\_channel\_multi.go
                        \item[Execução]:
\begin{lstlisting}[language=Shell, texcl=true, numbers=none, breaklines, escapechar={\%}]
$ ./pc_channel_multi.go -s BUFFER_SIZE -t MAX_SLEEP_TIME -m MAX_PRODUCTIONS -p N_PRODUCERS -c N_CONSUMERS
\end{lstlisting}
                        \item[Implementação (parte principal)]:
\lstinputlisting[firstline=40, lastline=130, language=Go, texcl=true, escapechar={\#}]{../pc_channel_multi.go}
                \end{description}

\chapter{Conclusão}
        Go é uma linguagem que tenta aliar um certo nível de abstração (coletor de lixo, canais inspirados num modelo formal amplamente aceito) com eficiência de compilação e execução. A linguagem não apresenta nativamente algumas funcionalidades comuns de concorrência, mas sua implementação é relativamente fácil, pois a linguagem possui o tipo canal que é tão poderoso quanto as funcionalidades a que estamos acostumados.

        Com a disseminação de computadores multiprocessados, e as dificuldades que temos atualmente para programar corretamente sistemas concorrentes, certamente linguagens como essa terão grande crescimento e importância, podendo começar a substituir gradualmente linguagens mais antigas (como C), pois a ineficiência de execução de suas abstrações individualmente vai ser compensada pela eficiência de sua execução como um todo, por aproveitarem melhor os recursos de hardware disponíveis.

\begin{thebibliography}{10}
        \bibitem{GO} \emph{The Go Programming Language}, http://golang.org/. Acessado em: 04/04/2010.
        \bibitem{CSP} Hoare, C. A. R., \emph{Communicating Sequential Processes},  Communications of the ACM 21 (8): 666–677.
\end{thebibliography}

\end{document}