In this thesis, a page cache using new replacement policy, named context-aware LRU page cache, is proposed and implemented for reducing the response time of executing user applications running in the memory-constrained wearable computer. In the conventional page cache replacement policy, page frames will be reclaimed in the least recently used (LRU) order. In contrast, the proposed predictive page cache replacement gets six different types of context information including location, time, and nearby devices from the context-aware environment and selects the application working set(AWS) that will be used in the next user context with our rule-based context predictor. Then, the page frames that are accessed by the applications not in the selected AWS become the first candidates for reclamation instead of least-recently used page James on reclaiming page frames in the page cache. Therefore, the page frames that will be used in the next AWS become the last candidates for reclaiming page frames.
Our work has two major contributions. First, we devise an architecture of predicting next AWS of a user by utilizing user context information. Second, we propose the predictive page cache replacement and implement the context-aware LRU page cache. The context manager that takes part in the process of predicting user's future AWS is also implemented. With the context-aware LRU page cache and context manager, OS becomes able to reduce the average response time of re-accessing data in disk by minimizing the probability of paging out cached data that will be used in the next AWS.
Assuming that the accuracy of context prediction is 100%, the average response time of file access to user is reduced up to 47% for sequential access pattern. Furthermore, on the assumption of 90% accuracy of context prediction, the average response time is reduced up to 18% for sequential access pattern and 19% for random access pattern. Only under 80% context prediction accuracy, average random access time is reduced up to 1.2% and average sequential access time is increased by 5%.
Consequently, the predictive page cache replacement exhibits its excellent performance especially for users who have predictable habits and read-intensive multimedia applications.
본 논문에서는 새로운 교체 방법을 사용하는 사용자 컨텍스트 인식 LRU 페이지 캐시를 제안하고 사용자 응용프로그램을 메모리가 제한되어 있는 웨어러블 컴퓨터에서 실행할 때의 응답 시간을 줄이기 위해서 이를 구현하였다. 기존의 페이지 캐시 교체 정책에서는, 페이지 프레임은 가장 이전에 사용되었던 순서에 의해서 페이지의 재사용이 이루어진다. 이에 비해서 제안된 예측적 페이지 캐시 교체는 위치, 시간, 주변장치 등을 포함하는 여섯 종류의 서로 다른 컨텍스트 정보를 컨텍스트 인식 환경에서 얻어내어 다음 사용자 컨텍스트에서 사용될 응용프로그램 실행 집합을 룰 기반 예측기를 통해 선택한다. 그리하여 응용프로그램 실행 집합에 포함되지 않는 응용프로그램들이 접근했던 페이지 프레임들이 페이지 캐시에서 페이지를 재사용할 때 가장 이전에 사용되었던 순서에 의한 페이지 프레임들 대신에 재사용의 첫 대상으로 선정되게 된다. 따라서 다음 응용프로그램 실행 집합에서 사용될 페이지 프레임들은 페이지 프레임의 재사용시에 가장 마지막 대상이 된다.
이 연구는 두 가지의 기여를 하였다. 첫 번째로 사용자 컨텍스트 정보를 활용함으로써 다음 응용프로그램 실행 집합을 예측하는 구조를 고안하였다. 두 번째로 예측적 페이지 캐시 교체를 제안하고 이를 컨텍스트 인식 LRU 페이지 캐시로 구현하였다. 사용자의 다음 컨텍스트의 응용프로그램 실행 집합을 예측하는 과정의 일부분을 담당하는 컨텍스트 관리자 또한 구현되었다. 이러한 컨텍스트 인식 LRU 페이지 캐시와 컨텍스트 관리자를 이용하여 운영체제는 디스크에서의 데이터 재접근시의 평균 응답 시간을 다음 응용프로그램 실행 집합에서 사용될 캐싱된 데이터의 방출 확률을 최소화함으로써 줄일 수 있다.
컨텍스트 예측률이 100%라고 가정할 때 파일 접근의 평균 사용자 응답 시간은 순차 접근에 대해서 47% 감소를 보였다. 또한 90%의 컨텍스트 예측 정확도에서도 평균 응답 시간이 순차 접근에 대해 18%, 임의 접근에 대해 19%의 감소를 보였다. 단지 80%의 컨텍스트 예측 정확도에서만 평균 응답시간이 임의 접근시 1.2% 감소를, 순차 접근시 5%의 증가를 보였다.
결과적으로 예측적 페이지 캐시 교체는 그 탁월한 성능을 특히 예측 가능한 습관을 갖고 읽기 집약적 멀티미디어 응용 프로그램을 사용하는 사용자들에 대해서 보여주게 된다.
