Serban Georgica Obreja
email: serban@radio.pub.ro

Radu Iorga
email: radu.iorga@elcom.pub.ro

Eugen Borcoci
email: eugen.borcoci@elcom.pub.ro

Cristian Cernat
email: cristian.cernat@elcom.pub.ro

Marius Vochin
email: marius.vochin@elcom.pub.ro

Jordi Mongay Batalla
email: jordim@interfree.it

Daniel Negru
email: daniel.negru@labri.frjbruneauqueyreix@labri.fr

Joachim Bruneau-Queyreix

Over the Top Content Streaming Adaptive System-Implementation and Validation

Keywords: Content delivery, Dynamic Adaptive Streaming over HTTP, Quality of Service, Quality of Experience, Monitoring, Server and Path selection. I

Adaptive content streaming is an efficient and cheap solution to achieve a good Quality of Service and Experience for media streaming, having an Over-the -Top light architecture, i.e., working on top of the current IP technologies. The adaptation in the system considered here consists in content server initial optimized selection based on multi-criteria algorithm and then in-session media adaptation (using dynamic adaptive streaming) and/or server switching. In this paper, a first set of results on the implementation and functional validation of the system are presented. It focuses on presenting some of the functional validation scenarios and the tests results of the server selection component.

INTRODUCTION

The light Over-the-Top (OTT) architectures are recently developed for media/content delivery over the current public Internet. These are more simple and cheaper in comparison to complex solutions involving the network resources management and control architecture, like Content Oriented Networking [START_REF] Choi | A Survey on Content-Oriented Networking for Efficient Content Delivery[END_REF].

