Mitchell Neilsen
Lucas Tandang
Computer Science Department
Marvin L. Stone
Biosystems and Agricultural Engineering
Oklahoma State University
A virtual terminal (VT) is a network device that provides display and keyboard services to other devices on the netowork. A VT allows an operator to interact with other devices on a network. Before a screen can be displayed by the operator, the network device associated with the screen must secure memory within the terminal to store the screen. If there is not enough memory within the virtual terminal to store all screens, the memory must be managed dynamically. Much is known about memory management in the context of operating systems. In this study, traditional page replacement algorithms are considered for memory management within a virtual terminal. Algorithms are analyzed with respect to network load under various constraints. In addition, modifications to the existing algorithms are proposed. These modifications are considered to meet the unique demands required for in-vehicle networking.
J1939 is a high speed, class C type communication network designed to interconnect a set of electronic control devices. A virtual terminal (VT) is a network device on a J1939 network. The VT protocol is currently defined in the J1939/72 draft [1]. A VT allows multiple network devices to display information to an operator and retrieve input from the operator. The operator communicates with a network device by switching to a screen associated with the device. Each screen is associated with a single network device, but a network device may have more than one screen. A screen is defined by a screen macro. A screen macro is a sequence of commands. The VT displays a screen in its 200x200-minimum-pixel-wide display by executing the corresponding screen macro. A screen macro must be completely loaded into VT memory before the VT can display the screen. Therefore, the VT should have enough memory to store at least one screen macro. Further discussion about macro commands can be found in the J1939/72 draft [1]. In the rest of the paper, a screen and the corresponding screen macro will be referred to as a screen when no confusion will result.
Each network device can have more than one screen. Conceptually, the VT can display any number of screens from multiple network devices. The VT can secure the screens within its memory and display the screen to the operator on demand without re-loading the screen macro over the network. However, since the amount of VT memory is limited, only a subset of all screen macros can reside in VT memory at any given time. A screen macro replacement algorithm is used to judiciously select which screen currently in memory should be ejected when another screen macro needs to be loaded.
In the remainder of this paper, formal descriptions of the problems are introduced. Then, various screen replacement algorithms are presented and analyzed.
The set of all screens from all network devices is defined as
the screen set and is denoted S = {si | i = 1,2,3,......,m}.
Operator screen references are defined by a reference string,
= r1 ,r2 ,r3 , .... ,rT , where rt 
S for 1
t
T.
Note that the VT displays a screen in the foreground by executing
the corresponding screen macro. The VT records a screen reference
each time the corresponding screen macro is executed. The resident
set Rt is the set of screens present in VT memory after screen
rt is referenced at time t. Note that Rt
S.
During operation of the VT, a resident set Rt is constructed
on each reference t such that rt 
Rt
. Now, let Size(sj) be the size of screen sj in bytes. The size
of Rt is limited by the amount of VT memory, denoted VT_RAM;
that is,
Size(sj) 
VT_RAM.
Obviously, the perfect condition occurs when 
Size(sj)
VT_RAM. In this case, the VT can always
store all screens from all network devices at all times. Unfortunately,
this will generally not be the case. So, a judicious screen management
policy must be employed to decide which screens are eligible to
stay in VT memory at any given time.
A screen fault occurs when the operator tries to reference a screen that is not presently in VT memory. The screen fault indicator function Ft is defined as follows:
Rt-1
Rt-1.
When a screen fault occurs, the screen macro is sent from the corresponding network device to the VT over the network. In this paper, we introduce a demand-driven strategy that can be used to manage memory in a virtual terminal. The network devices are not required to initially download the screens on power up. The screens are brought into VT memory only when the operator references them. The demand driven strategy is defined as follows:
Rt = Rt-1, if rt 
Rt-1.
Rt = Rt-1 
{rt}, if rt 
Rt-1 and (
Size(sj) + Size(rt) ) 
VT_RAM
Rt = Rt-1 
{rt} -Pt-1, if rt 
Rt-1 and (
Size(sj) + Size(rt) ) 
VT_RAM where Pt-1 is the set of replaced screens (Pt-1
Rt-1). Note that Pt-1 may have more than one element when the
size of rt is such that more than one screen is replaced to make
room for rt .
The following examples illustrates the demand-driven strategy.
 |
