Check to see if the maximum number of speculative tasks are
already being executed currently.
@param tasks the set of tasks to test
@param type the type of task (MAP/REDUCE) that we are considering
@return has the cap been reached?
555585
private boolean atSpeculativeCap(TaskType type) {
     float numTasks = (type == TaskType.MAP) ?
       (float)(runningMapTasks - speculativeMapTasks) :
       (float)(runningReduceTasks - speculativeReduceTasks);
     if (numTasks == 0){
       return true; // avoid divide by zero
     }
     int speculativeTaskCount = type == TaskType.MAP ? speculativeMapTasks
         : speculativeReduceTasks;
     int totalSpeculativeTaskCount = type == TaskType.MAP ?
         totalSpeculativeMapTasks.get() : totalSpeculativeReduceTasks.get();
     //return true if totalSpecTask < max(10, 0.01 * total-slots,
     //                                   0.1 * total-running-tasks)

     if (speculativeTaskCount < MIN_SPEC_CAP) {
       return false; // at least one slow tracker's worth of slots(default=10)
     }
     ClusterStatus c = jobtracker.getClusterStatus(false);
     int numSlots = (type == TaskType.MAP ? c.getMaxMapTasks() : c.getMaxReduceTasks());
     if (speculativeTaskCount < numSlots * MIN_SLOTS_CAP) {
       return false;
     }
     // Check if the total CAP has been reached
     if (totalSpeculativeTaskCount >= numSlots * TOTAL_SPECULATIVECAP) {
       return true;
     }
     boolean atCap = (((speculativeTaskCount)/numTasks) >= speculativeCap);
     if (LOG.isDebugEnabled()) {
       LOG.debug("SpeculativeCap is "+speculativeCap+", specTasks/numTasks is " +
           ((speculativeTaskCount)/numTasks)+
           ", so atSpecCap() is returning "+atCap);
     }
     return atCap;
   }
593856
public static boolean isPopulatable(final Type type) {
        return !isWildcardType(type) && !isTypeVariable(type) && !isCollectionType(type) && !isParameterizedType(type);
    }
532760
function(tasks, callback) {

      var keys; var length; var i; var results; var kind;
      var updated_tasks = [];
      var is_object;
      var counter = 0;

      if (isArray(tasks)) {

        length = tasks.length;
        results = [];

      } else if (isObject(tasks)) {

        is_object = true;
        keys = ObjectKeys(tasks);
        length = keys.length;
        results = {};

      } else {
        return callback();
      }

      for (i=0; i<length; i++) {

        if (is_object) {
          updated_tasks.push({ k: keys[i], t: tasks[keys[i]] });
        } else {
          updated_tasks.push({ k: i, t: tasks[i] });
        }

      }

      updated_tasks.forEach(function(task_object) {

        task_object.t(function(err, result) {
          if (err) return callback(err);

          results[task_object.k] = result;

          counter++;
          if (counter == length) callback(null, results);
        });

      });

    }
942681
@SuppressWarnings("ReferenceEquality")
  private boolean hasVisitedType(TemplateType type) {
    for (TemplateType visitedType : visitedTypes) {
      if (visitedType == type) {
        return true;
      }
    }
    return false;
  }
1175589
public int getRunningTasks(String poolName, TaskType type) {
    Map<String, Integer> runningMap = (type == TaskType.MAP ?
                                       poolRunningMaps : poolRunningReduces);
    return (runningMap.containsKey(poolName) ?
            runningMap.get(poolName) : 0);
  }