This paper considers an OTT-style content streaming system, proposed, designed and implemented by the European DISEDAN Chist-Era project [2], (service and userbased DIstributed SElection of content streaming source and Dual AdaptatioN, [2014][2015]. The business actors involved are: Service Provider (SP) delivering the content services to the users and possibly owing and managing the transportation network; End Users (EU) that consumes the content; a Content Provider (CP) could exist, owning some Content Servers (CS). In DISEDAN light architecture, it is assumed that CSs are also owned by the SP.

The DISEDAN solution novelty [2][9]- [START_REF] Batalla | D2.3 Specification of the Dual adaptation mechanism[END_REF], consists in: (1) two-step server selection mechanism (at SP and at EU) using algorithms that consider context-and contentawareness and (2) dual adaptation mechanism consisting of media adaptation and content source adaptation (by streaming server switching) when the quality observed by the user suffers degradation during the media session.

For in-session media adaptation, the Dynamic Adaptive Streaming over Hypertext Transfer Protocol -HTTP (DASH) technology has been selected. The DASH is a recent multimedia streaming standard, to deliver high quality multimedia content over the Internet, by using conventional HTTP Web servers [START_REF] Dreier | Netflix sees cost savings in MPEG DASH adoption[END_REF][START_REF] Sodagar | The MPEG-DASH Standard for Multimedia Streaming Over the Internet[END_REF][START_REF]Information technology --Dynamic adaptive streaming over HTTP (DASH) --Part 1: Media presentation description and segment formats[END_REF][START_REF][END_REF]. It minimizes server processing power and is video codec agnostic. A DASH client continuously selects the highest possible video representation quality that ensures smooth play-out, in the current downloading conditions. This selection is performed on-thefly, during video play-out, from a pre-defined discrete set of available video rates and with a pre-defined granularity (according to video segmentation).

This presents the DISEDAN testbed where the system components and samples of validation scenarios have been implemented. This paper study is focused on phase 1 of functioning, i.e., initial server selection. The specific DASH topics are treated in other studies [START_REF] Batalla | D2.3 Specification of the Dual adaptation mechanism[END_REF].

The paper structure is the following. Section II is a short overview of related work. Section III outlines the overall DISEDAN architecture and main design decisions. Section IV contains the paper main contributions, focused on DISEDAN system testing and validation performed on a real life testbed. Section V contains conclusions and future work outline.

II. RELATED WORK

Assuring a "good" Quality of Experience (QoE) based on QoS control at server and transport levels is an important feature of the real time media related services. Apart from resource provisioning method, which supposes a complex management infrastructure at network level, adaptive methods are recently considered as good solutions [3][4].

Media flow adaptation is used in recent standards [START_REF]Information technology --Dynamic adaptive streaming over HTTP (DASH) --Part 1: Media presentation description and segment formats[END_REF][6], as a significant technique to improve the QoE. Content server switching during session (assuming that replica servers are available) can additionally be decided if the media adaptation no longer produces good results. To these two, the DISEDAN solution adds an initial server selection phase (based on cooperation between SP and EU) integrating all three in a single solution. The initial server selection can be based on optimization algorithms like Multi-Criteria Decision Algorithms (MCDA). In [START_REF] Beben | Multicriteria decision algorithms for efficient content delivery in content networks[END_REF][9], several scenarios are proposed, analyzed and evaluated, considering the availability of different static and/or dynamic input parameters. Therefore several control plane design decisions are possible [START_REF] Borcoci | Control Plane Design for a Content Streaming System with Dual Adaptation[END_REF], different in complexity/performance. The dynamic capabilities for the initial CS selection and then for adaptation decisions depends essentially on the power of the DISEDAN monitoring system [START_REF] Borcoci | Control Plane Design for a Content Streaming System with Dual Adaptation[END_REF]. The system combines in a novel solution the DASH functionalities with additional monitoring in order to finally realize the dual adaptation.

III. SUMMARY ON DISEDAN SYSTEM ARCHITECTURE

AND DESIGN DECISIONS This section provides a short description of the DISEDAN architecture and main design decisions. More complete description is given in [START_REF] Borcoci | Control Plane Design for a Content Streaming System with Dual Adaptation[END_REF][11] [START_REF] Batalla | D2.3 Specification of the Dual adaptation mechanism[END_REF].

The connectivity between CSs and EU Terminals (EUT) is assured by traditional Internet Services Providers (ISP) / Network Providers (NP) -operators. The ISP/NPs do not enter explicitly in the business relationships set considered by DISEDAN, neither in the management architecture. Service Level Agreements (SLAs) might be agreed between SP and ISPs/NPs, related to connectivity services offered by the latter to SP; however such SLAs are not directly visible at DISEDAN system level.

The system is flexible; it can work either in OTT style, or over a managed connectivity service offered by the network. An implicit assumption is that network environment is the traditional TCP/IP. No reservation for connectivity resources, neither connectivity services differentiation at network level are supposed (but they are not forbidden). The SP does not commit to offer strong QoS guarantees for the streaming services provided to EUs, therefore no SLA relationships between EUs and SPs management entities is mandatory. However, it is assumed that a Media Description Server exists, managed by SP, to which EUT will directly interact.

The media streaming actions are transport-independent. The EUT works as a standalone application; no mandatory modifications applied to the conventional SP; however, SP should provide some basic information to EUT, to help it in making initial server selection (and optionally to help insession CS switching). The decision about dual adaptation (media flow adaptation and/or CS switching) is taken mainly locally at EUT, thus assuring user independency and avoiding complex SP-EUT signaling during the session. Several CSs exist, known by SP; so, the SP and/or EUs can operate servers' selection and/or switching. DISEDAN does not treat how to solve failures, except attempts to do media flow DASH adaptation or CS switching.

The work [START_REF] Borcoci | D2.1 System requirements and comparative analysis of existing solutions for media content server selection and media adaptation[END_REF] has defined all requirements coming for EU, SP and derived the general and specific system requirements and some assumptions and constrains. The architecture (Figure 1) has been determined by such requirements. Details on that are included in [START_REF] Borcoci | D2.1 System requirements and comparative analysis of existing solutions for media content server selection and media adaptation[END_REF]. The functional blocks correspond respectively to SP, EUT and CS. Note that only relevant to DISEDAN blocks are shown in the picture.

The Service Provider (SP) includes in its Control Plane: MPD File generatordynamically generates Media Presentation Description (MPD) XML file, containing media segments information (video resolution, bit rates, etc.), ranked list of recommended CSs and, optionallycurrent CSs state information and network state (if applicable).

Selection algorithmruns Step 1 of server selection process. It exploits MCDA [START_REF] Wierzbicki | The use of reference objectives in multiobjective optimization[END_REF] [START_REF] Beben | Multicriteria decision algorithms for efficient content delivery in content networks[END_REF] to rank the CSs and media representations.

Monitoring modulecollects information from CSs and processes it to estimate the current state of each CS.

The End User Terminal (EUT) includes the modules: Data Plane: DASH (access and application)parses the MD file received from SP and handles the download of media segments from CS; Media Playerplaybacks the downloaded media segments. The standard ISO/IEC 23009-1, "Information technology --Dynamic adaptive streaming over HTTP (DASH)" [START_REF]Information technology --Dynamic adaptive streaming over HTTP (DASH) --Part 1: Media presentation description and segment formats[END_REF] The CS entity includes the modules: Data Plane: Streaming modulesends media segments requested by End Users; Monitoring modulemonitors CS performance metrics (CPU utilization, network interfaces utilization, etc.).

Figure 1 shows the main functional steps: (1) EUT issues to SP a media file request. (2) SP analyzes the status of the CSs and runs the CS selection algorithm. (3) SP returns to EUT an ordered list of candidates CS (SP proposal, embedded in a MD-xml) file. (4) The EUT finally selects the CS, by running its own algorithm. ( 5) EUT starts asking segments from the selected CS. During media session, the EUT makes quality and context measurements. Continuous media flow DASH adaptation is applied, or, (6) CS switching is decided. From the EU point of view, the steps 1-2-3 composed the so-called Phase1 and steps 4-5-6 composed the so-called the Phase 2.

During the receipt of consecutive chunks, the user's application can automatically change the rate of the content stream (based on DASH measurements, which are out of scope in this paper) and/or also can switch to another CS.

The design decisions are taken for the Control Plane, details on this being given in [START_REF] Borcoci | Control Plane Design for a Content Streaming System with Dual Adaptation[END_REF].

IV. DISEDAN SYSTEM TESTING AND VALIDATION

This section is dedicated to present the test configuration and validation scenarios. The overall goal is to validate the content server selection phase in different server and network load conditions. Two sample scenarios, out of the complete set performed, are given as examples in this paper.

A. Testbed configuration

An experimental testbed has been built for DISEDAN functionalities validation (Figure 2). The system comprises three independent IP network domains, equipped with several core and edge/border routers (Linux based). No QoS technologies are active in these networks. Several DISEDAN entities are connected to this network: SP, EU, and CS through some access networks. Note that the presence of the access networks in the overall system is not essential, given the OTT-style of work for DISEDAN.

B. Basic signaling test and validation

The sequence of steps for functional validation scenario is illustrated in Figure 2 as a set of actions:

1. The EUT requests a streaming service from SP. The request contains the ID of the media service requested.

2. The SP gets from its local database the identity of the servers hosting the requested content. Using its monitoring module, the SP interrogates the monitoring agents located on the CSs about the CS state. The main monitoring parameters collected by SP are: CS processor load, CS free memory (normalized at the total memory), number of streaming processes on CS, total bandwidth on the network interface.

3. After receiving the monitoring parameters, the SP selects, using the MCDA, the best servers from the list of servers hosting the requested resource.

4. An ordered list of selected servers is returned to EUT. The best server from SP's point of view is on the first position on the list. 5-6. The EUT performs a second selection step. The Round Trip Time (RTT) and the distance in terms of hop count are measured from EUT to the CSs in the list recommended by SP. The communication on fifth step is performed only with the SP's selected servers not with all CSs. Based on this metric the best server is selected by EUT.

Final step: the EUT requests the service from the selected CS; the latter will start streaming packets towards the EUT.

All the functional steps described above have been validated by capturing and analyzing the messages exchanged between EUT, CS, SP.

C. Validation of the server selection algorithm in different

servers load conditions This test illustrates how the CS server's selection is influenced by the load of the content servers. The same setup as the one illustrated in Figure 2 was used.

In the first phase, the terminal requests from Service Provider a new service. The request follows the steps of the selection procedures, as described in the previous section, till it is accepted by the SP and the terminal gets the movie stream from the selected server. The selection of the best CS servers is done by the MCDA algorithm running on SP. It selects the best server based on the list with the network distance between the terminal and the content servers and the lists with the CPU load on content servers, the number of sessions on CSs, the load on the serving network interface on CSs, and the occupied memory on CSs. The values of these parameters are first normalized and then passed to the MCDA algorithm organized into a matrix, MCDA matrix, as it is described in [START_REF] Beben | Multicriteria decision algorithms for efficient content delivery in content networks[END_REF] [START_REF] Borcoci | On Server and Path Selection Algorithms and Policies in a light Content-Aware Networking Architecture[END_REF]. The normalization is done such that a small value indicates a busy server, while a big value indicates a free server. The MCDA algorithm uses a min-max approach. First, it selects for each server the minimum value among the values of the normalized monitoring parameters for that server. So, it has the worst score for each server. Secondly, it selects the best server as the one that have the greatest score among the scores determined in the first phase.

In this scenario, initially, all the servers' monitoring parameters are similar (because the servers are not loaded), except the network distances which are different. In the first phase the selection, is decided by the network distance. The closest server is chosen as the best one.

In the second phase, the terminal triggers another request for the same service. Prior to this action, the CPU on the server which was selected in the first phase is loaded using the stress Linux application. The CPU is loaded at around 55%. Consequently, the value of the parameter associated with the CPU load in the MCDA matrix will decrease, forcing the MCDA algorithm to select another best server from the list of servers hosting the requested resource.

D. Validation of the server selection algorithm in different

network load conditions This scenario is similar with the previous one; the difference consists in the parameter used to influence the server selection algorithm. The load on the content server network interface will be used to influence the selection. In this case, the MCDA will be forced to select the servers CS1 and CS4 in the first phase, by decreasing the network distance between EUT and CS1/CS4. The CS1 will be the recommended server due to the lowest network distance. Then, the CS1 sending interface will be loaded with traffic. Iperf application will be used to load CS1's interface, by sending traffic from CS1 to the router e122 (Figure 2).

After iperf application is started, a second request for the same resource will be initiated by EUT1. Due to the iperf traffic, the monitoring parameter network interface load will increase significantly on server CS1, which determines the associate MDCA parameter to decrease accordingly. As a consequence, the MCDA algorithm will select CS4 server, which was the second on the list, as the best serving server to provide the requested resource. In the first phase of this scenario, the content servers are not loaded, which means that decision variables will have similar values. In this case, the selection is done based on the values for the variable representing the network distance between EUT and CSs. The minimum network distance is allocated for CS1 (10.3.6.132), second on the list, followed by CS4 (10.2.6.129), fourth on the list. In Figure 3, the values for the decision variables related to the traffic load on the sending interface for each server hosting the requested resource are shown. Because there is no load on any of the interfaces, the values are similar.

With green there are emphasized the values for the variables related to network cost. They have the minimum values among the values of the parameters in the resource matrix used by MCDA, which means that the selection is done based on these values. As it can be seen, the maximum value among them is for the server 10.3.6.132, which is recommended as the best server, as is emphasized with blue on Figure 3.

In the second phase, the sending interface of the CS1 server is loaded with background traffic, which is generated with iperf application and is sent to the e122 machine, as can be seen in Figure 2. In this case, the value of the decision variable related to the load on the CS1's sending interface will decrease, determining the MCDA to select as the best server the CS4 machine, with the IP 10.2.6.129. This is illustrated by the SP's messages captured Figure 4. As it is emphasized with blue, the sending interface load decision variable for server CS1 (10.3.6.132) decreased (the second position in the array -its value is around 0.674), determining that this variable will be selected to represent CS1. It also determines the selection of the CS4 server as the best one, due to the min-max approach in server selection algorithm. So, in the second phase, the selected server is CS4 (10.2.6.129), because it has all the decision variables bigger than 0.674, which is the value of the decision variable selected to represent CS1 -as can be seen in the resource matrix delivered to MCDA in Figure 4. CS4 decision variables are on fourth position in each vector, the servers' order being shown in the last row of messages captured in Figure 3.

V. CONCLUSIONS AND FUTURE WORK

In this paper, a functional validation for the multimedia delivering system proposed in the framework of the DISEDAN project, is presented. A media streaming system, working in OTT style has been considered. To improve the QoS/QoE, the system combines an initial (Phase1) optimized content server selection (based on multi-criteria decision algorithms-MCDA) with in-session (Phase 2) media flow adaptation or content server switching.

The results presented in this paper illustrate the basic functionalities of the DISEDAN system's modules and the operating mode of the MCDA algorithm in the first phase of the content server's selection process, in different content servers and network load conditions. The experimental results obtained on the real life testbed validated the capability of the system to properly select the "best server", thus efficiently contributing to prepare the media session phase. A more complete set of results regarding the first phase of the server selection were obtained on a simulation model developed for the DISEDAN system and are presented in [START_REF] Catrina | Two-Phase Multicriteria Server Selection for Lightweight Video Distribution Systems[END_REF].

More elaborate tests to find some quantitative values for the QoE improvements are under investigation and will be developed in order to take advantage of the real life prototype available. Also, investigation on the second selection phase and the adaptation profess will be performed.

Figure 1 .

 1 Figure 1. DISEDAN general architecture

Figure 2 .

 2 Figure 2. DISEDAN System testbed; interactions between system's modules

Figure 3 .

 3 Figure 3. CS selection at SP when the servers are not loaded

Figure 4 .

 4 Figure 4. CS selection at SP when the sending interface on the best CS is loaded with traffic.

  , defines the DASH-Metrics client reference model, composed of DASH access client (DAC), followed by the DASH-enabled application (DAE) and Media Output (MO) module. The DAC issues HTTP requests (for DASH data structures), and receives HTTP request responses. Control Plane: Content Source Selection and Adaptation engineimplements the dual adaptation mechanism; Selection algorithmperforms the Step 2 of server selection process. It can also exploit MCDA, or other algorithms to select the best CS from those recommended by SP; Monitoring modulemonitors changing (local) network and server conditions.

ACKNOWLEDGMENT

This work has been partially supported by the Research Project DISEDAN, No.3-CHIST-ERA C3N, 2014-2015.


Pedro H Penna

The Nanvix Operating System

Introduction

Nanvix is an operating system created by Pedro H. Penna for educational purposes. It was designed from scratch to be small and simple, and yet modern and fully featured, so that it could help enthusiasts in operating systems, to learn about kernel hacking. The first release of Nanvix came out in early 2011, and since then the system has undergone through several changes. This paper details the internals of Nanvix 1.2. All previous and future releases are available at github.com/ppenna/nanvix, under the GPLv3 license.

In this section, we present an overview of Nanvix, starting with the system architecture, then presenting the system services, and finally discussing the required hardware to run the system. In later sections, we present a more detailed description of Nanvix.

System Architecture

The architecture of Nanvix is outlined in Figure 1. It presents a similar structure to Unix System V, and it has been intentionally designed to be so due to two main reasons. First, some successful operating systems, such as Aix, Linux and Solaris, are based on this architecture. Second, System V has earned Dennis Ritchie and Kenneth Thompson the 1983 Turing Award. These points indicate that System V is a well-structured system, thus serving as a good baseline design for a new educational operating system, such as Nanvix.

Nanvix is structured in two layers. The kernel, the bottom layer, seats on top of the hardware and runs in privileged mode, with full access to all resources. Its job is to extended the underlying hardware so that: (i) a more pleasant interface, which is easier to program, is exported to the higher layer; and (ii) resources can be shared among users, fairly and concurrently. The userland, the top layer, is where user software run in unprivileged mode, with limited access to the hardware, and the place where the user itself interacts with the system.

The kernel presents a monolithic architecture, and it is structured in four subsystems: the hardware abstraction layer; the memory management system; the process management system; and the file system. The hardware abstraction layer interacts directly with the hardware and exports to the other subsystems a set of well defined low-level routines, such as those for dealing with IO devices, context switching and interrupt handling. Its job is to isolate, as much as possible, all the hardware intricacies, so that the kernel can be easily ported to other compatible platforms, by simply replacing the hardware abstraction layer. The memory management subsystem provides a flat virtual memory abstraction to the system. It does so by having two modules working together: the swapping and virtual memory modules. The swapping module deals with paging, keeping in memory those pages that are more frequently used and swapping out to disk those that are not. The virtual memory system, on the other hand, relies on the paging module to manage higher-level abstractions called memory regions, and thus enable advanced features such as shared memory regions, on-demand loading, lazy coping and memory pinning.

The process management system handles creation, termination, scheduling, synchronization and communication of processes. Processes are single thread entities and are created on demand, either by the system itself or the user. Scheduling is based on preemption and happens in userland whenever a process runs out of quantum or blocks awaiting for a resource. In kernel land, on the other hand, processes run in nonpreemptive mode and scheduling occurs only when a processes voluntarily relinquishes the processor. Additionally, the process management subsystem exports several routines that allow processes to synchronize their activities and communicate with one another.

The file system provides a uniform interface for dealing with resources. It extends the device driver interface and creates on top of it the file abstraction. Files can be accessed through a unique pathname, and may be shared among several processes transparently. The Nanvix file system is compatible with the one present in the Minix 1 operating system, it adopts an hierarchical inode structure, and supports mounting points and disk block caching.

The userland relies on the system calls exported by the kernel. User libraries wrap around some of these calls to provide interfaces that are even more friendly to programmers. Nanvix offers great support to the Standard C Library and much of the current development effort is focused on enhancing it. User programs are, ultimately, the way in which the user itself interacts with the system. Nanvix is shipped out with the Tiny Shell (tsh) and the Nanvix Utilities (nanvix-util), which heavily resemble traditional Unix utilities.

System Services

The main job of the kernel is to extend the underlying hardware and offer the userland a set of services that are easier to deal with, than those provided by the bare machine. These services are indeed exported as system calls, which user applications invoke just as normal functions and procedures. Nanvix implements 45 system calls, being the majority of them derived from the Posix 1 specification [START_REF]IEEE Standard for Information Technology-Portable Operating System Interface (POSIX) Base Specifications[END_REF]. The most relevant system calls that are present in Nanvix are listed in Table 1 and briefly discussed in the paragraphs that follow. For further information about all system calls in Nanvix, refer to the system man pages.

Files are high-level abstractions created for modeling resources, being primarily designed and used to provide a natural way to manipulate disks. One program that wants to manipulate a file shall first open it by calling open(). Then, it may call read() and/or write() to read and/or write data to the file. If the file supports random access, the read/write file offset may be moved through the lseek() system call. Finally, when the program is done with that file, it may explicitly close it by calling close(), and have its contents flushed to the underlying device.

The file system is organized hierarchically, in a tree-like structure, and files are uniquely identified by their pathnames. A program may refer to a file either by using an absolute pathname, which starts in the root directory; or by using a relative pathname to the current working directory of the program. Programs may change their current working directory by invoking chdir(). Alternatively, users can create links to files by calling link(), and then refer to the linked file by referring to the link (Figure 2). Links and files may be destroyed through the unlink() system call.

Every file has a owner user and a 9-bit flag assigned to it. These flags state what are the read, write and execution permissions for the file, for the owner user, the owner's group users and all others. If a program wants to perform any of these operations it must have enough permissions to do so. The file ownership and permissions may be changed through the chown() and chmod() system calls, respectively, and users can query these information by calling stat(). Processes are abstraction of running programs and play a central role in Nanvix. Programs may create new processes by calling fork(), which creates an exact copy of the current running process. The primal process is called the parent and the new process is called child, and they have the same code, variables, opened files, and execution flow, differing only differ in their ID number.

Processes may query about their ID by calling getpid() and may change their core through the execve() system call. When the process is done, it invokes exit() to relinquish all resources that it was using.

Processes may synchronize their activities using two approaches: through signals or synchronization primitives. In the former, the intend recipient process A first registers a callback function that will handle some specific signal, by calling signal(). If the process has nothing more to do than waiting for a signal to arrive, it may invoke pause() to block until such event happens. Later, another process may send a signal to A by calling kill(), therefore triggering the handler function in A. In the second approach, two processes may open a pipe, a dedicate communication channel, and effectively exchange data with one another. A process in one end of the pipe writes data to it, and in the other end a second processes reads data from the pipe, with all the required producer-consumer synchronization being transparently handled by the kernel.

Hardware Requirements

Nanvix has been primarily designed to target the x86 architecture. Nevertheless, thanks to the hardware abstraction layer, it may be easily ported to other platforms. Still, the new platform shall meet some requirements to enable this smooth transition.

First, paging shall be somehow supported, since the memory management subsystem relies on this feature to enable virtual memory. Additionally, the hardware shall provide a protection mechanism that would point out whether a page fault has been caused due to a missing page or to a permission violation. Nanvix uses this information to easy the creation of new processes through the copy-on-write and demand paging techniques.

Second, the hardware shall support interrupts. Nanvix is a preemptive system, and the hardware shall provide some clock device that generates interrupts at regular time intervals. The scheduler completely relies on this feature, and the system would not even boot without it. Additionally, the hardware should also offer a mechanism to enable and disable interrupts. The kernel uses this mechanism to achieve exclusion on critical regions, and thus avoid race conditions in kernel land (chaos).

Process Management

In this section, we take a closer look in the process management subsystem. We start by first presenting the process structure itself; then highlighting how process scheduling and switching happens; and finally discussing the most important mechanisms exported by this subsystem.

The Process Structure

A process is an abstraction of a running program. It depicts the memory core, opened files, execution flow, access permissions, current state and every other relevant information about a program. Table 2 outlines the (simplified) structure of a process in Nanvix. The information about all processes is kept in a kernel table, named the process table, and it is globally visible to all subsystems. The process management subsystem maintains the process table: whenever a new process is created, a new entry is added to it; and when a process terminates, the corresponding entry is erased. However, it is worthy to point that each subsystem is in charge of maintaining their own fields in the process structure. For instance, the memory management subsystem is the one that fills up information regarding the segment regions and page directory, whereas the file system keeps track of the current working directory and opened files fields.

A process is created whenever a user launches a program or the system itself spawns a new daemon. After that, the new process goes through a complex lifetime before it terminates, as it is shown in Figure 3. Initially this new processes is ready to execute (state 1), and it is eventually selected to run by the scheduler. At this moment, the process resumes back its execution in kernel land (state 2) and jumps to userland (state 3). There, the process performs some computation, and it may either get preempted if it runs out of quantum time (state 4), or block waiting for a resource (state 5). Either way, the process later resumes its work, and loops back on these states. When the process finally gets its job done, or it somehow crashes, it terminates and becomes a zombie process (state 6). A zombie process awaits to gets all resources assigned to it to be taken away by the kernel, and then it is turned in a dead process (state 7).

Process Scheduling and Switching

Several processes may be active in the system, but only one can be running at a time 1 . The scheduler chooses which process to run next whenever the running process gets preempted or blocks. In user mode, that happens when the running process runs out of quantum and gets preempted by the kernel, or else when it issues a system call. In kernel mode on the other hand, scheduling occurs only when the running process voluntarily relinquishes the processor and goes wait for a resource to be released. The scheduler (Figure 4) uses a priority based criteria to choose the next process to run, with processes with higher priorities being scheduled to run before those with lower priorities2 . Processes with equal priorities are chained in a queue and are selected in a round-robin fashion.

The priority of a process changes over the time and it is given by the sum of three numbers: base priority, dynamic priority and nice value. The base priority is assigned by the kernel itself and changes as the process sleeps and wakes up from resource queues, and leaves the kernel or enters it. The dynamic priority is increased by the scheduler as the process waits longer in the ready queue. Finally, the nice value is adjusted by the users, exporting them a mechanism to control which processes are more priority over others.

Once the scheduler chooses which process to run next, the process management subsystem performs the context switching operation. It first pushes the contents of all machine registers in the kernel stack. Then, it instructs the memory management unit hardware to switch to the address space of the selected process. Finally, the state of the machine registers are restored from the kernel stack of the selected process. The context switching operation is machine dependent and it is actually carried on by the hardware abstraction layer.

Process Creation and Termination

In Nanvix, processes are created through the fork() system call. This call instructs the process management subsystem to create a new process that is an exact copy of the calling process. The primal process is called parent and the new process is called child, and they have the same code, stack and data segments, opened files and execution flow, differing only differ in their ID number. The fork() system call is a complex and expensive operation, and in order to get it done the process management subsystem heavily interacts with the memory management system and the file system.

To create a process, the kernel first looks for an empty slot in the process table, to store there the information about the process. Then, an address space for the process is created: page tables are initialized, the kernel code and data segments are attached to the process' core, and a kernel stack for the process is created. After that, the kernel duplicates every memory region of the parent process and attaches them to the address space of the child process. In this operation, underlying pages are not actually copied, but they are rather linked and copied on demand. This technique, called copy-on-write, greatly speeds up the fork() system call, and it is covered in Section 3.3. Then, when the address space of the new process is built, file descriptors for all opened files are cloned, and every other information is handcrafted. Finally, the process management system marks the child process as new, so that the scheduler can properly handles this situation, and places it in the ready queue for later execution.

The process then performs some computation and undergoes through a complex lifetime, which we depict in Section 2.1. When the process finally finishes its job it invokes the exit() system call to terminate. This call orders the process management subsystem to actually kill the process and release all resources that are assigned to it.

To do so, several steps are involved. First, the kernel masks out signals and closes all files that are still opened. After that, all child processes of the process that is about to terminate are assigned to a special process, called init3 . This ensures that no process becomes orphan, and thus become unreachable by signals (see Section 2.4). Then, the kernel detaches all memory regions from the dying process and marks it as a zombie. At this moment, the dying process still has an address space and a slot in the process table, and the kernel has no way to wipe off these information. Therefore the dying process hands out this task to the parent process, and sends a death of child (SIGCHLD) to it. This signal cannot be blocked or ignored, and it is eventually handled by the corresponding parent process. When that happens, the parent process destroys the address space of its zombie child process, and marks the corresponding slot in the process table as not used.

Process Synchronization and Communication

In Nanvix, processes may cooperate to one another to accomplish a common goal. To enable this, the kernel provides three synchronization primitives, so that processes can work together without messing up each other's job: sleep(), wakeup() and wait().

When running in kernel land, processes often need to acquire and later release resources, such as slots in the system's tables and some temporary memory. The sleep() and wakeup() routines are used in these situations to avoid race conditions in kernel land. The former puts the calling process to wait in a chain; whereas the later causes all processes that are sleeping in a chain of processes to be moved to the ready-to-execute scheduling queue. These routines support two different sleeping states: one that is interrupitible by the receipt of signals, and another that is not. Thanks to this mechanism, users can interact with foreground processes, such as those that read/write to the terminal.

In userland, processes may coordinate their activities by calling the wait() system call. This call causes a process to block until one of its child process terminates. When such event happens, the parent process is awaken and the exit status of the terminated child is made available to it. This information can be later parsed by the parent process, so that it can known why exactly its child process has terminated and properly handle the situation. These three mechanisms enable processes to synchronize their activities and friendly work together towards a common goal. Notwithstanding, processes also have to somehow be able to communicate with one another to exchange valuable information about their work progress. Nanvix offers two main mechanisms to do that: signals and pipes.

Signals are short messages that processes can send/receive asynchronously. They are mainly used to notify about the occurrence of interesting events, such as that a process has to be killed, a remote terminal has hangup and a breakpoint has been reached. The process management subsystem exports two system calls to deal with signals: signal() and kill(). The former allows a process to actually control how signals shall be handled. A process can either choose to ignore a signal, and not be notified at all about it, or else handle a signal, by registering a callback function that will do the job. The kill() system call on the other hand, allows a process to raise a signal, either to another process or to itself. Additionally to these system calls, the kernel also provides a system call, named pause(), which allows a process to wait for the receipt of a signal. Signals are implemented by having the kernel to instrument the user stack, when a signal is send. The kernel carefully inserts hooks to the registered signal handler in the stack, and when the process leaves the kernel, it transparently executes the signal handler function (Figure 5).

Signals are useful for exchanging small amount of information. However, if processes want to carry on more verbose conversations, they can use pipes instead. A pipe is a virtual file that serves as a dedicated communication channel between two processes. At one end of the pipe, a writer process puts data on the pipe, and at the other end a reader process takes data out from it. Processes can open pipes through the pipe() system call, and after that they can read/write data to it by using the read() and write() system calls, as they would normally do. In all these operations, data transfers take place entirely in memory, with the kernel borrowing a page frame from the kernel page pool and pinning it in memory. Additionally, the kernel handles the required producer-consumer synchronization with the help of the sleep() and wakeup() routines.

Memory Management

In this section, we detail the internals of the memory management subsystem. We first present the memory layout of a process in Nanvix, then we introduce the memory region abstraction, and finally we detail the virtual memory and paging systems.

Memory Layout

The virtual memory layout of typical process in Nanvix is presented in Figure 6. The overall address space is divided in two great portions: one that is owned by the kernel and is shared among all processes; and a second one that is private and belongs to the process itself. The kernel is the only one that has full access to the address space of a process. While running in user mode, if a process touches any kernel memory, a protection fault is raised. This way, the kernel can isolate and protect itself against malicious software, thus increasing the system's security and reliability.

The kernel address space is carefully handcrafted so that it looks as transparent as possible to user processes. The kernel code and data segments are placed to two different locations: identity mapped at the bottom of the memory, and virtually linked just after the user memory. Some operations performed by the kernel, like physical memory copy and context switching, require the virtual memory system to be shutdown momentarily. Placing the kernel code and data segments at the bottom of the memory, enables physical address access; whereas positioning the whole kernel just after user memory ensures that future enhancements on the kernel will not affect the user memory layout. The kernel buffers, kernel page pool and init ramdisk are accessed exclusively through virtual addresses. The kernel buffer area provides the file system with some temporary memory to hold disk data. The kernel page pool feeds the kernel memory allocator with some memory that will indeed be used to build dynamic structures in the kernel, such as page tables. Finally, the init ramdisk is a static memory area that functions as an in-memory file system and stores configuration files and (eventually) dynamic loadable drivers, which are all used during system's startup.

The user memory portion occupies most of the virtual address space and it is divided in several regions. The user code and data regions are statically allocated and hold the text and static data segments of the binary file, respectively. The user stack and heap regions on the other hand, dynamically grow and shrink with the course of time. The former is used to store temporary variables and it is managed by the kernel's memory management subsystem. The heap region however, holds long-term variables and it is handled by the process itself. User libraries rely on the brk() system call to request the kernel to attach, or detach, some memory to the heap.

Memory Regions

In Section 3.1 we have briefly discussed that the user memory portion of a process is divided in four regions, namely code, data, stack and heap regions. A region is a high-level abstraction created by the memory subsystem to easy the management of user memory and abstract away the underlying technique that is used to actually enable virtual memory (ie. segmentation or paging). This abstraction is presented in Figure 7 and briefly discussed bellow. From a design perspective, a memory region is indeed a collection of page tables4 , with some extra metainformation about the region itself. Pointers to underlying page tables are stored in a table, so that the virtual memory and paging systems can quickly retrieve low-level information about the pages that are assigned to a region. The owner and group IDs, and access permissions fields are used together to determine what processes can read or write to the memory region. Finally, the flags field indicate the growing direction of the region, whether or not the region can be swapped out to disk, and whether or not the region is shared among several processes.

The memory management subsystem maintains memory regions in a global table, namely the memory regions table, and exports a well defined interface for dealing with them. The process management subsystem heavily relies on the routines provided by this interface to implement the brk(), exec(), exit() and fork() system calls, as it is outlined in Figure 8. The allocreg() allocates a new memory region, by searching an empty slot in the memory regions table and properly initializing its fields. It is important to point out however, that underlying pages are not actually assigned to the memory region in this routine, but they are rather allocated on-the-fly, using a technique called demand paging (see Section 3.3). Conversely, freereg() frees a region table by releasing underlying pages and page tables, and erasing the corresponding entry from the memory regions table.

The loadreg() routine is used to load a region with some data from a binary file. This routine invokes raw I/O procedures exported by the file system to actually find the corresponding inode and perform the read operation. The growreg() procedure expands (or shrinks) a target region by a certain size, by allocating/freeing page tables accordingly. The attachreg() and detachreg() routines attach and detach a memory region to the address space of a process, respectively. They do so by effectively linking/unlinking underlying page tables to/from the page directory of a process. Finally, the dupreg() routine creates an exact copy of a target memory region. To speedup this task, the memory management subsystem uses a lazy copying technique known as copy-on-write, which e further discuss in Section 3.3.

The Virtual Memory and Paging Systems

While the memory management system exports the memory region interface to other system modules, internally it works with paging and swapping to enable virtual memory. The former technique delivers a flat memory abstraction, whereas the latter effectively enables the physical memory to be virtually extended. The paging system relies on a two-level page table that is depicted in Figure 9 and detailed next. Each process has a single page directory, and each entry in this directory points to a page table. Whenever a virtual address is generated, the memory management unit (MMU) breaks it in three portions. The upper portion is used to index the currently active page directory, and thus to find out the corresponding page table. Then, the middle portion is used to index the page table, and hence to discover the physical frame where the requested page is placed. Finally, the third portion is added to the address of the memory frame to build the ultimate target physical address.

Page directories and page tables of all processes are pinned down in kernel memory, and the paging system carefully bookkeeps the physical addresses of these structures. This way, the kernel can access any address space from whatever process is running, handle physical memory copying, and step away from live locks when performing swapping. Memory frames, on the other hand, are handled in a different way by the internal memory frame allocator. The paging system maintains a table, namely the memory frames table, where all information about in-memory pages are stored. When the system first startups, it marks all entries in this table as not used. Whenever a page is requested, the paging system searches this table for an empty slot and allocates the corresponding memory frame. If no slot is available, the swapping system is invoked to swap out an in-memory page to disk.

Aside from managing page directories and page tables, and dealing with page allocation, it is worthy to note that the paging system also implements two fundamental mechanisms: demand paging and copy-on-write. The former is extensively used in the exec() system call and works as follows. Whenever an executable file needs to be loaded to memory, the paging system does not copy any data from disk nor allocate any space in memory at first. Instead, it marks all corresponding entries in the page table as "not present, demanded paging". Later, when an attempt to access an address that falls in such kind of page is made, a page fault occurs and then the paging system allocates a frame to that page and loads it in to memory.

The second mechanism, namely copy-on-write, is heavily employed in the fork() system call to easy the overall task of creating a new process. In a nutshell, this system call creates a child process that is an exact copy of the calling process by duplicating every opened file descriptor and cloning the memory address space of the parent process. The former step can be completed in a handful of time as it comes down to iterate over the file descriptors table incrementing the reference count for each opened file. On the other hand, cloning the address space of a process can be a real time-consuming endeavor, since that involves copying a massive amount of data. When copy-on-write is enabled however, such operation is greatly speed up by having the copy operation to happen on demand, rather than immediately. To enable so, at first, the kernel marks writable pages of the parent process as "read-only, copy-on-write". Later, when a write attempt is made to a marked page, a protection fault is fired and the kernel performs the actual cloning, marking both pages as writable in the end.

So far, we have detailed the internals of the paging system, which delivers a flat memory abstraction to the whole system, but now it is time to turn our attentions to the swapping system. The ultimate goal of this later one is to keep in memory those pages that are more frequently used, and use some disk space to store those that are not. This way, it is possible to execute a process whose memory footprint is larger than the physical memory available. In other words, the physical memory is virtual extended, enabling the maximum memory footprint of a process to be bounded by the size of the virtual address space, rather than the physical one.

To achieve such goal, the swapping system relies on a First-in-First-out (FiFo) strategy to evict pages to disk. For each in-memory page, the swapping system bookkeeps the timestamp in which that page has been brought into memory. Whenever the swapper is invoked, the page with the oldest timestamp is evicted to the swapping area, in disk. The swapping system selects pages using a local-policy and implements no load control mechanism. On the other way around, when a page is brought in to memory from the swapping area, a shadow copy is kept there. This way, if no modifications are done to that page, no extra I/O operation to write the page back to disk needs to be performed.

File System

The file system is certainly the largest and most complex subsystem in Nanvix. It extends the hardware abstraction layer and exports through the file abstraction a uniform interface for dealing with bare resources. In this section we take a closer look in this subsystem. We first present the buffer cache, an internal module that speedups the performance of the file system, and then we move our discussion to the file system's layout, structure and internals.

The Buffer Cache Module

Most requests that arrive at the file system involve disk I/O operations. If, in order to handle each of them, the file system would have to issue an I/O operation, the system's performance would be awful. Therefore, to get around this problem, the file system buffers disk blocks in memory and also maintains a cache of most frequently used buffers there, as shown in Figure 10. In this cache, all buffers are hashed in a table according to the number of the disk block that they currently hold, and buffers that are not in use are linked in a list structure. This way, any buffer can be quickly retrieved through the hash table, and the kernel can easily get a free buffer from the list, whenever it needs one. The buffer cache module exports a set of routines to other subsystems to enable them manipulate buffers. To read a buffer from the cache, the bread() routine is provided. Internally, this routine searches the buffer cache for a specific block and returns a pointer to it. If the requested block is not in the buffer cache, its contents are read from disk to some buffer. What buffer will be be used to handle the request may come from two different sources. If the list of free buffers is not empty, the kernel claims a buffer from there and uses it in the operation. However, if this list is empty, a buffer from the cache is evicted to disk, according to a least-recently used policy, and then it is used to handle the bread() request.

After retrieving a block buffer from the buffer cache, subsystems may freely read/write data from/to the buffer. Nevertheless, it is important to point out that buffers are indeed shared resources, and thus to consistently operate these structures subsystems should carefully use locking mechanisms. To handle this situation, the buffer buffer cache module provides the blklock() and blkunlock() routines, to enable buffers to be locked and unlocked respectively. Finally, when a subsystem is done with a buffer, it calls bwrite() to release it. If no more processes are using that buffer, its contents are flushed to the underlying device and then the buffer is marked as "not used".

As a final remark, it is worthy to note two techniques that are supported by the buffer cache to further improve the system's performance. The first technique, namely delayed write, is outlined in Figure 10 and works as follows. As we detailed before, not-used buffers are linked in a list of free buffers, so that the kernel can easily get a buffer whenever it needs one. Note, however, that buffers that are not being used also appear in the hashing structure. The buffer cache does so in the hope that those buffers will soon be need, and thus tries to postpone writing as much as possible. The second technique, known as asynchronous read, improves the overall system usage by having read operations to take place asynchronously, rather than synchronously to the process' execution flow. To enable this, the buffer cache handles a read operation as it would normally do, however, instead of scheduling a synchronous read operation in the disk driver, it schedules an asynchronous one and immediately returns. The process may then go compute something else, and when the content of the buffer gets valid, it is notified about this event.

File System Layout and Structure

Nanvix adopts an hierarchical file system based on inodes, which heavily resembles the original System V file system reported in [START_REF] Bach | The Design of the UNIX Operating System[END_REF]. Indeed, the Nanvix file system has been intentionally designed to be somewhat compatible with the Minix 1 file system, so that existing user-level utilities specifically designed to manipulate this file system could be used in early development phases5 . The Nanvix file system is outlined in Figure 11 and detailed next. The Nanvix file system works with 1 KB blocks and it is divided in two major zones, one that stores meta information about the file system itself and another one that actually holds user data. The very first block in the meta information zone stores the bootloader, a very small and special program that setups all machine dependent features and actually loads the kernel. Following the boot block, is the superblock, the place where information concerning the file system's peculiarities are kept. For instance, it holds how many data blocks and inodes the file system has, what is the maximum size for a file size and what is the file system version. After this block, there are the inode-map (imap) and block-map (bmpap) blocks, which are used for managing disk space; and the inode blocks, which store all inodes of the file system. Finally, data blocks hold user data, and are linked to the file system hierarchy through the inode structure.

In turn, an inode is a low-level abstraction of a file. It stores information concerning the file's type, owner, access permissions, current size, time of last modification, and blocks pointers, as it is shown in Figure 12. Data blocks are assigned using an hierarchical addressing scheme, where the first seven data blocks are directly addressed, and next ones are addressed via either double or triple indirections. The way that blocks pointers are actually used depend on the type of the file itself. If it is a regular file, then blocks pointers point to data blocks filled with user data. If the file is a directory, however, block pointers point to data blocks that store directory entries. Finally, if the file is a special file, the block pointers hold the minor and major numbers of the referred device.

File System Internals

So far we have explored the buffer cache module and the file system layout. In this section, however, we turn our attentions to the file system internals. We first discuss how disk space is actually managed, then we introduce the interface that is exported for dealing with inodes, and finally we detail some kernel routines for manipulating files.

The file system manages disk space with the help of the bmap and imap blocks (see Section 4.2). These are indeed bitmaps that point out which data blocks and inodes are currently in use in the file system, respectively. Whenever an inode or a data block needs to bee allocated, the correspondent bitmap is sequentially searched for an inode/data block that is available. To speedup the search, the kernel maintains these bitmaps in memory and from time to time it writes them back to disk. Additionally, the kernel keeps track of the last allocated bit in each bitmap and uses bitwise operations to perform the search. This way, the first free bit in a bitmap can be find slightly fast, if the disk is not heavily fragmented, and search time is decreased by a factor of n, where n is the width in bits of the largest machine register. To allocate and free data blocks the kernel exports two routines, namely block alloc() and block free(); and conversely does the same for inodes, through the inode alloc() and inode free() routines.

Inodes are low-level abstractions for files, and are used to model regular files, directories and devices. The most relevant routines for manipulating such structures are presented in Table 3 and briefly discussed next. Ultimately, inodes are stored in disk, so that changes in the file system can persist over time. However, to further improve the file system's performance, the kernel caches in memory the most recently used inodes, in a similar way as it does with disk blocks (see Section 10). To get an inode from the inode cache, the file

Figure 1 :

 1 Figure 1: Nanvix architecture.

Figure 2 :

 2 Figure 2: link() system call.

Figure 3 :

 3 Figure 3: States of a process in Nanvix.

Figure 4 :

 4 Figure 4: Scheduler queues.

Figure 5 :

 5 Figure 5: Signal stack.

Figure 6 :

 6 Figure 6: Virtual memory layout of a process in Nanvix.

Figure 7 :

 7 Figure 7: Memory region.

Figure 8 :

 8 Figure 8: Memory regions interface.

Figure 9 :

 9 Figure 9: Two-level paging scheme used in Nanvix.

Figure 10 :

 10 Figure 10: Buffer cache.

Figure 11 :

 11 Figure 11: File system layout.

Figure 12 :

 12 Figure 12: Inode Structure.

Table 1 :

 1 Most relevant system calls that are present in Nanvix.

	Category	System Call Description
		chdir	Changes the current working directory
		close	Closes a file descriptor
		chmod	Changes the file permissions
		chown	Changes the file ownership
		ioctl	Device control
	File System	link lseek	Creates a new link to a file Moves the read/write file offset
		open	Opens a file descriptor
		read	Reads from a file
		stat	Gets the status of a file
		unlink	Removes a file
		write	Writes to a file
		execve	Executes a program
		exit	Terminates the current process
	Process Management	fork getpid kill	Creates a new process Gets the process ID Sends a signal to a process
		pause	Suspends the process until a signal is received
		pipe	Creates an interprocess communication channel
		signal	Signal management

Table 2 :

 2 Simplified structure of a process in Nanvix.

	Category	Field	Description
	Context Switch Information	kesp kstack intlvl	Kernel Stack pointer Kernel Stack Interrupt Level
	File System Information	pwd ofiles tty	Current Working Directory Opened Files Output Terminal Device
	General	status	Exit status
	Information	pid, gid, uid Process, group and user IDs
	Memory	pregs	Code, data, stack and heap segment regions
	Information	pgdir	Page directory
		state	Current state
	Scheduling	counter	Remaining quantum
	Information	nice	Priority adjustment
		priority	Priority
	Signal	received	Received signals
	Information	handler	Signal handlers
	Timing	utime	User CPU Time
	Information	ktime	Kernel CPU Time

Table Directory

 Directory

	Virtual Address	Page Frame
		Physical Address
	Page Table Entry
	Entry

Nanvix does not support multiprocessor systems, thus processes are indeed not running in parallel.

Nanvix adopts the Unix's priority system, in which lower values mean higher priorities.

init is a daemon process whose job is to spawn the logging processes.

The memory region abstraction equally applies to segmentation.

Since version 1.1 Nanvix is shipped with its own utilities for sake of portability.

Gets inode of the topmost directory of a path system exports the inode get() routine. If the requested inode is in the cache, a pointer to it is immediately returned. However, if the inode is not in the cache, the kernel reads it from the disk, first evicting not-in-use inodes using a least recently used strategy if needed. Conversely, the inode put() routine is provided to release an in-memory inode, making available the correspondent slot in the inode cache. Finally, to sync the in-memory inodes with in-disk inodes, the file system provides the inode sync() routine. This call iterates over the cache, writing back to disk every inode that is dirty. The inode get() routine is handful in situations where the serial number of the target inode is known in advance. For instance, when mounting a device or reading/writing data to a file that has been already opened. On the other hand, if the serial inode number is not known, but its pathname is, one can use either inode name() or inode dname() routines. The first one retrieves the inode that matches a given pathname, and the second when gets the inode for the topmost directory in the pathname. These routines work by having the pathname to be parsed and the file system hierarchy to be traversed, differing essentially in their stop criteria.

The last two routines exported by the file system, namely inode lock() and inode unlock(), are provided for locking purposes. The first one causes the calling process to block until it acquires exclusive access to a target inode, and the second routine releases the lock that a process owns over an inode and wakes up all processes that were awaiting for this event. Having a process to call inode lock() before using and inode and inode unlock() when it is done with it enables processes to consistently operate over inodes, thus promoting the file system's integrity.

On top of the inode interface, the kernel builds higher-level abstractions and routines. A table, namely the opened file descriptors table, is used to bookkeep all files that are opened in the system. Each entry in this table stores a pointer to the underlying in-memory inode and tracks the current read/write cursor in the file. The opened file descriptors table is heavily manipulated by the open() and close() system calls. For reading/writing to a file, the kernel provides file read() and file write(). These routines take as parameters a target inode and buffer, and transparently handle a read/write request by traversing the data-block tree in the inode structure. Conversely, to add and remove entries from a directory, the file system exports the dir add() and dir remove() routines.


Hossain Soharab
email: soharab.hossain@gmail.com

Marek Shaikh

Nabendu Tabedzki
email: nabendu@ieee.org

Khalid Chaki

Saeed
email: saeed@agh.edu.pl

S H Shaikh

M Tabedzki
email: m.tabedzki@pb.edu.pl

N Chaki

K Saeed

A K Choudhury

Bengali Printed Character Recognition -A New Approach

Keywords: Bengali character, view-based algorithm, layer-based method, bounding box, unequal partition

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Character recognition has been a popular field of research for past few decades. Research, in this arena, has been done not only on Bengali but also on some other languages [START_REF] Tabędzki | Handwriting Recognition System on the basis of Toeplitz Matrices[END_REF], [START_REF] Adamski | Signature Recognition by the use of Template Matching Techniques[END_REF], [START_REF] Das | Segmentation and Recognition of Unconstrained Bangla Handwritten Numeral[END_REF], [START_REF] Mahmud | A Complete OCR System for continuous Bengali Character[END_REF]. In [START_REF] Tabędzki | Handwriting Recognition System on the basis of Toeplitz Matrices[END_REF], a method for handwriting recognition is proposed for Polish alphabet. It is based on Toeplitz matrix minimal Eigen values approach. In [START_REF] Adamski | Signature Recognition by the use of Template Matching Techniques[END_REF] a Template Matching based signature recognition algorithm is presented. In [START_REF] Das | Segmentation and Recognition of Unconstrained Bangla Handwritten Numeral[END_REF] a successful trial was made to recognize both typewritten and handwritten English and Arabic texts without thinning on the basis of region growing segmentation. In this work, however, and following the view-based approach of [START_REF] Tabedzki | New Results for View-Based Feature Extraction Method for Handwritten Words Recognition without Segmentation[END_REF], the Bengali language is studied for automatic recognition. Recognition of Bengali script has a lot of importance. Bengali is one of the most popular languages in India. All over the world more than 200 million people speak in Bengali and this is the second most popular script next to Devanagari in India. It also suggests the scripts of two other languages, Assamese and Manipuri. Bengali is the official language of Bangladesh, a neighbour of India.

Recognition of Bengali printed as well as handwritten characters [START_REF] Pal | Handwritten Bangla Compound Character Recognition using Gradient Feature[END_REF], [START_REF] Saeed | Region Growing Based Segmentation Algorithm for Typewritten and Handwritten Text Recognition[END_REF] has been a popular area of research in the arena [START_REF] Bag | Recognition of Bengali Handwritten Characters Using Skeletal Convexity and Dynamic Programming[END_REF], [START_REF] Naser | Recognition of Bangla Characters using Regional Features and Principal Component Analysis[END_REF], [START_REF] Shaikh | A View-based Approach for Recognition of Bengali Printed Characters[END_REF] of OCR for past few years as found in the literature. Research is being done on the recognition of both the basic [START_REF] Majumdar | Bengali Basic Character recognition using Digital Curvelet Transform[END_REF] and compound [START_REF] Pal | Handwritten Bangla Compound Character Recognition using Gradient Feature[END_REF] Bengali characters. Attempts have also been made in the recognition of Bengali numerals [START_REF] Das | Segmentation and Recognition of Unconstrained Bangla Handwritten Numeral[END_REF], [START_REF] Bhattacharya | Recognition of Handprinted Bangla Numerals Using Neural Network Models[END_REF]. The modern Bengali alphabet set consists of 11 vowels and 39 consonants. These characters are called basic characters. Bengali text is written from left to right. The concept of upper/lower case is missing in Bengali. Most of the Bengali characters have a running horizontal line on the upper part of the characters; this line is known as Matra.

Characters in Bengali are not alphabetical as in English (or Roman) where the characters largely have one-sound one-symbol characteristics. It is a mixture of syllabic and alphabetic characters [START_REF] Pal | Handwritten Bangla Compound Character Recognition using Gradient Feature[END_REF]. The use of modified and compound characters is also very common in Bengali. This paper presents methods for recognizing Bengali printed characters based on view-based approach. Both the top-bottom and the leftright-view-based approach have been considered. This work is an extension of [START_REF] Shaikh | A View-based Approach for Recognition of Bengali Printed Characters[END_REF]. In this paper we have considered unequal partitions of the character images. Also a set of compound characters have been considered for view-based analysis.

The rest of the paper is organized as follows: section 2 is a short review of the existing literature. Section 3 describes the major functional steps involved in the recognition process and feature extraction methods. In section 4 the concept of unequal partitioning is presented followed by the considerations for compound characters. Classification and experimental results are given in section 5.

Previous Work

Different techniques have been found in the literature for optical character recognition. The curvelet transform has been heavily utilized in various areas of image processing.

In [START_REF] Majumdar | Bengali Basic Character recognition using Digital Curvelet Transform[END_REF] a novel feature extraction scheme is proposed on the basis of the digital curvelet transform. The curvelet coefficients of an original image as well as its morphologically altered versions are used to train separate k-nearest neighbour classifiers. Output values of these classifiers are fused using a simple majority voting scheme to arrive at a final decision. In [START_REF] Dutta | Bengali Alpha-numeric Character Recognition using Curvature Features[END_REF] a method has been suggested based on curvature-based feature extraction strategy for both printed and handwritten Bengali characters. BAM (Bidirectional Associative Memories) neural network has been used in [START_REF] Syeed | Bengali Character Recognition using Bidirectional Associative Memories (BAM) Neural Network[END_REF] for Bengali character recognition. The conventional methods are used for text scanning to segmentation of a text line to a single character. An efficient procedure is proposed for boundary extraction, scaling of a character and the BAM neural network which increases the performance of character recognition are used. In [START_REF] Karim | A Modified Neural Network Learning Approach and its Application to Bengali Character Recognition[END_REF] a modified learning approach, using neural network learning for recognizing Bengali characters, has been presented. Research has been done on the recognition of handwritten Bengali characters [START_REF] Bhattacharya | On Recognition of Handwritten Bangla Characters[END_REF]. Multi-Layer Perceptron (MLP) trained by back-propagation (BP) algorithm have been used as classifier. In [START_REF] Bhattacharya | Recognition of Handprinted Bangla Numerals Using Neural Network Models[END_REF] an automatic recognition scheme for handwritten Bengali numerals using neural network models has been presented.

A Topology Adaptive Self Organizing Neural Network is first used to extract from a numeral pattern a skeletal shape that is represented as a graph. Certain features like loops, junctions etc. present in the graph are considered to classify a numeral into a smaller group. If the group is a singleton, the recognition is done. Otherwise, multilayer perceptron networks are used to classify different numerals uniquely. Hidden Markov Models (HMMs) are used for both online and offline character recognition systems for different scripts around the world. A OCR program that uses HMM, for recognition process, has been made for Bengali documents in [START_REF] Monjel | Optical Character Recognition For Bangla Documents Using HMM[END_REF]. For using HMM it is required to have a sequence of objects to traverse through the state sequence of HMM. So the features are shaped into a sequence of objects. For each character component, a tree of features is made and finally the prefix notation of the tree is applied to the HMM. In the tree, the number of child of a node is not fixed, so, the child-sibling approach is applied to make the tree. Hence the prefix notation of the tree will contain nodes in the order: root, prefix notation of the tree rooted at its child, prefix notation of the trees rooted at the child's siblings from left to right order. After that HMM is used for the recognition purpose. Attempts have also been made on methods of segmentation and recognition of unconstrained offline Bengali handwritten numerals [START_REF] Das | Segmentation and Recognition of Unconstrained Bangla Handwritten Numeral[END_REF]. A projection profile based heuristic technique is used to segment handwritten numerals. A neural network based classifier is used for classification purpose. Paper [START_REF] Datta | On Recognition of Bengali Numerals with Back Propagation Learning[END_REF] addresses various aspects of the problems associated with processing and recognition of printed and handwritten Bengali numerals. A scheme is proposed in this work for recognizing handwritten as well as printed numerals with different fonts and writing styles including noisy and occluded numerals. Polygon approximation is used to represent the contours of the letters. After that Fourier descriptors are used as shape features. The standard Multi-Layer Perceptron (MLP) augmented with MAXNET was used as a classifier. In [START_REF] Chaudhuri | A Complete Printed Bangla OCR System[END_REF] a method has been presented based on primitive analysis with template matching to detect compound Bengali characters. Most of the works on Bengali character are recognition of isolated characters. Very few papers deal with a complete OCR for printed document in Bengali. In [START_REF] Mahmud | A Complete OCR System for continuous Bengali Character[END_REF] a chain code method of image representation is used. Thinning of the character image is needless when chain code representation is used. The main difficulties in printed Bengali text recognition are the separation of lines, words and individual characters. In [START_REF] Hasan | A New Approach to Bangla Text Extraction and Recognition From Textual Image[END_REF] a new approach has been proposed to segment and recognize printed Bengali text using characteristic functions and Hamming network. A new algorithm has been proposed to detect and separate text lines, words and characters from printed Bengali text. The algorithm uses a set of characteristic functions for segmenting upper portion of some characters and characters that come under the Base line. It also uses a combination of Flood-fill and Boundary-fill algorithm for segmenting some characters that cannot be segmented using traditional approach. Hamming network is used for recognition scheme. Recognition is done for both isolated and continuous size independent printed characters. In [START_REF] Chaudhuri | A Complete Handwritten Numeral Database of Bangla -A Major Indic Script[END_REF] a study has been made on handwritten Bengali numerals.

Major functional steps

Figure 1 shows the flowchart of major functional steps which have been outlined as follows:

i) Binarization: Printed documents written in Bengali have been scanned using a flatbed scanner. Samples have also been collected using software supporting different Bengali fonts. These samples are converted to images and all the samples have been binarized.

