OPERATING SYSTEMS

• Processor (CPU)


  Performs calculations and executes programs
• Program (job)


  Inactive unit, e.g., file stored on a disk. Unit of work submitted by the user
• Process (task)


  Active entity that requires resources (processor, special registers, etc.) to perform function. Executable program single instance
• Thread


  Portion of a process that runs independently
• Multithreading


  Allows applications to manage a separate process with several threads of control
• Multiprogramming


  Processor allocated to each job or each process for a time period, then deallocated at appropriate moment
• Interrupt


  Call for help that activates higher-priority program
• Context switch


  Saving job processing information when interrupted
• Completed jobs


  Finished or terminated
• Single processor


  • May be shared by several jobs (processes), requires scheduling policy and scheduling algorithm
• Multi-core CPU


  More than one processor (core) located on computer chip, resolves leakage and heat problems, allows multiple calculations to occur simultaneously
• Processor Manager


  Composite of two submanagers: Job Scheduler and Process Scheduler
• Job Scheduler


  Higher-level scheduler responsible for job initiation based on certain criteria
• Process Scheduler


  Lower-level scheduler responsible for determining execution steps based on certain criteria
• Job Scheduler functions


  1. Selects incoming job from queue

  2. Places in process queue

  3. Decides on job initiation criteria
• Process Scheduler functions


  1. Determines job to get CPU resource

  2. Decides interrupt processing

  3. Determines queues for job movement during execution

  4. Recognizes job conclusion

  
• Process Scheduler


  • Exploits common computer program traits of alternating CPU and I/O cycles

  
• Middle-level scheduler found in highly interactive environments handles overloading by removing active jobs from memory and reducing degree of multiprogramming
• Job and process states

  • HOLD
  • READY
  • WAITING
  • RUNNING
  • FINISHED
• Job and process state transitions

  1. User submits job

  2. Job accepted and placed on HOLD queue

  3. Job state changes to READY

  4. Job state changes to RUNNING

  5. Job state changes to WAITING

  6. Job state changes to FINISHED

  
• Thread states


  • READY
  • RUNNING
  • WAITING
  • DELAYED
  • BLOCKED
• Thread state transitions


  1. Application creates a thread and places it in READY queue

  2. READY to RUNNING: Process Scheduler assigns it to a processor

  3. RUNNING to WAITING: when dependent on an outside event

  4. WAITING to READY: outside event occurs or previous thread finishes

  5. RUNNING to DELAYED: application delays thread processing

  6. DELAYED to READY: prescribed time elapsed

  7. RUNNING to BLOCKED: I/O request issued

  8. BLOCKED to RUNNING: I/O completed

  9. RUNNING to FINISHED: exit or termination
• Process Control Block (PCB)

  Data structure for each process in the system
• Thread Control Block (TCB)

  Data structure for each thread
• Control blocks and queuing

  1. Job PCB created when Job Scheduler accepts job, updated as job executes, linked to form queues

  2. PCBs or TCBs require orderly management of queues determined by process scheduling policies and algorithms
• Scheduling policies


  • Resolve system limitations of finite resources, resources that cannot be shared, and resources requiring operator intervention
• Good process scheduling policy criteria

  • Maximize throughput
  • Minimize response time
  • Minimize turnaround time
  • Minimize waiting time
  • Maximize CPU efficiency
  • Ensure fairness for all jobs

  
• Problem of job claiming CPU for very long time before I/O request issued, building up READY queue and emptying I/O queues, creating unacceptable system imbalance
• Corrective measure: Interrupt


  Used by Process Scheduler upon predetermined expiration of time slice to suspend current job activity and reschedule job into READY queue
• Preemptive scheduling


  Used in time-sharing environments, interrupts job processing and transfers CPU to another job
• Nonpreemptive scheduling


  Functions without external interrupts
• Scheduling algorithms


  • First-come, first-served (FCFS)
  • Shortest job next (SJN)
  • Priority scheduling
  • Shortest remaining time (SRT)
  • Round robin
  • Multiple-level queues
  • Earliest deadline first (EDF)
• First-come, first-served (FCFS)


  Nonpreemptive scheduling algorithm

  
• Interrupts


  • Cause system imbalance
  • Corrective measure is to interrupt
• Interrupt handling


  1. Interrupt type described and stored

  2. Interrupted process state saved

  3. Interrupt processed

  4. Processor resumes normal operation
• Preemptive scheduling


  Interrupts job processing and transfers CPU to another job
• Scheduling algorithms


  • First-come, first-served (FCFS)
  • Shortest job next (SJN)
  • Priority scheduling
  • Shortest remaining time (SRT)
  • Round robin
  • Multiple-level queues
  • Earliest deadline first (EDF)
• First-come, first-served (FCFS)


  • Nonpreemptive
  • Job handled based on arrival time
  • Simple algorithm implementation
  • Good for batch systems
  • Unacceptable in interactive systems
  • Average turnaround time varies; seldom minimized

  
• Shortest Job Next (SJN)

  • Nonpreemptive
  • Job handled based on length of CPU cycle time
  • Easy implementation in batch environment
  • Does not work well in interactive systems
  • Optimal algorithm if all jobs available at same time and CPU estimates accurate
• Priority scheduling


  • Nonpreemptive
  • Preferential treatment for important jobs
  • Processor Manager uses different methods to assign priorities