1293708
boolean canBeSpeculated(long currentTime) {
    if (skipping || !isRunnable() || !isRunning() || 
        completes != 0 || isOnlyCommitPending() ||
        activeTasks.size() > MAX_TASK_EXECS) {
      if (isMapTask() ? job.shouldLogCannotspeculativeMaps() :
            job.shouldLogCannotspeculativeReduces()) {
           LOG.info("Task "+ getTIPId() + " cannot be speculated because of " 
               + "skipping = "+ skipping + " isRunnable() = "+ isRunnable() 
               + " isRunning() = "+ isRunning() + " completes = " + completes
               + " isOnlyCommitPending() = "+ isOnlyCommitPending()  
               + " activetask-size = "+ activeTasks.size() 
               + " MAX_TASK_EXECS = " + MAX_TASK_EXECS);
      }
      return false;
    }

    if (isSpeculativeForced()) {
      return true;
    }

    // no speculation for first few seconds
    if (currentTime - lastDispatchTime < speculativeLag) {
      if (isMapTask() ? job.shouldLogCannotspeculativeMaps() :
            job.shouldLogCannotspeculativeReduces()) {
           LOG.info("Task "+ getTIPId() + " cannot be speculated because of "
               + "no speculation for first few seconds");
      }
      return false;
    }

    // if the task is making progress fast enough to complete within
    // the acceptable duration allowed for each task - do not speculate
    if ((maxProgressRateForSpeculation > 0) &&
        (progressRate > maxProgressRateForSpeculation)) {
      if (isMapTask() ? job.shouldLogCannotspeculativeMaps() :
            job.shouldLogCannotspeculativeReduces()) {
           LOG.info("Task "+ getTIPId() +" cannot be speculated because "
               + "the task progress rate is fast enough to complete."
               + " maxProgressRateForSpeculation = " 
               + maxProgressRateForSpeculation
               + " and progressRate = " + progressRate);
      }
      return false;
    }

    if (isMapTask() ? job.shouldSpeculateAllRemainingMaps() :
                      job.shouldSpeculateAllRemainingReduces()) {
      if (LOG.isDebugEnabled()) {
        LOG.debug("Speculate " + getTIPId() +
            " because the job is almost finished");
      }
      return true;
    }
    if (useProcessingRateForSpeculation) {
      return canBeSpeculatedUsingProcessingRate(currentTime);
    } else {
      return canBeSpeculatedUsingProgressRate(currentTime);
    }
  }
946285
public static boolean isResolved(Type type) {
    if (type instanceof GenericArrayType) {
      return isResolved(((GenericArrayType) type).getGenericComponentType());
    }
    if (type instanceof ParameterizedType) {
      for (Type t : ((ParameterizedType) type).getActualTypeArguments()) {
        if (!isResolved(t)) {
          return false;
        }
      }
      return true;
    }
    return type instanceof Class;
  }
256968
protected void refreshTaskCountsAndWaitTime(TaskType type, long now) {
    TaskInProgress[] allTips = getTasks(type);
    int finishedTips = 0;
    int runningTips = 0;
    int runningTaskAttempts = 0;
    long totalWaitTime = 0;
    long jobStartTime = this.getStartTime();
    for (TaskInProgress tip : allTips) {
      if (tip.isComplete()) {
        finishedTips += 1;
      } else if(tip.isRunning()) {
        runningTaskAttempts += tip.getActiveTasks().size();
        runningTips += 1;
      }
      if (tip.getExecStartTime() > 0) {
        totalWaitTime += tip.getExecStartTime() - jobStartTime;
      } else {
        totalWaitTime += now - jobStartTime;
      }
    }
    if (TaskType.MAP == type) {
      totalMapWaitTime = totalWaitTime;
      runningMapTasks = runningTaskAttempts;
      neededMapTasks = numMapTasks - runningTips - finishedTips
          + neededSpeculativeMaps();
      pendingMapTasks = numMapTasks - runningTaskAttempts
          - failedMapTIPs - finishedMapTasks + speculativeMapTasks;
    } else {
      totalReduceWaitTime = totalWaitTime;
      runningReduceTasks = runningTaskAttempts;
      neededReduceTasks = numReduceTasks - runningTips - finishedTips
          + neededSpeculativeReduces();
      pendingReduceTasks = numReduceTasks - runningTaskAttempts
          - failedReduceTIPs - finishedReduceTasks + speculativeReduceTasks;
    }
  }
44915
public void setTasks(java.util.Collection<TaskListEntry> tasks) {
        if (tasks == null) {
            this.tasks = null;
            return;
        }

        this.tasks = new java.util.ArrayList<TaskListEntry>(tasks);
    }
473665
private boolean isRelated(Task task, List<Relation> list)
   {
      boolean result = false;
      for (Relation relation : list)
      {
         if (relation.getTargetTask().getUniqueID().intValue() == task.getUniqueID().intValue())
         {
            result = true;
            break;
         }
      }
      return result;
   }
412526
final int externalHelpComplete(CountedCompleter<?> task, int maxTasks) {
        WorkQueue[] ws; int wl;
        int r = ThreadLocalRandom.getProbe();
        return ((ws = workQueues) != null && (wl = ws.length) > 0) ?
            helpComplete(ws[(wl - 1) & r & SQMASK], task, maxTasks) : 0;
    }
