CSDS 338 HW1

hw1.ts

import {
  MAX_BATCH, MAX_BURST,
  MAX_DELAY, MIN_BURST,
  MIN_DELAY, MIN_PRIORITY,
  TASKS_COUNT, MAX_PRIORITY,
  Stopwatch, Task,
  randomInt, TaskAggregate
} from './util'

export default async function () {
  const appTimer = new Stopwatch('app')
  appTimer.start()
  console.clear()
  const queue: Task[] = [],
    history: Task[] = [],
    aggregates: TaskAggregate[] = []
  // populate queue with tasks
  queue.push(new Task(0, MIN_DELAY + 1000))
  // simulate later-arriving tasks
  let n = 0
  while (n++ < TASKS_COUNT) {
    let i = 0, batch = randomInt(1, MAX_BATCH)
    let delay = randomInt(MIN_DELAY, MAX_DELAY)
    while (i++ < batch) {
      let priority = randomInt(MIN_PRIORITY, MAX_PRIORITY)
      let burst = randomInt(MIN_BURST, MAX_BURST)
      setTimeout(() => {
        queue.push(new Task(priority, burst))
      }, delay)
    }
  }
  while (queue.length) {
    console.log(queue.length, 'remaining')
    // sort the queue by ascending niceness
    queue.sort((a, b) => (a.niceness - b.niceness) * 2 + (a.id - b.id))
    const task = queue.shift()!
    history.push(task)
    await task.execute()
    console.clear()
  }
  const totalRuntime = appTimer.stop()
  for (const task of history) {
    if (!aggregates[task.niceness]) {
      const agg = new TaskAggregate()
      agg.niceness = task.niceness
      agg.tasks = [task]
      aggregates[task.niceness] = agg
    } else {
      aggregates[task.niceness].tasks.push(task)
    }
  }
  console.table(aggregates.map(e => e.stats))
  console.log('Completed in', totalRuntime, 'ms')
  console.log('# tasks:', history.length)
  console.log('priorities: min', MIN_PRIORITY, 'max', MAX_PRIORITY)
  console.log('batch: max', MAX_BATCH)
  const totalBurst = history.map(e => e.duration).reduce((p, n) => p + n)
  console.log(
    'burst: min', MIN_BURST, 'max', MAX_BURST, 'avg',
    (totalBurst / history.length).toFixed(0)
  )
}

interrupt.ts

import {
  MAX_BATCH, MAX_BURST,
  MAX_DELAY, MIN_BURST,
  MIN_DELAY, MIN_PRIORITY,
  TASKS_COUNT, SWITCH_PENALTY,
  MAX_PRIORITY,
  Stopwatch, Task,
  useEventQueue,
  randomInt, TaskAggregate
} from './util'

export default async function () {
  console.clear()
  const {
    queue, // Task[]

    // emitter.emit() to dispatch events
    // emitter.on() to listen to events
    emitter,

    // emits the 'push' event
    push
  } = useEventQueue()
  const taskTimer = new Stopwatch('task'),
    appTimer = new Stopwatch('app'),
    penalties: number[] = []
  emitter.setMaxListeners(TASKS_COUNT * MAX_BATCH + 1)
  Task.registerEmitter(emitter)

  const history: Task[] = [],
    aggregates: TaskAggregate[] = []
  queue.push(new Task(0, MIN_DELAY + 1000))
  // simulate later-arriving tasks
  let n = 0
  while (n++ < TASKS_COUNT) {
    let i = 0, batch = randomInt(1, MAX_BATCH)
    let delay = randomInt(MIN_DELAY, MAX_DELAY)
    while (i++ < batch) {
      let priority = randomInt(MIN_PRIORITY, MAX_PRIORITY)
      let burst = randomInt(MIN_BURST, MAX_BURST)
      setTimeout(() => {
        push(new Task(priority, burst))
      }, delay)
    }
  }
  appTimer.start()
  while (queue.length) {
    console.log(queue.length, 'tasks remaining')
    console.log('wasted', penalties.reduce((p, n) => p + n, 0) * SWITCH_PENALTY)
    // sort the queue by ascending niceness and pushed order
    queue.sort((a, b) => (a.niceness - b.niceness) * 2 + (a.id - b.id))
    const task = queue.shift()!
    history.push(task)
    taskTimer.start()
    await task.execute().catch(async () => {
      // log how much time the task got,
      // then push it back to the queue with the new duration
      const timeElapsed = taskTimer.stop()
      if (task.duration - timeElapsed > 0) {
        if (penalties[task.niceness]) {
          penalties[task.niceness]++
        } else {
          penalties[task.niceness] = 1
        }
        const _task = new Task(task.niceness, task.duration, timeElapsed, task.responseTime)
        queue.push(_task)
        history.push(_task)
        await new Promise(resolve => {
          setTimeout(resolve, SWITCH_PENALTY)
        })
      }
    })
    console.clear()
  }
  const totalRuntime = appTimer.stop()
  for (const task of history) {
    const key = task.niceness
    if (!aggregates[key]) {
      const agg = new TaskAggregate()
      agg.niceness = task.niceness
      agg.tasks = [task]
      agg.wasted = penalties[task.niceness]
      aggregates[key] = agg
    } else {
      const agg = aggregates[key]
      if (agg) {
        agg.tasks.push(task)
        aggregates[key] = agg
      }
    }
  }
  console.table(aggregates.map(e => e.stats))
  // console.table(penalties)
  console.log('Completed in', totalRuntime, 'ms')
  console.log('# tasks:', history.length)
  console.log('priorities: min', MIN_PRIORITY, 'max', MAX_PRIORITY)
  console.log('batch: max', MAX_BATCH)
  const totalBurst = history.map(e => e.duration).reduce((p, n) => p + n)
  const wasted = penalties.reduce((p, n) => p + n, 0) * SWITCH_PENALTY
  console.log(
    'burst: min', MIN_BURST, 'max', MAX_BURST, 'avg',
    (totalBurst / history.length).toFixed(0)
  )
  console.log('context switch penalty:', SWITCH_PENALTY)
  console.log('wasted:', wasted)
  console.log('context switch/burst ratio:', (wasted / totalBurst * 100).toFixed(2), '%')
}

