5 processus de planification des tâches de la CPU

Question.

Il y a 5 CPU et N nombre de tâches dans la file. Vous devez utiliser un nombre minimal de processeurs pour traiter les tâches.

Une tâche est au format [heure d’arrivée, heure du traitement de la tâche].

Remarque:

• vérifier si quatre points sont sur le même plan, uniquement en utilisant des distances (vérifier la colinéarité)
• std :: ratio puissance d’un std :: ratio au moment de la compilation?
• Existe-t-il un moyen d’implémenter l’analogue du ‘séparateur’.join () de Python en C ++?
• calculer la sum des diagonales dans une masortingce
• Existe-t-il une implémentation de tas C ++ MinMax?

1. Vous ne pouvez utiliser que 5 CPU au maximum. Si cela n’est pas possible dans 5 UC, imprimez -1.

2. Le temps de traitement de la tâche ne doit pas être supérieur à 10, c’est-à-dire (temps d’attente dans la queue + temps de traitement de la tâche) <= 10.

3. Si le traitement de la tâche en cours nécessite plus de 10 secondes dans la CPU actuelle, vous pouvez passer à une autre CPU et vérifier s’il est possible de traiter la tâche dans un délai <= 10.

4. S’il n’est pas possible de traiter la tâche dans <= 10 ou au plus 5 CPU, imprimez -1.

Contraintes.

0 <= heure d'arrivée <= 500

1 <= heure de traitement de la tâche <= 10

0 <= N <= 500

Vous ne pouvez utiliser que la bibliothèque iostream. Aucune STL n’est autorisée.

Temps: 3 secondes pour les cas de test T

Par exemple:-

Consortingbution

3

1 6

2 7

3 1

Sortie

2

Explication:

3 – N

1 6 – la première tâche arrive dans CPU0 à l’heure 1 et part à l’heure 7 (1 + 6). CPU utilisés = 1.

2 7 – la deuxième tâche arrive dans CPU0 à l’heure 2 et attend 5 secondes dans la queue; le temps de traitement global est donc 5 + 7> 10. Elle est donc déplacée vers CPU1. CPU utilisées = 2.

3 1 – la troisième tâche arrive. il peut aller à CPU0 ou CPU1, le temps de traitement étant respectivement de 5 ( (7-3) + 1 ) et de 7 ( (9-3) + 1 ) secondes. CPU utilisées = 2.

CPU1 est un nouveau processeur. Donc, la tâche 2 sera complétée en 9 (2 + 7) secondes sans aucun délai d’attente dans la queue.

Mon approche:

1. Initialement, cela a été pensé comme une variante du minimum train-platform problem . Mais c’était faux.

2. J’ai essayé une approche greedy , mais cela a donné -1 pour des solutions valables.

CODE:

 #include  using namespace std; #define MAXN 500 int N; int arr[MAXN]; int len[MAXN]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>N; for(int i=0;i> arr[i] >> len[i]; } int exit_time_of_task_in_CPUs[5]={0}; int cpus_used_so_far=1; int min_processing_time; int min_processing_time_idx; for(int task_idx=0; task_idx<N; task_idx++){ min_processing_time = INT_MAX; min_processing_time_idx = -1; // finds the CPU which can process task in minimum time. for(int i=0; i<cpus_used_so_far ; i++){ int processing_time = 0; int time_in_queue = exit_time_of_task_in_CPUs[i] - arr[task_idx]; if( time_in_queue < 0 ) // ie processor is free before arrival time_in_queue = 0; processing_time = time_in_queue + len[task_idx]; if( processing_time <=10){ if(processing_time < min_processing_time){ min_processing_time = processing_time; min_processing_time_idx = i; } } } if( min_processing_time_idx == -1){ // No Existing CPU can solve this task. // Check if spawning a new CPU is possible. if (cpus_used_so_far+1 <= 5){ //spawn a new CPU cpus_used_so_far++; int new_cpu_index = cpus_used_so_far - 1; // last CPU, converting to zero index exit_time_of_task_in_CPUs[new_cpu_index] = arr[task_idx] + len[task_idx] ; }else{ cpus_used_so_far = -1; // not possible to spawn a new CPU, break; //and you can't process with existing CPUs } }else{ // Possible to handle with existing CPUs exit_time_of_task_in_CPUs[min_processing_time_idx] = arr[task_idx] + min_processing_time; } } cout << cpus_used_so_far <<endl; } 

3. Essayer l’approche de memoization .

L’approche récursive résout le problème, mais le délai est dépassé. (Pas étonnant)

Quel est le moyen possible de sauvegarder l’état de int , int , int[] ?

Je suis également ouvert à une solution itérative pour la même chose.

CODE:

 #include  using namespace std; #define MAXN 500 int min_cpus_used = 6; int N; int arr[MAXN]; int len[MAXN]; void recurse( int task_idx, int cpus_used_so_far, int exit_time_of_task_in_CPUs[] ){ if( task_idx == N-1){ min_cpus_used = min( min_cpus_used, cpus_used_so_far); return ; } if( cpus_used_so_far >= min_cpus_used ){ return ; //optimization } for(int i=0; i<cpus_used_so_far ; i++){ int processing_time = 0; int time_in_queue = exit_time_of_task_in_CPUs[i] - arr[task_idx]; if( time_in_queue < 0 ) // ie processor is free before arrival time_in_queue = 0; processing_time = time_in_queue + len[task_idx]; // try with existing CPUs if( processing_time <=10){ int prev = exit_time_of_task_in_CPUs[i]; exit_time_of_task_in_CPUs[i] = arr[task_idx] + processing_time; recurse( task_idx + 1 , cpus_used_so_far , exit_time_of_task_in_CPUs ); // can we optimize passing array exit_time_of_task_in_CPUs[i] = prev; } // try with new CPU if (cpus_used_so_far+1 >N; for(int i=0;i> arr[i] >> len[i]; } int exit_time_of_task_in_CPUs[5]={0}; recurse(0, 1, exit_time_of_task_in_CPUs); if(min_cpus_used==6){ cout<< -1 <<endl; }else{ cout << min_cpus_used <<endl; } } 

Aidez-moi à réfléchir à l’optimisation de cette solution.

PS: Cela n’a rien à voir avec la planification du processeur.

• Algorithme d’interpolation bi-cubique pour la mise à l’échelle de l’image
• Pourquoi écrivons-nous lo + (hi-lo) / 2 en recherche binary?
• trouver la médiane dans une fenêtre mobile de taille fixe le long d’une longue séquence de données
• Complexité du parcours dans l’ordre dans un arbre de recherche binary (à l’aide d’iterators)?
• for_each qui donne deux (ou n) éléments adjacents

 Task start: 0 0 0 0 0 Task length: 1 5 2 9 3 Assigned CPU: ABBAB