106910
private void preemptTasks(int tasksToPreempt) {
    LOG.info("Start preempt " + tasksToPreempt + " for type " + type);
    long maxRunningTime = configManager.getPreemptedTaskMaxRunningTime();
    int rounds = configManager.getPreemptionRounds();
    while (tasksToPreempt > 0) {
      int preempted = preemptOneSession(tasksToPreempt, maxRunningTime);
      if (preempted == 0) {
        maxRunningTime *= 2;
        // Check for enough rounds or an overflow
        if (--rounds <= 0 || maxRunningTime <= 0) {
          LOG.warn("Cannot preempt enough " + type + " tasks " +
              " rounds " + configManager.getPreemptionRounds() +
              " maxRunningTime " + maxRunningTime +
              " tasks not preempted:" + tasksToPreempt);
          return;
        }
      }
      tasksToPreempt -= preempted;
    }
  }
1136436
function has(tasks, when) {
  if (!tasks) {
    return false;
  }
  if (!when) {
    if (tasks.length) {
      return true;
    }
    return false;
  }
  return !!utils.classify(tasks)[when].length;
}
1254758
private void updateTotalTaskCapacity(TaskTrackerStatus status) {
    int mapSlots = taskScheduler.getMaxSlots(status, TaskType.MAP);
    String trackerName = status.getTrackerName();
    Integer oldMapSlots = trackerNameToMapSlots.get(trackerName);
    if (oldMapSlots == null) {
      oldMapSlots = 0;
    }
    int delta = mapSlots - oldMapSlots;

    if (delta != 0) {
      totalMapTaskCapacity += delta;
      trackerNameToMapSlots.put(trackerName, mapSlots);

      LOG.info("Changing map slot count due to " + trackerName + " from " +
               oldMapSlots + " to " + mapSlots + ", totalMap = " + totalMapTaskCapacity);
    }

    int reduceSlots = taskScheduler.getMaxSlots(status, TaskType.REDUCE);
    Integer oldReduceSlots = trackerNameToReduceSlots.get(trackerName);
    if (oldReduceSlots == null) {
      oldReduceSlots = 0;
    }

    delta = reduceSlots - oldReduceSlots;

    if (delta != 0) {
      totalReduceTaskCapacity += delta;
      trackerNameToReduceSlots.put(trackerName, reduceSlots);

      LOG.info("Changing reduce slot count due to " + trackerName + " from " +
               oldReduceSlots + " to " + reduceSlots +
               ", totalReduce = " + totalReduceTaskCapacity);
    }
  }
1046040
@Service
    public Map<String, Integer> getTaskQueueSizes(List<String> taskTypes) {
        return executionService.getTaskQueueSizes(taskTypes);
    }
