Trier le calendrier d'accès des ressources pour plusieurs threads afin que le nombre de conflits d'écriture soit minimisé

Approche

1. à partir de la liste de ressources de chaque thread Nous créons une liste fusionnée, appelée compteurResourcelist code> qui stocke le code> ordre décroissant des comptes. Cela prendra l'heure O (RT * Log (RT)). Le pourquoi? Em> de cela est expliqué dans l'échantillon exécuté ci-dessous. Également dans la même itération, nous créons un haschmap afin que nous puissions trouver dans O (1) de temps sur lequel la liste des threads de cet ID de ressource doit être placée (en fonction de l'idée de Index inversé pour ceux qui peuvent raconter). LI>
2. Ensuite, nous créons une matrice - appelée tritedlistMatrix code> - de t lignes et r colonnes. Dans cette matrice, nous commençons par placer les identifiants de ressources à partir de compteurResourcelist code> dans la ligne de threads qui contenait initialement cet ID de ressource maximum survenant. De cette façon, les ID de ressources échappent dans l'ordre de la plupart se produisant au moins se produisant em>. Li>
3. Pour aider à l'insertion des ressources ressources, nous créons également un int [t] freecolumncount code> qui empêche le nombre de colonnes totales gratuites pour chaque thread. Étant donné que le thread avec des emplacements gratuits moindes a moins de capacité à déplacer l'ID de ressource en cas d'un conflit, une pièce d'identité de ressources sera d'abord remplie dans la ligne qui contient des emplacements maux pour les fils contenant cet identifiant de ressources. li>
4. à partir de la colonne de la 0ème colonne du premier fil contenant l'ID de ressource survenant le plus élevé, nous choisissons l'emplacement de l'identifiant suivant à mettre à l'aide des formules rangées = getRowforresource (ID) dans le hashmap et la colonne = ( Colonne + 1)% R code>. Si la colonne résultante d'une rangée est occupée, nous prenons la prochaine valeur de colonne inoccupée en itérant à l'aide de la même formule de la valeur de colonne, sans changer la ligne. Par conséquent - Les colonnes sont soumises à une enveloppe et les lignes sont déterminées à partir du hashmap de manière à ce qu'un ID de ressource passe dans la liste correcte et à la localisation la moins conflictuelle forte>. Li>.
5. Une fois cette matrice complètement peuplée, commencez par une rangée de la section 0 et attribuez les lignes à chaque fil comme leur nouvelle liste de ressources em>. li>. ol>

   ATTN: strong> J'ai mentionné par intermittence la complexité de quelques étapes, mais mettra à jour avec la complexité globale du temps d'exécution. Pour le moment, j'essaie de trouver un algorithme correct. P>

   un échantillon exécuté h2>

hypothèses et définitions initiales: p>

• Nombre de threads = t fort>, à partir du fil 0 au t-1 li>
• Nombre de ressources pour chaque thread = r strong> li>
• Total des ressources pour préparer la liste des ressources pour les threads sera > = r strong> li> ul>

  Commençons par un cas de T = 4. T0 = {4, 3, 5}, T1 = {1, 2, 6}, T2 = {3, 1, 2}, T4 = { 2, 7, 1}. Maintenant, je sais que cette liste n'a pas déjà de conflit. Il devrait y avoir une étape de prétraitement qui découvre s'il devrait y avoir un re-arrangement effectué en premier lieu. Comme si les listes ont déjà le minimum de conflits possibles ou s'il n'y a pas de conflit, les listes doivent être renvoyées comme elles sont. Néanmoins, voyons le pseudocode en action. P>

  Nous lisons d'abord toutes les ressources dans toutes les listes et mettons-les dans des godets individuels d'ID de ressources. Utilisation de compter le tri , ce sera une étape linéaire prise O (tr + constante ) fort> temps. Cependant, comme cela va simplement donner un compte d'identité de ressources, nous devrons utiliser davantage Fusionner le tri trier les identifiants dans l'ordre de décroissance. Cette étape prendra O ((RT) Journal (RT)) Strong>. Le résultat sera une liste ou des identifiants triés dans l'ordre décroissant d'occurrence - P>

  compteurResourcelist code> = , , , blockQuote>

  Au cours de la même itération, nous créons également le tableau HASHMAP et le tableau code> freecolumncount CODE>. P>

  Suivant, nous créons le sortidlistMatrix code> qui est peuplé à partir de rangée = premier thread à contenir de la ressource-id maximum survenant em> (en appelant getRowforresource (ID)) em> strong>, colonne = 0 em>. La matrice sera initialement vide puis renseignée comme suit: P>

  Initially:
  {_, _, _}
  {_, _, _}
  {_, _, _}
  {_, _, _}
  
  Taking 1st element '1' at (1, 0):
  {_, _, _}
  {1, _, _}
  {_, _, _}
  {_, _, _}  
  
  Taking 2nd element '1' at (2, 1):
  {_, _, _}
  {1, _, _}
  {_, 1, _}
  {_, _, _} 
  
  Taking 3rd element '1' at (3, 2):
  {_, _, _}
  {1, _, _}
  {_, 1, _}
  {_, _, 1}
  
  Taking 4th element '2' at (1, 1) as (1, 0) is already occupied:
  {_, _, _}
  {1, 2, _}
  {_, 1, _}
  {_, _, 1}
  
  Taking 5th element '2' at (2, 2):
  {_, _, _}
  {1, 2, _}
  {_, 1, 2}
  {_, _, 1}
  
  Taking 6th element '2' at (3, 0):
  {_, _, _}
  {1, 2, _}
  {_, 1, 2}
  {2, _, 1}
  
  Taking 7th element '3' at (0, 0) because row 2 has least free slots:
  {_, _, _}
  {1, 2, _}
  {3, 1, 2}
  {2, _, 1} 
  
  Taking 8th element '3' at (0, 1):
  {_, 3, _}
  {1, 2, _}
  {3, 1, 2}
  {2, _, 1} 
  
  Taking 9th element '4' at (0, 2):
  {_, 3, 4}
  {1, 2, _}
  {3, 1, 2}
  {2, _, 1}
  
  Taking 10th element '5' at (0, 0):
  {5, 3, 4}
  {1, 2, _}
  {3, 1, 2}
  {2, _, 1}
  
  Taking 11th element '6' at (1, 2):
  {5, 3, 4}
  {1, 2, 6}
  {3, 1, 2}
  {2, _, 1}
  
  Taking 12th element '7' at (3, 1):
  {5, 3, 4}
  {1, 2, 6}
  {3, 1, 2}
  {2, 7, 1}
  

Je pense que la question est de demander "Pouvons-nous trier les listes pour réduire les conflits."

Je pense qu'une solution optimale est la NP complète, mais je rechercherais le nombre de surveurs dans l'ensemble pour chaque ressource.

Étape 1

La ressource la plus couramment utilisée est la plus difficile à planifier. Ainsi, je placerais dans chacun des threads cette ressource en position 1, 2, 3, 4, ... jusqu'à ce que le conflit se produise (ce qui peut être inévitable) par exemple. 1,2,3,4, ..., n, 1, 2, ....

Ce sont les "grosses pierres". Ceux-ci doivent être placés en premier.

Étape 2

La ressource suivante la plus couramment utilisée devrait alors être essayée. Cela devrait identifier les machines à sous (1 => N) ont été utilisées récemment et recherchées à travers cette liste pour une tranche à la fois non allouée et non utilisée récemment.

Quelle que soit la fente choisie, il se déplace vers le haut de la file d'attente récemment utilisée à éviter pendant un moment.

Ceci favorise la distribution de la ressource, mais permet des doublons. Ces doublons deviendront récemment utilisés et non favorisés pour la planification jusqu'à ce qu'aucun choix valide ne soit disponible.

Enfin

L'étape 2 est répétée pour chacune des ressources dans l'ordre de leurs occurrences.