ii) Segmentation: The documents contain Bengali text. Individual character has to be extracted from the text before applying view-based approach. Histogram of individual pixel row and columns of the text is computed. The individual lines containing many words have been segmented out from the text image using a horizontal histogram. The individual letters have been segmented out from the images of lines of text using vertical histogram.

iii) Matra Removal: The Matra is removed from top of the character. Standard imageediting software is used for doing the same. After removing the Matra, the characters without Matra is stored. View based approach is performed on these images. The importance of this phase is detailed out in section 3.1.1.

Figure 1. Flow-chart of Major Functional Steps iv) Applying Bounding Box:

The character is put into a bounding box (rectangle that most tightly contains the character) before applying the view-based approach. The bounding box may be used as an indicator of the relative positions of features in a character.

v) View-based Feature Extraction:

The features are extracted from four views of each individual letter. Additionally, the number of changes of the pixel values from whiteto-black and vice versa have been calculated for each row and column. In inner-views approach the views of partitioned image are used to extract the features. These values form the feature vector representing the particular letter. This is detailed out in section 3.1. This vector is finally fed to the classifier for classification and recognition.

Binarization

Methods for feature extraction

In this section the view-based approach is detailed out. Also the layer based approach and the concept of bounding box is described.

View-based approach

This idea was presented in [START_REF] Tabedzki | New Results for View-Based Feature Extraction Method for Handwritten Words Recognition without Segmentation[END_REF], [START_REF] Shaikh | A View-based Approach for Recognition of Bengali Printed Characters[END_REF] and [START_REF] Saeed | New Experiments On Word Recognition Without Segmentation[END_REF]. The method is based on the fact that for correct character recognition one usually needs only partial information about its shapeor contour.

