Di bistecche, fornelli e ... multicore!

Il post di ieri poneva un semplice problemino che ha a che fare con il mio campo di ricerca.

Riporto prima le soluzioni alle due domande.

La soluzione alla prima domanda è 9 minuti. Vedere il commento dell'ottimo Ivo, che riporta anche il metodo per cuocere il tutto in 9 minuti. Faccio uno schemino qui sotto.

Slot	1	2	3
Fornello 1	1a	1b	2a
Fornello 2	2b	3a	3b

Con slot intendo un intervallo di tempo pari a 3 minuti. Durante il primo slot cuocio la prima bistecca dal lato A, e la seconda bistecca dal lato B. Nel secondo slot giro la prima bistecca sul primo fornello e metto a cuocere la terza bistecca sul secondo fornello. Etc.

Passiamo adesso alla generalizzazione richiesta nella seconda domanda. Il ragionamento e la soluzione proposte da Juhan sono corrette. Ogni bistecca è composta da 2 lati, ognuno dei due lati ha bisogno di uno slot di 3 minuti per cuocere. Quindi ho bisogno di 2N slots. Se ho a disposizione K fornelli, e se K divide esattamente 2N, allora il tempo totale necessario è pari a 2N / K slot.
Rimane però da dimostrare che esiste effettivamente un modo di cuocere queste bistecche. Infatti, i 2N lati da cuocere non sono del tutto indipendenti. Una cosa è avere 2N oggetti distinti da cuocere; una cosa è avere da cuocere N bistecche con 2 lati! Nel secondo caso, non è possibile cuocere in parallelo i due lati di una bistecca. Quindi, dobbiamo far vedere come si fa a cuocere N bistecche in 2N/K slot.
Facciamo l'esempio di N=5 bistecche su K=2 fornelli. Secondo la formula ci vogliono 5 slot. Ecco come si fa:

Slot	1	2	3	4	5
Fornello 1	1a	1b	2a	2b	3a
Fornello 2	3b	4a	4b	5a	5b

Avete capito il trucco? Per generare lo schema, comincio a riempire il primo fornello con i due lati di ciascuna bistecca, in ordine. Quando arrivo alla terza, essa ci entra solo per metà: poco male, vado a capo e continuo a metterle una di seguito all'altra. Come potete notare, non esiste uno slot in cui sui dui fornelli ci sia la stessa bistecca. Si può dimostrare agevolmente che questa costruzione è sempre possibile quando 2N/K è un numero intero.

Se invece 2N/K non è intero... facciamo prima il calcolo fatto da Juhan, cioè manteniamo lo slot di 3 minuti. In questo caso, nell'ultimo slot mi rimarrà qualche fornello libero. Il numero massimo di slot necessari è quindi ceil(2N/K) (cioè, prendo l'intero successivo al numero con la virgola ottenuto dalla divisione 2N/K). La costruzione è analoga alla precedente. Ad esempio, con 5 bistecche su 3 fornelli, il numero di slot necessari è 4 (pari a 12 minuti). Ecco due soluzioni:

Slot	1	2	3	4
Fornello 1	1a	1b	2a	2b
Fornello 2	3a	3b	4a	4b
Fornello 3	5a	5b
Slot	1	2	3	4
Fornello 1	1a	1b	2a	2b
Fornello 2	3a	3b	4a
Fornello 3	4b	5a	5b

Bene, ma nessuno ci obbliga a mantenere lo slot di 3 minuti. In effetti, la cottura di una bistecca potrei dividerla in 3 parti da 2 minuti ciascuna: nella prima parte cuocio il primo lato per 2 minuti; poi cuocio il primo lato per 1 minuto e il secondo lato per un minuto; infine cuocio il secondo lato per 2 minuti. In pratica, è come se la bistecca avesse 3 lati!. Li indichiamo con A, B e C.
Quindi, lo slot diventa di 2 minuti, e la formula diventa T = 6N/K. Nel nostro esempio con 5 bistecche su 3 fornelli, abbiamo 5 slot da 2 minuti, ovvero 10 minuti in tutto. E la schedulazione diventa la seguente:

Slot	1	2	3	4	5
Fornello 1	1a	1b	1c	2a	2b
Fornello 2	2c	3a	3b	3c	4a
Fornello 3	4b	4c	5a	5b	5c

Notate che non troverete lo stesso indice di bistecca su alcuna colonna!

E se avessi 100 bistecche e 99 fornelli (come suggerisce hronir)?
Beh, in linea teorica potrei avere slot di 6min/99, ovvero 2/33 di minuto. Però, diventa difficile spostare bistecche su 99 fornelli con slot di meno di 4 secondi!

Metafora

Che c'entra la tua ricerca? Che c'entrano i multicore nel titolo del post?
Beh, facciamo la seguente analogia:

• le bistecche sono programmi in esecuzione (in gergo: processi)
• i fornelli sono processori (in gergo: core)
• il povero Mario è colui che scegli quali bistecche cuocere di volta in volta (in gergo: lo schedulatore)

Questa classe di problemi, siano processi da eseguire su processori, bistecche da cuocere su fornelli, manufatti da fabbricare con macchine utensili, merci da caricare su camion, etc. fa parte di una branca della matematica conosciuta come "teoria della schedulazione" (scheduling theory). Io mi occupo di una sottobranca chiamata schedulazione in tempo reale o real-time scheduling.

Vediamo se mi viene in mente qualche altro problemino carino da sottoporvi nei prossimi post, tempo permettendo (continua...)