||||||||||||
When screen 1 is referenced at time 1, a screen fault occurs and screen 1 is loaded into memory. Thus R1={1}, and F1=1. At time 3, screen 1 is referenced for the second time and no fault occurs. Finally, at time 7, one of the screens currently in memory must be evicted to make room for screen 3. In the example, screen 1 is evicted. The screen or screens selected for eviction is determined by the screen replacement policy used.
In order to better understand the policies that can be used to select which screen is evicted the following formalism is required.
The number of bytes transferred on reference t is defined by: Dt = Ft * Size (rt). So, the average number of bytes transferred for each reference is
= 
The maximum average number of bytes transferred for each reference occurs when a screen fault occurs on every reference. The upper bound on Av is given by:
. The minimum average number of bytes transferred for each reference occurs when the VT can afford to store all of the referenced screens in its memory and thus, for each screen, the fault occurs only once. The subsequent references to the screen will not cause a screen fault. If all screens are referenced at least once, the lower bound on Av is given by:
Avmin = 
However, in general the lower bound is given by:
Avmin = 
, where:
i 
t, such that ri = rt .
Several different methods can be used to manage memory allocation within a VT. Two possible methods are presented below.
CONTIGUOUS ALLOCATION - The VT stores variable size screen macros
in its memory. If the screen macros are stored in a contiguous
area of memory, external fragmentation may occur. Then, frequent
memory compaction may need to be performed. The following example
illustrates the problem.
Figure 1. Memory fragmentation.
In Figure 1a, after screen 1 and screen 3 are evicted, screen 4 still cannot be stored in memory because the memory is fragmented. Figure 1b shows the result of memory compaction. If memory compaction is executed frequently the VT performance may be adversely affected.
Fixed Size Block Allocation - A screen macro is a sequence of VT commands. The maximum length of a VT command is 8 bytes [1]. If each VT command is stored in an 8-byte frame and a linked list structure is used to store a screen macro, the fragmentation problem will not occur.
Figure 2. A screen macro stored as a linked list.
With a linked list structure, the memory fragmentation will not occur because each 8-byte frame can be located anywhere in the memory. The first frame points to the second frame, the second frame points to the third frame and so on.
The problem with the linked list strategy is the space required to maintain the pointer in each frame. With a 32-bit (4 byte) pointer, the wasted space is 4/(8+4) = 33.3%. However, the wasted space can be minimized simply by using a larger block size. Let p be the block size in frames (1 block = p frames = 8 *p bytes). Assuming that each block is fully occupied, the wasted space is given by:
In practical, some blocks are not fully occupied. For example, if a screen requires 20 frames and the block size is 8 frames , then 3 blocks will be allocated. The last four frames are not used. This is called internal fragmentation.
Independent of which method is used to manage memory allocation, a screen replacement policy must be implemented to determine which screens should remain in memory.
If enough memory is not available to bring a new screen into memory,
the VT must evict some screens to make room. Recall from above
that
Rt = Rt-1 
{rt} -Pt-1, if rt 
Rt-1 and (
Size(sj) + Size(rt) ) 
VT_RAM,
where Pt-1 is the set of replaced screens. The construction of Pt-1 can be performed as follows:
(Rt-1 - Pt-1). Formally, we write y=Sp(Rt-1 - Pt-1). The selection
process (Sp) depends on the particular replacement policy as described
below.
{y}
Size(sj) + Size(rt) 
VT_RAM, then stop; that is, stop if there is enough memory after
evicting the screen.
Upon completion of the algorithm, Pt-1 contains all screens that have been evicted.
Given a reference string 
= r1 ,r2 ,r3
, .... ,rT. The forward distance of screen y at time t
(1
t
T) is defined
as:
, if y does not appear
in rt+1,rt+2 , ....,rT .
The backward distance of screen y at time t (1
t
T) is defined as:
, if y does not appear
in r1 ,r2 ,r3 ,... ,rt-1.
In each of the following algorithms, for brevity in exposition
we assume that the screen size is fixed.
OPTIMAL SCREEN REPLACEMENT ALGORITHM - The screen replacement
policy performs best if it can perfectly predict the future screen
references. On a screen fault, the screens with the maximum forward
distance are evicted. Unfortunately, this algorithm is impractical
since the full reference string must be known in advance.
PRIORITY-BASED REPLACEMENT ALGORITHM - The network device writer can assign static information for each screen indicating the level of usage of the screen. Then, the replacement policy is to replace screens with lowest priority. The policy is based on the expectation that the lowest priority screens will not be referenced again soon , and thus, should be selected for replacement.
With a priority-based policy, the network designer assigns a priority to every screen indicating the level of usage or importance of the screens. For example, suppose that a particular network device has 5 screens. Since screen 1 contains critical information, the designer predicts that screen 1 will be used most of the time and should be assigned a priority of 0 (the highest). After careful examination of the data contained in each of the remaining screens, the designer assigns screens 2, 3, 4, and 5 with priorities 1, 2, 3, and 3, respectively.
Let us assume that the prediction is correct. The higher priority screens are used more frequently. So, on a particular run the operator may make the following screen references:
 |