The "views" of given object are examined to extract from them a characteristic vector, which describes its shape. The view is representation of the coordinates of the points lying on one of four boundaries of the object (top, bottom, left or right)it consists of pixels belonging to the contour of a word and having extreme values of x (for left and right view) or y coordinate (for top and bottom). The conventional preprocessing stage of thinning is not essential here because in this approach only the shape of the character is analyzed. However, and in some cases, as will be seen later, the thinning process helps improve the results. The binarization is required to convert the scanned image into a black-and-white one. The main feature extraction step is to take out all the characteristic points from the views. Thus, characteristic vector for top view consists of maximal values from each pixelcolumn on an image. To reduce dimensionality of obtained vectors one can introduce some form of down-sampling. In our case it is equivalent to searching for characteristic points in each view that describes the shape. In [START_REF] Tabedzki | A Method for Handwritten Word Recognition without Segmentation[END_REF] several methods of selecting these points have been explored. In the method used in this paper, characteristic values are found by dividing original vectors into n identical segments, and calculating mean value for each one. In this way four characteristic vectors describing the given letter is found. Next, these four vectors are transformed into a one vector, which describes the given letter

The top-bottom view based approach cannot be directly applied to Bengali characters. This is because most of the Bengali characters have a line known as the "Matra" on top of them. So, the top view for almost every character (except a few characters that do not have a Matra on top of them) is same. So the Matra should be removed first; after that the character without Matra can be processed for feature extraction using top-bottom view-based approach. Matra removal phase is not necessary if only lateral-view based approach is applied for feature extraction. But here both the lateral as well as top-bottom view based approaches have been applied, so removing Matra is necessary.

