Evolutionary Computation for Scheduling Controls
in Concurrent Object-Oriented Systems

This paper has been accepted by CAINE-97 (ISCA 10th INTERNATIONAL CONFERENCE ON COMPUTER APPLICATIONS IN INDUSTRY AND ENGINEERING).

Also, it will be published for the September (or June), 1998 issue of International Journal of Computers and Their Applications (IJCA).

Abstract

Keywords:

1 Introduction

2 Evolving Processes and Evolution Scheduling

Figure 2.1: Ready Queues and Blocked Queues

Figure 2.2: Flow Chart for Evolution Scheduling

2.1 Evolving Processes

2.2 Evolution Scheduling

Figure 2.3: Two Phases of Evolution Scheduling
(We define a class as a collection of queues.)

2.3 Fitness Functions and Objective Functions

Table 2.1: System Variables Available

2.4 Guarantee Values and Chromosome Values

Figure 2.4: An 8-bit Chromosome

2.5 Process Dispatching and Queue Dispatching

Program 2.1: Pseudo Code for Process Dispatching

Program 2.2: Pseudo Code for Queue Dispatching

2.6 Genetic Algorithms and Evolutionary Programming

Table 2.2: Genetic Algorithms vs. Evolutionary Programming

2.7 OS Scheduling and PL Scheduling

Table 2.3: Comparisons of Scheduling Queues

Figure 2.5: OS Scheduling and PL Scheduling

2.8 Real-Time Scheduling and High-Performance Scheduling

Figure 2.6: Real-Time Scheduling and High-Performance Scheduling

2.9 Comparisons of Process Scheduling

2.9.1 Evolution Scheduling vs. Round Robin Scheduling

Figure 2.7: Evolution Scheduling vs. Round Robin Scheduling
(The number beside an arrow is the fitness value.)

2.9.2 Evolution Scheduling vs. Priority Scheduling

Figure 2.8: Evolution Scheduling vs. Priority Scheduling

2.10 Flexible Mechanisms and Rich Policies

Table 2.4: Flexible Mechanisms of Evolution Scheduling

Table 2.5: Rich Policies of Evolution Scheduling

2.11 Theorems of Evolution Scheduling

Theorem 2.1: Flexible Mechanisms and Rich Policies

3 Implementation

3.1 Ready-Queue Scheduling Controls

Table 3.1: Scheduling Controls for Ready Queues

3.2 Blocked-Queue Scheduling Controls

Table 3.2: Scheduling Controls for Blocked Queues

3.3 PC-Queue and CS-Queue Scheduling Controls

Table 3.3: Scheduling Controls for PC Queues and CS Queues

3.4 Major Primitives for Process and Scheduler Classes

3.4.1 Process Classes

Figure 3.1: Process Class Primitives

3.4.2 Scheduler Classes

Figure 3.2: Scheduler Class Ready-Queue Primitives

Figure 3.3: Scheduler Class Blocked-Queue Primitives

3.5 Syntax and Semantics

Figure 3.4: System Calls and Language Functions

3.5.1 Ready-Queue Evolution Scheduling

3.5.1.1 Fork

  where es structure is 
    char rq_class_id[10]
    char rq_queue_id[10]
    char rq_queue_fitness[80]
    char rq_process_fitness[80]
    char bq_class_id[10]
    char bq_queue_id[10]
    char bq_queue_fitness[80]
    char bq_process_fitness[80]

3.5.1.2 Nice

  where es structure is 
    char rq_class_id[10]
    char rq_queue_id[10]
    char rq_queue_fitness[80]
    char rq_process_fitness[80]
    char bq_class_id[10]
    char bq_queue_id[10]
    char bq_queue_fitness[80]
    char bq_process_fitness[80]

3.5.2 Blocked-Queue Evolution Scheduling

3.5.2.1 Wait and Signal

  where es structure is 
    char bq_class_id[10]
    char bq_queue_id[10]
    char bq_queue_fitness[80]
    char bq_process_fitness[80]

  where es structure is 
    char bq_class_id[10]
    char bq_queue_id[10]

3.5.3 PC-Queue and CS-Queue Evolution Scheduling

3.5.3.1 Monitor

server::
monitor monitor_name
  procedure procedure_name [with server_es];
  ...
  end;
end monitor;

client::
monitor_name.procedure_name [with client_es];

  where server_es structure is 
    char bq_default_queue_id[10]
    char bq_default_queue_fitness[80]
    char bq_default_process_fitness[80]

  and client_es structure is 
    char bq_queue_id[10]
    char bq_queue_fitness[80]
    char bq_process_fitness[80]

3.5.3.2 Forerunner Controls

Figure 3.5: Forerunner Control

server::
accept entry_name(in;out)
  [with server_es] do ...

client::
task_name.entry_name [with client_es];

  where server_es structure is 
    char bq_default_process_fitness[80]

  and client_es structure is
    char bq_process_fitness[80]

3.5.3.3 Preference Controls

Figure 3.6: Preference Control

server:: 
select
  prefer: HIGH [with high_es]
    accept entry_name (HIGH) (in; out)
      ...
or
  prefer: MEDIUM [with medium_es]
    accept entry_name (MEDIUM) (in; out) 
      ...                                      
or
  prefer: LOW [with low_es]
    accept entry_name (LOW) (in; out)
      ...
end select;

client::
task_name.entry_name (HIGH) (in; out) [with client_es]

where high_es, medium_es, and low_es  structures can be 
    char bq_queue_fitness[80]
    char bq_default_process_fitness[80]

  and client_es structure is
    char bq_process_fitness[80]

3.5.3.4 Priority Controls

Figure 3.7: Priority Control

4 Significance of This Research

4.1 Object-Oriented Schedulers and Processes

4.2 Flexible Mechanisms and Rich Policies

4.3 Parallel Scheduling

4.4 Relative Resource Scheduling

4.5 Reflective Artificial Intelligence Frameworks

4.6 Parallel and Distributed Evolutionary Computing

5 Conclusions and Further Work

References