combinazione misteriosa

Question

ho deciso di imparare concorrenza e voluto scoprire in quanti modi istruzioni da due diversi processi potrebbero sovrapporsi. Il codice per entrambi i processi è solo un anello 10 di iterazione con 3 istruzioni eseguite in ogni iterazione. Ho capito il problema consisteva di lasciare istruzioni X fissi in un punto e poi montare le altre istruzioni X dall'altro processo tra gli spazi, tenendo conto che essi devono essere ordinati (istruzione 4 del processo B deve sempre venire prima di istruzioni 20).

Ho scritto un programma per contare il numero, guardando i risultati ho scoperto che la soluzione è n Combinazione k, dove k è il numero di istruzioni eseguite durante tutto il ciclo di un processo, quindi per 10 iterazioni sarebbe 30, ed n è k * 2 (2 processi). In altre parole, n il numero di oggetti con n / 2 fisse e dover montare n / 2 tra gli spazi senza quest'ultimo n / 2 di perdere il loro ordine.

problema Ok risolto. No, non proprio. Non ho idea perché questo è, capisco che la definizione di aggregazione è, in quanti modi si può prendere k elementi da un gruppo di n tale che tutti i gruppi sono diversi, ma l'ordine in cui si prende gli elementi doesn' t questione. In questo caso abbiamo n elementi e in realtà stiamo tutti prendendo, perché tutte le istruzioni vengono eseguite (n C n).

Se uno lo spiega dicendo che ci sono 2k blu (A) e rossa (B) Gli oggetti in un sacchetto e si prendono gli oggetti k dalla borsa, si sta ancora solo prendendo istruzioni k quando 2k istruzioni sono in realtà eseguite. Potete per favore fare una certa luce in tutto questo?

Grazie in anticipo.

Answer 1

In generale, sono d'accordo con la risposta di Pietro, ma dal momento che non sembra aver pienamente cliccato per l'OP, ecco il mio colpo a esso (puramente da un punto di vista matematico / combinatoria).

Hai 2 set di 30 (k) istruzioni che si sta mettendo insieme, per un totale di 60 (n) istruzioni. Dal momento che ogni gruppo di 30 deve essere tenuto in ordine, non abbiamo bisogno di tenere traccia di quali istruzioni all'interno di ogni set, solo che ha fissato un'istruzione è da. Così, abbiamo 60 "slot" in cui collocare 30 istruzioni da un set (diciamo, rosso) e 30 istruzioni del altra serie (diciamo, blu).

La partenza di Let mettendo le 30 istruzioni rosse nelle 60 slot. Ci sono (60 scelgono 30) = 60! / (30! 30!) Modi per farlo (stiamo scegliendo quale 30 slot del 60 sono occupati da istruzioni rosse). Ora, abbiamo ancora le 30 istruzioni blu, ma abbiamo solo 30 slot aperti a sinistra. C'è (30 scelgono 30) = 30! / (30! 0!) = 1 modo per posizionare le istruzioni blu nei rimanenti slot. Quindi, in totale, ci sono (60 scelgono 30) * (30 scelgono 30) = (60 scelgono 30) * 1 = (60 scelgono 30) modi per farlo.

Ora, supponiamo che invece di 2 set di 30, si dispone di 3 set (rosso, verde, blu) di istruzioni k. Si dispone di un totale di 3k slot da riempire. In primo luogo, inserire i rossi: (3k scegliere k) = (3k) / = (3K) /! (K (3k-k)!!)! (K (2k)!!). Ora, posto quelle verdi nelle restanti 2k slot: (2k scegliere k) = (2k) / (k k!!)!. Infine, posizionare quelli blu nelle fessure ultima k: (k scegliere k) = k / (k 0!!) = 1. In totale:! (3k scegliere k) * (2k scegliere k) * (k scegliere k) = ((3k) * (2k) * k!) / (k! (2k) * k! k * k! 0!) = (3k)! / (k! k! k!).

Come ulteriori estensioni (anche se io non ho intenzione di fornire una spiegazione completa):

• se si dispone di 3 set di istruzioni di lunghezza a, b, c, il numero di possibilità è (a + b + c)! / (Una! B! C!).
• se si dispone di n set di istruzioni in cui il set-esimo ha istruzioni ki, il numero di possibilità è (k1 + k2 + ... + kn)! / (K1! K2! ... kn!).

Answer 2

FWIW può essere visto in questo modo: si dispone di una borsa con k k palle rosse e blu. Palle dello stesso colore sono indistinguibili (in analogia con la restrizione che l'ordine delle istruzioni all'interno dello stesso processo / thread è fisso - che non è vero nei processori moderni btw, ma teniamolo semplice per ora). In quanti modi diversi si può tirare tutti le palline dal sacchetto?

Le mie capacità combinatorie sono abbastanza arrugginito, ma la mia prima ipotesi è

(2k!)
-----
2*k!

, che, in base alle Wikipedia , equivale infatti

(2k)
(k )

(mi dispiace, non ho idea di meglio come mostrare questo).

Per n processi, può essere generalizzata con palline di n colore diverso nel sacchetto.

Aggiornamento: Si noti che in senso stretto, questo modelli solo la situazione in cui diversi processi vengono eseguiti su un singolo processore, per cui tutte le istruzioni da tutti i processi devono essere ordinati linearmente a livello del processore. In un ambiente multiprocessore, diverse istruzioni possono essere eseguite letteralmente allo stesso tempo.

Answer 3

La risposta di Pietro è bene abbastanza, ma questo non spiega il motivo per cui solo la concorrenza è difficile. Questo perché unità di esecuzione multipla sempre più spesso al giorno d'oggi avete ottenuto disponibili (siano essi core, CPU, nodi, computer, a prescindere). Che nei mezzi sua volta che le possibilità di sovrapposizione tra istruzioni viene aumentata ulteriormente; non c'è alcuna garanzia che ciò che accade può essere modellato correttamente con qualsiasi interleaving convenzionale.

Questo è il motivo per cui è importante pensare in termini di utilizzo di semafori / mutex in modo corretto, e perché le barriere di memoria contano. Questo perché tutte queste cose finiscono per trasformare la vera immagine sgradevole in qualcosa che è molto più facile da capire. Ma perché mutex riducono il numero di possibili esecuzioni, stanno riducendo le prestazioni complessive e potenziale di efficienza. E 'sicuramente difficile, e che a sua volta è il motivo per cui è molto meglio se si può lavorare in termini di scambio di messaggi tra i thread di attività che altrimenti non interagiscono; è più facile da capire e avere un minor numero di sincronizzazioni è meglio.