Question d'entretien : temps d'exécution de deux programmes exécutés séparément et ensuite ensemble.

Question

On m'a récemment posé cette question lors d'un entretien, et si j'ai bien répondu aux deux premières parties [je suppose], j'ai eu un peu de mal à répondre à la troisième. Voici la question :

Vous avez deux programmes Linux, A et B. Lorsqu'ils sont exécutés séparément, A et B mettent chacun une minute à se terminer sur un système qui vient d'être redémarré. (c'est-à-dire un système neuf : vous le redémarrez, vous vous connectez, obtenez une invite shell, exécutez le programme).

Que pouvez-vous me dire sur les programmes si :

a) lorsqu'ils sont exécutés ensemble, ils prennent 2 minutes b) lorsqu'ils sont exécutés ensemble, ils prennent 1 minute c) lorsqu'ils sont exécutés ensemble, ils prennent 30 secondes

J'ai dit pour a) que s'ils prennent exactement le double du temps lorsqu'ils sont exécutés ensemble, ils ne partagent aucune exclusion mutuelle et se disputent toutes les mêmes ressources, ne partagent probablement aucune sorte de données ou d'instructions de cache [et donc ne s'entraident pas du point de vue du cache] et chaque programme a besoin de la pleine utilisation de ladite ressource pour être achevé, de sorte que le système d'exploitation ne peut pas les paralléliser.

Pour b), j'ai dit que s'ils peuvent s'exécuter aussi rapidement ensemble, ils partagent probablement une certaine localité spatiale/temporelle dans l'argent, et peuvent se prêter à être correctement pipelinés de telle sorte que pendant que le programme A attend quelque chose, le programme B peut s'exécuter entre ces étapes, et vice versa - les exécuter tous les deux en 1 minute.

Pour le point c), j'étais un peu bloqué. Rétrospectivement, j'aurais probablement dû dire que les programmes A et B effectuaient tous deux une tâche commune, et que deux d'entre eux fonctionnant en même temps pouvaient accomplir cette tâche plus rapidement que l'un d'entre eux fonctionnant seul - comme un collecteur d'ordures. Mais le mieux que j'ai pu trouver, c'est qu'ils se sont peut-être chargés à partir du même secteur du disque dur, ce qui les a aidés à s'exécuter plus rapidement.

Je cherche juste à obtenir l'avis de quelques intelligents ici sur les choses que j'ai probablement manquées. Le poste à pourvoir est celui d'une plateforme/système qui nécessite une bonne compréhension du matériel/logiciel et des systèmes d'exploitation, et notamment des interactions entre eux, c'est pourquoi [je suppose] que la question a été posée.

J'ai également essayé de penser à des exemples que je pourrais appliquer à chaque partie pour aider à montrer ma connaissance des applications de la vie réelle des questions, mais sur le coup, je n'ai pas réussi.

Merci.

Answer 1

Ensemble, ils prennent 2 minutes à compléter

Dans ce cas, je pense que chaque programme est entièrement lié au processeur et peut saturer 100% des processeurs disponibles sur la machine. Par conséquent, lorsque les programmes s'exécutent ensemble, chacun d'eux tourne à la moitié de sa vitesse.

Il est également possible que ce soit le comportement observé si les deux programmes étaient capables et désireux de saturer une autre ressource que le CPU, par exemple un périphérique d'entrée/sortie. Cependant, étant donné que en pratique, généralement les performances des périphériques d'E/S ne diminuent pas linéairement avec la charge qui leur est appliquée s'ils sont sursaturés, je considérerais ce scénario comme moins probable et opterais pour la limitation du processeur comme première hypothèse.

Ensemble, ils prennent 1 minute à compléter

Les deux programmes ne se disputent pas les mêmes ressources, ou il y a suffisamment de ressources dans le système pour satisfaire les demandes des deux. Par conséquent, ils finissent par ne pas interférer l'un avec l'autre.

Ensemble, ils prennent une demi-minute à compléter

Les programmes fonctionnent avec les mêmes données d'entrée, et tous deux peuvent savoir quand toutes les données d'entrée sont utilisées, de sorte que chacun d'entre eux effectue la moitié du travail qu'il ferait s'il était lancé seul avec la moitié du temps d'exécution. De plus, le système a manifestement la capacité de fournir le double de la quantité de la ressource à laquelle ces programmes sont limités.

Puisque dans ce cas le temps d'exécution diminue linéairement avec le nombre de processus (mise à l'échelle parfaite), il semble plus probable que la ressource qui contraint les programmes soit le CPU pour les mêmes raisons que celles expliquées dans le scénario "2 minutes". Cela correspond également à l'hypothèse d'une "entrée commune", car il est peu probable que l'entrée provienne d'une seule source si, par exemple, différents dispositifs d'E/S la fournissent.

Par conséquent, la première hypothèse dans ce cas est que chaque programme est lié au CPU et écrit de telle sorte qu'il consomme au maximum la moitié des ressources du CPU dans le système.

Answer 2

Pour A, ce sont des programmes qui sont en compétition pour une ressource mutuellement exclusive.

Pour B, ce sont des programmes indépendants qui n'interagissent pas vraiment.

Pour C, qui est celui qui vous pose problème, il semble qu'ils aient tous deux le même travail à choisir. Par exemple, il y a une file d'attente de tâches à effectuer, les deux programmes sont capables d'effectuer ces tâches, et ils savent quelles tâches ont été effectuées. Donc, s'ils s'exécutent tous les deux en même temps (en supposant une machine à plusieurs cœurs, mais même dans ce cas, ce n'est pas nécessaire, l'important est qu'il n'y ait pas de goulot d'étranglement au niveau des ressources), ils effectuent le travail en deux fois moins de temps.

Answer 3

Ver Performances d'une application Java multithread pour une autre raison possible pour laquelle les processus peuvent s'exécuter plus rapidement lorsque vous en avez plus d'un.

Bien que j'admette que la file d'attente des tâches qui peuvent être exécutées simultanément est une raison beaucoup plus simple pour expliquer ce temps d'exécution réduit.