Combinaison mystérieuse

Question

J'ai décidé d'apprendre la concurrence et je voulais savoir de combien de façons les instructions de deux processus différents pouvaient se chevaucher. Le code pour les deux processus est juste une boucle de 10 itérations avec 3 instructions exécutées dans chaque itération. J'ai compris que le problème consistait à laisser X instructions fixées en un point puis à adapter les autres instructions X de l'autre processus entre les espaces en tenant compte du fait qu'elles doivent être ordonnées (l'instruction 4 du processus B doit toujours précéder l'instruction 20). J'ai écrit un programme pour compter ce nombre, en regardant les résultats, j'ai découvert que la solution est n Combinaison k, où k est le nombre d'instructions exécutées tout au long de la boucle d'un processus, donc pour 10 itérations il serait être 30, et n est k * 2 (2 processus). En d'autres termes, n nombre d'objets avec n/2 fixé et devant s'adapter n/2 parmi les espaces sans que ce dernier n/2 perde son ordre.

Problème résolu. Non, pas vraiment. Je ne sais pas pourquoi c'est, je comprends que la définition d'une combinaison est, de combien de façons pouvez-vous prendre k éléments d'un groupe de n tels que tous les groupes sont différents, mais l'ordre dans lequel vous prenez les éléments doesn ' t importe. Dans ce cas, nous avons n éléments et nous les prenons tous, car toutes les instructions sont exécutées (n C n). Si on l'explique en disant qu'il y a 2k objets bleus (A) et rouges (B) dans un sac et que vous prenez 8 objets du sac, vous ne prenez encore que k instructions quand les instructions 2k sont réellement exécutées. Pouvez-vous s'il vous plait éclaircir cela?

Merci d'avance.

Answer 1

Généralement, je suis d'accord avec la réponse de Péter, mais comme il ne semble pas avoir complètement cliqué sur l'OP, voici mon point de vue (uniquement d'un point de vue mathématique/combinatoire).

Vous avez 2 séries d'instructions de 30 (k) que vous mettez ensemble, pour un total de 60 instructions. Puisque chaque ensemble de 30 doit être maintenu dans l'ordre, nous n'avons pas besoin de suivre quelle instruction dans chaque ensemble, juste de quel jeu provient une instruction. Donc, nous avons 60 "emplacements" dans lesquels placer 30 instructions d'un ensemble (par exemple, rouge) et 30 instructions de l'autre ensemble (disons, bleu).

Commençons par placer les 30 instructions rouges dans les 60 emplacements. Il y a (60 choisir 30) = 60!/(30! 30!) Façons de le faire (nous choisissons quels 30 emplacements des 60 sont remplis par des instructions rouges). Maintenant, nous avons toujours les 30 instructions bleues, mais nous n'avons plus que 30 slots ouverts. Il y a (30 choisir 30) = 30!/(30! 0!) = 1 façon de placer les instructions bleues dans les emplacements restants. Donc, au total, il y a (60 choisir 30) * (30 choisir 30) = (60 choisir 30) * 1 = (60 choisir 30) façons de le faire. Maintenant, supposons qu'au lieu de 2 séries de 30, vous ayez 3 ensembles (rouge, vert, bleu) de k instructions. Vous avez un total de 3k emplacements à remplir. Placez d'abord les rouges: (3k choisissez k) = (3k)!/(K! (3k-k)!) = (3k)!/(K! (2k)!). Maintenant, placez les vertes dans les fentes 2k restantes: (2k choisissez k) = (2k)!/(K! K!). Enfin, placez les bleus dans les k derniers créneaux: (k choisissez k) = k!/(K! 0!) = 1. Au total: (3k choisissez k) * (2k choisissez k) * (k choisissez k) = ((3k)! * (2k)! * K!)/(K! (2k)! * K! K! * K! 0!) = (3k)!/(K! K! K!).

Comme d'autres extensions (bien que je ne vais pas donner une explication complète):

• si vous avez 3 séries d'instructions de longueur a, b, et c, le nombre de possibilités est (un + b + c)!/(a! b! c!).
• Si vous avez n ensembles d'instructions où le ième ensemble a des instructions ki, le nombre de possibilités est (k1 + k2 + ... + kn)!/(K1! K2! ... kn!).

Answer 2

FWIW il peut être vu comme ceci: vous avez un sac avec k bleu et k boules rouges. Des boules de même couleur sont indiscernables (par analogie avec la restriction que l'ordre des instructions dans le même processus/thread est fixé - ce qui n'est pas vrai dans les processeurs modernes, mais gardons-le simple pour l'instant). Combien de façons différentes pouvez-vous tirer tous les balles du sac?

Mes compétences combinatoires sont tout à fait rouillé, mais ma première supposition est

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

qui, selon Wikipedia, égale en effet

(2k) 
(k) 

(désolé, je n'ai pas de meilleure idée comment montrer).

Pour n processus, elle peut être généralisée en ayant des boules de n couleur différente dans le sac. Notez qu'au sens strict, cela ne modélise que le cas où différents processus sont exécutés sur un seul processeur, donc toutes les instructions de tous les processus doivent être ordonnées linéairement au niveau du processeur. Dans un environnement multiprocesseur, plusieurs instructions peuvent être exécutées littéralement en même temps.

Answer 3

La réponse de Péter est assez bien, mais cela n'explique pas pourquoi la concurrence est difficile. C'est parce que de plus en plus souvent de nos jours, vous avez plusieurs unités d'exécution disponibles (que ce soit des noyaux, des processeurs, des nœuds, des ordinateurs, etc.). Cela signifie à son tour que les possibilités de chevauchement entre les instructions sont encore accrues; il n'y a aucune garantie que ce qui se passe peut être modélisé correctement avec n'importe quel entrelacement conventionnel.C'est pourquoi il est important de penser en termes d'utilisation correcte des sémaphores/mutex, et pourquoi les barrières de la mémoire sont importantes. C'est parce que toutes ces choses finissent par transformer la vraie image désagréable en quelque chose qui est beaucoup plus facile à comprendre. Mais parce que les mutex réduisent le nombre d'exécutions possibles, ils réduisent la performance globale et l'efficacité potentielle. C'est vraiment délicat, et c'est pourquoi il vaut mieux que vous travailliez en termes de passage de messages entre des activités qui n'interagissent pas autrement; c'est plus facile à comprendre et avoir moins de synchronisations, c'est mieux.