Figure 2 presents this process for a word "Somoy" meaning time in Bengali.

Layer-based approach

In layer based approach the number of changes of pixel values from black to white (or transitions from foreground to background) is considered. It tells whether the pixel-column (or row) contains one or several strokes, as is presented in Figure 3. This way some information about the inner shape of the letters can be obtained. For example two Bengali characters Ja and Sha have been considered here. Both the characters look exactly the same as far as the contour is concerned. The only difference is in the internal shape of the characters. Layer based approach can be applied to distinguish these letters. The same can be done for pixel rows. With the use of layer-counting (layer-view), improvements in results have been achieved for word recognition as in [START_REF] Chaudhuri | A Complete Handwritten Numeral Database of Bangla -A Major Indic Script[END_REF]. Two variations of this approach have been considered. In each pixel column the number of changes of colour from white to black and black to white is counted. The same approach is performed for the pixel rows.

When considered the logical partitioning of the image (3 and 6 partitions) the average number of colour changes in each partition is calculated and used to form a feature vector. However, that lead to very poor recognition accuracy. So, later the whole image without any partition is considered and the layer-based approach over all the pixel rows and columns of the binary image has been performed.

Inner-view approach

In order to improve the effectiveness of detection another idea was proposed. It implies the inclusion of additional information in the feature vector about the internal structure of the characters. It took the form of internal views. This is an innovative proposal used for the first time.