432590
public synchronized boolean completedTask(TaskInProgress tip,
                                            TaskStatus status)
  {
    TaskAttemptID taskid = status.getTaskID();
    int oldNumAttempts = tip.getActiveTasks().size();
    final JobTrackerInstrumentation metrics = jobtracker.getInstrumentation();

    // Metering
    meterTaskAttempt(tip, status);

    // Sanity check: is the TIP already complete?
    // It _is_ safe to not decrement running{Map|Reduce}Tasks and
    // finished{Map|Reduce}Tasks variables here because one and only
    // one task-attempt of a TIP gets to completedTask. This is because
    // the TaskCommitThread in the JobTracker marks other, completed,
    // speculative tasks as _complete_.
    if (tip.isComplete()) {
      // Mark this task as KILLED
      tip.alreadyCompletedTask(taskid);

      // Let the JobTracker cleanup this taskid if the job isn't running
      if (this.status.getRunState() != JobStatus.RUNNING) {
        jobtracker.markCompletedTaskAttempt(status.getTaskTracker(), taskid);
      }
      return false;
    }


    LOG.info("Task '" + taskid + "' has completed " + tip.getTIPId() +
             " successfully.");

    // Mark the TIP as complete
    tip.completed(taskid);
    resourceEstimator.updateWithCompletedTask(status, tip);

    // Update jobhistory
    TaskTrackerStatus ttStatus =
      this.jobtracker.getTaskTrackerStatus(status.getTaskTracker());
    String trackerHostname = jobtracker.getNode(ttStatus.getHost()).toString();
    String taskType = getTaskType(tip);
    if (status.getIsMap()){
      JobHistory.MapAttempt.logStarted(status.getTaskID(), status.getStartTime(),
                                       status.getTaskTracker(),
                                       ttStatus.getHttpPort(),
                                       taskType);
      JobHistory.MapAttempt.logFinished(status.getTaskID(), status.getFinishTime(),
                                        trackerHostname, taskType,
                                        status.getStateString(),
                                        status.getCounters());
    }else{
      JobHistory.ReduceAttempt.logStarted( status.getTaskID(), status.getStartTime(),
                                          status.getTaskTracker(),
                                          ttStatus.getHttpPort(),
                                          taskType);
      JobHistory.ReduceAttempt.logFinished(status.getTaskID(), status.getShuffleFinishTime(),
                                           status.getSortFinishTime(), status.getFinishTime(),
                                           trackerHostname,
                                           taskType,
                                           status.getStateString(),
                                           status.getCounters());
    }
    JobHistory.Task.logFinished(tip.getTIPId(),
                                taskType,
                                tip.getExecFinishTime(),
                                status.getCounters());

    int newNumAttempts = tip.getActiveTasks().size();
    if (tip.isJobSetupTask()) {
      // setup task has finished. kill the extra setup tip
      killSetupTip(!tip.isMapTask());
      setupComplete();
    } else if (tip.isJobCleanupTask()) {
      // cleanup task has finished. Kill the extra cleanup tip
      if (tip.isMapTask()) {
        // kill the reduce tip
        cleanup[1].kill();
      } else {
        cleanup[0].kill();
      }

      //
      // The Job is done
      // if the job is failed, then mark the job failed.
      if (jobFailed) {
        terminateJob(JobStatus.FAILED);
      }
      // if the job is killed, then mark the job killed.
      if (jobKilled) {
        terminateJob(JobStatus.KILLED);
      }
      else {
        jobComplete();
      }
      // The job has been killed/failed/successful
      // JobTracker should cleanup this task
      jobtracker.markCompletedTaskAttempt(status.getTaskTracker(), taskid);
    } else if (tip.isMapTask()) {
      // check if this was a sepculative task
      if (oldNumAttempts > 1) {
        speculativeMapTasks -= (oldNumAttempts - newNumAttempts);
        if (!garbageCollected) {
          totalSpeculativeMapTasks.addAndGet(newNumAttempts - oldNumAttempts);
        }
      }
      if (tip.isSpeculativeAttempt(taskid)) {
        metrics.speculativeSucceededMap(taskid,
            tip.isUsingProcessingRateForSpeculation());
      }
      int level = getLocalityLevel(tip, ttStatus);
      long inputBytes = tip.getCounters()
                .getGroup("org.apache.hadoop.mapred.Task$Counter")
                .getCounter("Map input bytes");
      switch (level) {
      case 0: jobCounters.incrCounter(Counter.LOCAL_MAP_INPUT_BYTES,
                inputBytes);
              metrics.addLocalMapInputBytes(inputBytes);
              break;
      case 1: jobCounters.incrCounter(Counter.RACK_MAP_INPUT_BYTES,
                inputBytes);
              metrics.addRackMapInputBytes(inputBytes);
              break;
      default:metrics.addMapInputBytes(inputBytes);
              break;
      }
      finishedMapTasks += 1;
      metrics.completeMap(taskid);
      if (!garbageCollected) {
        if (!tip.isJobSetupTask() && hasSpeculativeMaps) {
          updateTaskTrackerStats(tip,ttStatus,trackerMapStats,mapTaskStats);
        }
      }
      // remove the completed map from the resp running caches
      retireMap(tip);
      if ((finishedMapTasks + failedMapTIPs) == (numMapTasks)) {
        this.status.setMapProgress(1.0f);
      }
    } else {
      if (oldNumAttempts > 1) {
        speculativeReduceTasks -= (oldNumAttempts - newNumAttempts);
        if (!garbageCollected) {
          totalSpeculativeReduceTasks.addAndGet(newNumAttempts - oldNumAttempts);
        }
      }
      if (tip.isSpeculativeAttempt(taskid)) {
        metrics.speculativeSucceededReduce(taskid,
            tip.isUsingProcessingRateForSpeculation());
      }
      finishedReduceTasks += 1;
      metrics.completeReduce(taskid);
      if (!garbageCollected) {
        if (!tip.isJobSetupTask() && hasSpeculativeReduces) {
          updateTaskTrackerStats(tip,ttStatus,trackerReduceStats,reduceTaskStats);
        }
      }
      // remove the completed reduces from the running reducers set
      retireReduce(tip);
      if ((finishedReduceTasks + failedReduceTIPs) == (numReduceTasks)) {
        this.status.setReduceProgress(1.0f);
      }
    }

    // is job complete?
    if (!jobSetupCleanupNeeded && canLaunchJobCleanupTask()) {
      jobComplete();
    }

    return true;
  }
470767
@GuardedBy("evictionLock")
    void runTasks(Task[] tasks, int maxTaskIndex) {
        for (int i = 0; i <= maxTaskIndex; i++) {
            runTasksInChain(tasks[i]);
        }
    }