main.ts

import queue from './hw1'
import interrupt from './interrupt'

function main () {
    // run one of these, not both!
    queue()
    // interrupt()
}

main()

util.ts

import { EventEmitter } from 'events'

export class Emitter extends EventEmitter { }

export function useEventQueue () {
    const queue: Task[] = [],
        emitter = new Emitter()
    emitter.setMaxListeners(TASKS_COUNT + 1)
    function push (task: Task) {
        // console.log('> task id', task.id, 'created')
        queue.push(task)
        emitter.emit('push', task)
    }
    return {
        queue, emitter, push
    }
}

export class Task {
    niceness = 0
    duration = 0
    interruptedAt = 0
    id = 0
    responseTime = 0
    handle
    static emitter: Emitter
    static _id = 0
    constructor(priority: number, duration: number, interruptedAt?: number, responseTime?: number) {
        if (responseTime) this.responseTime = responseTime
        this.handle = setInterval(() => { this.responseTime++ }, 1)
        this.id = Task._id++
        this.niceness = priority
        this.duration = duration
        if (interruptedAt) this.interruptedAt = interruptedAt
    }
    execute () {
        clearInterval(this.handle)
        // console.log('+ task id', this.id, 'started')
        return new Promise<void>((resolve, reject) => {
            const handle = setTimeout(resolve, this.duration - this.interruptedAt)
            if (Task.emitter) {
                Task.emitter.once('push', (task: Task) => {
                    if (task.niceness < this.niceness) {
                        clearTimeout(handle)
                        reject()
                    }
                })
            }

        })
    }
    static registerEmitter (emitter: Emitter) {
        Task.emitter = emitter
    }
}

export class TaskAggregate {
    tasks: Task[] = []
    niceness = 0
    wasted = 0
    get avgResponseTime () {
        const totalRes = this.tasks.map(e => e.responseTime).reduce((p, n) => p + n)
        return totalRes / this.tasks.length
    }
    get stats () {
        const avgBurst = (this.tasks
            .map(e => e.duration)
            .reduce((p, n) => p + n)
            / this.tasks.length).toFixed(0)
        return {
            niceness: this.niceness,
            tasks: this.tasks.length,
            avgBurst,
            avgResponseTime: this.avgResponseTime.toFixed(0),
            wasted: (this.wasted || 0) * SWITCH_PENALTY
        }
    }
}

export class Stopwatch {
    time = 0
    handle: any = null
    name = ''
    constructor(name: string) {
        this.name = name
    }
    start () {
        this.time = 0
        this.handle = setInterval(() => { this.time++ }, 1)
    }
    stop () {
        const elapsed = this.time
        clearInterval(this.handle)
        this.time = 0
        return elapsed
    }
}



export const MIN_DELAY = 1
export const MIN_PRIORITY = 0
export const MAX_PRIORITY = 4
export const MIN_BURST = 10
export const MAX_BURST = 50
export const SWITCH_PENALTY = 10
export const TASKS_COUNT = 1200
export const MAX_BATCH = 3
export const MAX_DELAY = 30000

export function randomInt (min: number, max: number) {
    min = Math.ceil(min)
    max = Math.floor(max)
    return Math.floor(Math.random() * (max - min) + min)
}