As with the classical view-based approach, there are also four possible viewstop, bottom, left and right. This time, however, they do not form the outer shape of the letter, but the internal one. For this purpose, the character image is divided into two parts. For example, to obtain the top and bottom views, the image is divided horizontally into lower and upper parts. Then a bottom view of the upper half and a top view of the lower one can be obtained. Similarly, for the right and left view -the internal view of the left and right halves is created. The method of characteristic vector extraction for each view does not differ from the one presented in section 3.1.1.

Handling Compound Characters

A compound character is one that is formed by clubbing more than one basic character. Examples of some compound characters in Bengali are given in Figure 4. The basic characters forming those compound characters are also shown. There are a few problems in recognizing the compound characters.

Firstly, the problem is that there is no standard segmentation method that suits for all the compound characters properly. Component basic characters may retain their shapes in the compound character. Figure 4 shows two groups of compound characters. In the first group, the shapes of the component basic characters are retained in the compound one whilst in the second group, the basic shapes of the component characters are not retained. So if the compound character is segmented properly then the basic component characters can be extracted out of it and on the basis of information of the component characters, the compound character can be identified. But as shown in Figure 4, first group, that no specific segmentation method applies well for all the compound characters. For the characters at line 1 and 2 a horizontal segmentation works well.

For the characters at line 3 and 4, a diagonal segmentation is required, whereas for the character at line 4a horizontal segmentation will be suitable.

