# Presentation: 063400

## Fractal Analysis of Resource Exhaustion in Operating Systems:Initial Steps Mark Shereshevsky, Bojan CukicJonathan Crowell Computer Sc. and Electrical Engineering DepartmentWest Virginia University (smark, cukic, crowell)@csee.wvu.edu

## Software aging phenomenon 

- “Software aging" phenomenon implies that the state of the software system degrades with time.
-  The degradation manifests itself in performance decline (excessive paging and swapping activity etc.), possibly leading to crash/hang failures or both.
- Degradation is caused, in particular, by the exhaustion of the operating system resources, such as the number of unused memory pages, the number of disk blocks available for page swapping, etc.

## Earlier studies of resource exhaustion 

- Vaidyanathan and Trivedi describe the behavior of operating system recourses as a function of time
-  Slope (trend) depends on the workload state of the system,
- Workload dynamics is modeled as semi-Markov process.
- However, *in many workload states the dynamics of the resources demonstrates very high variance* resulting in very broad confidence intervals. The highly irregular and oscillatory behavior of the data makes any linear trend model insufficient.

## Our research objectives

- Investigate correlation between fractal properties of the resource data and the system’s workload
- Develop fractal-based model of the resource exhaustion process
- Apply it to real-time operating systems.
- Investigate possibility of using such model for predicting system outages and for preventive maintenance planning

## Data collection

- Two sets of data collected from WVU machines, plus a set of data from Duke University.
- WVU1: resources *realMemoryfree* and *freeSwapSpace* on a  *SUN server*,
- Data collected once per second for 488,051 seconds (approximately 5 days and 18 hours between June 13 and June 19).
- WVU2: resources *realMemoryfree*,* freePageBytes* and *freeVirtualMemory* from *an NT server*,
- 106 data points were collected (using a fairly simple C++ application) from June 26, 2:50:50 PM to June 27, 6:47:45 PM.

**Notes:**
WVU1:  a heavily used CSEE department server at WVU  with 256 MB of RAM, dual 333 MHz processors, which runs SunOS 5.5.1.  We used the UNIX utility “sar –r” (“system activity reporter” with the option that reports unused memory pages and disk blocks).

WVU2:  a print server with 64 MB of RAM and running Windows NT.

## Fractal signals: theory

-  Most popularly known fractals are two-dimensional “beautiful pictures” (Mandelbrot, Julia sets Koch snowflake, Serpinski triangle, “ferns” etc.) exhibiting complex structure at every scale and self-similarity: zoom any fragment of it with any resolution and get a picture which resembles the whole set.
-  Functions may also be fractal, i.e. have fractal graphs. Such functions are non-smooth, do not have a derivative at any point.

## Example of fractal function

-  Weierstrass function:   		             , *a *= 0.5, *b *= 3.

## Fractal signals: applications

-  The study of fractal functions (i.e. those whose plots exhibit fractal properties) has proved important in several scientific domains. The examples of processes described by such functions include
- the heartbeat oscillations;
- the speech signals;
- the network traffic;
- Solar wind;
- the stock index charts etc.

## Holder exponent: theory and computation  

-  Fractal functions have local singularities exhibiting wild oscillations at every scale.
- Mathematical tool for studying the fractal functions:
*Hölder exponent* measures the intensity of these oscillations
-  The Hölder exponent of a function *f*(*t*) at the point *t* is defined by the formula:
- The exponent ranges from 0 to 1. _*It equals 1 wherever the function is smooth*__*, and it decreases to zero as the the oscillatory singularities intensify.*_
- For Weirstrass: *H**w*(*t*) = log2/log3.

## Using Hölder exponent to Analyze time series  

-  The study of experimental time series with fractal structure is often done by computing and analyzing its Hölder exponent.
- As we deal with a discrete sequence of measurements we cannot apply the definition of Hölder exponent directly. We have developed an algorithm for computing the Hölder exponent of the *discrete* time series.
- Our algorithm showed very robust performance on several test examples.

## Performance of our algorithm for computing Hölder exponent 

-  Test signal: generalized Weierstrass function:
-  with* s*(*t*) = |sin (5*t*)| sampled with step 105. The HE is known to be *s*(*t*).
- The Holder exponents computed by our algorithm versus actual values.

## Hölder exponent computations for memory free data

- Two experiments performed on the *realMemoryFree* time series from the *SUN* server.
- SET1: A three-hour set of data collected in early morning hours: from 2:30 AM to 5:30 AM;
- SET1: Collected in the midday: from 12 noon to 3 PM.
- The measurements taken once per second (10,800 points in each time series)
- Both time series show *multifractal* behavior.
- Since the Hölder exponent plots are extremely chaotic, we also computed the histograms of the Hölder exponents, in order to visualize their distribution over the range [0, 1].

## Plots of data with Hölder exponent (1)

*realMemoryFree* from 2:30 AM to 5:30 AM (“low workload”);

- The Hölder exponents for the data.

## Hölder exponent hystogram (1)

-  	The histogram (distribution) of the values of Hölder exponent (SET1: low workload).

## Plots of data with Hölder exponent (2)

*realMemoryFree* data from *SUN server* (high workload);

- Hölder exponents for the data sets.

## Hölder exponent hystogram (2)

-  	The histogram of Hölder exponent for *realMemoryFree* (high workload).

## Fractality of memory time series reflects workload

-  The histograms show clear differences in the shape of Hölder exponents distribution for these the two sets of data.
- The midday hours yield *realMemoryFree* data with very few Hölder exponents in the upper part of the range (very few points where data are relatively smooth).
*realMemoryFree* time series obtained in the night hours is quite “fat” in the upper part of the range (i.e. significant portions of the signal are relatively “smooth”).
-  The *higher workload* data gives a less dispersed spectrum of Hölder exponents which are mainly concentrated in the [0.4, 0.6] range.
- This is sign of *higher self-similarity* (a perfectly self-similar signal has a strictly constant Hölder exponent).

## Future work

- Recognition of the systems behavioral patterns from fractal properties of resource data;
- Correlation between fractal characteristics of the system resource data and malfunction/failure events.
- Experimental application to a real-time application
- Substantial benefit from preventive maintenance.