|||||||||||||
At time t=6, a screen fault occurs, and screen 4 is replaced because the priority of screen 4 is the lowest.
The priority-based policy provides good performance if the network device designer has a good idea of which network devices will coexist on the same network. Unfortunately, that may not be the case. For instance, in the example above, the network device designer already predicted that screen 1 will be the most frequently used screen (0 priority). However, an operator may decide to connect a second network device (D2) on the same network. Suppose that D2 has 2 screens: screen 6 and screen 7 with assigned priorities of 1 and 2, respectively. The two D2 screens may be used far more frequently than screen 1, but instead of storing screen 6 and 7, the VT stores screen 1 (0 priority) which is not used frequently compared with the D2 screens. The result will surely adversely affect network traffic performance.
LEAST RECENTLY USED (LRU) POLICY - The LRU policy is based on
the assumption that recently used screens are likely to be used
again in the near future. Conversely, the screens that are not
used recently will likely being unused in the near future. The
LRU policy causes screens that are recently used to remained in
memory. The LRU screen is y = Sp(Rt-1), where distb(y,t)= max(distb(x,t))
among all x
Rt-1 . So with the same reference
string, the LRU policy will provide the following result:
 |
|||||||||||||
A screen fault occurs at t=6. The replaced screen is 2 because
distb(2,6)=max(distb(x,6)) among all x
R5;
that is, screen 2 is the least recently used screen. The LRU policy
is more convenient to use because the network device designers
do not have to worry about assigning a priority for each screen.
NOT FREQUENTLY USED (NFU) POLICY - On a screen fault, the NFU
policy retains the most frequently used screens in memory and
replaces a screen that was not used frequently in the past. When
a screen fault occurs at time t, the NFU policy replaces screen
y=Sp(Rt-1), such that freq(y,t)=max(freq(x,t)) among all x
Rt-1.
The problem with NFU is that it never forgets. Suppose that
an operation consists of two phases, initialization and execution.
The initialization phase uses screens 1 and 2 frequently, and
the execution phase uses screens 3 and 4 frequently. If only 2
screens can fit into memory, the result can be described as follows:
 |
|||||||||||||
During the execution phase, screen 1 still resides in VT memory even though it is no longer used. When a screen fault occurs at t=10, the replaced screen is screen 4 because it was not used frequently. If the LRU policy is employed, the above reference string will result in the following:
 |
|||||||||||||
Screen 1 will be replaced from VT memory as soon as it is no longer
used in the execution phase, and only 4 screen faults will occur.
Modified Least Recently Used (MLRU) Policy - The LRU policy can readily be employed if the VT can display only one screen at a time. If the VT can display multiple screens simultaneously, the LRU policy may yield unexpected results. The following example illustrates the problem:
 |
|||||
Suppose that the VT can display 2 screens simultaneously. After screen 6 at time 2 is referenced, screens 5 and 6 reside in VT memory and both are displayed. At time 3, screen 7 is referenced. Screens 5 and 7 are displayed in the foreground, while screen 6 is stored in the background, not displayed. At time 4, screen 6 is referenced and displayed together with screen 5 while screen 7 is kept in the background. When screen 8 is referenced at time 5, screen 5 is evicted while the operator may be still using it. The problem is that a screen may be referenced (read-only) while simply being displayed. The solution is to consider display in the foreground as a reference.
The MLRU policy maintains a bit vector vi for every screen i that currently resides in VT memory. Using MLRU with a 5-bit vector, the above example will lead to the following result :
2. Screen 6 is referenced at time 2. Two steps are performed:
The bit vector is shifted one step right.
Screens 5 and 6 are displayed in the foreground. The MSBs are set to 1.
3. Screen 7 is referenced at time 3.
4. Screen 6 is referenced at time 4.
5. Screen 8 is referenced at time 5. Screen 7 is selected for eviction because it has the smallest binary value.
Note that since screen 5 is always displayed in the foreground,
it retains the largestt binary value and thus, has the absolute
right to reside in VT memory. The MLRU policy also uses information
about how recently a screen has been referenced. In the above
example, screen 6 is used more frequently than screen 8, but since
screen 8 is more recently used, screen 8 has a larger binary value
than screen 6. The length of the bit vector determines how far
back in the past the VT should consider the screen usage record.
PRIORITY OVER LRU (PLRU) - The PLRU policy maintains 2 priority classes:
High priority (0) for screens that are displayed in the foreground.
Low priority (1) for screens that remain in memory, but are not displayed.
The PLRU applies LRU policy is used for the screens within the same priority class. Using PLRU, screens in the foreground are never replaced as long as there are screens in the background. Among screens in the background, the PLRU policy still chooses the least recently used screen to be replaced.
The VT displays a screen by executing the corresponding screen macro. A screen macro must be completely loaded into VT memory before the VT can execute it. Since the amount of VT memory is limited, only a subset of all screen macros can be stored in memory. In order to minimize the number of screen faults, the VT must judiciously selects which screen macros should reside in VT memory at any given time. This paper analyzed various applicable algorithms to achieve this purpose.