Secondly, as shown in the second group of Figure 4, the shape of the compound characters may change significantly when two basic characters are clubbed to form it. This compound character contains no clue of the basic components. So no segmentation can be done for recognizing such characters.

Thus, the methods based on the segmentation of compound characters do not give satisfactory results for recognizing compound characters. In this paper view-based approach is applied for performing this recognition task. The idea is that the contour of each compound character is unique. So, applying view-based approach a feature vector can be formed for each of the compound characters. This feature vectors should be stored in a vector codebook database. Whenever a character has to be identified, the view-based approach is applied to it to form a feature vector. This vector is then compared with those at the codebook to find a similar match. This way a compound character can be identified.

Classification and Experimental Results

For the purpose of classification the method based on k-Nearest Neighbor (k-NN) algorithm has been used. It is a type of instance-based learning, where classification is based on closest training examples in the feature space. The training set is composed of labeled examples (feature vectors of correctly classified Bengali characters). In the classification phase, an unlabeled vector is classified by assigning the label which is most frequent among the k training samples nearest to that vector. In the present experiments distance is calculated using DTW approach [START_REF] Adamski | Signature Recognition by the use of Template Matching Techniques[END_REF], [START_REF] Salvador | Toward accurate dynamic time warping in linear time and space[END_REF].

