PROCESSOR MANAGEMENT

A process is a single instance of an executable program."

An interrupt is a hardware signal that suspends execution of a program and calls the interrupt handler."

• identifies the job
• indicates its current status (HOLDING, READY, RUNNING or WAITING)
• stores the current instruction counter
• takes a snapshot of the register contents
• indicates required memory locations
• specifies resource needs
• specifies priority if required

Multiprogramming (multitasking) :technique allowing several processes to reside simultaneously in main memory and interleave their execution .

Before operating system can schedule jobs, needs to resolve limitations of system:

• Finite number of resources (drives, printers)
• Some resources, once allocated, can’t be shared.

• Maximise throughput by running as many jobs in a given amount of time. (E.g. run only short jobs or those without interrupts).
• Minimise response time by quickly dealing with interactive requests, and letting batch requests wait.
• Minimize turnaround time by moving jobs in and out as fast as possible, by doing batch jobs first.
• Maximise CPU efficiency by keeping CPU busy 100% of the time - avoid IO bound jobs.
• Ensure fairness for all by giving every job equal CPU and IO time. No special priority.

Final decision on which strategy to take rests with system designer.

1. First come, first served (FCFS)

When a new job enters the system, it is added straight onto the queue for the processor. Turnaround time is unpredictable – for example, suppose there are three jobs:

Job 1 needs 15 milliseconds CPU time
Job 2 needs 2 milliseconds CPU time
Job 3 needs 1 millisecond CPU time


Timeline 1

Job 1

Job 2

Job 3

0

15

17

18

If all three jobs arrive almost same time, turnaround for Job 1 is 15, Job 2 is 17 and Job 3 is 18, so average turnaround is:

(15 + 17 + 18) / 3 = 16.67

If the jobs arrived in a different order results would be

Job 3

Job 2

Job 1

0

1

3

18

(1 + 3 + 18) / 3 = 7.3



2. Shortest job next (SJN)

Gives minimum average turnaround - always gives second situations shown for FCFS. Only works when all jobs are available at the same time and CPU estimates are accurate.



3. Priority scheduling

Most common method in batch systems, but may give slow turnaround to some users. Gives preferential treatment to important jobs. Jobs with the same priority are treated FCFS. Priority could be based on:

• Least amount of memory required
• Least number of peripheral devices needed
• Shorted estimated CPU time
• Time already spent waiting.

1. Shortest remaining time.

Pre-emptive version of SJN. The processor is allocated to the job closest to completion. Can’t be implemented on interactive system because it requires advance knowledge of required CPU time.

For example, if the following four jobs arrive:

Arrival Time: Job: CPU Time:

0 A 6

1 B 3

2 C 1

3 D 4

Processing will occurs as follows:

• Job A will start running because it was there first
• After 1 CPU cycle, Job B arrives and preempts A because it is shorter.
• After 2 CPU cycles, Job C arrives, and it preempts B because it is shorter.
• Job C runs to completion
• After 3 CPU cycles, Job D arrives, but it needs 4 cycles and B only needs two to finish, so B runs to completion.
• D needs four cycles and A has five remaining, so D runs to completion, followed by A




Job A

Job B

Job C

Job B

Job D

Job A

0

1

2

3

5

9

14

Turnaround (14 + 4 + 1 +6) /4 = 6.25

However, the time for context switching is not included in this and it takes valuables CPU time.

2. Round robin

Preemptive process scheduling algorithm used extensively in interactive systems. Easy to implement and isn’t based on job characteristics, but on time slicing. Goal is to ensure that CPU is equally shared and not monopolized.

The size of the time slice is crucial to the performance. Jobs are placed in a queue, FCFS. First job is allocated one time slice. If processing isn’t finished after 1 slice, job is put at end of queue.

Example:

Arrival Time: Job: CPU Cycles:

0 A 8

1 B 4

2 C 9

3 D 5

If the time slices are 4 cycles, the following will occur:

• Job A will run for 4 cycles, then be preempted and put to back of queue.
• Job B will run to completion
• Job C will run for 4 cycles and then go to the back behind Job A
• Job D will run for 4 cycles and then go to the back behind C
• Job A is now at the front of the queue, and will run to completion.
• Job C will take 4 more cycles.
• Job D will run its last 1 cycle
• Job C will then run to completion.




Job A

Job B

Job C

Job D

Job A

Job C

Job D

Job C

0

4

8

12

16

20

24

25

26

Turnaround time (20 + 7 +24 +22)/4 = 18.25

If time slice is too big, jobs will run FCFS. If too small, there will be too much context switching.



3. Multiple level queues

Not really separate type, but hybrid. Can be:

• Different queues for different priorities
• Put CPU intensive jobs in one queue and IO intensive jobs in another. Select alternately.
• Put batch in one queue and interactive in another, ("Foreground and background") with interactive given priority.

Within the queues, jobs are served FCFS. Much attention has to be paid to "aging" how long job has been waiting. Have to avoid indefinite postponement.

INTERRUPTS

Interrupts to a process can occur when a process makes an IO request or due to context switching.

Interrupts can also occur as a direct result of the job instruction currently being processed, e.g

• Attempts to divide by zero
• Floating point overflow or underflow
• Attempts to address protected storage or non-existent locations
• Attempts to use an undefined operation code (instruction)

Interrupts handled by interrupt handler as follows:

• The type of interrupt is described and stored, to be passed on to the user as an error message.
• The state of the interrupted process is saved (registers, instruction counter, etc)
• Interrupt is processed, and error message and current state of process is conveyed to user, program execution is halted, resources released and job exits system.

PROCESS MANAGEMENT UNDER DOS

DOS is a single-user single-task environment. DOS does not support multitasking.

However, although two jobs can’s run together, some software programs give that illusion. Both Windows 3.1 and Borland Sidekick for example appear to interrupt the main program, change screen displays, run a couple of programs and then return to the main program. They feel like multitasking, but there is never more than one program in the RUNNING state at the same time. The other programs "sleep". The interrupt handlers allow the parent program to start again after the child has finished.

DOS has 256 interrupts and associated handlers and they are accessed via the interrupt vector residing in the lowest byes of RAM. There are three types of DOS interrupt:

• Internal hardware interrupts, eg division by zero
• External hardware interrupts caused by peripheral devices, e.g. screen.
• Software interrupts are generated by the system and application programs. The TSR (terminate and stay resident) interrupt terminates a program without releasing its memory. This is called memory resident programming.

When CPU gets a DOS interrupt, it puts onto a stack the code segment register and the instructions pointer register(where the program is stored and at what point in processing ). It also disables the interrupt handler so that no more interrupts can be received till the current one has been handled. CPU uses 8 bit number placed on system bus to get the address of the handler from the vector table.

PROCESS MANAGEMENT UNDER WIN NT

NT is a preemptive multitasking multithreaded operating system.

A process is :

• An executable program
• Its private memory area
• System resources allocated by OS

With NT there is a fourth component - a "thread of execution". A thread is the entity that NT kernel schedules as a task. This can be split into several parts called multithreading, allowing several executable segments to execute in parallel with multiple processors. By default, a process contains one thread. A process can have as many threads as there are CPU’s available in the system. It is important to note the NT has inbuilt protection that stops one thread from modifying a global variable independently from another.

WIN 95/98

Preemptive multitasking operating system using time slicing (20 milliseconds). In 95/98 threads can share a single CPU. The CPU is switched from one thread to another.