-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-23.html
334 lines (252 loc) · 60 KB
/
book-Z-H-23.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:ops="http://www.idpf.org/2007/ops">
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<meta http-equiv="Content-Type: text/html; charset=utf-8"/>
<title>Estrutura e Interpretação de Programas de Computador</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title="default"/>
</head>
<body>
<a name="%_sec_3.4" id="%_sec_3.4"/>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_3.4">3.4 Concorrência: o tempo é essencial</a></h2><p>
<a name="%_idx_3578" id="%_idx_3578"/>Vimos o poder dos objetos computacionais com o estado local como ferramentas para modelagem. No entanto, como a seção <a href="book-Z-H-20.html#%_sec_3.1.3">3.1.3</a> advertiu, esse poder possui um preço: a perda da transparência referencial, dando origem a um emaranhado de perguntas sobre igualdade e mudança e a necessidade de abandonar o modelo de substituição de avaliação em favor do modelo de ambiente mais complexo.</p><p>
<a name="%_idx_3580" id="%_idx_3580"/>A questão central que se esconde sob a complexidade do estado, da igualdade e da mudança é que, ao introduzir a atribuição, somos forçados a admitir <em>tempo</em> em nossos modelos computacionais. Antes de introduzirmos a atribuição, todos os nossos programas eram atemporais, no sentido de que qualquer expressão que tenha um valor sempre terá o mesmo valor. Por outro lado, lembre-se do exemplo de modelagem de retiradas de uma conta bancária e devolução do saldo resultante, introduzido no início da seção <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>:</p><p>
</p><p/><p><tt>(withdraw 25)<br/><i>75</i><br/>
(withdraw 25)<br/><i>50</i><br/></tt></p><p/><p>Aqui, avaliações sucessivas da mesma expressão produzem valores diferentes. Esse comportamento decorre do fato de que a execução de instruções de atribuição (neste caso, atribuições à variável <tt>balance</tt>) delineia <em>momentos no tempo</em> quando os valores mudam. O resultado da avaliação de uma expressão depende não apenas da expressão em si, mas também da avaliação ocorrer antes ou depois desses momentos. A construção de modelos em termos de objetos computacionais com o estado local nos obriga a confrontar o tempo como um conceito essencial na programação.</p><p>Podemos ir além na estruturação de modelos computacionais para corresponder à nossa percepção do mundo físico. Objetos no mundo não mudam um de cada vez em sequência. Antes, os percebemos como agindo <em>concorrentemente</em> – tudo de uma vez. Portanto, muitas vezes é natural modelar sistemas como coleções de processos computacionais executados concorrentemente. Assim como podemos tornar nossos programas modulares organizando modelos em termos de objetos com estado local separado, muitas vezes é apropriado dividir modelos computacionais em partes que evoluem separadamente e concorrentemente. Mesmo que os programas sejam executados em um computador sequencial, a prática de escrever programas como se fossem executados concorrentemente força o programador a evitar restrições desnecessárias de tempo e, assim, torna os programas mais modulares.</p><p>Além de tornar os programas mais modulares, a computação concorrente pode fornecer uma vantagem de velocidade sobre a computação sequencial. Os computadores sequenciais executam apenas uma operação por vez, portanto, o tempo necessário para executar uma tarefa é proporcional ao número total de operações executadas.<a name="call_footnote_Temp_405" href="#footnote_Temp_405" id="call_footnote_Temp_405"><sup><small>34</small></sup></a> No entanto, se for possível decompor um problema em partes que são relativamente independentes e precisam se comunicar apenas raramente, pode ser possível alocar peças para separar processadores de computação, produzindo uma vantagem de velocidade proporcional ao número de processadores disponíveis.</p><p>Infelizmente, as complexidades introduzidas pela atribuição se tornam ainda mais problemáticas na presença de concorrência. O fato de execução concorrente, seja, pois o mundo opera em paralelo ou, pois nossos computadores, implica complexidade adicional em nossa compreensão do tempo.</p><p>
<a name="%_sec_3.4.1" id="%_sec_3.4.1"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.4.1">3.4.1 A natureza do tempo em sistemas concorrentes</a></h3><p>
<a name="%_idx_3584" id="%_idx_3584"/>Na superfície, o tempo parece simples. É uma ordem imposta aos eventos.<a name="call_footnote_Temp_406" href="#footnote_Temp_406" id="call_footnote_Temp_406"><sup><small>35</small></sup></a> Para qualquer evento <em>A</em> e <em>B</em>, ou <em>A</em> ocorre antes <em>B</em>, <em>A</em> e<em>B</em> são concorrentes ou <em>A</em> ocorre depois <em>B</em>. Por exemplo, voltando ao exemplo da conta bancária, suponha que Peter retire $10 e Paul retire $25 de um <a name="%_idx_3588" id="%_idx_3588"/>conta conjunta que inicialmente contém $100, deixando $65 na conta. Dependendo da ordem dos dois saques, a sequência de saldos na conta é de $100 ⟶ $90 ⟶ $65 ou $100 ⟶ $75 ⟶ $65. Em uma implementação computacional do sistema bancário, essa sequência variável de saldos pode ser modelada por atribuições sucessivas a uma variável <tt>balance</tt>.</p><p>Em situações complexas, no entanto, essa visão pode ser problemática. Suponha que Peter e Paul e outras pessoas acessem a mesma conta bancária através de uma rede de máquinas bancárias distribuídas em todo o mundo. A sequência real de saldos na conta dependerá criticamente do tempo detalhado dos acessos e dos detalhes da comunicação entre as máquinas.</p><p>
<a name="%_idx_3590" id="%_idx_3590"/>Essa indeterminação na ordem dos eventos pode representar sérios problemas no design de sistemas concorrentes. Por exemplo, suponha que as retiradas feitas por Peter e Paul sejam implementadas como dois processos separados, compartilhando uma variável comum <tt>balance</tt>, cada processo especificado pelo procedimento fornecido na seção <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>:</p><p/><p><tt><a name="%_idx_3592" id="%_idx_3592"/>(define (withdraw amount)<br/>
(if (>= balance amount)<br/>
(begin (set! balance (- balance amount))<br/>
balance)<br/>
"Insufficient funds"))<br/></tt></p><p/><p>Se os dois processos operarem independentemente, Peter poderá testar o saldo e tentar retirar uma quantia legítima. No entanto, Paul pode retirar alguns fundos entre o momento em que Peter verifica o saldo e o tempo em que Peter completa a retirada, invalidando assim o teste de Peter.</p><p>Ainda pode piorar mais. Considere a expressão</p><p/><p><tt>(set! balance (- balance amount))<br/></tt></p><p/><p>executada como parte de cada processo de retirada. Isso consiste em três etapas: (1) acessar o valor da variável <tt>balance</tt>; (2) computando o nova balanço; (3) configurando <tt>balance</tt> para esse novo valor. Se as retiradas de Peter e Paul executarem essa declaração concorrentemente, as duas retiradas poderão intercalar a ordem em que acessam <tt>balance</tt> e defini-la para o novo valor.</p><p>O diagrama de tempo na figura <a href="#%_fig_3.29">3.29</a> descreve uma ordem de eventos em que <tt>balance</tt> começa em 100, Peter retira 10, Paul retira 25, e ainda o valor final de <tt>balance</tt> é 75. Como mostrado no diagrama, o motivo dessa anomalia é que a atribuição de 75 a Paul para <tt>balance</tt> é feita sob a suposição de que o valor de <tt>balance</tt> a ser decrementado é 100. Essa suposição, no entanto, tornou-se inválida quando Peter mudou <tt>balance</tt> para 90. Esta é uma falha catastrófica para o sistema bancário, pois a quantidade total de dinheiro no sistema não é conservada. Antes das transações, o valor total era de $100. Depois, Peter possui $10, Paul possui $25 e o banco possui $75.<a name="call_footnote_Temp_407" href="#footnote_Temp_407" id="call_footnote_Temp_407"><sup><small>36</small></sup></a></p><p>
<a name="%_idx_3596" id="%_idx_3596"/><a name="%_idx_3598" id="%_idx_3598"/>O fenômeno geral ilustrado aqui é que vários processos podem compartilhar uma variável de estado comum. O que torna isso complicado é que mais de um processo pode tentar manipular o estado compartilhado ao mesmo tempo. Para o exemplo da conta bancária, durante cada transação, cada cliente deve poder agir como se os outros clientes não existissem. Quando um cliente altera o saldo de uma maneira que depende do saldo, ele deve ser capaz de assumir que, pouco antes do momento da mudança, o saldo ainda é o que ele pensava que era.</p><p>
<a name="%_sec_Temp_408" id="%_sec_Temp_408"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_408">Comportamento correto de programas concorrentes</a></h4><p>
<a name="%_idx_3600" id="%_idx_3600"/>O exemplo acima tipifica os erros sutis que podem se infiltrar em programas concorrentes. A raiz dessa complexidade está nas atribuições a variáveis compartilhadas entre os diferentes processos. Já sabemos que devemos ter cuidado ao escrever programas que usam <tt>set!</tt>, pois os resultados de um cálculo dependem da ordem em que as atribuições ocorrem.<a name="call_footnote_Temp_409" href="#footnote_Temp_409" id="call_footnote_Temp_409"><sup><small>37</small></sup></a> Com processos concorrentes, devemos ter um cuidado especial com as atribuições, pois talvez não possamos controlar a ordem das atribuições feitas pelos diferentes processos. Se várias dessas alterações puderem ser feitas concorrentemente (como acontece com dois depositantes acessando uma conta conjunta), precisamos de alguma maneira de garantir que nosso sistema se comporte corretamente. Por exemplo, no caso de saques de uma conta bancária conjunta, devemos garantir que o dinheiro seja conservado. Para fazer com que os programas concorrentes se comportem corretamente, talvez tenhamos de colocar algumas restrições na execução concorrente.</p><p>
<a name="%_fig_3.29" id="%_fig_3.29"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-31.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.29:</b> Diagrama de tempo, mostrando como a intercalação da ordem dos eventos em dois saques bancários pode levar a um saldo final incorreto.</div></caption><tr><td>
<a name="%_idx_3602" id="%_idx_3602"/>
</td></tr></table></div><p>Uma restrição possível à concorrência estipularia que duas operações que alteram quaisquer variáveis de estado compartilhadas podem ocorrer ao mesmo tempo. Este é um requisito extremamente rigoroso. Para serviços bancários distribuídos, seria necessário que o projetista do sistema garantisse que apenas uma transação pudesse prosseguir por vez. Isso seria ineficiente e excessivamente conservador. A figura <a href="#%_fig_3.30">3.30</a> mostra Peter e Paul compartilhando uma conta bancária, onde Paul também possui uma conta privada. O diagrama ilustra dois saques da conta compartilhada (um por Peter e outro por Paul) e um depósito na conta privada de Paul.<a name="call_footnote_Temp_410" href="#footnote_Temp_410" id="call_footnote_Temp_410"><sup><small>38</small></sup></a> Os dois saques da conta compartilhada não devem ser concorrentes (pois acessam e atualizam a mesma conta), e o depósito e o saque de Paul não devem ser concorrentes (pois acessam e atualizam o valor na carteira de Paul). Mas não deve haver problema em permitir que o depósito de Paul em sua conta privada prossiga concorrentemente com a retirada de Peter da conta compartilhada.</p><p>
<a name="%_fig_3.30" id="%_fig_3.30"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-32.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.30:</b> Depósitos e saques concorrentes de uma conta conjunta no Banco1 e uma conta privada no Banco2.</div></caption><tr><td>
</td></tr></table></div><p/><p>Uma restrição menos rigorosa à concorrência garantiria que um sistema concorrente produzisse o mesmo resultado como se os processos tivessem sido executados sequencialmente em alguma ordem. Existem dois aspectos importantes para esse requisito. Primeiro, ele não exige que os processos sejam executados sequencialmente, mas apenas para produzir resultados iguais. <em>Até parece</em> eles correram sequencialmente. Para o exemplo na figura <a href="#%_fig_3.30">3.30</a>, o criador do sistema de contas bancárias pode permitir com segurança que o depósito de Paul e a retirada de Peter ocorram concorrentemente, pois o resultado líquido será o mesmo que se as duas operações tivessem ocorrido sequencialmente. Segundo, pode haver mais de um resultado “correto” possível produzido por um programa concorrente, pois exigimos apenas que o resultado seja o mesmo que para <em>alguma</em> ordem sequencial. Por exemplo, suponha que a conta conjunta de Peter e Paul comece com $100, e Peter deposita $40 enquanto Paul concorrentemente retira metade do dinheiro na conta. A execução sequencial pode resultar no saldo da conta em $70 ou $90 (consulte o exercício <a href="#%_thm_3.38">3.38</a>)<a name="call_footnote_Temp_411" href="#footnote_Temp_411" id="call_footnote_Temp_411"><sup><small>39</small></sup></a></p><p>Ainda existem requisitos mais fracos para a execução correta de programas concorrentes. Um programa para simular <a name="%_idx_3606" id="%_idx_3606"/>difusão (digamos, o fluxo de calor em um objeto) pode consistir em um grande número de processos, cada um representando um pequeno volume de espaço, que atualiza seus valores concorrentemente. Cada processo muda repetidamente seu valor para a média de seu próprio valor e dos valores de seus vizinhos. Esse algoritmo converge para a resposta correta, independentemente da ordem em que as operações são realizadas; não há necessidade de restrições no uso concorrente dos valores compartilhados.</p><p>
</p><p><a name="%_thm_3.38" id="%_thm_3.38"/>
<b>Exercício 3.38.</b> Suponha que Peter, Paul e Mary compartilhem uma conta bancária conjunta que inicialmente contenha $100. Concorrentemente, Peter deposita $10, Paul retira $20 e Mary retira metade do dinheiro da conta, executando os seguintes comandos:</p><table border="0"><tr><td valign="top">Peter: </td><td valign="top"><tt>(set! balance (+ balance 10))</tt></td></tr><tr><td valign="top">Paul: </td><td valign="top"><tt>(set! balance (- balance 20))</tt></td></tr><tr><td valign="top">Mary: </td><td valign="top"><tt>(set! balance (- balance (/ balance 2)))</tt>
</td></tr></table><p>
</p><p/><p>a. Liste todos os diferentes valores possíveis para <tt>balance</tt> após a conclusão dessas três transações, assumindo que o sistema bancário force os três processos a serem executados sequencialmente em alguma ordem.</p><p>
</p><p/><p>b. Quais são alguns outros valores que poderiam ser produzidos se o sistema permitir que os processos sejam intercalados? Desenhe diagramas de tempo como o da figura <a href="#%_fig_3.29">3.29</a> para explicar como esses valores podem ocorrer.</p><p>
<a name="%_sec_3.4.2" id="%_sec_3.4.2"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.4.2">3.4.2 Mecanismos para controlar a concorrência</a></h3><p>
<a name="%_idx_3608" id="%_idx_3608"/>Vimos que a dificuldade de lidar com processos concorrentes está enraizada na necessidade de considerar a intercalação da ordem dos eventos nos diferentes processos. Por exemplo, suponha que tenhamos dois processos, um com três eventos ordenados (<em>a</em>,<em>b</em>,<em>c</em>) e um com três eventos ordenados (<em>x</em>,<em>y</em>,<em>z</em>) Se os dois processos forem executados concorrentemente, sem restrições sobre como sua execução é intercalada, existem 20 pedidos possíveis diferentes para os eventos que são consistentes com os pedidos individuais dos dois processos:</p><p/><div align="left"><img src="images/ch3-Z-G-33.gif" border="0"/></div><p>Como programadores que projetam esse sistema, teríamos que considerar os efeitos de cada um desses 20 pedidos e verificar se cada comportamento é aceitável. Essa abordagem rapidamente se torna desajeitado à medida que o número de processos e eventos aumenta.</p><p>Uma abordagem mais prática para o projeto de sistemas concorrentes é a criação de mecanismos gerais que nos permitam restringir a intercalação de processos concorrentes, para que possamos ter certeza de que o comportamento do programa está correto. Muitos mecanismos foram desenvolvidos para esse fim. Nesta seção, descrevemos um deles, o <em>serializador</em>.</p><p>
<a name="%_sec_Temp_413" id="%_sec_Temp_413"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_413">Serializando o acesso ao estado compartilhado</a></h4><p>
<a name="%_idx_3610" id="%_idx_3610"/>A serialização implementa a seguinte ideia: Os processos serão executados concorrentemente, mas haverá certas coleções de procedimentos que não podem ser executados concorrentemente. Mais precisamente, a serialização cria conjuntos distintos de procedimentos, de modo que somente uma execução de um procedimento em cada conjunto serializado é permitida por vez. Se algum procedimento no conjunto fosse executado, um processo que tente executar qualquer procedimento no conjunto será forçado a aguardar até a conclusão da primeira execução.</p><p>Podemos usar a serialização para controlar o acesso a variáveis compartilhadas. Por exemplo, se queremos atualizar uma variável compartilhada com base no valor anterior dessa variável, colocamos o acesso ao valor anterior da variável e a atribuição do novo valor à variável no mesmo procedimento. Em seguida, garantimos que nenhum outro procedimento atribuído à variável possa ser executado concorrentemente com esse procedimento serializando todos esses procedimentos com o mesmo serializador. Isso garante que o valor da variável não possa ser alterado entre um acesso e a atribuição correspondente.</p><p>
<a name="%_sec_Temp_414" id="%_sec_Temp_414"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_414">Serializadores no Scheme</a></h4><p>Para tornar o mecanismo acima mais concreto, suponha que estendemos o Scheme para incluir um procedimento chamado <a name="%_idx_3612" id="%_idx_3612"/><tt>parallel-execute</tt>:</p><p>
</p><p/><p><tt>(execução paralela <<em>p<sub>1</sub></em>> <<em>p<sub>2</sub></em>><tt>…</tt> <<em>p<sub><em>k</em></sub></em>>)<br/></tt></p><p/><p>Cada <<em>p</em>> deve ser um procedimento sem argumentos. <tt>Parallel-execute</tt> cria um processo separado para cada <<em>p</em>>, que se aplica <<em>p</em>> (sem argumentos). Todos esses processos são executados concorrentemente.<a name="call_footnote_Temp_415" href="#footnote_Temp_415" id="call_footnote_Temp_415"><sup><small>40</small></sup></a></p><p>Como um exemplo de como isso é usado, considere</p><p>
</p><p/><p><tt>(define x 10)<br/><br/>
(parallel-execute (lambda () (set! x (* x x)))<br/>
(lambda () (set! x (+ x 1))))<br/></tt></p><p/><p>Isso cria dois processos concorrentes - <em>P</em><sub>1</sub>, que define <tt>x</tt> para <tt>x</tt> vezes <tt>x</tt> e <em>P</em><sub>2</sub>, que incrementa <tt>x</tt>. Após a conclusão da execução, <tt>x</tt> ficará com um dos cinco valores possíveis, dependendo da intercalação dos eventos de <em>P</em><sub>1</sub> e <em>P</em><sub>2</sub>:</p><table border="0"><tr><td valign="top">101: </td><td valign="top"><em>P</em><sub>1</sub> define <tt>x</tt> para 100 e depois <em>P</em><sub>2</sub> incrementa <tt>x</tt> para 101.</td></tr><tr><td valign="top">121: </td><td valign="top"><em>P</em><sub>2</sub> incrementa <tt>x</tt> para 11 e depois <em>P</em><sub>1</sub> define <tt>x</tt> para <tt>x</tt> vezes <tt>x</tt>.</td></tr><tr><td valign="top">110: </td><td valign="top"><em>P</em><sub>2</sub> altera <tt>x</tt> de 10 a 11 entre as duas vezes que <em>P</em><sub>1</sub> acesse o valor de <tt>x</tt> durante a avaliação de <tt>(* x x)</tt>.</td></tr><tr><td valign="top">11: </td><td valign="top"><em>P</em><sub>2</sub> acessa <tt>x</tt>, então <em>P</em><sub>1</sub> define <tt>x</tt> para 100, então <em>P</em><sub>2</sub> define <tt>x</tt>.</td></tr><tr><td valign="top">100: </td><td valign="top"><em>P</em><sub>1</sub> acessa <tt>x</tt> (duas vezes), então <em>P</em><sub>2</sub> define <tt>x</tt> para 11, então <em>P</em><sub>1</sub> define <tt>x</tt>.</td></tr><tr><td valign="top"/></tr></table><p>Podemos restringir a concorrência usando procedimentos serializados, criados por <em>serializadores</em>. Os serializadores são construídos por <tt>make-serializer</tt>, cuja implementação é fornecida abaixo. Um serializador usa um procedimento como argumento e retorna um procedimento serializado que se comporta como o procedimento original. Todas as chamadas para um determinado serializador retornam procedimentos serializados no mesmo conjunto.</p><p>Assim, em constraste com o exemplo acima, executando</p><p>
</p><p/><p><tt>(define x 10)<br/><br/>
(define s (make-serializer))<br/><br/>
(parallel-execute (s (lambda () (set! x (* x x))))<br/>
(s (lambda () (set! x (+ x 1)))))<br/></tt></p><p/><p>pode produzir apenas dois valores possíveis para <tt>x</tt>, 101 ou 121. As demais possibilidades são eliminadas, pois a execução de <em>P</em><sub>1</sub> e <em>P</em><sub>2</sub> não pode ser intercalado.</p><p>Aqui está uma versão do procedimento <tt>make-account</tt> da seção <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>, onde os depósitos e retiradas foram serializados:</p><p>
</p><p/><p><tt><a name="%_idx_3614" id="%_idx_3614"/><a name="%_idx_3616" id="%_idx_3616"/>(define (make-account balance)<br/>
(define (withdraw amount)<br/>
(if (>= balance amount)<br/>
(begin (set! balance (- balance amount))<br/>
balance)<br/>
"Insufficient funds"))<br/>
(define (deposit amount)<br/>
(set! balance (+ balance amount))<br/>
balance)<br/>
(let ((protected (make-serializer)))<br/>
(define (dispatch m)<br/>
(cond ((eq? m 'withdraw) (protected withdraw))<br/>
((eq? m 'deposit) (protected deposit))<br/>
((eq? m 'balance) balance)<br/>
(else (error "Unknown request -- MAKE-ACCOUNT"<br/>
m))))<br/>
dispatch))<br/></tt></p><p/><p>Com esta implementação, dois processos não podem ser retirados ou depositados em uma única conta concorrentemente. Isso elimina a fonte do erro ilustrado na figura <a href="#%_fig_3.29">3.29</a>, em que Peter altera o saldo da conta entre os horários em que Paul acessa o saldo para calcular o novo valor e quando Paul realmente executa a atribuição. Por outro lado, cada conta possui seu próprio serializador, para que depósitos e retiradas de contas diferentes possam prosseguir concorrentemente.</p><p>
</p><p><a name="%_thm_3.39" id="%_thm_3.39"/>
<b>Exercício 3.39.</b> Quais das cinco possibilidades na execução paralela mostrada acima permanecem se, em vez disso, serializarmos a execução da seguinte maneira:</p><p>
</p><p/><p><tt>(define x 10)<br/><br/>
(define s (make-serializer))<br/><br/>
(parallel-execute (lambda () (set! x ((s (lambda () (* x x))))))<br/>
(s (lambda () (set! x (+ x 1)))))<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.40" id="%_thm_3.40"/>
<b>Exercício 3.40.</b> Forneça todos os valores possíveis de <tt>x</tt> que pode resultar da execução</p><p>
</p><p/><p><tt>(define x 10)<br/><br/>
(parallel-execute (lambda () (set! x (* x x)))<br/>
(lambda () (set! x (* x x x))))<br/></tt></p><p/><p>Quais dessas possibilidades permanecem se, em vez disso, usarmos procedimentos serializados:</p><p>
</p><p/><p><tt>(define x 10)<br/><br/>
(define s (make-serializer))<br/><br/>
(parallel-execute (s (lambda () (set! x (* x x))))<br/>
(s (lambda () (set! x (* x x x)))))<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.41" id="%_thm_3.41"/>
<b>Exercício 3.41.</b> Ben Bitdiddle teme que seria melhor implementar a conta bancária da seguinte forma (onde a linha comentada foi alterada):</p><p>
</p><p/><p><tt><a name="%_idx_3618" id="%_idx_3618"/>(define (make-account balance)<br/>
(define (withdraw amount)<br/>
(if (>= balance amount)<br/>
(begin (set! balance (- balance amount))<br/>
balance)<br/>
"Insufficient funds"))<br/>
(define (deposit amount)<br/>
(set! balance (+ balance amount))<br/>
balance)<br/>
<em>;; continued on next page</em><br/><br/>
(let ((protected (make-serializer)))<br/>
(define (dispatch m)<br/>
(cond ((eq? m 'withdraw) (protected withdraw))<br/>
((eq? m 'deposit) (protected deposit))<br/>
((eq? m 'balance)<br/>
((protected (lambda () balance)))) <em>; serialized</em><br/>
(else (error "Unknown request -- MAKE-ACCOUNT"<br/>
m))))<br/>
dispatch))<br/></tt></p><p/><p>porque permitir acesso não serializado ao saldo bancário pode resultar em comportamento anômalo. Você concorda? Existe algum cenário que demonstre a preocupação de Ben?</p><p/><p>
</p><p><a name="%_thm_3.42" id="%_thm_3.42"/>
<b>Exercício 3.42.</b> Ben Bitdiddle sugere que é uma perda de tempo criar um novo procedimento serializado em resposta a todos as mensagens <tt>withdraw</tt> e <tt>deposit</tt>. Ele diz que <tt>make-account</tt> pode ser alterado para que as chamadas para <tt>protected</tt> são feitos fora do procedimento <tt>dispatch</tt>. Ou seja, uma conta retornaria o mesmo procedimento serializado (criado ao mesmo tempo que a conta) toda vez que for solicitado um procedimento de retirada.</p><p/><p><tt><a name="%_idx_3620" id="%_idx_3620"/>(define (make-account balance)<br/>
(define (withdraw amount)<br/>
(if (>= balance amount)<br/>
(begin (set! balance (- balance amount))<br/>
balance)<br/>
"Insufficient funds"))<br/>
(define (deposit amount)<br/>
(set! balance (+ balance amount))<br/>
balance)<br/>
(let ((protected (make-serializer)))<br/>
(let ((protected-withdraw (protected withdraw))<br/>
(protected-deposit (protected deposit)))<br/>
(define (dispatch m)<br/>
(cond ((eq? m 'withdraw) protected-withdraw)<br/>
((eq? m 'deposit) protected-deposit)<br/>
((eq? m 'balance) balance)<br/>
(else (error "Unknown request -- MAKE-ACCOUNT"<br/>
m))))<br/>
dispatch)))<br/></tt></p><p/><p>É uma alteração segura a fazer? Em particular, há alguma diferença em que concorrência é permitida por essas duas versões do <tt>make-account</tt> ?</p><p>
<a name="%_sec_Temp_420" id="%_sec_Temp_420"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_420">Complexidade do uso de vários recursos compartilhados</a></h4><p>
<a name="%_idx_3622" id="%_idx_3622"/><a name="%_idx_3624" id="%_idx_3624"/>Os serializadores fornecem uma abstração poderosa que ajuda a isolar as complexidades dos programas concorrentes, para que possam ser tratados com cuidado e corretamente. No entanto, embora o uso de serializadores seja relativamente direto quando houver apenas um único recurso compartilhado (como uma única conta bancária), a programação concorrente pode ser traiçoeira difícil quando há vários recursos compartilhados.</p><p>Para ilustrar uma das dificuldades que podem surgir, suponha que desejamos trocar os saldos em duas contas bancárias. Acessamos cada conta para encontrar o saldo, calcular a diferença entre os saldos, retirar essa diferença de uma conta e depositá-la na outra conta. Poderíamos implementar isso da seguinte maneira:<a name="call_footnote_Temp_421" href="#footnote_Temp_421" id="call_footnote_Temp_421"><sup><small>41</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3626" id="%_idx_3626"/><a name="%_idx_3628" id="%_idx_3628"/>(define (exchange account1 account2)<br/>
(let ((difference (- (account1 'balance)<br/>
(account2 'balance))))<br/>
((account1 'withdraw) difference)<br/>
((account2 'deposit) difference)))<br/></tt></p><p/><p/><p>Este procedimento funciona bem quando apenas um único processo tenta fazer a troca. Suponha, no entanto, que Peter e Paul tenham acesso a contas <em>a</em>1 <em>a</em>2 e <em>a</em>3, e que Peter troca <em>a</em>1 e <em>a</em>2 enquanto Paul troca concorrentemente <em>a</em>1 e <em>a</em>3) Mesmo com depósitos e saques em conta serializados para contas individuais (como no procedimento <tt>make-account</tt> mostrado acima nesta seção), <tt>exchange</tt> ainda pode produzir resultados incorretos. Por exemplo, Peter pode calcular a diferença nos saldos para <em>a</em>1 e <em>a</em>2, mas Paul pode mudar o saldo em <em>a</em>1 antes que Peter possa concluir a troca.<a name="call_footnote_Temp_422" href="#footnote_Temp_422" id="call_footnote_Temp_422"><sup><small>42.</small></sup></a> Para um comportamento correto, precisamos providenciar o procedimento <tt>exchange</tt> para bloquear quaisquer outros acessos concorrentes às contas durante todo o período da troca.</p><p>Uma maneira de conseguir isso é usando os serializadores de ambas as contas para serializar todo o procedimento <tt>exchange</tt>. Para fazer isso, providenciaremos o acesso ao serializador de uma conta. Observe que estamos deliberadamente quebrando a modularidade do objeto de conta bancária, expondo o serializador. A seguinte versão do <tt>make-account</tt> é idêntico à versão original dada na seção <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>, exceto que um serializador é fornecido para proteger a variável de saldo e o serializador é exportado via passagem de mensagem:</p><p>
</p><p/><p><tt><a name="%_idx_3630" id="%_idx_3630"/>(define (make-account-and-serializer balance)<br/>
(define (withdraw amount)<br/>
(if (>= balance amount)<br/>
(begin (set! balance (- balance amount))<br/>
balance)<br/>
"Insufficient funds"))<br/>
(define (deposit amount)<br/>
(set! balance (+ balance amount))<br/>
balance)<br/>
(let ((balance-serializer (make-serializer)))<br/>
(define (dispatch m)<br/>
(cond ((eq? m 'withdraw) withdraw)<br/>
((eq? m 'deposit) deposit)<br/>
((eq? m 'balance) balance)<br/>
((eq? m 'serializer) balance-serializer)<br/>
(else (error "Unknown request -- MAKE-ACCOUNT"<br/>
m))))<br/>
dispatch))<br/></tt></p><p/><p/><p>Podemos usar isso para fazer depósitos e saques serializados. No entanto, ao contrário da nossa conta serializada anterior, agora é responsabilidade de cada usuário de objetos de conta bancária gerenciar explicitamente a serialização, por exemplo, da seguinte maneira:<a name="call_footnote_Temp_423" href="#footnote_Temp_423" id="call_footnote_Temp_423"><sup><small>43</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3632" id="%_idx_3632"/>(define (deposit account amount)<br/>
(let ((s (account 'serializer))<br/>
(d (account 'deposit)))<br/>
((s d) amount)))<br/></tt></p><p/><p/><p>Exportar o serializador dessa maneira nos dá flexibilidade suficiente para implementar um programa de troca serializado. Simplesmente serializamos o procedimento original <tt>exchange</tt> com os serializadores para ambas as contas:</p><p>
</p><p/><p><tt><a name="%_idx_3634" id="%_idx_3634"/>(define (serialized-exchange account1 account2)<br/>
(let ((serializer1 (account1 'serializer))<br/>
(serializer2 (account2 'serializer)))<br/>
((serializer1 (serializer2 exchange))<br/>
account1<br/>
account2)))<br/></tt></p><p/><p/><p>
</p><p><a name="%_thm_3.43" id="%_thm_3.43"/>
<b>Exercício 3.43.</b> Suponha que os saldos em três contas comecem a $10, $20 e $30 e que vários processos sejam executados, trocando os saldos nas contas. Argumente que, se os processos forem executados sequencialmente, após qualquer número de trocas concorrentes, os saldos das contas deverão ser de $10, $20 e $30 em alguma ordem. Desenhe um diagrama de tempo como o da figura <a href="#%_fig_3.29">3.29</a> para mostrar como essa condição pode ser violada se as trocas forem implementadas usando a primeira versão do programa de troca de contas nesta seção. Por outro lado, argumente que mesmo com esse programa <tt>exchange</tt>, a soma dos saldos nas contas será preservada. Desenhe um diagrama de tempo para mostrar como essa condição seria violada se não serializássemos as transações em contas individuais.</p><p/><p>
</p><p><a name="%_thm_3.44" id="%_thm_3.44"/>
<b>Exercício 3.44.</b> <a name="%_idx_3636" id="%_idx_3636"/>Considere o problema de transferir um valor de uma conta para outra. Ben Bitdiddle afirma que isso pode ser realizado com o procedimento a seguir, mesmo se houver várias pessoas transferindo dinheiro concorrentemente entre várias contas, usando qualquer mecanismo de conta que serialize transações de depósito e retirada, por exemplo, a versão do <tt>make-account</tt> no texto acima.</p><p>
</p><p/><p><tt>(define (transfer from-account to-account amount)<br/>
((from-account 'withdraw) amount)<br/>
((to-account 'deposit) amount))<br/></tt></p><p/><p>Louis Reasoner afirma que existe um problema aqui e que precisamos usar um método mais sofisticado, como o necessário para lidar com o problema da troca. Louis está certo? Caso contrário, qual é a diferença essencial entre o problema da transferência e o problema da troca? (Você deve assumir que o saldo em <tt>from-account</tt> é, pelo menos, <tt>amount</tt>).</p><p/><p>
</p><p><a name="%_thm_3.45" id="%_thm_3.45"/>
<b>Exercício 3.45.</b> Louis Reasoner acha que nosso sistema de contas bancárias é desnecessariamente complexo e propenso a erros, agora que depósitos e saques não são serializados automaticamente. Ele sugere que <tt>make-account-and-serializer</tt> deveria ter exportado o serializador (para uso por procedimentos como <tt>serialized-exchange</tt>) além de (em vez de em vez de) usá-lo para serializar contas e depósitos como <tt>make-account</tt> fez. Ele propõe redefinir contas da seguinte maneira:</p><p>
</p><p/><p><tt>(define (make-account-and-serializer balance)<br/>
(define (withdraw amount)<br/>
(if (>= balance amount)<br/>
(begin (set! balance (- balance amount))<br/>
balance)<br/>
"Insufficient funds"))<br/>
(define (deposit amount)<br/>
(set! balance (+ balance amount))<br/>
balance)<br/>
(let ((balance-serializer (make-serializer)))<br/>
(define (dispatch m)<br/>
(cond ((eq? m 'withdraw) (balance-serializer withdraw))<br/>
((eq? m 'deposit) (balance-serializer deposit))<br/>
((eq? m 'balance) balance)<br/>
((eq? m 'serializer) balance-serializer)<br/>
(else (error "Unknown request -- MAKE-ACCOUNT"<br/>
m))))<br/>
dispatch))<br/></tt></p><p/><p>Os depósitos são tratados como no original <tt>make-account</tt>:</p><p/><p><tt>(define (deposit account amount)<br/>
((account 'deposit) amount))<br/></tt></p><p/><p>Explique o que há de errado com o raciocínio de Louis. Em particular, considere o que acontece quando <tt>serialized-exchange</tt> é chamado.</p><p>
<a name="%_sec_Temp_427" id="%_sec_Temp_427"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_427">Implementando serializadores</a></h4><p>
<a name="%_idx_3638" id="%_idx_3638"/>Implementamos serializadores em termos de um mecanismo de sincronização mais primitivo chamado de <a name="%_idx_3640" id="%_idx_3640"/><em>mutex</em>. Um mutex é um objeto que suporta duas operações – o mutex pode ser <a name="%_idx_3642" id="%_idx_3642"/><em>adquirido</em> e o mutex pode ser <a name="%_idx_3644" id="%_idx_3644"/><em>liberado</em>. Depois que um mutex for adquirido, nenhuma outra operação de aquisição nesse mutex poderá prosseguir até que o mutex seja liberado.<a name="call_footnote_Temp_428" href="#footnote_Temp_428" id="call_footnote_Temp_428"><sup><small>44</small></sup></a> Em nossa implementação, cada serializador possui um mutex associado. Dado um procedimento <tt>p</tt>, o serializador retorna um procedimento que adquire o mutex, executa <tt>p</tt> e libera o mutex. Isso garante que apenas um dos procedimentos produzidos pelo serializador possa ser executado ao mesmo tempo, que é precisamente a propriedade de serialização que precisamos garantir.</p><p>
</p><p/><p><tt><a name="%_idx_3660" id="%_idx_3660"/>(define (make-serializer)<br/>
(let ((mutex (make-mutex)))<br/>
(lambda (p)<br/>
(define (serialized-p . args)<br/>
(mutex 'acquire)<br/>
(let ((val (apply p args)))<br/>
(mutex 'release)<br/>
val))<br/>
serialized-p)))<br/></tt></p><p/><p/><p>O mutex é um objeto mutável (aqui usaremos uma lista de um elemento, à qual chamaremos de <a name="%_idx_3662" id="%_idx_3662"/><em>célula</em>) que podem reter o valor verdadeiro ou falso. Quando o valor é falso, o mutex está disponível para aquisição. Quando o valor for verdadeiro, o mutex estará indisponível e qualquer processo que tente adquiri-lo deve esperar.</p><p>Nosso construtor mutex <tt>make-mutex</tt> começa iniciando o conteúdo da célula como falso. Para adquirir o mutex, testamos a célula. Se o mutex estiver disponível, configuramos o conteúdo da célula como verdadeiro e prosseguimos. Caso contrário, esperamos em um laço, tentando adquirir repetidamente, até descobrirmos que o mutex está disponível.<a name="call_footnote_Temp_429" href="#footnote_Temp_429" id="call_footnote_Temp_429"><sup><small>45</small></sup></a> Para liberar o mutex, definimos o conteúdo da célula como falso.</p><p>
</p><p/><p><tt><a name="%_idx_3668" id="%_idx_3668"/>(define (make-mutex)<br/>
(let ((cell (list false))) <br/>
(define (the-mutex m)<br/>
(cond ((eq? m 'acquire)<br/>
(if (test-and-set! cell)<br/>
(the-mutex 'acquire))) <em>; retry</em><br/>
((eq? m 'release) (clear! cell))))<br/>
the-mutex))<br/>
(define (clear! cell)<br/>
(set-car! cell false))<br/></tt></p><p/><p/><p>
<tt>Test-and-set!</tt> testa a célula e retorna o resultado do teste. Além disso, se o teste for falso, <tt>test-and-set!</tt> define o conteúdo da célula como verdadeiro antes de retornar falso. Podemos expressar esse comportamento como o seguinte procedimento:</p><p>
</p><p/><p><tt><a name="%_idx_3670" id="%_idx_3670"/>(define (test-and-set! cell)<br/>
(if (car cell)<br/>
true<br/>
(begin (set-car! cell true)<br/>
false)))<br/></tt></p><p/><p/><p>No entanto, esta implementação de <tt>test-and-set!</tt> não é suficiente como está. Há uma sutileza crucial aqui, que é o local essencial onde o controle de concorrência entra no sistema: operação <tt>test-and-set!</tt> deve ser executada <a name="%_idx_3672" id="%_idx_3672"/><em>atomicamente</em>. Ou seja, devemos garantir que, uma vez que um processo tenha testado a célula e considerado falso, o conteúdo da célula será realmente definido como verdadeiro antes que qualquer outro processo possa testar a célula. Se não fizermos essa garantia, o mutex poderá falhar de maneira semelhante à falha da conta bancária na figura <a href="#%_fig_3.29">3.29</a>. (Veja exercício <a href="#%_thm_3.46">3.46</a>).</p><p>A implementação real de <tt>test-and-set!</tt> depende dos detalhes de como nosso sistema executa processos concorrentes. Por exemplo, podemos executar processos concorrentes em um processador sequencial usando um <a name="%_idx_3674" id="%_idx_3674"/>mecanismo de divisão de tempo que percorre os processos, permitindo que cada processo seja executado por um curto período de tempo antes de interrompê-lo e passar para o próximo processo. Nesse caso, <tt>test-and-set!</tt> pode funcionar desativando a redução do tempo durante o teste e a configuração.<a name="call_footnote_Temp_430" href="#footnote_Temp_430" id="call_footnote_Temp_430"><sup><small>46</small></sup></a> Como alternativa, os computadores de multiprocessamento fornecem instruções que suportam operações atômicas diretamente no hardware.<a name="call_footnote_Temp_431" href="#footnote_Temp_431" id="call_footnote_Temp_431"><sup><small>47</small></sup></a></p><p>
</p><p><a name="%_thm_3.46" id="%_thm_3.46"/>
<b>Exercício 3.46.</b> Suponha que implementemos <tt>test-and-set!</tt> usando um procedimento comum, como mostrado no texto, sem tentar tornar a operação atômica. Desenhe um diagrama de tempo como o da figura <a href="#%_fig_3.29">3.29</a> demonstrar como a implementação do mutex pode falhar, permitindo que dois processos adquiram o mutex ao mesmo tempo.</p><p/><p>
</p><p><a name="%_thm_3.47" id="%_thm_3.47"/>
<b>Exercício 3.47.</b> <a name="%_idx_3692" id="%_idx_3692"/>Um semáforo (de tamanho <em>n</em>) é uma generalização de um mutex. Como um mutex, um semáforo suporta operações de aquisição e lançamento, mas é mais geral em até <em>n</em> processos podem adquiri-lo concorrentemente. Processos adicionais que tentam adquirir o semáforo devem esperar pelas operações de liberação. Dar implementações de semáforos</p><p>
</p><p/><p>a. em termos de mutexes</p><p>
</p><p/><p>b. em termos de atômica operações <tt>test-and-set!</tt>.</p><p>
<a name="%_sec_Temp_434" id="%_sec_Temp_434"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_434">Impasse</a></h4><p>
<a name="%_idx_3694" id="%_idx_3694"/><a name="%_idx_3696" id="%_idx_3696"/>Agora que vimos como implementar serializadores, podemos ver que a troca de contas ainda possui um problema, mesmo com o procedimento <tt>serialized-exchange</tt> acima. Imagine que Peter tenta trocar <em>a</em>1 com <em>a</em>2 enquanto Paul concorrentemente tenta trocar <em>a</em>2 com <em>a</em>1 Suponha que o processo de Peter chegue ao ponto em que ele entrou em um procedimento serializado, protegendo <em>a</em>1 e, logo após, o processo de Paul entra em um procedimento serializado que protege <em>a</em>2) Agora, Peter não pode prosseguir (para inserir um procedimento serializado <em>a</em>2) até que Paul saia do procedimento serializado, protegendo <em>a</em>2) Da mesma forma, Paul não pode prosseguir até que Peter saia do procedimento serializado, protegendo <em>a</em>1 Cada processo é interrompido para sempre, aguardando o outro. Essa situação é chamada de <em>impasse</em>. O impasse é sempre um perigo em sistemas que fornecem acesso concorrente a vários recursos compartilhados.</p><p>
<a name="%_idx_3698" id="%_idx_3698"/>Uma maneira de evitar o impasse nessa situação é atribuir a cada conta um número de identificação exclusivo e reescrever <tt>serialized-exchange</tt> para que um processo sempre tente inserir um procedimento que proteja primeiro a conta com o menor número. Embora esse método funcione bem para o problema de troca, há outras situações que requerem técnicas mais sofisticadas de prevenção de impasses ou em que o impasse não pode ser evitado. (Veja exercícios <a href="#%_thm_3.48">3.48</a> e <a href="#%_thm_3.49">3.49</a>).<a name="call_footnote_Temp_435" href="#footnote_Temp_435" id="call_footnote_Temp_435"><sup><small>48</small></sup></a></p><p>
</p><p><a name="%_thm_3.48" id="%_thm_3.48"/>
<b>Exercício 3.48.</b> <a name="%_idx_3708" id="%_idx_3708"/>Explique em detalhes por que o método de prevenção de impasse descrito acima (ou seja, as contas são numeradas e cada processo tenta adquirir a conta com números menores primeiro) evita impasse no problema de troca. Reescreva <tt>serialized-exchange</tt> para incorporar essa ideia. (Você também precisará modificar <tt>make-account</tt> para que cada conta seja criada com um número, que pode ser acessado enviando uma mensagem apropriada).</p><p/><p>
</p><p><a name="%_thm_3.49" id="%_thm_3.49"/>
<b>Exercício 3.49.</b> Forneça um cenário em que o mecanismo de prevenção de impasse descrito acima não funcione. (Dica: no problema de troca, cada processo sabe antecipadamente quais contas precisará acessar. Considere uma situação em que um processo deve ter acesso a alguns recursos compartilhados antes de saber quais recursos compartilhados adicionais serão necessários).</p><p>
</p><p>
<a name="%_sec_Temp_438" id="%_sec_Temp_438"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_438">Concorrência, tempo e comunicação</a></h4><p>Vimos como a programação de sistemas concorrentes requer o controle da ordem dos eventos quando diferentes processos acessam o estado compartilhado e vimos como obter esse controle através do uso criterioso de serializadores. Mas os problemas de concorrência são mais profundos do que isso, pois, de um ponto de vista fundamental, nem sempre é claro o que se entende por “estado compartilhado”.</p><p>Mecanismos como <tt>test-and-set!</tt> exigem processos para examinar um sinalizador compartilhado global em momentos arbitrários. Isso é problemático e ineficiente para implementar em processadores modernos de alta velocidade, onde, devido a técnicas de otimização, como pipelining e memória em cache, o conteúdo da memória pode não estar em um estado consistente a cada instante. Nos sistemas contemporâneos multiprocessados, portanto, o paradigma serializador é suplantado por novas abordagens ao controle de concorrência.<a name="call_footnote_Temp_439" href="#footnote_Temp_439" id="call_footnote_Temp_439"><sup><small>49</small></sup></a></p><p>Os aspectos problemáticos do estado compartilhado também surgem em sistemas grandes e distribuídos. Por exemplo, imagine um sistema bancário distribuído em que bancos individuais mantêm valores locais para saldos bancários e os comparam periodicamente com valores mantidos por outras agências. Nesse sistema, o valor do “saldo da conta” seria indeterminado, exceto logo após a sincronização. Se Peter deposita dinheiro em uma conta que ele mantém em conjunto com Paul, quando devemos dizer que o saldo da conta mudou – quando o saldo da agência local muda, ou não até depois da sincronização? E se Paul acessa a conta de uma agência diferente, quais são as restrições razoáveis a serem impostas ao sistema bancário, de modo que o comportamento seja “correto”? O único objeto que pode ter importância é o comportamento observado por Peter e Paul individualmente e o “estado” da conta imediatamente após a sincronização. Perguntas sobre o saldo “real” da conta ou a ordem dos eventos entre as sincronizações podem ser irrelevantes ou sem sentido.<a name="call_footnote_Temp_440" href="#footnote_Temp_440" id="call_footnote_Temp_440"><sup><small>50</small></sup></a></p><p>
<a name="%_idx_3720" id="%_idx_3720"/>O fenômeno básico aqui é que sincronizar diferentes processos, estabelecer estado compartilhado ou impor uma ordem aos eventos requer comunicação entre os processos. Em essência, qualquer noção de tempo no controle de concorrência deve estar intimamente ligada à comunicação.<a name="call_footnote_Temp_441" href="#footnote_Temp_441" id="call_footnote_Temp_441"><sup><small>51</small></sup></a> É intrigante que uma conexão semelhante entre tempo e comunicação também surja na <a name="%_idx_3724" id="%_idx_3724"/>Teoria da Relatividade, onde a velocidade da luz (o sinal mais rápido que pode ser usado para sincronizar eventos) é uma constante fundamental, relacionando tempo e espaço. As complexidades que encontramos ao lidar com o tempo e o estado em nossos modelos computacionais podem de fato espelhar uma complexidade fundamental do universo físico.</p><p>
</p><p/><div class="smallprint"><hr/></div><p>
</p><div class="footnote"><p><a name="footnote_Temp_405" href="#call_footnote_Temp_405" id="footnote_Temp_405"><sup><small>34</small></sup></a> A maioria dos processadores reais realmente executa algumas operações por vez, seguindo uma estratégia chamada <a name="%_idx_3582" id="%_idx_3582"/><em>tubulação</em>. Embora essa técnica melhore bastante a utilização eficaz do hardware, ela é usada apenas para acelerar a execução de um fluxo de instruções sequencial, mantendo o comportamento do programa sequencial.</p><p><a name="footnote_Temp_406" href="#call_footnote_Temp_406" id="footnote_Temp_406"><sup><small>35</small></sup></a> Para citar alguns grafites vistos na parede de um edifício <a name="%_idx_3586" id="%_idx_3586"/>de Cambridge: “O tempo é um dispositivo inventado para impedir que tudo aconteça de uma vez só”.</p><p><a name="footnote_Temp_407" href="#call_footnote_Temp_407" id="footnote_Temp_407"><sup><small>36</small></sup></a> Uma falha ainda pior para este sistema pode ocorrer se os duas as operações <tt>set!</tt> tentam alterar a balança concorrentemente; nesse caso, os dados reais que aparecem na memória podem acabar sendo uma combinação aleatória das informações gravadas pelos dois processos. A maioria dos computadores possui intertravamentos nas operações primitivas de gravação na memória, que protegem contra esse acesso concorrente. Mesmo esse tipo aparentemente simples de proteção, no entanto, levanta desafios de implementação no projeto de computadores de multiprocessamento, onde elaborados protocolos de <a name="%_idx_3594" id="%_idx_3594"/><em>coerência de cache</em> são necessários para garantir que os vários processadores mantenham uma visão consistente do conteúdo da memória, apesar do fato de que os dados podem ser replicados (em cache) entre os diferentes processadores para aumentar a velocidade do acesso à memória.</p><p><a name="footnote_Temp_409" href="#call_footnote_Temp_409" id="footnote_Temp_409"><sup><small>37</small></sup></a> O programa fatorial na seção <a href="book-Z-H-20.html#%_sec_3.1.3">3.1.3</a> ilustra isso para um único processo sequencial.</p><p><a name="footnote_Temp_410" href="#call_footnote_Temp_410" id="footnote_Temp_410"><sup><small>38</small></sup></a> As colunas mostram o conteúdo da carteira de Peter, a conta conjunta (no Banco1), a carteira de Paul e a conta privada de Paul (no Banco2), antes e depois de cada retirada (W) e depósito (D). Peter retira $10 do Bank1; Paul deposita $5 no Banco2 e depois retira $25 do Banco1.</p><p><a name="footnote_Temp_411" href="#call_footnote_Temp_411" id="footnote_Temp_411"><sup><small>39</small></sup></a> Uma maneira mais formal de expressar essa ideia é dizer que programas concorrentes são inerentemente <a name="%_idx_3604" id="%_idx_3604"/><em>não determinístico</em>. Ou seja, eles são descritos não por funções de valor único, mas por funções cujos resultados são conjuntos de valores possíveis. Na seção <a href="book-Z-H-28.html#%_sec_4.3">4.3.</a> estudaremos uma linguagem para expressar cálculos não determinísticos.</p><p><a name="footnote_Temp_415" href="#call_footnote_Temp_415" id="footnote_Temp_415"><sup><small>40</small></sup></a><tt>Parallel-execute</tt> não faz parte do Scheme padrão, mas pode ser implementado no MIT Scheme. Em nossa implementação, os novos processos concorrentes também são executados concorrentemente com o processo original do Scheme. Além disso, em nossa implementação, o valor retornado por <tt>parallel-execute</tt> é um objeto de controle especial que pode ser usado para interromper os processos recém-criados.</p><p><a name="footnote_Temp_421" href="#call_footnote_Temp_421" id="footnote_Temp_421"><sup><small>41</small></sup></a> Simplificamos <tt>exchange</tt> explorando o fato de que nossos a mensagem <tt>deposit</tt> aceita valores negativos. (Este é um problema sério em nosso sistema bancário!)</p><p><a name="footnote_Temp_422" href="#call_footnote_Temp_422" id="footnote_Temp_422"><sup><small>42</small></sup></a> Se os saldos da conta começarem em $10, $20 e $30, depois de qualquer número de trocas concorrentes, os saldos ainda deverão ser de $10, $20 e $30 em alguma ordem. Serializar os depósitos em contas individuais não é suficiente para garantir isso. Veja o exercício <a href="#%_thm_3.43">3.43</a>.</p><p><a name="footnote_Temp_423" href="#call_footnote_Temp_423" id="footnote_Temp_423"><sup><small>43</small></sup></a> Exercício <a href="#%_thm_3.45">3.45</a> investiga por que os depósitos e saques não são mais serializados automaticamente pela conta.</p><p><a name="footnote_Temp_428" href="#call_footnote_Temp_428" id="footnote_Temp_428"><sup><small>44</small></sup></a> O termo “mutex” é uma abreviação de <a name="%_idx_3646" id="%_idx_3646"/><em>exclusão mútua</em>. O problema geral de organizar um mecanismo que permita que processos concorrentes compartilhem recursos com segurança é chamado de problema de exclusão mútua. Nosso mutex é uma variante simples do mecanismo do <a name="%_idx_3648" id="%_idx_3648"/><em>semáforo</em> (ver exercício <a href="#%_thm_3.47">3.47</a>), que foi introduzido no <a name="%_idx_3650" id="%_idx_3650"/>Sistema de Multiprogramação “THE” desenvolvido na <a name="%_idx_3652" id="%_idx_3652"/>Universidade Tecnológica de Eindhoven e nomeada para as iniciais da universidade em holandês (Dijkstra 1968a). As operações de aquisição e liberação foram originalmente chamadas <a name="%_idx_3654" id="%_idx_3654"/><a name="%_idx_3656" id="%_idx_3656"/><a name="%_idx_3658" id="%_idx_3658"/>P e V, das palavras holandesas <em>passeren</em> (para passar) e <em>vrijgeven</em> (a liberar), em referência aos semáforos utilizados nos sistemas ferroviários. A exposição clássica de Dijkstra (1968b) foi uma das primeiras a apresentar claramente os problemas do controle de concorrência e mostrou como usar semáforos para lidar com uma variedade de problemas de concorrência.</p><p><a name="footnote_Temp_429" href="#call_footnote_Temp_429" id="footnote_Temp_429"><sup><small>45</small></sup></a> Na maioria dos sistemas operacionais compartilhados, processos que são <a name="%_idx_3664" id="%_idx_3664"/>bloqueados por um mutex <a name="%_idx_3666" id="%_idx_3666"/>não pedem mais tempo “espera ativa” como acima. Em vez disso, o sistema agenda outro processo para ser executado enquanto o primeiro está aguardando, e o processo bloqueado é despertado quando o mutex fica disponível.</p><p><a name="footnote_Temp_430" href="#call_footnote_Temp_430" id="footnote_Temp_430"><sup><small>46</small></sup></a> No MIT Scheme para um único processador, que usa um modelo de divisão de tempo, <tt>test-and-set!</tt> pode ser implementado da seguinte maneira:<a name="%_idx_3676" id="%_idx_3676"/><a name="%_idx_3678" id="%_idx_3678"/></p><p/><p><tt><a name="%_idx_3680" id="%_idx_3680"/>(define (test-and-set! cell)<br/>
(without-interrupts<br/>
(lambda ()<br/>
(if (car cell)<br/>
true<br/>
(begin (set-car! cell true)<br/>
false)))))<br/></tt></p><p/><p>
<tt>Without-interrupts</tt> desativa as interrupções de divisão de tempo enquanto o argumento do procedimento é executado.</p><p><a name="footnote_Temp_431" href="#call_footnote_Temp_431" id="footnote_Temp_431"><sup><small>47</small></sup></a> Existem muitas variantes dessas <a name="%_idx_3682" id="%_idx_3682"/>instruções – incluindo testar e definir, testar-e-limpar, trocar, comparar-e-trocar, carregar-reservar e armazenar-condicional, cujo design deve ser cuidadosamente combinado com a interface processador-memória da máquina. Um problema que surge aqui é determinar o que acontece se dois processos tentam adquirir o mesmo recurso exatamente ao mesmo tempo usando essa instrução. Isso requer algum mecanismo para tomar uma decisão sobre qual processo obtém controle. Esse mecanismo é chamado de <a name="%_idx_3684" id="%_idx_3684"/><em>árbitro</em>. Os árbitros geralmente se resumem a algum tipo de dispositivo de hardware. Infelizmente, é possível provar que não se pode construir fisicamente um árbitro justo que trabalhe 100% do tempo, a menos que se permita ao árbitro um tempo arbitrariamente longo para tomar sua decisão. O fenômeno fundamental aqui foi originalmente observado pelo filósofo francês do século XIV <a name="%_idx_3686" id="%_idx_3686"/>Jean Buridan em seu comentário sobre <a name="%_idx_3688" id="%_idx_3688"/>Aristóteles <i>De caelo</i>. Buridan argumentou que um <a name="%_idx_3690" id="%_idx_3690"/>cão perfeitamente racional colocado entre duas fontes igualmente atraentes de comida morrerá de fome, pois é incapaz de decidir aonde ir primeiro.</p><p><a name="footnote_Temp_435" href="#call_footnote_Temp_435" id="footnote_Temp_435"><sup><small>48</small></sup></a> A técnica geral para evitar impasse, numerando os<a name="%_idx_3700" id="%_idx_3700"/>recursos compartilhados e adquiri-los em ordem é devido a <a name="%_idx_3702" id="%_idx_3702"/><a name="%_idx_3704" id="%_idx_3704"/><a name="%_idx_3706" id="%_idx_3706"/>Havender (1968). As situações em que o impasse não pode ser evitado exigem <em>recuperação de impasse</em> métodos, o que implica a retirada de processos do estado de impasse e tente novamente. Mecanismos de recuperação de impasse são amplamente utilizados em sistemas de gerenciamento de banco de dados, um tópico tratado em detalhes em Gray e Reuter 1993.</p><p><a name="footnote_Temp_439" href="#call_footnote_Temp_439" id="footnote_Temp_439"><sup><small>49</small></sup></a> Uma dessas alternativas à serialização é chamada <a name="%_idx_3710" id="%_idx_3710"/><em>sincronização de barreira</em>. O programador permite que processos concorrentes sejam executados como bem entenderem, mas estabelece certos pontos de sincronização (“barreiras”) pelos quais nenhum processo pode prosseguir até que todos os processos tenham atingido a barreira. Os processadores modernos fornecem instruções da máquina que permitem aos programadores estabelecer pontos de sincronização em locais onde a consistência é necessária. o <a name="%_idx_3712" id="%_idx_3712"/>PowerPC<sup><em>T</em><em>M</em></sup>, por exemplo, inclui para esse fim duas instruções chamadas <a name="%_idx_3714" id="%_idx_3714"/>SYNC e <a name="%_idx_3716" id="%_idx_3716"/>EIEIO (Execução ordenada forçada de entrada/saída).</p><p><a name="footnote_Temp_440" href="#call_footnote_Temp_440" id="footnote_Temp_440"><sup><small>50</small></sup></a> Pode parecer um ponto de vista estranho, mas existem <a name="%_idx_3718" id="%_idx_3718"/>sistemas que funcionam dessa maneira. As cobranças internacionais em contas de cartão de crédito, por exemplo, são normalmente compensadas por país e as cobranças feitas em diferentes países são periodicamente reconciliadas. Portanto, o saldo da conta pode ser diferente em diferentes países.</p><p><a name="footnote_Temp_441" href="#call_footnote_Temp_441" id="footnote_Temp_441"><sup><small>51</small></sup></a> Para sistemas distribuídos, essa perspectiva foi seguida por <a name="%_idx_3722" id="%_idx_3722"/>Lamport (1978), que mostrou como usar a comunicação para estabelecer “relógios globais” que podem ser usados para estabelecer pedido em eventos em sistemas distribuídos.</p></div>
</body>
</html>