In all experiments K-fold cross-validation method is used, so original database was randomly partitioned into K (where K = 10) equal size subsets. Classification process was then repeated k times, with each of the k subsets used exactly once as a test set, where the remaining K -1 subsets are used as training data. The results from K folds were then combined to produce recognition result estimation.

Tests were performed on the collected database of about 1000 characters. Images were binarized, cleaned of noise and prepared to recognize.

Authors performed a series of experiments, designed to allow the determination of the optimal strategy and parameters. The following table shows some sample results. In the first approach only views were used (four for each character), wherein from each view 8 points were collected giving a 32-element long feature vector. This has resulted in a rather low efficiency of about 44% characters correctly classified.

The next experiment revealed that prior character skeletonization allows for a significant improvement in efficiency. For this purpose authors used KMM algorithm [START_REF] Saeed | K3M -A Universal Algorithm for Image Skeletonization and a Review of Thinning Techniques[END_REF]. In this approach the character image was thinned to a skeleton form before applying view-based method to extract features. Thanks to this the percentage increased to 57%.

Approach 3 and 4 show an attempt to determine the optimal number of points extracted from each view. As can be seen an attempt to reduce or increase this value does not bring improvement indicating that for the studied characters, the optimal number proved to be eight points per view.

The fifth study tested the effectiveness of the layer-based approach. For this purpose the algorithm of section 3.1.2 was used, designating the number of transitions for the vertical and horizontal directions. For each of the two directions only 8 values were consideredusing the very same method of downsampling, as in the view-based approach described in section 3.1.1. The percentage is lower than that of the viewbased approach, but the attention should be paid to the smaller size of the vector as well as that both of these approaches will be used jointly.

Experiment 6 shows a novel approach used for the first time as presented in this work -it is based on the use of internal views as described in section 3.1.3. Also four views were used and 8 characteristic points were collected from each view. As can be seen, this allows for a larger percentage than the classical approach of over 60%.

The last row of the table shows the results obtained by a combination of all these approaches. In this manner, the effectiveness of recognition has reached 76.8%. The cost is obtaining a large feature vector due to the fact that all of the features of the previous studies: views, layers and inner views were used. The solution to this issue would be to carry out a prior feature selection, it would help to determine which of features are relevant to the process of classification and which may be removed.

Table 2 collects the results of the last survey (approach no 7) breaking them into some selected characters. This allows to observe the individual results of each of them. Columns of the table presents the selected letter and the results of recognition.

As can be seen, some characters were classified with efficiency exceeding 90%, while some decreases the performance. In order to determine the causes of low rate obtained for some of the characters, the results of recognition were formed into matrix of confusion, to expose most common mistakes. This revealed that some of the characters were particularly often confused with each other. Some of these pairs are shown in Table 3.

Table 3. Most common mistakes

Pairs of confused letters

ম -স গ -প ষ -য খ -থ Each of these pairs was confused with each other in at least 20% of cases. As can be seen they are actually very similar to each other and of very similar shape. Hence, the algorithm could not distinguish between them.. Further work will be aimed at more closely look at the similar pairs of characters to find specifications that allow them to differentiate and thus improve the efficiency of recognition.

Conclusions and Future Work

In this paper, the authors have proposed a new method for Bengali printed character recognition using View-based and Layer-based methods. The concept of unequal partitioning has been applied in this study. A classifier based on DTW and k-NN has been used for the experimentation purposes. Recognition accuracy of 76.8% has been achieved which is considered to be very high as the Bengali alphabets resemble handwriting rather than type writing. It contains alphabets that are cursive in nature. The proposed method therefore, will be the basis of handwritten character recognition.

The view-based approach is being applied for Bengali character recognition for the first time. The experiments show gradual improvements. The future plan is to modify the recognition engine and use a different pattern classifier like a neural network to study the performance of the proposed method.

  Recognition -A New Approach vi) Classification: The feature vectors are classified with the help of Dynamic Time Warping distance, k-NN and Ensemble of Classifiers in the present experiment. This has been explained in section 5.

Figure 2 .

 2 Figure 2. (a) The Bengali word Somoy with Matra. (b) Somoy after removing Matra, (c) The letters of the word segmented and 3 horizontal partition is done. Also characteristic points have been marked on the left and right contour in each segment for Lateral view based consideration.

Figure 3 .

 3 Figure 3. Number of transitions for the letters Ja and Sh.

Figure 4 .

 4 Figure 4. Compound characters and segmentation for extracting the individual basic component characters.

Table 1 .

 1 Results of classification

	Test Views Layers Inner Views KMM Features Recognition rate
	1	✔				32	43.7%
	2	✔			✔	32	57.2%
	3	✔			✔	40	56.5%
	4	✔			✔	24	55.9%
	5		✔		✔	16	46.2%
	6			✔	✔	32	62.7%
	7	✔	✔	✔	✔	80	76.8%

Table 2 .

 2 Results of classification for individual letters

	Letter	Recognition rate
	ঔ	95%
	ঢ়	90%
	ড়	85%
	ড	70%
	গ	70%
	ন	60%
	ম	50%
	ঘ	50%
	প	40%
	খ	35%
	স	25%
	Overall	76.8%

Acknowledgement. This work was supported by Bialystok University of Technology grant S/WI/2/2013.