DRAFT. Paternoster of Programmers Reloaded. Dr. Norbert Bátfai. March 9, C, C++, Java, Python and AspectJ Case Studies

A FT

Paternoster of Programmers Reloaded C, C++, Java, Python and AspectJ Case Studies

Dr. Norbert Bátfai

D R

March 9, 2014

Paternoster of Programmers Reloaded by Dr. Norbert Bátfai Edition Lecture notes, version 0.1.14 Published 2014 Copyright © 2012, 2013, 2014 Norbert Bátfai, PhD

FT

The lecture notes were supported by the TÁMOP-4.1.2.A/1-11/1-2011-0103 project. The project has been supported by the European Union, co-financed by the European Social Fund.

D

R

A

The author endeavors to maintain and to keep the author’s editions of this book, and the others in the series up-to-date. These author’s editions can be found at the page http://www.inf.unideb.hu/~nbatfai/konyvek/.

ii

Contents 1

Introduction 1.1 The Paternoster of Programmers . . . . . . . . 1.2 About these lecture notes . . . . . . . . . . . . 1.2.1 The environment of this book . . . . . . 1.2.2 The courses of the book . . . . . . . . . 1.2.2.1 High-Level Programming 1.2.2.2 Other courses . . . . . . . . . . 1.2.3 About the author . . . . . . . . . . . . . 1.2.4 About the peer reviewers . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Languages . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . 1 . . . . . .

C Case Studies

2

MINIX kernel hacking: analysing microkernel’s IPC 2.1 Introduction: the MINIX which acted as the detonator of open 2.1.1 The MINIX microkernel and the MINIX IPC . . . . . . 2.2 The installation of MINIX3 system . . . . . . . . . . . . . . . . 2.2.1 Installation in VirtualBox . . . . . . . . . . . . . . . . . 2.2.2 The first MINIX kernel hacking . . . . . . . . . . . . . . 2.3 Analysis of MINIX3 IPC . . . . . . . . . . . . . . . . . . . . . . 2.3.1 A solution with modifying the PCB . . . . . . . . . . . 2.3.2 Another solution by introducing a new system call . .

4

II 5

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

1 3 3 3 4 4 5 5 5

7

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

11 13 13 17 17 20 24 24 31

GNU/Linux kernel hacking: making entries in the /proc virtual file system 3.1 The monolithic kernel of Linux . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Linux kernel compiling . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Kernel modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Making entries in the /proc virtual file system . . . . . . . . . . . . . . . 3.2.1 Creating the module in VirtualBox. . . . . . . . . . . . . . . . . . . . 3.2.1.1 „Celebrating” the source code . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

37 39 39 46 48 48 51

Berkeley socket API, Sys V IPC and I/O multiplexing 4.1 Berkeley socket API, Sys V IPC, I/O multiplexing . . . . . . . . 4.2 A simple client/server sample . . . . . . . . . . . . . . . . . . . . 4.2.1 The client side . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 The server side . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2.1 Discussing the source code of the server side . 4.2.2.2 Protecting the memory of the processes . . . . 4.2.3 Testing of the example . . . . . . . . . . . . . . . . . . . . 4.2.3.1 Testing on localhost . . . . . . . . . . . . . . . . 4.2.3.1.1 Compiling and running the server . . 4.2.3.1.2 Compiling and running the client . . . 4.2.3.1.3 There is some disturbance in the force 4.2.3.2 Testing on two machines . . . . . . . . . . . . . 4.2.3.2.1 Portability . . . . . . . . . . . . . . . . 4.2.3.2.2 Testing on a virtualized machine . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

57 59 59 59 62 66 71 72 72 72 73 73 74 74 77

D R

3

. . . . . . . .

A FT

I

. . . . . . . .

source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

C++ Case Studies

79

A simplified protocol of 2D RCSS 5.1 Emasculation of the AI-based simulation model of RCSS . . . . . . . . . . . . . . . . . . . 5.1.1 Introducing a new positioning command for RCSS client protocol . . . . . . . . . 5.1.1.1 Testing of the newly introduced command . . . . . . . . . . . . . . . . . iii

83 85 85 85

CONTENTS

5.2

5.3 5.4

7

V 8

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

88 89 90 92 95 97 99 99 99 102 104 105 105 105 106

109

Community consciousness net 111 6.1 The Seventh Eye mobile game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.1.1 The Seventh Eye and the „Community consciousness net” . . . . . . . . . . . . . . 113

Python Case Studies

117

A virtual librarian 121 7.1 Kálmán Könyves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 7.1.1 The structure of the AIML files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

AspectJ Case Studies

137

What is the mother tongue of the object oriented programs? 141 8.1 An analytical weaving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 8.2 A robot soccer weaving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

Bibliography 8.3 8.4 8.5 8.6 8.7 8.8 8.9

Quotes . . . . . . . Operating systems Programming . . . Football . . . . . . . Math . . . . . . . . For children . . . . Background . . . .

D

VI

. . . . . . .

. . . . . . . . . . . . . . .

FT

IV

. . . . . . .

A

6

Java Case Studies

R

III

5.1.1.2 The response of the simplified server . . . . . . . . . . . . . . . The team called Debrecen Great Forest FC++--> . . . . . . . . . . . . . . . . . . . 5.2.1 The implementation of the throw-in . . . . . . . . . . . . . . . . . . . . . . 5.2.1.1 Testing the throw-in . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 The introduction of the tactical lineups . . . . . . . . . . . . . . . . . . . . 5.2.2.1 The implementation of the corner kick . . . . . . . . . . . . . . . 5.2.2.1.1 Testing the corner kick . . . . . . . . . . . . . . . . . . . 5.2.2.1.2 The evaluation of the team Debrecen Great Forest FC++ The team called Debrecen Deep Forest FC++ . . . . . . . . . . . . . . . . . . . . . 5.3.1 The evaluation of the team Debrecen Deep Forest FC++ . . . . . . . . . . The team called Debrecen Round Forest FC++ . . . . . . . . . . . . . . . . . . . . 5.4.1 The additional command line arguments of the simplified server . . . . 5.4.1.1 The response of the simplified server . . . . . . . . . . . . . . . 5.4.1.2 Receiving the response of the simplified server . . . . . . . . . . 5.4.2 Introducing the usage of the online coach . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

145 . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

Index

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

147 147 147 149 149 149 149

151

iv

List of Figures MINIX kernel hacking: analysing microkernel’s IPC 2.1 SEND and RECEIVE message passing primitives. . . . . . . . . . . . . . . . . . . . 2.2 The sender is blocked while the receiver is not ready to receive. . . . . . . . . . . . 2.3 The receiver is blocked while the message is not being received. . . . . . . . . . . . 2.4 Giving the name of the MINIX system that will be installed. . . . . . . . . . . . . . 2.5 Launching the virtualized MINIX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Starting the installation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Loading the system from disk. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 We accept defaults, mutatis mutandis. . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 MINIX starts from hard disk now. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Opening the source file kernel/main.c with vi. . . . . . . . . . . . . . . . . . . . 2.11 The modification of the function announce() in the kernel/main.c source file. 2.12 The booting of the newly compiled kernel. . . . . . . . . . . . . . . . . . . . . . . . 2.13 The message from the kernel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.14 The first step of managing packages. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.16 Printing out the size of the PCB and the size of the process table. . . . . . . . . . . . 2.17 Read the size of the PCB and the size of the process table. . . . . . . . . . . . . . . . 2.18 Extending the MINIC PCB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.19 Counting massages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.20 The kernel process table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.21 Connecting a debug function to a function key. . . . . . . . . . . . . . . . . . . . . . 2.22 The beginning of the function uzenetszam_dmp. . . . . . . . . . . . . . . . . . . . 2.23 The midst of the function uzenetszam_dmp. . . . . . . . . . . . . . . . . . . . . . . 2.24 The end of the function uzenetszam_dmp. . . . . . . . . . . . . . . . . . . . . . . . 2.25 The prototype of the function uzenetszam_dmp. . . . . . . . . . . . . . . . . . . . 2.26 Displaying the IPC matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.27 List of the non-empty slots from the process table. . . . . . . . . . . . . . . . . . . . 2.28 An array to store the „IPC matrix”. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.29 Incrementing of the appropriate element of the uzenetszam array. . . . . . . . . . 2.30 This is the uzenetszam that we defined in the server layer. . . . . . . . . . . . . . 2.31 Usage of the sys_getmatrix system call that will be newly developed. . . . . . . 2.32 Printing the matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.33 Defining the sys_getmatrix macro. . . . . . . . . . . . . . . . . . . . . . . . . . . 2.34 The GET_MATRIX macro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.35 Supplying the do_getinfo system call. . . . . . . . . . . . . . . . . . . . . . . . . . 2.36 Displaying the IPC matrix in the second solution. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14 15 16 17 18 18 19 19 20 20 21 22 22 23 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35

GNU/Linux kernel hacking: making entries in the /proc virtual file system 3.1 Downloading the kernel sources. . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Making the .config with command make menuconfig. . . . . . . . . . . 3.3 Setting the option Kernel .config support. . . . . . . . . . . . . . . . 3.4 Starting the compiling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Starting the installation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 The version of the running kernel. . . . . . . . . . . . . . . . . . . . . . . . 3.7 The updated GRUB menu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 The new kernel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Switching off the option Enable loadable module support. . . . . . 3.10 The size of the kernel image. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 The circular doubly linked list of PCBs in Linux. . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

40 41 42 43 44 45 45 46 47 48 51

D R

A FT

2

3

v

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

LIST OF FIGURES

5

75 76 77

A simplified protocol of 2D RCSS 5.1 The LightFC++ team assembles before kick off using the move command. . . . . . . . . . 5.2 After kick off the players move using the pos command. . . . . . . . . . . . . . . . . . . . 5.3 Testing the throw-in: player 11 kicks the ball across the touch line. . . . . . . . . . . . . . 5.4 Testing of the throw-in: player 4 starts to move towards the ball. . . . . . . . . . . . . . . 5.5 Testing the throw-in: player 4 is closer than 30 meters. . . . . . . . . . . . . . . . . . . . . 5.6 Testing of the throw-in: player 4 has just arrived to the ball. . . . . . . . . . . . . . . . . . 5.7 Testing of the throw-in: player 4 passes the ball to player 3. . . . . . . . . . . . . . . . . . 5.8 Testing the throw-in: the ball is moving towards player 3. . . . . . . . . . . . . . . . . . . 5.9 The 4-4-2 formation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10 Corner kick formations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.11 Player 3 and player 6 should go to the ball. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.12 An opposing player gains possession of the ball. . . . . . . . . . . . . . . . . . . . . . . . . 5.13 A portion of the soccerwindow2’s log file. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.14 The Debrecen Round Forest FC++’s team logo in the soccerwindow2 and the rcssmonitor.

87 88 93 93 94 94 95 95 96 97 100 100 105 108

Community consciousness net 6.1 The starting icon of the Seventh Eye. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.2 The splash screen of the Seventh Eye. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.3 The main menu of the Seventh Eye. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

D

R

A

6

Berkeley socket API, Sys V IPC and I/O multiplexing 4.1 Compiling the client and the server. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Running the client and the server. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Checking the results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

FT

4

LIST OF FIGURES

vi

List of Examples . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

A FT

Number of processes . . . . . . . . . . . . . . . . . . . . The size of the PCB . . . . . . . . . . . . . . . . . . . . . Non-empty slots . . . . . . . . . . . . . . . . . . . . . . . The contents of the PCB . . . . . . . . . . . . . . . . . . Playing the game with the current macro . . . . . . . Drawing a memory map . . . . . . . . . . . . . . . . . . 30 processes, with using a paper and pen . . . . . . . . Placing a player beside a goalpost . . . . . . . . . . . . Free kicks . . . . . . . . . . . . . . . . . . . . . . . . . . . Do not pass backward . . . . . . . . . . . . . . . . . . . A good starting . . . . . . . . . . . . . . . . . . . . . . . Create the your own XPM team logo . . . . . . . . . . . Running the Seventh Eye on a real mobile phone . . . . The client side of the „Community consciousness net” The server side of the „Community consciousness net” A community-based exercise . . . . . . . . . . . . . . . A community portal based on the mental fingerprints . Kálmán Könyves on IRC using the Program W . . . . . Kálmán Könyves on the web using the Program D . . Create your own chatterbot . . . . . . . . . . . . . . . . Weaving this aspect into ALICE . . . . . . . . . . . . . . Try this AspectJ aspect yourself . . . . . . . . . . . . . .

D R

2.1 2.2 2.3 3.1 3.2 3.3 4.1 5.1 5.2 5.3 5.4 5.5 6.1 6.2 6.3 6.4 6.5 7.1 7.2 7.3 8.1 8.2

vii

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

25 26 30 51 55 56 60 97 99 103 104 107 113 114 114 114 115 125 126 134 143 144

FT

A

R

D

Dedication

D R

A FT

This book is dedicated to my acquaintances on social networks.

ix

FT

A

R

D

Preface

D R

A FT

The book that the dear reader is holding in his hands shows seven more or less well designed greater or smaller programming case studies. The level of elaboration of the examples also depends on the course in which the given example is taught. In the case of the subjects of the first three semesters of BSc studies, for example, for the course High level programming languages 1-2, the case studies are highly developed. In contrast, in the case of the latter subjects, such as C, C++ Case Studies, Program ming in GNU/Linux environment, Java Case Studies and Mobile Programming only the specification of the tasks is dominant. Topics of the case studies are scattered in a broad spectrum, because C, C++, Java, Python and AspectJ examples will be shown. Even for this reason alone these lecture notes are not regarded as a programmed introduction to a given particular field of information technology. Let’s see the first case study about MINIX. For the understanding of this, the reader must be familiar with the textbook [OS]. The MINIX case study and this Tannenbaum book are very closely linked, because the case study itself is a solution of an exercise of the book [OS]. In other cases the link between the special literature and our lecture notes is not so close. However, even in these cases, close relations can be found in the environment of these notes. For example, here we only briefly outline the structure of the famous RCSS team Agent2D [HELIOS], because the detailed introduction can be found in the book entitled Mesterséges intelligencia a gyakorlatban: bevezetés a robotfoci programozásba, http://www.inf.unideb.hu/~nbatfai/konyvek/MIRC/mirc.book.xml.pdf, [MIRC]. But, we attach great importance to developing an our own RCSS team, which has been started from the sampleclient of rcssserver, therefore this example is well-developed here. We can also find such example that was developed mainly in the environment of these notes. For example, the developing the Sevent Eye case study can be found in the book Mobil programozás, Nehogy már megint a mobilod nyomkodjon Téged! http://www.inf.unideb.hu/~nbatfai/konyvek/MOBP/mobp.book.xml.pdf, [MOBP]. Finally, it may be noted that this work can be regarded as a continuation and an extension of the lecture notes Programozó Páternoszter [PP].

xi

FT

A

R

D

Chapter 1

D R

A FT

Introduction

1

FT

D

R

A

Abstract We are not in a difficult situation when we need to write the introduction to this book, because the „original” Paternoster of Programmers can be a good muse for this, where in a minimalist style, the Éric Lévénez’s timelines were mentioned. Now, we will try to give a more pathetic one.

CHAPTER 1. INTRODUCTION

1.1. THE PATERNOSTER OF PROGRAMMERS

„Facebook is not your friend.” —Richard Stallman stallman.org/facebook.html

1.1

The Paternoster of Programmers „A lot of people misinterpret that, as if I don’t care about revenue or profit or any of those things. But what not being just a company means to me is not being just that — building something that actually makes a really big change in the world.” —Mark Zuckerberg [FBB] David Kirkpatrick: The Facebook Effect: The Inside Story of the Company That Is Connecting the World

A FT

On the one hand, the background to the name Paternoster is the metaphor that anybody can travel some floors. It means exactly that the reader can choose an arbitrary task of current interest from the wide spectrum of the tasks of the book and is able to reproduce the solution that is also fully explained in the book Paternoster. On the other hand, the Latin name Pater noster has distinctly religious overtone, because it means the Lord’s Prayer. This direction is also confirmed by the fun question asked in the lab sessions „Who can celebrate the source code”. The basic message of the usage of the name paternoster is that programmers must program every day. But also there is one other motivation... The great ones of science give meaning to intuitive notions such as • changing (Newton, 1643-1727, mathematics, physics) • infinity (Cantor, 1845-1918, mathematics)

• space and time (Einstein, 1876-1955, physics).

• computability (Turing, 1912-1954, informatics).

D R

The programming also has its own legendary hackers like Richard Stallman, Mark Zuckerberg or Linus Torvalds. But who will be the next genius who is able to give meaning to the following exciting notion standing on the shoulders of the giants. And what will be the next concept? The intuitive notion of love was reinterpreted by Jesus in the New Testament, but it has not still been developed deductively, in sense that it has no mathematical background. I believe, the most promising candidates are imagination and reality. This was the reason why the Penrose-Hameroff „Orch OR” model of consciousness was mentioned in the „original” Paternoster of Programmers [PP] as part of the introduction to quantum informatics. Many programmers know the feeling that we really ought to write a good computer program. The root of this is that the programmers can create whole worlds in their programs. In this sense, beginner programmers have already participated in a sort of a genesis. It may be actually true for only a few professions. Programming something is a very constructive process, as Chaitin said in [METAMATH] „you understand something only if you can program it”. Based on Turing’s work on computing machinery, in my humble opinion, programmers may do the next scientific conceptual breakthrough. For example, to define random infinite sequences of 0 and 1 is a hard mathematical statistical issue, but the same result is achieved, relatively easily, by using the algorithmically complexity. When reading this book, it is important for dear readers to keep in mind that neither this book nor other books can give the excitement of writing programs. This book can be only the preliminary step in knowing the real nature of programming. First, try the examples in the book, then write your own modifications to these examples. Certainly you must work on real computers from the start of reading the book.

1.2

About these lecture notes

1.2.1

The environment of this book

This book has been continuously improved together with other books in the following series • Bátfai Norbert: Programozó Páternoszter http://www.inf.unideb.hu/~nbatfai/ProgramozoPaternoszter.pdf, [PP]. 3


1.2. ABOUT THESE LECTURE NOTES

• Bátfai Norbert, Juhász István: Javát tanítok, Bevezetés a programozásba a Turing gépekt˝ol a CORBA technológiáig http://www.tankonyvtar.hu/hu/tartalom/tkt/javat-tanitok-javat, [JAVATTANITOK]. • Bátfai Norbert: Mobil programozás, Nehogy már megint a mobilod nyomkodjon Téged! http://www.inf.unideb.hu/~nbatfai/konyvek/MOBP/mobp.book.xml.pdf, [MOBP]. • Bátfai Norbert: Mesterséges intelligencia a gyakorlatban: bevezetés a robotfoci programozásba http://www.inf.unideb.hu/~nbatfai/konyvek/MIRC/mirc.book.xml.pdf, [MIRC].

• Bátfai Norbert: Párhuzamos programozás GNU/Linux környezetben: SysV IPC, P-szálak, OpenMP http://www.inf.unideb.h ~nbatfai/konyvek/PARP/parp.book.xml.pdf, [PARP]. • Bátfai Norbert: Programozó Páternoszter újratöltve: C, C++, Java, Python és AspectJ esettanulmányok http://www.inf.unideb.hu/~nbatfai/konyvek/PROP/prop.book.xml.pdf (ez a jelen könyv).

FT

• Bátfai Norbert et al.: The Yearbook of the Programmers of University of Debrecen http://sourceforge.net/projects/udprog/, [UDPROG]. All these (only Hungarian language) books in this series try to support each other with background information and know-how. It is not too hard to organize because these books contain many common programming themes. Moreover, in many cases, it occurs that an example of one book is further developed in another one.

1.2.2

The courses of the book

1.2.2.1

A

In this section, we briefly introduce the courses that are based on using this book. High-Level Programming Languages 1

R

This is a fundamental and the first hard core Programming class on the software engineering B.Sc. at University of Debrecen. The programming tasks for this course can be found in an exercise workbook entitled The Yearbook of the Programmers of University of Debrecen. It can be found on Sourceforge under the project name udprog that contains the book itself in DocBook 5.1 and a git repository to maintain the source codes of solutions of exercises. But some of the exercises of udprog are developed in details here, in the present lecture notes.

AVAILABILITY OF THE SOURCE CODES AND THE BOOK ITSELF

D

In the spirit of „Release Early, Release Often” [KATEDRALIS], these lecture notes have already been downloadable since the beginning of its writing. It can be downloaded in DocBook XML 4.4 source format and in some other formats such as PDF and EPUB as well from the author’s homepage. The source codes were copied from this book itself for testing, so all programs will work properly, at least in theory. In addition, the usage of the source codes is shown in detail for all examples.

T HE EVOLUTION OF THE LECTURE NOTES This book is an informatics one so its basic nature is changing. Therefore we are continuously maintaining it as an author’s edition at the page http://www.inf.unideb.hu/~nbatfai/konyvek/.

4


1.2.2.2

1.2. ABOUT THESE LECTURE NOTES

Other courses

The examples of these lecture notes can be naturally used in other courses. For example, in the author’s (only Hungarian language) courses, by the following breakdowns of exercises: • C, C++ esettanulmányok (PTI, GI M.Sc. lab), MINIX kernel IPC exercise, Linux kernel module exercise. • Programozás GNU/Linux környezetben (PTI, GI M.Sc. lecture and lab), • Java esettanulmányok (PTI, GI B.Sc. lab), • XML, HTML (PTI B.Sc. lab), • Mobil programozás (PTI, GI B.Sc. lab). • Magas szint˝ u programozási nyelvek 2 (PTI, MI, GI B.Sc. lecture and lab)

About the author

A FT

1.2.3

D R

Norbert Bátfai is working as an assistant professor in the Faculty of Informatics at the University of Debrecen, Hungary. He received his M.Sc. (summa cum laude) in Computer Science in 1998 at the Kossuth Lajos University (KLTE), Debrecen, Hungary. In 1999, he won the first prize in the Java Programming Contest organized by Hungarian Java Alliance: Sun, IBM, Oracle, Novell and IQSoft. In 2004, his company won the first prize in the Hungarian Mobile Java Developer Contest organized by Sun Hungary and Nokia Hungary. In 2008, the Hungarian Chief Information Officers’ Association selected him as an IT trainer of the year. He received the Ph.D. degree in 2011. He won the Pollák-Virág award from Scientific Association for Infocommunications Hungary in 2012.

1.2.4

About the peer reviewers

András Keszthelyi, PhD., [email protected], Óbuda University. Ildikó Novák, [email protected], private teacher, http://www.angolora.hu.

5

FT

A

R

D

A FT Part I

D R

C Case Studies

7

FT

A

R

D

This part is divided into three chapters. • In the first chapter we solve a MINIX kernel exercise. • In the next chapter we are going to show how to create entries to Linux /proc virtual file system from an our own kernel module.

D R

A FT

• Finally, in the last chapter, we present a parallel network server that is based on I/O multiplexing and use shared memory as IPC.

9

FT

A

R

D

Chapter 2

D R

A FT

MINIX kernel hacking: analysing microkernel’s IPC

11

FT

Abstract In this chapter we have made a lifelong friend with a beautifully simple microkernel called MINIX. We solve an exercise of Tanenbaum and Woodhull’s operating systems book, • first with the modification of a part of PCB (Process Control Block) defined in proc.h, • then with the creation of a new system call.

D

R

A

First of all we setup a MINIX system and we show how to compile the MINIX kernel.

CHAPTER 2. MINIX KERNEL HACKING: . . .

2.1. INTRODUCTION: THE MINIX WHICH . . .

„Re 2: your job is being a professor and researcher: That’s one hell of a good excuse for some of the brain-damages of minix.”

—Linus Benedict Torvalds Linus-Tanenbaum vita

Introduction: the MINIX which acted as the detonator of open source

A FT

2.1

Eric Steven Raymond (esr) changed the term free software to open source in The Cathedral and the Bazaar in 1998. More than ten years back, the MINIX had been released in 1987, so obviously it was not open source.

GNU GPL

It may be noted that the first version of GNU GPL was released in 1989 and the first Linux had already been licensed under GNU GPL version 2, released in 1991.

D R

At the beginning of the informatics profession, the C source codes of UNIX systems could have been used in university courses, but it lasted only a short period of time due to UNIXs had become a very valuable product quickly and then it was no longer possible to teach the operating systems in its C source form. The MINIX was born in this environment. The purpose of it was specifically to allow the usage of the source code of a UNIX-like operating system in education again. From this aspect, the MINIX can be regarded as a pioneer of open source operating systems and, ultimately, we can say that the open source was brought into existence by the closing of the source code [OS3].

2.1.1

The MINIX microkernel and the MINIX IPC

The IPC (Inter-Process Communication) determines a communication method in which programs can exchange data with each other. There are several IPC mechanisms, from pipes through anonymous, local and network sockets to using shared memory (from these methods semaphore arrays and the shared memory will be used in the third case studies). The MINIX IPC is based on the message passing. The massage passing takes place between two appropriately synchronised (by the rendezvous principle) processes, so we would not buffer the messages [OS], [OS3], as shown in the following figures. 13



D

R

A

FT

Figure 2.1 SEND and RECEIVE message passing primitives.

14



D R

A FT

Figure 2.2 The sender is blocked while the receiver is not ready to receive.

15



D

R

A

FT

Figure 2.3 The receiver is blocked while the message is not being received.

16


2.2

2.2. THE INSTALLATION OF MINIX3 SYSTEM

The installation of MINIX3 system

2.2.1

A FT

There is a great experience for speed lovers to use the MINIX installed on a primary partition, but it is simpler if the first encounter with MINIX takes place on a virtualized machine. So we are going to install MINIX3 in VirtualBox. For example, let’s choose the latest development snapshot image minix3_2_1_ide_20131118.iso, that should be written to a CD disk, but it is a better way to mount this ISO image directly.

Installation in VirtualBox

D R

Figure 2.4 Giving the name of the MINIX system that will be installed.

Creating a virtual machine in VirtualBox is a very simple, but necessary subtask. After some clicks with using the default settings the new virtual MINIX system will be launched soon. 17



FT

Figure 2.5 Launching the virtualized MINIX.

A

At first startup, we must give from where we want to boot. All we have to do is to choose the downloaded image file.

D

R

Figure 2.6 Starting the installation.

From this point we have to give some settings that must be applied mutatis mutandis. 18



A FT

Figure 2.7 Loading the system from disk.

We must follow the instructions which appeared on the screen: the installation will start after we have logged in as root and entered setup.

D R

Figure 2.8 We accept defaults, mutatis mutandis.

During the next installation steps we may accept the defaults by pressing Enter, mutatis mutandis. Then (after unmounting the installer disk image in the menu item Devices/CD/DVD Device) we are able to boot the new MINIX system from the hard disk. 19



FT

Figure 2.9 MINIX starts from hard disk now.

In the next section we are going to take possession of the newly installed MINIX.

The first MINIX kernel hacking

A

2.2.2

The first kernel compilation is an obligatory task for all students. Let’s do it together now! Using the command cd /usr/src we enter the directory that contains the MINIX kernel-tree. Then we open the source file kernel/main.c with vi editor. The usage of vi is not masochism, because the installed MINIX has no other editors now.

D

R

Figure 2.10 Opening the source file kernel/main.c with vi.

20



In this source file, search for the function announce().

A FT

/*===========================================================================* announce * * *===========================================================================*/ static void announce(void) { /* Display the MINIX startup banner. */ printf("\nMINIX %s.%s. " #ifdef _VCS_REVISION "(" _VCS_REVISION ")\n" #endif "Copyright 2012, Vrije Universiteit, Amsterdam, The Netherlands\n", OS_RELEASE, OS_VERSION); printf("MINIX is open source software, see http://www.minix3.org\n"); printf("nORBi a kernelben\n"); printf("%c%s",0x1B,"[47;30m"); }

D R

Figure 2.11 The modification of the function announce() in the kernel/main.c source file.

All we did was to write a message during booting. The Hungarian language message nORBi a kernelben roughly means „the author is in the kernel” that is similar to a „Hello, World!„ message from the kernel. This message will be printed in boot time. In addition, the video mode of the terminal is changed to gray background and black foreground. The description of the used ANSI escape codes, for example, can be found in Wikipedia. After saving the source (using Shift+zz key combination in vi) the make install command compiles the kernel sources, then the system must be rebooted by the command shutdown -r. 21



FT

Figure 2.12 The booting of the newly compiled kernel.

A

In the case of the newly compiled kernel we can see the message from the kernel and the changed video mode as well.

D

R

Figure 2.13 The message from the kernel.

22



I NSTALLING THE PACKAGES Handling packages and the packages themselves are always changing... At first in Minix3, we could use packman package manager program and for example the emacs editor could be installed from package. At this moment MINIX’s package manager is pkgin and emacs cannot be installed from package. Before listing the available packages we must enter the command pkgin update, after this we are able to choose from packages using command pkgin av|more.

D R

A FT

Figure 2.14 The first step of managing packages.

C USTOMIZE Y OUR M INIX !

For example, I like to set the bash’s PS1 environment variable to show the host name, the user name and the working directory. I usually add the following lines to the bottom of the .profile file.

export PS1="\[\033[47;30m\][minix@\u]\w > " clear bash exit If we have already set the video mode in kernel, we do the same in the shell too. Here we may notice that using .bashrc to set PS1 is a more robust solution than using

.profile export PS1="\[\033[47;30m\][minix@\u]\w > " clear because in this case the make world will not delete this file.

23


2.3

2.3. ANALYSIS OF MINIX3 IPC

Analysis of MINIX3 IPC

The examples of this section are the solutions of exercise 44 on page 219 of book [MINIX3_OS_BOOK]. The exact wording of the exercise, cited from the book [MINIX3_OS_BOOK], is the following: „Add code to the MINIX 3 kernel to keep track of the number of messages sent from process (or task) i to process (or task) j. Print this matrix when the F4 key is hit.”

2.3.1

FT

In the author’s Operating System courses between 2008 and 2010, the solutions of this task were used as typical examples to illustrate the Minix kernel programming. At that time, the Minix kernel was 3.1, and our students were helped to solve this exercise by the following notes: DEIK_MIPPOS_2008tavasz_BN_KiemeltOttoni_O But remember, Minix is a living system, its code is changing rapidly, and therefore we may find several points, in this linked document, where the source code has already changed. This is a common phenomenon in informatics. For example, being restricted to Minix only, in the Minix book we can read about managing penalty points in sched() and we can see it in source code in the appendix of the book, but it is not included in the current version of the Minix kernel.

A solution with modifying the PCB

A

In this section we are working with MINIX 3.2.1. At the time of the writing of this book, it is the current version and it has just been installed in the section „The installation of MINIX3 system”

R

The PCB is an abstraction of the processes of the operating system, which is typically realised as a C structure. In Minix this structure is the struct proc that is defined in kernel/proc.h source file. The process table in Minix is simply a structure array of NR_TASKS + NR_PROCS PCB elements.

A CQUIRING ROUTINE

D

If you have no experience in Minix kernel programming we suggest that you should suspend the elaboration of this example and first start by solving the following exercise.

300 processes

When you log into the machine a special process called the shell will be created. If you enter a command in the shell, a (child) process will be created to execute the command. Web servers may fork processes to handle client requests and the list goes on. Many situations can be listed in which processes play significant roles. Actually, it is not suprising because processes are abstractions of computer programs. But it is obvious that the number of processes is limited by the size of the process table array anyway. Therefore, it is a legitimate exercise to increase the size of the process table: set the number of possible processes to 300 (from 256). We may set the value of NR_PROCS in the source file include/minix/sys_config.h

1. Set the value of NR_PROCS to 300 from 256. 24



A FT

Figure 2.15

2. After setting the NR_PROCS, it will be interesting to see the size of the process table. It can be done easily by following the previous exercise in Section The first MINIX kernel hacking.

D R

Figure 2.16 Printing out the size of the PCB and the size of the process table.

Example 2.1 Number of processes We have also done this exercise ourselves. After the above two steps we can see in the next figure that the size of the PCB is equal to 1664 bytes and the size of the process table is 507520 (=1664*(5+300)). If the reader completes this exercise by himself/herself, he or she will see that the result will be different due to the fact that we have already used a modified version of PCB. Because our PCB has already contains a vector in which the number of elements is dependent on the value of NR_PROCS too. 25



FT

Figure 2.17 Read the size of the PCB and the size of the process table.

Example 2.2 The size of the PCB Print the size of the PCB and the size of the process table from kernel. This exercise was solved as an implicit part of the previous exercise.

A

Returning to the original exercise, the MINIX PCB is being extended with an array of integers (called in Hungrian uzenetszam that means the number of messages). The i-th element of this array says how many messages were sent to the i-th process.

D

R

Figure 2.18 Extending the MINIC PCB.

In principle, we know where to store the number of sent messages, now we are going to program the counting procedure itself. ++(caller_ptr->uzenetszam[dst_ptr->p_nr + NR_TASKS]);

The appropriate element of the uzenetszam array in the caller’s PCB is being incremented. Here, it is necessary to add + NR_TASKS to the array index because the numbering of processes starts from -NR_TASKS. 26



To avoid complication (in the first approach), this increment statement has been placed into the source file kernel/proc.c, into the begining of the function mini_send.

A FT

Figure 2.19 Counting massages.

We have already mentioned that the numbering of processes starts from -NR_TASKS. It can be seen not only in the kernel sources but also if you press F1 key:

D R

Figure 2.20 The kernel process table.

In GNU/Linux systems, the /proc virtual file system serves for monitoring the running kernel. Minix kernel has no such tool like this. We can obtain information about the running kernel over the Information Server (is), which is located in the server part of the Minix microkernel architecture. If we are going to debug the running kernel (in our case to print out the added PCB vectors), we need to use Information Server. We can link debug functions to function keys in the source file servers/is/dmp. c, right now to the F4. 27



FT

Figure 2.21 Connecting a debug function to a function key.

A

The debug function uzenetszam_dmp first prints the process names of the non-empty slots of the process table as a header line. We may have noticed that we are in the server layer of the kernel tree to be more precise we have worked in the is server, where to the process table is copied from the bottom layer of the kernel by the system call sys_getproctab. The uzenetszam_dmp function works this copied instance of the process table, because the bottom layer of the kernel cannot be seen from the layer of servers.

D

R

Figure 2.22 The beginning of the function uzenetszam_dmp.

After the header line, the next lines will contain the vectors of non-empty PCBs. 28



A FT

Figure 2.23 The midst of the function uzenetszam_dmp.

At the end of printing the matrix, the mennyitol (in English it means „from number”) variable will be incremented by 21, it implements a kind of paging for displaying the „IPC matrix”. To be more precise, if the F4 key has been pressed, a submatrix of size 22x9 will be printed from the actual value of mennyitol.

D R

Figure 2.24 The end of the function uzenetszam_dmp.

Since the function uzenetszam_dmp is also used outside of the source file servers/is/dmp_ kernel.c, we must declare it, therefore we give its prototype in the source file servers/is/proto.h. 29



FT

Figure 2.25 The prototype of the function uzenetszam_dmp.

A

After this, all we have to do is to compile the kernel, then to boot the new kernel. And after the login, if we press F4 the following debug screen appears:

D

R

Figure 2.26 Displaying the IPC matrix.

Example 2.3 Non-empty slots Print out the non-empty slots of the kernel process table in the form of [process name][p_quantum_size_ms]-[p_cpu_time_left] when F1 key is pressed (that is using the is Information Server). By solving this exercise, you must know the struct proc structure members p_quantum_size_ms and p_cpu_time_left defined in the kernel part of Minix PCB in the source file kernel/proc.h. 30



2.3.2

A FT

Figure 2.27 List of the non-empty slots from the process table.

Another solution by introducing a new system call

In the previous section, we modified the PCB. Then (using the sys_getproctab system call) we copied the kernel process table to the layer of server processes. Now, outside the PCB, but inside the kernel we create a data structure: a matrix of integers to store the „IPC matrix”. To access this matrix, we create a new system call.

D R

Define a 2 dimensional array of size (NR_TASKS + NR_PROCS)*(NR_TASKS + NR_PROCS) outside the PCB structure Figure 2.28 An array to store the „IPC matrix”.

Counting of IPC messages will be done in the same manner as described in the previous section. But now, the uzenetszam array will be accessed directly and not through the PCB. 31



FT

Figure 2.29 Incrementing of the appropriate element of the uzenetszam array.

A

The uzenetszam array of the kernel is also defined with the same name in the server layer.

D

R

Figure 2.30 This is the uzenetszam that we defined in the server layer.

Use the sys_getmatrix system call that will be newly developed for copying the IPC matrix from kernel level to the server level. 32



A FT

Figure 2.31 Usage of the sys_getmatrix system call that will be newly developed.

Printing the matrix has changed very little only in one line:

printf("%7d|", uzenetszam[rp->p_nr + NR_TASKS][i]);

D R

Figure 2.32 Printing the matrix.

In the source file include/minix/syslib.h, write the sys_getmatrix macro. This macro will call the system call do_getinfo that will do the real work. The sys_getmatrix macro helps simplify using the do_getinfo. 33



FT

Figure 2.33 Defining the sys_getmatrix macro.

A

The GET_MATRIX constant (used in the sys_getmatrix macro) is defined in source include/ minix/com.h, its value is chosen to be equal to 255.

D

R

Figure 2.34 The GET_MATRIX macro.

There is not much for us to do to add a case branch to the switch of do_getinfo in order to handle the calls of the sys_getmatrix. 34



A FT

Figure 2.35 Supplying the do_getinfo system call.

Now we are ready to recompile and boot the new kernel. Then, after pressing F4, we can see the fruits of our labour.

D R

Figure 2.36 Displaying the IPC matrix in the second solution.

It is interesting to compare the two solutions. For example, what happens if processes are created then destroyed after they have been finished and so on.

T HE AVAILABILITY OF THIS CASE STUDY. The two presented solutions are available in a VirtualBox virtual machine that can be found at http://www.inf.unideb.hu/~nbatfai/MINIX3.2.ova

35

FT

A

R

D

Chapter 3

D R

A FT

GNU/Linux kernel hacking: making entries in the /proc virtual file system

37

FT

Abstract In this chapter we have made a lifelong friend with a beautifully sophisticated monolithic kernel called Linux. • First, we are going to configure and compile a custom Linux kernel.

D

R

A

• Then, we will write a kernel module that will create and maintain a simple „debugging file” under /proc virtual file system.

CHAPTER 3. GNU/LINUX KERNEL . . .

3.1. THE MONOLITHIC KERNEL OF LINUX

„LINUX is obsolete” —Andy Tanenbaum (ast) Linus-Tanenbaum vita

3.1

The monolithic kernel of Linux „.x.x: Linus went crazy, broke absolutely _everything_, and rewrote the kernel to be a microkernel using a special message-passing version of Visual Basic.” —Linus Torvalds RFD: Kernel release numbering (Linux Kernel Mailing List)

3.1.1

A FT

In the previous case study, we had some experience with the operation of the microkernel, where architectural components are organized in different hierarchical levels. This section drives us towards the other end of the spectrum, to the world of monolithic kernels. What do monolithic and micro kernels mean in practice? Think about the previous MINIX case study, where the data structures of the lower levels of the kernel could not be accessed from the higher levels. For example, from the Minix Information Server, we could not access the vector added to PCB, we needed to copy it up to the server level. In a monolithic kernel, the data structures and functions of the kernel can be accessed from anywhere in the kernel code. In the known history of mankind, there have been several examples where huge masses of people were cooperating to achieve some mutual goals or were involved in achieving some goals. Some examples may be the building of the pyramids, the religious communities and the large mass armies of the 19th century. If we investigate only pure intellectual purposes, we will find that we are not an embarrassment of riches. A present day example may be the building of the LHC (Large Hadron Collider), that was built by 10.000 technicians, engineers and scientist from all over the world. This may be comparable to writing the Linux kernel that is being maintained by more than 8000 developers [KERNELDEV]. And if we focus not only on the kernel itself but the whole GNU/Linux system (including editors, browsers, games, etc.), then we will get a much greater number than 10000 volunteers.

Linux kernel compiling

D R

We believe that compiling the kernel should be a fundamental experience for all programming students. If the reader has never done it, we will do it now, in this section. Compiling the kernel is a relatively safe activity, but it is better to do it in a virtualized Linux system. So if the reader has never done it before, we will compile it now, using the virtualized image Batfai_Prog1.ova. The Linux kernel is a large C program, in order to compile it we need to download its source. The actual kernel sources can be downloaded from kernel.org. Here, at the time of writing, the 3.5 is the actual version. In the beginning, a simple version numbering scheme was used: the unstable versions were numbered by odd numbers and the stable ones by even numbers. But it was too „mathematical”, now a more sophisticated model was used.

K ERNEL VERSION NUMBERING

But joking apart, the rethinking of the numbering concept was suggested by Linus Torvalds in his email subjected „RFD: Kernel release numbering”.

The 2.6 kernels had already been numbered by the next schema. A stable major. minor.revision is followed by a sequence of major.minor.revision. patchlevel stable versions that contain bugfixes and security fixes. In parallel with these versions, the major.minor.revision+1"-rc-patchlevel" is the development (unstable) version, where new things are introduced. The next stable version major.minor.revision+1 will be evolved from the development versions. On the Linux’s 20th birthday, the version numbering was bumped from 2.6 to 3.0. Now, the revision shows the fixes, the development versions have the rc prefix.

39



We have chosen the current version, that is 3.5. The whole source tree is roughly 70-80 MB (it is not sufficient to download the patch that is only some kilobytes of large.) The unpacked size will be roughly a half gigabyte, but it should be noted that the size of the compiled kernel tree may be larger than 5 GB. Using the command wget http://www.kernel.org/pub/linux/kernel/v3.0/linux-3.5.tar.bz2, here we are downloading the kernel sources.

D

R

A

FT

Figure 3.1 Downloading the kernel sources.

The root of the unpacked kernel tree contains a README file, we follow the procedure descripted in this. First, unpack the sources with command tar xvjf linux-3.5.tar.bz2 or cited from the README, with the bzip2 -dc linux-3.5.tar.bz2 | tar xvf - command. The compiling is controlled by the .config file of the kernel tree that file also can be found in the running system’s /boot folder. We will use the command make menuconfig in order to customize the kernel. The make menuconfig works in the terminal screen and its output is the file .config. If you have already compiled the kernel, use the command make mrproper. This program will clean up the config and the object files from the source tree. As a best practice, the reader can copy the existing file from the /boot directory into the root of the source tree, then uses the command make oldconfig, because in this case it is enough to make decisions about the new features only. 40



D R

A FT

Figure 3.2 Making the .config with command make menuconfig.

Reading all kernel options in make menuconfig is a whole day’s work, here we can see only one: under the General setup menu, we are going to set the Kernel .config support option that will save the .config file into the running kernel itself. 41



D

R

A

FT

Figure 3.3 Setting the option Kernel .config support.

Linux kernel compiling may be coming now. Use the make command to compile the sources (here we do not follow the README, the argument O=output/dir is simply omitted, because we do not want to use a separate build directory). 42



D R

A FT

Figure 3.4 Starting the compiling.

The compilation has already finished, now we sudo into root and give the command make modeules_install install. With this command, we install the modules and the kernel. 43



D

R

A

FT

Figure 3.5 Starting the installation.

By using the command uname -a, print the version of the running kernel. 44



A FT

Figure 3.6 The version of the running kernel.

D R

We should now reboot the computer. After this, it can be seen that the grub menu has also been updated properly.

Figure 3.7 The updated GRUB menu.

Now, the compiled custom kernel controls our computer. 45



D

R

A

FT

Figure 3.8 The new kernel.

3.1.2

Kernel modules

In the previous section, you can see that options marked by a star (*) will be compiled into the kernel. If we mark an option with M, it will be compiled into the kernel as a module.

At creating the configuration, we also have opportunity to compile a pure monolithic kernel without module support. 46



D R

A FT

Figure 3.9 Switching off the option Enable loadable module support.

Without module support, the size of the kernel image is much larger than the original one. Let’s also see it after creating and booting a new pure monolithic kernel:

[norbert@BatfaiProg1 ~]$ ls -l /boot/vmlinuz-‘uname -r‘ -rw-r--r--. 1 root root 25532624 Jul 31 15:50 /boot/vmlinuz-3.5.0

47


3.2. MAKING ENTRIES IN THE /PROC . . .

D R A

FT

Figure 3.10 The size of the kernel image.

3.2

Making entries in the /proc virtual file system

As a first step we present we are going to the whole solution of the exercise, then we will „celebrate the source code”.

3.2.1

Creating the module in VirtualBox.

The solution is presented using the virtual machine Batfai_Prog1.ova. Exercise: making entries in the /proc Write a kernel module that prints debug information about processes into a file under /proc. This example already appeared in the original Paternoster [PP] (pp. 177). Further background information can be found in the books [LDD] and [KMGUIDE] and especially in the following articles • Randy Dunlap: Linux kernel seq_file HOWTO • Driver porting: The seq_file interface

1. Now we have made the module. Its source code called sbejegyzes.c can be found in the PROP_ peldak/sajat_bejegyzes_modul directory of the virtualized system. #include #include #include #include #include #include #include #include

48



MODULE_DESCRIPTION ("Ez a sajat bejegyzes (PROP konyv) kernel modul"); MODULE_AUTHOR ("Bátfai Norbert ([email protected])"); MODULE_LICENSE ("GPL"); static int taszk_lista (struct seq_file *m, void *v) { int i = 0; struct task_struct *task; struct list_head *p; // a kernel/sched/core.c-ben latott modon iratjuk ki // a betut (szemben a fs/proc/array.c-ban lathatoval) // stat_nam[task->state ? __ffs(task->state) + 1 : 0] static const char stat_nam[] = TASK_STATE_TO_CHAR_STR; seq_puts (m, "sajat taszk lista (negyedik kernel modul, PROP konyv)\n"); seq_printf (m, "%-9s %-16s %-6s %-12s %-6s %-3s\n", "#", "CMD", "PID", "FLAGS", "ST1", "ST2");

FT

list_for_each (p, current->tasks.next) { task = list_entry (p, struct task_struct, tasks); seq_printf (m, "%-9i %-16s %-6i %-12u %-6li %-3c\n", ++i, task->comm, task->pid, task->flags, task->state, stat_nam[task->state ? __ffs (task->state) + 1 : 0]); } return 0; }

A

static int sajat_open (struct inode *inode, struct file *file) { return single_open (file, taszk_lista, NULL); }

D R

static struct file_operations sajat_fajl_muveletek = { .owner = THIS_MODULE, .open = sajat_open, .read = seq_read, .llseek = seq_lseek, .release = single_release }; static struct proc_dir_entry *sajat_proc; static int sbejegyzes_init_module (void) { struct proc_dir_entry *sajat_proc_fajl; if (!(sajat_proc = proc_mkdir ("sajat", NULL))) { remove_proc_entry ("sajat", NULL); printk (KERN_NOTICE "/proc/sajat/ letrehozas sikertelen\n"); return -1; } printk (KERN_NOTICE "/proc/sajat/ letrehozva\n"); if ((sajat_proc_fajl = create_proc_entry ("taszk_stat", S_IFREG | S_IRUGO, sajat_proc))) { sajat_proc_fajl->proc_fops = &sajat_fajl_muveletek; printk (KERN_NOTICE "/proc/sajat/taszk_stat letrehozva\n"); return 0; } else { remove_proc_entry ("taszk_stat", sajat_proc);

49



remove_proc_entry ("sajat", NULL); printk (KERN_NOTICE "/proc/sajat/taszk_stat letrehozas sikertelen\n"); return -1; } } static void sbejegyzes_exit_module (void) { remove_proc_entry ("taszk_stat", sajat_proc); printk (KERN_NOTICE "/proc/sajat/taszk_stat torolve\n"); remove_proc_entry ("sajat", NULL); printk (KERN_NOTICE "/proc/sajat torolve\n"); }

FT

module_init (sbejegyzes_init_module); module_exit (sbejegyzes_exit_module);

2. The module has been created into the kernel object file sbejegyzes.ko using the command make.

D R A

[norbert@matrica sajat_bejegyzes__modul]$ make make -C /lib/modules/‘uname -r‘/build M=‘pwd‘ modules make[1]: Entering directory ‘/usr/src/kernels/2.6.42.12-1.fc15.x86_64’ CC [M] /home/norbert/kernelfa/sajat_bejegyzes__modul/sbejegyzes.o Building modules, stage 2. MODPOST 1 modules CC /home/norbert/kernelfa/sajat_bejegyzes__modul/sbejegyzes.mod.o LD [M] /home/norbert/kernelfa/sajat_bejegyzes__modul/sbejegyzes.ko make[1]: Leaving directory ‘/usr/src/kernels/2.6.42.12-1.fc15.x86_64’

We assume that the Makefile is in the same directory as sbejegyzes.c. The reader can be familiar with Makefiles for kernel modules from the Documentation/kbuild/modules.txt of the kernel source tree. obj-m += sbejegyzes.o all: make -C /lib/modules/‘uname -r‘/build M=‘pwd‘ modules clean: make -C /lib/modules/‘uname -r‘/build M=‘pwd‘ clean rm *~

3. The created module can be loaded as root using the command insmod sbejegyzes.ko [root@matrica sajat_bejegyzes__modul]# insmod sbejegyzes.ko

4. We can see your entries under the /proc/sajat. Let’s try it. Enter the command more /proc/sajat/taszk_stat [root@matrica sajat_bejegyzes__modul]# more /proc/sajat/taszk_stat sajat taszk lista (negyedik kernel modul, PROP konyv) # CMD PID FLAGS ST1 ST2 1 systemd 1 4202752 1 S 2 kthreadd 2 2149613632 1 S 3 ksoftirqd/0 3 2216722496 1 S 4 migration/0 6 2216722496 1 S 5 watchdog/0 7 2216722752 1 S 6 migration/1 8 2216722496 1 S 7 ksoftirqd/1 10 2216722496 1 S 8 watchdog/1 12 2216722752 1 S 9 migration/2 13 2216722496 1 S 10 ksoftirqd/2 15 2216722496 1 S 11 watchdog/2 16 2216722752 1 S

50


12 13 14 15 16 17 18 19 20 21 22 23 24 ...

migration/3 ksoftirqd/3 watchdog/3 cpuset khelper kdevtmpfs netns sync_supers bdi-default kintegrityd kblockd ata_sff khubd

17 19 20 21 22 23 24 25 26 27 28 29 30


2216722496 2216722496 2216722752 2216722496 2216722496 2149613888 2216722496 2149613632 2157969472 2216722496 2216722496 2216722496 2149580864

1 1 1 1 1 1 1 1 1 1 1 1 1

S S S S S S S S S S S S S

3.2.1.1

A FT

Example 3.1 The contents of the PCB The Linux PCB is defined in the struct task_struct structure in the include/linux/sched.h source file. Investigate the elements of the PCB and add further columns to /proc/sajat/taszk_ stat.

„Celebrating” the source code

The essential part of the work of the module is done by taszk_lista function, in which the variable i counts the processes (PCBs) in the system and a struct task_struct * pointer task is used to iterate through the processes. To be more precise a struct list_head * pointer p is used because the next and back links of the circular doubly linked list of PCBs are organised around of the structure struct list_head as shown in the next figure.

D R

Figure 3.11 The circular doubly linked list of PCBs in Linux.

51



H ANDLING LINKED LIST IN THE KERNEL The macros in linux/list.h can be used to manage the linked list of PCBs. The link member of the PCB list is a list_head structure member that is defined in linux/ types.h.

struct list_head { struct list_head *next, *prev; }; the usage of these link members were shown in the previous figure. These elements are part of the PCB as it can be seen in the next code snippet cited from the code of PCB from linux/sched.h.

We have used the

A

list_for_each(pos, head)

-

FT

struct task_struct { volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */ ... struct list_head tasks;

R

macro defined in linux/list.h:

D

/** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */ #define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)

The

list_for_each(pos, head)

iterates a struct list_head * pointer pos that is passed as the first parameter through the list from the element head that is passed as the second parameter.

52



T HE CURRENT MACRO It should be noted that in the code snippet

list_for_each (p, current->tasks.next) { we have used the current macro that points to the process that is being executed. What is the current macro exactly? Its definition can be found in asm-generic/

current.h #define get_current() (current_thread_info()->task) #define current get_current() The current_thread_info function is defined in (arch/x86/include/ )asm/thread_info.h.

A FT

#ifndef __ASSEMBLY__ /* how to get the current stack pointer from C */ register unsigned long current_stack_pointer asm("esp") __used ;

-

/* how to get the thread information struct from C */ static inline struct thread_info *current_thread_info(void) { return (struct thread_info *) (current_stack_pointer & ~(THREAD_SIZE - 1)); } #else /* !__ASSEMBLY__ */

D R

/* how to get the thread information struct from ASM */ #define GET_THREAD_INFO(reg) \ movl $-THREAD_SIZE, reg; \ andl %esp, reg

in the kernel, the thread_union union is on the bottom of the memory area of a process. If we filled the entire stack, then the stack pointer would point to the bottom of the stack and the memory area of thread_union would be overwritten. This union is 8 KB, so we can easily calculate the address of struct thread_info of the running process. The stack pointer’s low 25 bits must be set to zero. It can be seen in the following code snippet from the (arch/x86/include/)asm/thread_info.h: current_stack_pointer & ~(THREAD_SIZE - 1), where the value of THREAD_SIZE is equal 8 KB

#define THREAD_SIZE 8192

//(2*PAGE_SIZE)

as can be seen in the file arch/xtensa/include/)asm/thread_info.h. The address of the thread_union and the address of the thread_info are the same:

union thread_union { struct thread_info thread_info; unsigned long stack[THREAD_SIZE/sizeof(long)]; }; and the task member of the struct thread_info points to PCB of the process.

struct thread_info { struct task_struct

*task;

/* main task structure */

See also the exercise at the end of this section.

53



Returning to the code snippet of the module to be developed, the list_for_each macro iterates through the list of PCBs, and accesses the PCBs using the list_entry(ptr, type, member) macro that defined in the linux/list.h header. /** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */

The printed debug information also includes a status character indicating the state of the given process. These possible characters are collected in the following macro that is defined in linux/sched.h.

FT

#define TASK_STATE_TO_CHAR_STR "RSDTtZXxKW" static int taszk_lista (struct seq_file *m, void *v) { int i = 0; struct task_struct *task; struct list_head *p; // a kernel/sched/core.c-ben latott modon iratjuk ki // a betut (szemben a fs/proc/array.c-ban lathatoval) // stat_nam[task->state ? __ffs(task->state) + 1 : 0] static const char stat_nam[] = TASK_STATE_TO_CHAR_STR;

D R A

seq_puts (m, "sajat taszk lista (negyedik kernel modul, PROP konyv)\n"); seq_printf (m, "%-9s %-16s %-6s %-12s %-6s %-3s\n", "#", "CMD", "PID", "FLAGS", "ST1", "ST2"); list_for_each (p, current->tasks.next) { task = list_entry (p, struct task_struct, tasks); seq_printf (m, "%-9i %-16s %-6i %-12u %-6li %-3c\n", ++i, task->comm, task->pid, task->flags, task->state, stat_nam[task->state ? __ffs (task->state) + 1 : 0]); } return 0;

}

Making entries under the /proc is done by using the next two functions defined in linux/proc_ fs.h extern struct proc_dir_entry *create_proc_entry(const char *name, umode_t mode, struct proc_dir_entry *parent); extern struct proc_dir_entry *proc_mkdir(const char *,struct proc_dir_entry *);

of which the first is the more interesting one

if ((sajat_proc_fajl = create_proc_entry ("taszk_stat", S_IFREG | S_IRUGO, sajat_proc)))

For example, according the linux/stat.h, the S_IRUGO #define S_IRUGO

(S_IRUSR|S_IRGRP|S_IROTH)

gives read permission to user (USR), group (GRP) and other (OTH). # ls -l /proc/sajat/taszk_stat -r--r--r--. 1 root root 0 Aug 10 17:42 /proc/sajat/taszk_stat

54



Example 3.2 Playing the game with the current macro Modify the third example module (that can be found in the virtualized system) to print the address pointed by the current macro. #include #include #include #include #include #include

struct thread_info *ti;

FT

MODULE_DESCRIPTION ("Ez a harmadik kernel modulom - modositasa"); MODULE_AUTHOR ("Bátfai Norbert ([email protected])"); MODULE_LICENSE ("GPL"); static int current_and_sp (void) { struct task_struct *task; struct list_head *p;

register unsigned long esp asm ("esp"); ti = (struct thread_info *) (esp & ~(sizeof (union thread_union) - 1)); list_for_each (p, current->tasks.next) { task = list_entry (p, struct task_struct, tasks);

A

printk (KERN_NOTICE "nORBi a kernelben: %p\n", ti->task); printk (KERN_NOTICE "nORBi a kernelben, current: %p\n", current); printk (KERN_NOTICE "%s %i %u %li\n", task->comm, task->pid, task->flags, task->state); } return 0;

D R

}

static int harmadik_init_module (void) { return current_and_sp (); } static void harmadik_exit_module (void) { current_and_sp (); }

module_init (harmadik_init_module); module_exit (harmadik_exit_module);

After compiling and loading/removing the module we can see the following in the kernel logs. [ [ [ [ [ [ [ [

8379.261436] 8379.261438] 8379.261440] 8379.261441] 8379.261442] 8379.261443] 8379.261444] 8379.261444]

nORBi a kernelben: f0f49920 nORBi a kernelben, current: f0f49920 systemd 1 4202752 1 nORBi a kernelben: f0f49920 nORBi a kernelben, current: f0f49920 kthreadd 2 2129984 1 nORBi a kernelben: f0f49920 nORBi a kernelben, current: f0f49920

55


8379.261445] ksoftirqd/0 3 69238848 1 8379.261446] nORBi a kernelben: f0f49920

nORBi a kernelben: f0f49920 nORBi a kernelben, current: kworker/0:1 2486 69238880 1 nORBi a kernelben: f0f49920 nORBi a kernelben, current: flush-253:1 3846 10485824 1 nORBi a kernelben: f0f49920 nORBi a kernelben, current: kworker/1:1 6477 69238880 1 nORBi a kernelben: f0f49920 nORBi a kernelben, current: insmod 6913 4202752 0 nORBi a kernelben: f0d28000 nORBi a kernelben, current: systemd 1 4202752 1 nORBi a kernelben: f0d28000 nORBi a kernelben, current: kthreadd 2 2129984 1 nORBi a kernelben: f0d28000 nORBi a kernelben, current: ksoftirqd/0 3 69238848 1 nORBi a kernelben: f0d28000

8393.315565] 8393.315566] 8393.315567] 8393.315569] 8393.315570] 8393.315571] 8393.315572] 8393.315573] 8393.315574] 8393.315575] 8393.315576] 8393.315578] 8393.315579] 8393.315580] 8393.315582]

nORBi a kernelben: f0d28000 nORBi a kernelben, current: bash 1733 4202496 1 nORBi a kernelben: f0d28000 nORBi a kernelben, current: kworker/0:1 2486 69238880 1 nORBi a kernelben: f0d28000 nORBi a kernelben, current: flush-253:1 3846 10485824 1 nORBi a kernelben: f0d28000 nORBi a kernelben, current: kworker/1:1 6477 69238880 1 nORBi a kernelben: f0d28000 nORBi a kernelben, current: rmmod 6915 4202752 0

f0f49920

f0f49920

f0f49920

f0f49920

f0d28000

FT

8379.261848] 8379.261849] 8379.261850] 8379.261851] 8379.261852] 8379.261853] 8379.261853] 8379.261854] 8379.261855] 8379.261856] 8379.261857] 8379.261858] 8393.314942] 8393.314945] 8393.314947] 8393.314948] 8393.314949] 8393.314951] 8393.314952] 8393.314953] 8393.314955] 8393.314956]

f0d28000

R

A

f0d28000

f0d28000

f0d28000

f0d28000

f0d28000

f0d28000

D

[ [ . . . [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ . . . [ [ [ [ [ [ [ [ [ [ [ [ [ [ [


Example 3.3 Drawing a memory map Draw a sketch of the memory to show how to compute the value of the current macro. See also the Figure 3.2 of the book [ULK], but use the number of the previous exercise.

56

Chapter 4

D R

A FT

Berkeley socket API, Sys V IPC and I/O multiplexing

57

• Berkeley socket API • I/O multiplexing • forking processes • mutual exclusion

D

R

A

• and semaphore arrays.

FT

Abstract In this chapter we are going to create a sample program from the examples of [PP] to help the reader get acquainted with

CHAPTER 4. BERKELEY SOCKET API, SYS . . .

4.1. BERKELEY SOCKET API, SYS V IPC, I/O . . .

„We should select any person from the 1.5 billion inhabitants of the Earth - anyone, anywhere at all. He bet us that, using no more than five individuals, one of whom is a personal acquaintance, he could contact the selected individual using nothing except the network of personal acquaintances.” —Frigyes Karinthy CHAIN-LINKS (1929, Everything is Different) „Tessék egy akármilyen meghatározható egyént kijelölni a Föld másfél milliárd lakója közül, bármelyik pontján a Földnek - o˝ fogadást ajánl, hogy legföljebb öt más egyénen keresztül, kik közül az egyik neki személyes ismer˝ose, kapcsolatot tud létesíteni az illet˝ovel, csupa közvetlen - ismeretség - alapon,” —Karinthy Frigyes Láncszemek

Berkeley socket API, Sys V IPC, I/O multiplexing

4.2

A simple client/server sample

FT

4.1

4.2.1

The client side

A

The first versions of this example were created for the course High level programming 1. These were based on merging the source files of [PP]. This sample program itself is a simple client/server program, its client side is based on the kliens.c of [PP] (see pp. 133). Now, we have complemented the client to wait for characters plus (+) or minus (-) to be typed in the command line. The code of the server is placed into a source file called szerver.c that is more complex than the client. It is based on a parallel and multiplexed example of [PP] (see pp. 123) that uses POSIX signal handling. The subject matter of the server and all other servers in [PP] are substantially identical. They implement a simple echo-like server. In the present example, this functionality is complemented by a counter that counts the actions of clients. The usage of the sources szerver.c and kliens.c is shown in the following YouTube video: http://youtu.be/J--bRSmNjZg

The whole source code of the server is the following.

D R

#include <stdio.h> #include <stdlib.h> #include #include <string.h> //#include <sys/types.h> #include <sys/socket.h> #include

#define SZERVER_PORT 2012 #define BUFFER_MERET 256

int kliens (char b) { int kapu, olvasva; struct sockaddr_in szerver; char buffer[BUFFER_MERET]; memset ((void *) &szerver, 0, sizeof (szerver)); szerver.sin_family = AF_INET; inet_aton ("127.0.0.1", &(szerver.sin_addr)); szerver.sin_port = htons (SZERVER_PORT); if ((kapu = socket (PF_INET, SOCK_STREAM, IPPROTO_TCP)) == -1) {4 perror ("socket"); return -1; } if (connect (kapu, (struct sockaddr *) &szerver, sizeof (szerver)) == -1)

59


4.2. A SIMPLE CLIENT/SERVER SAMPLE

{ perror ("connect"); return -1; } write(kapu, &b, 1); while ((olvasva = read (kapu, buffer, BUFFER_MERET)) > 0) write (1, buffer, olvasva); close(kapu); return 0;

int main (int argc, char *argv[]) { int gyermekem_pid; int statusz; int i; char b = ’+’; if (argc == 2) b = argv[1][0];

FT

}

}

R

A

for (i=0; i<4; ++i) if ((gyermekem_pid = fork()) == 0) { kliens(b); } else if (gyermekem_pid > 0) { kliens(b); // wait(&statusz); } else { exit(-1); } return 0;

D

In the main function first we check whether the second command-line argument is given or not. If yes, then its first character will be stored in the variable b that will be sent to the server. The default value of b is a plus (+) character. We are going to try to overload the server. For this reason, TCP connections will be opened simultaneously not sequentially. To be more precise, the following client program opens 30 TCP connections to the server. If you do not understand why exactly the following code snippet works, then suspend the elaboration of this example and first start by solving the next exercise. for (i=0; i<4; ++i) if ((gyermekem_pid = fork()) == 0) { kliens(b); } else if (gyermekem_pid > 0) { kliens(b); wait(&statusz); } else { exit(-1); }

Example 4.1 30 processes, with using a paper and pen

60



Show how the next code snippet operates. Just use a paper and pen in this exercise. Your solution is probably good if the result 30=2+4+8+16 can be read easily from your own sketch.

A FT

for (i=0; i<4; ++i) if ((gyermekem_pid = fork()) == 0) { kliens(b); } else if (gyermekem_pid > 0) { kliens(b); // wait(&statusz); } else { exit(-1); }

Connecting and communicating with the server are hidden in the kliens function. Here, if the dear reader is not already familiar with the structure struct sockaddr_in, it is described in the manual page man 7 ip. This structure represents a communication endpoint, as it can be seen on the next manual snippet from man 7 ip. struct sockaddr_in { sa_family_t sin_family; /* address family: AF_INET */ in_port_t sin_port; /* port in network byte order */ struct in_addr sin_addr; /* internet address */ };

/* address in network byte order */

D R

/* Internet address. */ struct in_addr { uint32_t s_addr; };

sin_family is always set to AF_INET. This is required; in Linux 2.2 most networking functions return EINVAL when this setting is missing. sin_port contains the port in network byte order. The port numbers below 1024 are called privileged ports (or some-

-

-

We need to create this structure and set its members (such as protocol family, IP address and port number) accordingly: struct sockaddr_in szerver; memset ((void *) &szerver, 0, sizeof (szerver)); szerver.sin_family = AF_INET; inet_aton ("127.0.0.1", &(szerver.sin_addr)); szerver.sin_port = htons (SZERVER_PORT);

In the following, if we see unknown function calls or data structures we we will find a more detailed description in the appropriate manual page. For example, in the actual case above, see the page man 3 htons.

61



O RGANIZATION OF THE MANUAL PAGES The readers have already noticed that manual pages are organized into numbered sections, as shown in the following breakdown: • Section 1, User commands (Linux User’s Manual/User Commands/User utilities), for example man w, man who or man passwd • Section 2, System calls (Linux Programmer’s Manual), man 2 read • Section 3, Library functions (Linux Programmer’s Manual), man 3 printf • Section 4, Special files, man 4 stdin • Section 5, Formats and protocols man 5 passwd • Section 6, Games, man 6 fortune

FT

• Section 7, Miscellaneous, man 7 hier

• Section 8, System administration, man 8 shutdown (For further details, see man man.)

The man {section number (1-8)} intro command gives a general description of the above sections.

D R A

Then, using the socket system call, we create the abstraction of a communication endpoint that will be connected to the previously specified address by the connect system call. It should be noted that the number returned by the socket is a file descriptor. (See also the Párhuzamos programozás GNU/Linux környezetben: SysV IPC, P-szálak, OpenMP http://www.inf.unideb.hu/~nbatfai/konyvek/PARP/parp.book.xml.pdf, [PARP] book about the appearance of file descriptors in the kernel.) The program sends a byte to this file descriptor using the write system call, then reads a byte from the same file descriptor using the read and so on in the while loop, whenever it can to read, during the read data is also echoed to the standard output. write(kapu, &b, 1); while ((olvasva = read (kapu, buffer, BUFFER_MERET)) > 0) write (1, buffer, olvasva);

T HE PORTABILITY OF THE EXAMPLE

If we compile the sources on different GNU/Linux environments we will get warnings from the compiler. In most of such cases it is typically enough to include the appropriate header files to solve these problems.

NOTES

POSIX.1-2001 does not require the inclusion of <sys/ types.h>, and this header file is not required on Linux. However, some historical (BSD) implementations required this header file, and portable applications are probably wise to include it.

4.2.2

The server side

The whole source code of the server can be found in the source file called szerver.c. 62

-

-


szerver.c "forkos, socketes, multiplexelt, szemaforos, osztott memóriás" állatorvosi szerver ló a laborra Programozó Páternoszter Copyright (C) 2011, 2012 Bátfai Norbert, [email protected] This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

FT

You should have received a copy of the GNU General Public License along with this program. If not, see .

Ez a program szabad szoftver; terjeszthetõ illetve módosítható a Free Software Foundation által kiadott GNU General Public License dokumentumában leírtak; akár a licenc 3-as, akár (tetszõleges) késõbbi változata szerint.

A

Ez a program abban a reményben kerül közreadásra, hogy hasznos lesz, de minden egyéb GARANCIA NÉLKÜL, az ELADHATÓSÁGRA vagy VALAMELY CÉLRA VALÓ ALKALMAZHATÓSÁGRA való származtatott garanciát is beleértve. További részleteket a GNU General Public License tartalmaz. A felhasználónak a programmal együtt meg kell kapnia a GNU General Public License egy példányát; ha mégsem kapta meg, akkor tekintse meg a oldalon.

Version history: 0.0.1 0.0.2

http://progpater.blog.hu/2011/03/06/halozati_vegyertek el˝ okészítés a PARP könyvhöz

D R

// // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // // //


#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include

<stdio.h> <stdlib.h> <string.h> <sys/socket.h> <arpa/inet.h> <sys/select.h> <signal.h> <errno.h> <sys/sem.h> <sys/shm.h> <sys/wait.h>

#define SZERVER_PORT 2012 #define SZERVER_SOR_MERET 10 #define CTIME_BUFFER_MERET 128 int kiszolgal (int kliens, int szemafor, int *osztott_memoria_terulet) {

63



char buffer[CTIME_BUFFER_MERET] = ""; time_t t = time (NULL); char *ts = ctime_r (&t, buffer); char buffer2[256] = ""; int ertek, nkliens; struct sembuf zar, nyit; zar.sem_num = 0; zar.sem_op = -1; zar.sem_flg= SEM_UNDO; nyit.sem_num = 0; nyit.sem_op = 1; nyit.sem_flg= SEM_UNDO; int olvasott = read (kliens, buffer2, 10); write (kliens, buffer2, olvasott);

++*(osztott_memoria_terulet+1);

D R A

if (buffer2[0] == ’+’) ++*osztott_memoria_terulet; else --*osztott_memoria_terulet;

FT

if (semop (szemafor, &zar, 1) == -1) { perror ("semop zar"); exit (EXIT_FAILURE); }

ertek = *osztott_memoria_terulet; nkliens = *(osztott_memoria_terulet+1); if (semop (szemafor, &nyit, 1) == -1) { perror ("semop nyit"); exit (EXIT_FAILURE); }

olvasott = snprintf(buffer2, 50, "Ertek=%d Kliensek=%d\n", ertek, nkliens);

write (kliens, buffer2, olvasott);

return write (kliens, ts, strlen (ts));

}

void zombi_elharito (int sig) { while (wait (NULL) > 0); }

int main (void) { int kapu_figyelo, kapcsolat, kliensm, sockoptval = 1, s, gyermekem_pid, szemafor; fd_set kapu_figyelok; int osztott_memoria; int *osztott_memoria_terulet; struct timeval timeout; struct sockaddr_in szerver, kliens; struct sigaction sa;

64



FT

sa.sa_handler = zombi_elharito; sigemptyset (&sa.sa_mask); sa.sa_flags = SA_RESTART; memset ((void *) &szerver, 0, sizeof (szerver)); szerver.sin_family = AF_INET; inet_aton ("127.0.0.1", &(szerver.sin_addr)); szerver.sin_port = htons (SZERVER_PORT); if ((kapu_figyelo = socket (PF_INET, SOCK_STREAM, IPPROTO_TCP)) == -1) { perror ("socket"); exit (EXIT_FAILURE); } setsockopt (kapu_figyelo, SOL_SOCKET, SO_REUSEADDR, (void *) &sockoptval, sizeof (sockoptval)); fcntl (kapu_figyelo, F_SETFL, fcntl (kapu_figyelo, F_GETFL) | O_NONBLOCK); if (bind (kapu_figyelo, (struct sockaddr *) &szerver, sizeof (szerver)) == -1) { perror ("bind"); exit (EXIT_FAILURE); } if (listen (kapu_figyelo, SZERVER_SOR_MERET) == -1) { perror ("listen"); exit (EXIT_FAILURE); } printf ("%s:%d\n", inet_ntoa (szerver.sin_addr), ntohs (szerver.sin_port));

D R

A

if ((szemafor = semget (ftok (".", 42), 1, IPC_CREAT | S_IRUSR | S_IWUSR)) == -1) { perror ("semget"); exit (EXIT_FAILURE); } printf ("szemafor: %d\n", szemafor); fflush (stdout); if (semctl (szemafor, 0, SETVAL, 1)) { perror ("semctl"); exit (EXIT_FAILURE); } if ((osztott_memoria = shmget (ftok (".", 44), 2*sizeof(int), IPC_CREAT | S_IRUSR | S_IWUSR)) == -1) { perror ("shmget"); exit (EXIT_FAILURE); } if ((osztott_memoria_terulet = (int *)shmat (osztott_memoria, NULL, 0)) < 0) { perror ("shmat"); exit (EXIT_FAILURE); } *osztott_memoria_terulet = 42; *(osztott_memoria_terulet+1) = 0; sigaction (SIGCHLD, &sa, NULL); FD_ZERO (&kapu_figyelok); for (;;) { FD_SET (kapu_figyelo, &kapu_figyelok); timeout.tv_sec = 3; timeout.tv_usec = 0; if ((s = select (kapu_figyelo + 1, &kapu_figyelok, NULL,

65



NULL, &timeout)) == -1) { // perror ("select"); // Interrupted system call/ EINTR - SIGCHLD // exit (EXIT_FAILURE);

-

D

R

A

FT

} else if (!s) { printf ("vartam...\n"); fflush (stdout); } else { if (FD_ISSET (kapu_figyelo, &kapu_figyelok)) { memset ((void *) &kliens, 0, (kliensm = sizeof (kliens))); if ((kapcsolat = accept (kapu_figyelo, (struct sockaddr *) &kliens, (socklen_t *) & kliensm)) == -1) { perror ("accept"); exit (EXIT_FAILURE); } printf (" <-> %s:%d\n", inet_ntoa (kliens.sin_addr), ntohs (kliens.sin_port)); if ((gyermekem_pid = fork ()) == 0) { close (kapu_figyelo); if (kiszolgal (kapcsolat, szemafor, osztott_memoria_terulet) == -1) { perror ("kiszolgal"); } close (kapcsolat); exit (EXIT_SUCCESS); } else if (gyermekem_pid > 0) { // wait(&statusz); e miatt kezeljuk a SIGCHLD jelet, // l. a Zombik fejezetet (PP)! // http://www.inf.unideb.hu/~nbatfai/#pp close (kapcsolat); } else { close (kapcsolat); perror ("fork"); exit (EXIT_FAILURE); } } }

}

}

4.2.2.1

Discussing the source code of the server side

The beginning of the main function can be familiar from the client. The communication endpoint is created on the server side the same way as in the client side. struct sockaddr_in szerver, kliens; memset ((void *) &szerver, 0, sizeof (szerver)); szerver.sin_family = AF_INET; inet_aton ("127.0.0.1", &(szerver.sin_addr)); szerver.sin_port = htons (SZERVER_PORT);

66



The next part of the beginning of the main function is the setting of the POSIX signal handling. Some lines below, we can see that the SIGCHLD signal will be processed by the signal handler function called zombi_elharito. struct sigaction sa; sa.sa_handler = zombi_elharito; sigemptyset (&sa.sa_mask); sa.sa_flags = SA_RESTART;

The variable osztott_memoria is used for identifying a shared memory segment that is pointed by the pointer osztott_memoria_terulet. It is interested to note that this pointer will point outside the process’s address space and all processes that attach to the shared memory segment will access to it. int osztott_memoria; int *osztott_memoria_terulet;

In the remaining part of the beginning of the main function,

FT

int kapu_figyelo, kapcsolat, kliensm, sockoptval = 1, s, gyermekem_pid, szemafor; fd_set kapu_figyelok; struct timeval timeout;

the kapu_figyelo is the server socket and the kapcsolat is a client socket. The kliensm is a technical variable that contains the size of client’s sockaddr_in structure. The sockoptval is also a technical variable that helps to test the server. The calling the function setsockopt (kapu_figyelo, SOL_SOCKET, SO_REUSEADDR, NULL, 0);

A

allows us to restart the server immediately without waiting for the freeing of the server socket by the operating system. vartam... ^C [norbert@matrica halozati]$ ./szerver bind: Address already in use

D R

The gyermekem_pid variable contains the returned value of the fork system call that returns 0 in the child and returns the child’s PID in the parent. The szemafor variable, like in the case of the shered memory, is used for identifying the IPC resource. The kapu_figyelok and timeout variables will be discussed later together with the fork system call. The socket is created the same way as in the client. if ((kapu_figyelo = socket (PF_INET, SOCK_STREAM, IPPROTO_TCP)) == -1) { perror ("socket"); exit (EXIT_FAILURE); }

We connect the socket to the previously specified (127.0.0.1:2012) address using the bind system call. if (bind (kapu_figyelo, (struct sockaddr *) &szerver, sizeof (szerver)) == -1) { perror ("bind"); exit (EXIT_FAILURE); }

Then we start to listen for incoming client connect requests if (listen (kapu_figyelo, SZERVER_SOR_MERET) == -1) { perror ("listen"); exit (EXIT_FAILURE); }

67



and in general we can start processing the client’s request if ((kapcsolat = accept (kapu_figyelo, (struct sockaddr *) &kliens, (socklen_t *) & kliensm)) == -1)

but now we are going to use a more sophisticated approach to handle clients. Because calling the accept will be embedded in the calling select. We set server socket to non-blocking. First, we read the socket descriptor flags then set it. fcntl (kapu_figyelo, F_SETFL, fcntl (kapu_figyelo, F_GETFL) | O_NONBLOCK);

The semaphore array is created by the semget system call, where the first argument is a key to identify the allocated shared memory segment. It is generated by the ftok library function using the name of actual directory and a magic number 42 (see the man page man 3 ftok).

FT

if ((szemafor = semget (ftok (".", 42), 1, IPC_CREAT | S_IRUSR | S_IWUSR)) == -1) { perror ("semget"); exit (EXIT_FAILURE); }

I DON ’ T UNDERSTAND WHY I DON ’ T UNDERSTAND ...

D R A

Suppose we are testing the server. If the server runs the first time but it doesn’t run other times again then we will change the actual directory or the magic number.

The second argument of semget is the number of the semaphores in the array to be created and that number is equal to 1 now. It is enough because the mutual exclusion can be achieved using only one semaphore. The third argument sets permissions on the semaphore to be created, these are set in the same way as the ones used in file handling. The properties of the created semaphore can be seen using the command ipcs:

nbatfai@morse:~$ ipcs

------ Shared Memory Segments -------key shmid owner perms 0x2c0003f5 32769 nbatfai 600

bytes 8

------ Semaphore Arrays -------key semid owner perms 0x2a0003f5 294921 nbatfai 600

nsems 1

------ Message Queues -------key msqid owner

used-bytes

perms

nattch 16

status

messages

This screen snippet shows that there are 16 serving processes that attach the shared memory segment with size of 8 (2*sizeof(int)) bytes. We set the first and now the only element of the semaphore array identified by szemafor to 1. This means that the semaphore is open. if (semctl (szemafor, 0, SETVAL, 1)) { perror ("semctl"); exit (EXIT_FAILURE); }

Similarly, we create the shared memory. The only one difference is in the second argument of the system call, because in this case it denotes the size of memory segment to be allocated. 68



if ((osztott_memoria = shmget (ftok (".", 44), 2*sizeof(int), IPC_CREAT | S_IRUSR | S_IWUSR)) == -1) { perror ("shmget"); exit (EXIT_FAILURE); }

-

We attach the shared memory segment if ((osztott_memoria_terulet = (int *)shmat (osztott_memoria, NULL, 0)) < 0) { perror ("shmat"); exit (EXIT_FAILURE); } *osztott_memoria_terulet = 42; *(osztott_memoria_terulet+1) = 0;

A FT

it is necessary because the forked child processes will inherit the attached shared memory segment as we can see it in the manual page man 2 shmat: After a fork(2) the child inherits the attached shared memory segments.

After an execve(2) all attached shared memory segments are detached from the process. Upon _exit(2) all attached shared memory segments are detached from the process.

-

-

Finally, the next line assigns the previously created sigaction sa structure to the handling of the SIGCHLD signal. sigaction (SIGCHLD, &sa, NULL);

A

SERVER OF ZOMBIES

D R

What will happen if we comment out the above line?

[norbert@matrica halozati]$ ps -p ‘echo $(pgrep -u norbert szerver)‘|tee zombik| wc 30 178 1388 [norbert@matrica halozati]$ more zombik PID TTY STAT TIME COMMAND 12885 pts/2 S+ 0:00 ./szerver 12892 pts/2 Z+ 0:00 [szerver] <defunct> 12893 pts/2 Z+ 0:00 [szerver] <defunct> 12894 pts/2 Z+ 0:00 [szerver] <defunct> 12895 pts/2 Z+ 0:00 [szerver] <defunct> 12897 pts/2 Z+ 0:00 [szerver] <defunct> 12899 pts/2 Z+ 0:00 [szerver] <defunct>

-

Or if we comment out the line sa.sa_flags =SA_RESTART; statement?

Let’s see now the multiplexing in the code. During multiplexing we usually use sets of file descriptors. Now first, we clear the set kapu_figyelok then add the server socket to it using the FD_SET macro. FD_ZERO (&kapu_figyelok); for (;;) { FD_SET (kapu_figyelo, &kapu_figyelok);

69



The members of the structure called timeval may already be known from the manual page man 2 select: The timeout The time structures involved are defined in <sys/time.h> and look like struct timeval { long tv_sec; long tv_usec; };

/* seconds */ /* microseconds */

According to these settings, the timeout is equal to 3 seconds and 0 microseconds, The select system call will return periodically after this timeout has expired. timeout.tv_sec = 3; timeout.tv_usec = 0; if ((s = select (kapu_figyelo + 1, &kapu_figyelok, NULL, NULL, &timeout)) == -1)

FT

We can also see the arguments of the select in the manual page man 2 select: int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

D R A

from where only the first file descriptor set will be used effectively because we want to multiplex the incoming client connections only and all the clients’ requests will be handled by separate processes. In accordance with this, we assign the kapu_figyelok actual parameter for the readfds formal parameter. As described in the manual page for select the value of nfds must be set to maximum file descriptor plus one. The select may return errors for several reasons. Errors are indicated by returning -1, to get the exact error we have to check the value of errno. If the select returns 0 it means that nothing important had happened before the timeout expired. if ((s = select (kapu_figyelo + 1, &kapu_figyelok, NULL, NULL, &timeout)) == -1) { // perror ("select"); // Interrupted system call/ EINTR - SIGCHLD // exit (EXIT_FAILURE); } else if (!s) { printf ("vartam...\n"); fflush (stdout); }

A non-negative and non-zero value are more interesting values, because this value is the number of file descriptors that are ready to be read from or written to. In our case, to be more precise, to read from the server socket. But as a defensive programming technique we check that whether the server socket is listed in the readfds set using the FD_ISSET macro: else {

if (FD_ISSET (kapu_figyelo, &kapu_figyelok)) {

Here, we are already sure that accept will not be blocked. if ((kapcsolat = accept (kapu_figyelo, (struct sockaddr *) &kliens, (socklen_t *) & kliensm)) == -1) { perror ("accept"); exit (EXIT_FAILURE); }

then after printing some debug messages we fork a child process 70



printf (" <-> %s:%d\n", inet_ntoa (kliens.sin_addr), ntohs (kliens.sin_port)); if ((gyermekem_pid = fork ()) == 0) {

The child process

-

A FT

if ((gyermekem_pid = fork ()) == 0) { close (kapu_figyelo); if (kiszolgal (kapcsolat, szemafor, osztott_memoria_terulet) == -1) { perror ("kiszolgal"); } close (kapcsolat); exit (EXIT_SUCCESS); }

closes the server socket and starts to serve the client through the client socket. Finally, after the client’s request has been served by the kiszolgal handler function the child process closes the client socket as well and exits. The parent process else if (gyermekem_pid > 0) { // wait(&statusz); e miatt kezeljuk a SIGCHLD jelet, // l. a Zombik fejezetet (PP)! // http://www.inf.unideb.hu/~nbatfai/#pp close (kapcsolat); }

closes the client socket and goes back immediately to wait for the next client connection requests. 4.2.2.2

Protecting the memory of the processes

D R

The client handler function kiszolgal gets three arguments. These are the file descriptor of client socket, the identifier of the semaphore array and a pointer to the attached memory segment. int kiszolgal (int kliens, int szemafor, int *osztott_memoria_terulet) {

The other variables are technical, for example the buffer is an internal puffer used by the reentrant function like ctime_r. char buffer[CTIME_BUFFER_MERET] = ""; time_t t = time (NULL); char *ts = ctime_r (&t, buffer); char buffer2[256] = ""; int ertek, nkliens;

It is much more interesting to create the two sembuf data structures that will control the semaphore operations. struct sembuf zar, nyit; zar.sem_num = 0; zar.sem_op = -1; zar.sem_flg= SEM_UNDO; nyit.sem_num = 0; nyit.sem_op = 1; nyit.sem_flg= SEM_UNDO;

The detailed description of semaphore handling of this example can be found in the book Párhuzamos programozás GNU/Linux környezetben: SysV IPC, P-szálak, OpenMP http://www.inf.unideb.hu/~nbatfai/konyvek/PARP/parp.book.xml.pdf, [PARP]. 71



As mentioned in the previous section about the parent process, the semaphore was set to signaled because its value was set to 1 by the parent process. We read the first 10 bytes of what the client sent to us and we write back it to the client. int olvasott = read (kliens, buffer2, 10); write (kliens, buffer2, olvasott);

We count how many clients worked on the int variable stored in the shared memory segment. The counter is the second variable on the shared memory area and it is pointed by osztott_memoria_te rulet+1. ++*(osztott_memoria_terulet+1);

if (buffer2[0] == ’+’) ++*osztott_memoria_terulet; else --*osztott_memoria_terulet;

FT

If client sends a plus sign, the following code snippet will increment the first variable that is stored in the shared memory segment. Otherwise, the shared variable will be decreased:

The above last two code snippets are part of the critical section. We would like to achieve that only one process may enter the critical section at the same time in order that variables should not go wrong. Therefore, here we apply mutual exclusion to achieve this goal: only one process can enter the critical section at a time. If a process can acquire the semaphore, all the other processes will be blocked until the semaphore is nonsignaled. The next snippet sets the semaphore to nonsignaled

D R A


or this one sets the semaphore to signaled after the process exits from the critical section. if (semop (szemafor, &nyit, 1) == -1) { perror ("semop nyit"); exit (EXIT_FAILURE); }

In the critical section we create copies of the two shared variables. ertek = *osztott_memoria_terulet; nkliens = *(osztott_memoria_terulet+1);

These copied values and the system time will be sent back to the client. olvasott = snprintf(buffer2, 50, "Ertek=%d Kliensek=%d\n", ertek, nkliens);

write (kliens, buffer2, olvasott);

return write (kliens, ts, strlen (ts));

}

4.2.3

Testing of the example

4.2.3.1

Testing on localhost

4.2.3.1.1

Compiling and running the server

[norbert@matrica halozati]$ gcc szerver.c -o szerver [norbert@matrica halozati]$ ./szerver 127.0.0.1:2012 szemafor: 98305 vartam...

72



vartam... <-> 127.0.0.1:55055 <-> 127.0.0.1:55056 . . . <-> 127.0.0.1:55079 <-> 127.0.0.1:55080 <-> 127.0.0.1:55081 <-> 127.0.0.1:55082 <-> 127.0.0.1:55083 <-> 127.0.0.1:55084 vartam... ^C

4.2.3.1.2

Compiling and running the client

A

FT

[norbert@matrica halozati]$ gcc kliens.c -o kliens [norbert@matrica halozati]$ ./kliens +Ertek=43 Kliensek=1 Sat Aug 4 16:18:49 2012 +Ertek=44 Kliensek=2 Sat Aug 4 16:18:49 2012 +Ertek=45 Kliensek=3 Sat Aug 4 16:18:49 2012 . . . +Ertek=69 Kliensek=27 Sat Aug 4 16:18:49 2012 +Ertek=70 Kliensek=28 Sat Aug 4 16:18:49 2012 +Ertek=71 Kliensek=29 Sat Aug 4 16:18:49 2012 +Ertek=72 Kliensek=30 Sat Aug 4 16:18:49 2012

D R

The second last row +Ertek=72 Kliensek=30 shows that the value of 42 does not go wrong because it is equal 72 after 30 incrementations. 4.2.3.1.3 There is some disturbance in the force the semaphore?

What will happen if we comment out the usage of

/*


*/

++*(osztott_memoria_terulet+1); if (buffer2[0] == ’+’) ++*osztott_memoria_terulet; else --*osztott_memoria_terulet;

ertek = *osztott_memoria_terulet; nkliens = *(osztott_memoria_terulet+1); /* if (semop (szemafor, &nyit, 1) == -1) { perror ("semop nyit"); exit (EXIT_FAILURE);

73



} */

Using the following command we run clients in a little bit more aggressive way. It is important that the magic value 42 should be unchanged after running the clients. [norbert@matrica halozati]$ ./kliens +& ./kliens -& ./kliens +& ./kliens -& ./ kliens +& ./kliens -& ./kliens +& ./kliens -& ./kliens +& ./kliens -& ./ kliens +& ./kliens -& ./kliens +& ./kliens -& ./kliens +& ./kliens -& ./ kliens +& ./kliens -&

-

We query the value using the telnet program as a client:

FT

[norbert@matrica halozati]$ telnet localhost 2012 Trying ::1... telnet: connect to address ::1: Connection refused Trying 127.0.0.1... Connected to localhost. Escape character is ’^]’. + + Ertek=47 Kliensek=514 Sat Aug 4 16:38:20 2012 Connection closed by foreign host.

It can be seen very well from the server’s response that the value of 42 goes wrong. If we put back the protection, we will get the right result:

R

A

[norbert@matrica halozati]$ telnet localhost 2012 Trying ::1... telnet: connect to address ::1: Connection refused Trying 127.0.0.1... Connected to localhost. Escape character is ’^]’. + + Ertek=43 Kliensek=541 Sat Aug 4 16:47:31 2012 Connection closed by foreign host.

the value of the shared variable is equal to 43 because the query as a client also increment the value. 4.2.3.2

Testing on two machines

D

The following changes have to be applied in the source codes of the client and the server. In the code of the server, //inet_aton ("127.0.0.1", &(szerver.sin_addr)); szerver.sin_addr.s_addr = htonl(INADDR_ANY);

and we use the wildcard address instead of localhost and accordingly with this we apply the server’s IP address in the code of the client: //inet_aton ("127.0.0.1", &(szerver.sin_addr)); inet_aton ("193.6.135.21", &(szerver.sin_addr));

4.2.3.2.1

Portability Now let’s see what may happen if we will try the example in another machine:

nbatfai@morse:~$ gcc szerver2.c -o szerver szerver2.c: In function ‘main’: szerver2.c:158: error: ‘S_IRUSR’ undeclared (first use in this function) szerver2.c:158: error: (Each undeclared identifier is reported only once szerver2.c:158: error: for each function it appears in.) szerver2.c:158: error: ‘S_IWUSR’ undeclared (first use in this function)

74



Recall what we wrote in the previous section about portability. The S_IRUSR and S_IWUSR macros can be found in the manual page man 2 stat. So including the sys/stat.h header hopefully everything will work well for the reader, too:

A FT

[norbert@matrica halozati]$ telnet morse 2012Trying 193.6.135.21... Connected to morse. Escape character is ’^]’. + + Ertek=43 Kliensek=541 Sat Aug 4 17:30:00 2012 Connection closed by foreign host.

D R

Figure 4.1 Compiling the client and the server.

75



D

R

A

FT

Figure 4.2 Running the client and the server.

76



A FT

Figure 4.3 Checking the results.

D R

4.2.3.2.2 Testing on a virtualized machine We have used and recommend the following books: [UNP] and [LINUXPROG]. If the reader wants to get a deeper and overall understanding on network programming, we recommend the former one.

77

FT

A

R

D

A FT Part II

D R

C++ Case Studies

79

FT

A

R

D

In this part • we are going to simplify the communication protocol of the 2D RCSS • then we will develop our own client agent that uses this simplified protocol and is based on the rcssserver (15.1.0) and its sample client.

D R

A FT

• finally, the modifications of rcssserver and rcsslogplayer will be shown that allow us to draw equipotential surfaces of the Brillinger potential.

81

FT

A

R

D

Chapter 5

D R

A FT

A simplified protocol of 2D RCSS

83

FT D

R

A

Abstract

CHAPTER 5. A SIMPLIFIED PROTOCOL OF . . .

5.1

5.1. EMASCULATION OF THE AI-BASED . . .

Emasculation of the AI-based simulation model of RCSS

Introducing a new positioning command for RCSS client protocol

A

5.1.1

FT

In the FerSML (Footballer and Football Simulation Markup Language) project, at first our interest was only to develop a simulation based decision making support expert system for professional football (soccer). But of course such a development is not possible without supporting the real football teams and using suitable analytical tools to observe players of these cooperative teams. The organisation of this work is already under way in the framework of an industrial research and development project. Our motivation comes from our former experience in mobile soccer gaming [FERSML] then we have concentrated only on the football played in reality. At that time, using the robocup simulation environment hadn’t even occurred to us, because the robot soccer is purely artificial intelligence. And because in our case, in contrast a player or in the FerSML’s terminology an avatar was considered to be a given and finished entity as a complete and perfect footballer in the simulation, accordingly we didn’t want to build the abstraction of the players from scratch and step by step to develop their cognitive skills required for playing football. For example, to illustrate our approach, in the FerSML simulations a player knows its own position with any degree of accuracy. The avatars are (trivially) fully aware of the meaning of the position of themselves and of all other players or the parts of the field of play. By contrast, in RCSS simulations an agent has to build positioning information for itself. But meanwhile, waiting for the start of the mentioned research and development project, the question arose whether RCSS tools may be applied to sport science purposes of FerSML platform, or more exactly, whether the rcssserver could possibly be used for support the FerSML simulations. However, even in that case, the classical RCSS client agents would not be required because the rcssserver would be modified in order to enable working with clients defined at a higher abstraction level. That is, for example, the FerSML clients would be able to access the all data of the rcssserver directly and they could communicate with each other without any restrictions during simulation. At this moment, the usage of RCSS software tools for purposes of the FerSML project is an open question.

D R

In this case study we investigate the possibility of modifying RCSS protocol to be able to be used for sport scientific purposes [SRCSS]. We introduce a new client command (pos X Y power) to control the agents. Here (X, Y) is the position on the field where the player will move. The parameter power is the same as the parameter of the original (dash power) command. With this lucky choice therefore the implementation of the new pos command may be built on the implementation of the dash command. 5.1.1.1

Testing of the newly introduced command

For testing we modify the team called Debreceni Hivatásos FC++. The newly added beforeKic kOffwithPos function will be called from the control POSIX thread: static void * prog1Thread(void * client) { Client * thisclient = (Client *) client; char buf[1024]; usleep(100*1000); for (;;) {

usleep(100*1000);

switch (thisclient->bl.get_play_mode()) { case before_kick_off: beforeKickOff(thisclient); break; case play_on: case kick_off_l: case kick_off_r: //playOn(thisclient); beforeKickOffwithPos(thisclient);

85



break; } } // for (;;) return 0; }

The beforeKickOffwithPos defines a line-up and the players will move towards the positions defined in this line-up. static void beforeKickOffwithPos(Client * thisclient) { char buf[1024];

D R A

FT

// középkezdési felállás static int formation[][2] = { // Goalie, kapus {-51, 0}, // Attackers, támadók {-4, 10}, {-1, 1}, {-3, -11}, // Midfielders, középpályások {-18, -16}, {-17, 2}, {-18, 17}, // Defenders, véd˝ ok {-35, -19}, {-33, -10}, {-34, 12}, {-35, 24} };

int squad_number = thisclient->bl.get_squad_number() -1; std::snprintf(buf, 64, "(pos %d %d 40)\0", formation[squad_number][0], formation[squad_number][1]); thisclient->sndCmd(buf);

In parallel we modified the original beforeKickOff line-up in order to allow easier interpretation: now players stand in a line. static void beforeKickOff(Client * thisclient) { char buf[1024];

// középkezdési felállás static int formation[][2] = { // Goalie, kapus {-10, 0}, // Attackers, támadók {-12, 0}, {-14, 0}, {-16, 0}, // Midfielders, középpályások {-18, 0}, {-20, 0}, {-22, 0}, // Defenders, véd˝ ok {-24, 0}, {-26, 0}, {-28, 0},

86



{-30, 0} }; // minden játékos a saját pozíciójába a középkezdéskor int squad_number = thisclient->bl.get_squad_number() -1; std::snprintf(buf, 64, "(move %d %d)\0", formation[squad_number][0], formation[squad_number][1]); thisclient->sndCmd(buf);

A FT

In the source code of rcssserver, the newly introduced pos command is developed by using the existing implementation of dash command. First, we simply calculate the angle of target position then the agent will be dashed to the calculated direction. Making this modification on the server side will not affect the existing client agents because the pos command will be received by the server. However, we have weaved the agent position into the server’s response. In most cases it does not cause any problems, but to be on the safe side, this behavior can be switched on using the server’s command line argument rcssserver server::light_response=true and it is switched off in default: [norbert@matrica rcssserver-15.1.0.light1]$ src/rcssserver rcssserver-15.1.0.light1

Copyright (C) 1995, 1996, 1997, 1998, 1999 Electrotechnical Laboratory. 2000 - 2012 RoboCup Soccer Simulator Maintenance Group. Simulator Random Seed: 1341319832 CSVSaver: Ready STDOutSaver: Ready Using simulator’s random seed as Hetero Player Seed: 1341319832 wind factor: rand: 0.000000, vector: (0.000000, 0.000000) Hit CTRL-C to exit Light response: false

D R

Figure 5.1 The LightFC++ team assembles before kick off using the move command.

87



FT

Figure 5.2 After kick off the players move using the pos command.

D R A

The continuous movement of the players is well observed in the video playback at URL http://youtu.be/ZoANLujlt1A

D OWNLOAD OF THE SIMPLIFIED RCSSSERVER AND THE TEAM L IGHT FC++ http://www.inf.unideb.hu/~nbatfai/rcssserver-15.1.0.light4.tar.bz2.

5.1.1.2

The response of the simplified server

We have already mentioned that modified server’s response can be switched on or switched off by using the server::light_response parameter. If it is set to true then sendLight function will print the agent’s own position to the beginning of the see command. This function is a newly added one to src/visualsenderplayer.cpp source in the rcssserver’s package. // light if (ServerParam::instance().lightResponse()) sendLight();

sendFlags(); sendBalls(); sendPlayers(); sendLines(); serializer().serializeVisualEnd( transport() ); transport() << std::ends << std::flush;

}

void VisualSenderPlayerV1::sendLight() { serializer().serializeVisualObject( transport(),

88


5.2. THE TEAM CALLED DEBRECEN . . .

"light", self().pos().x, self().pos().y); }

Now let’s see how the see sent to clients looks.

5.2

-

-

FT

(see 667 (light -35.0361 -19.0086) ((f c) 40 28) ((f c t) 38.1 -23) ((f r t) 89.1 -10) ((f r b) 102.5 31) ((f g r b) 90.9 17) ((g r) 90 12) ((f g r t) 88.2 8) ((f p r b) 81.5 29) ((f p r c) 73.7 15) ((f p r t) 70.8 -1) ((F) 1.5 -130) ((f t 0) 40.4 -30) ((f t r 10) 49.4 -24) ((f t r 20) 58.6 -20) ((f t r 30) 68 -17) ((f t r 40) 77.5 -15) ((f t r 50) 87.4 -13) ((f t l 10) 32.1 -39 0 0.1) ((f b r 30) 87.4 42) ((f b r 40) 94.6 38) ((f b r 50) 102.5 34) ((f r 0) 94.6 12) ((f r t 10) 92.8 6) ((f r t 20) 92.8 -1) ((f r t 30) 92.8 -7) ((f r b 10) 96.5 17) ((f r b 20) 100.5 23) ((f r b 30) 104.6 28) ((b) 40.4 28) ((p "LightFC++") 40.4 43) ((p "LightFC++") 40.4 30) ((p "LightFC++") 33.1 14) ((p "LightFC++" 5) 18.2 10 0 0 0 0) ((l r) 87.4 90))

The team called Debrecen Great Forest FC++-->

The team Debrecen Great Forest FC++ is further developed from the team Debreceni Hivatásos FC++ that was developed in the book [PARP]. The interesting thing about Debrecen Great Forest FC++ is that it has already used the newly introduced pos command. If we compare the lobogofcpp.h source files of Debrecen Great Forest FC++ and Debreceni Hivatásos FC++ we will see the that the former one is shorter than the latter one. Accordingly, the lexer has also changed as it is shown in the next code snippet from the point of view of the ball:

A

{BALL}{WS}{FLOAT}{WS}{FLOAT} { std::sscanf(yytext, "((b) %f %f", &dist_buffer, &ang_buffer); ball.setDistAng(time, dist_buffer, ang_buffer); }

The lexer had to be extended with further player modes, for example the following referee’s messages are received by the clients:

D R

enum RefereePlayMode { before_kick_off, play_on, half_time, drop_ball, kick_off_r, kick_off_l, corner_kick_r, corner_kick_l, free_kick_l, free_kick_r, kick_in_l, kick_in_r, goal_l, goal_r, free_kick_fault_l, free_kick_fault_r, offside_l, offside_r };

Our lecture notes focus on the corner kick and the throw-in play modes. The kick off and the ball in play modes have already been processed in the previous versions of the teams, see the book [?]. The kick off is handled by the beforeKickOff, the ball in play and the newly handled modes are processed by the function playOn: switch (thisclient->bl.get_play_mode()) {

89



D R A

FT

case half_time: case goal_l: case goal_r: case before_kick_off: beforeKickOff(thisclient); //beforeKickOff_light_testing(thisclient); break; case play_on: case kick_off_l: case kick_off_r: thisclient->bl.nof_kickin_quantums = 0; playOn(thisclient); //playOn_light_testing(thisclient); break; case kick_in_l: if (thisclient->bl.get_lr() == ’l’) kickIn(thisclient); else playOn(thisclient); break; case kick_in_r: if (thisclient->bl.get_lr() == ’r’) kickIn(thisclient); else playOn(thisclient); break; case corner_kick_r: if (thisclient->bl.get_lr() == ’r’) cornerKickAtt(thisclient); else cornerKickDef(thisclient); break; case corner_kick_l: if (thisclient->bl.get_lr() == ’l’) cornerKickAtt(thisclient); else cornerKickDef(thisclient); break; case free_kick_l: case free_kick_r: case free_kick_fault_l: case free_kick_fault_r: case offside_l: case offside_r: case drop_ball: playOn(thisclient); break; }

In this snippet, the commented out beforeKickOff_light_testing was used only to test the simplification. At taking a throw-in (in the case of kick_in_l and kick_in_r) we distinguish the team which throws in the ball. And finally the attacker and defender teams are treated separately at corner kicks.

5.2.1

The implementation of the throw-in

We follow the solution shown in the book [MIRC], where we distiguished the moving into the position to make the throw-in and the throw-in itself. The latter activity includes the looking out for teammates to whom the ball can be passed. These activities are not divided into various functions but we use the following kickIn function: static void kickIn(Client * thisclient) {

90



// http://youtu.be/HiaPWqSzYxk char buf[1024]; int time = thisclient->bl.get_time(); int squad_number = thisclient->bl.get_squad_number() -1; int lr = thisclient->bl.get_lr(); // ha látja a lasztit if (thisclient->bl.get_see_ball()) { 1v // kinek kell majd dobni int to;

-

-

FT

thisclient->coach.set_formation(Formations::F_4_4_2_F); int tx = thisclient->coach.get_formation().get_formation_x( squad_number, lr); int ty = thisclient->coach.get_formation().get_formation_y( squad_number);

if (thisclient->bl.get_ball_dist() < .8) { 2v if ((to = thisclient->bl.pass_to_farthes(3)) != -1) { 3v std::snprintf(buf, 64, "(kick %d %f)\0", thisclient->bl. tavhozEro(thisclient->bl.get_own_player(to).getDist()), thisclient->bl.get_own_player(to).getAng()); thisclient->sndCmd(buf); std::cout << time << " " << thisclient->bl.get_squad_number() << " passz (bedobas) " << to+1 << std::endl; } else { // ha nem lát társat if (++thisclient->bl.nof_kickin_quantums > 10) { 4v // ha többen fogognak éppen nem látva egymást, akkor ne a játékvezet˝ oi beavatkozásig tegyék std::snprintf(buf, 64, "(kick %d %f)\0", 20, thisclient->bl.get_ball().getAng()); thisclient->sndCmd(buf); std::cout << thisclient->bl.get_squad_number()<< " vissza pocc a palyara " << std::endl;

A

-

-

D R

-

} else { thisclient->sndCmd("(turn 25)\0"); std::cout << thisclient->bl.get_squad_number()<< " kinek kene dobni? ..." << thisclient->bl.nof_kickin_quantums << std:: endl; }

-

-

}

// megy a labdára innen 5v } else if (std::abs(thisclient->bl.get_ball_ang()) > 20.0) { std::snprintf(buf, 64, "(turn %f)\0", thisclient->bl.get_ball_ang ()); thisclient->sndCmd(buf); std::cout << thisclient->bl.get_squad_number()<< "turn" << thisclient->bl.get_ball_ang() << std::endl; } else if (thisclient->bl.get_ball_dist() < 30.0 && thisclient->bl. pass_to_farthes(2)==-1) { 6v // 30-ról is sprintel bedobni, ha nincs közelebbi társ thisclient->sndCmd("(dash 100)"); std::cout << thisclient->bl.get_squad_number()<< " megyek dobni 100" << std::endl; 7v } else if (thisclient->bl.get_ball_dist() < 40.0 && ((to=thisclient->

91

-

-

-

-



bl.nof_seen_teammates()) < 3)) { // 40-ról is jön bedobni, ha esetleg lát is társakat (mert az el ˝ oz˝ o ág nem teljesült) std::snprintf(buf, 64, "(dash %f)\0", 100.0/(to + 1.0)); thisclient->sndCmd(buf); std::cout << thisclient->bl.get_squad_number()<< " megyUNK dobni " << std::endl;

-

-

} else { std::snprintf(buf, 64, "(pos %d %d 30)\0", tx, ty); thisclient->sndCmd(buf); } } else { // ha nem látja a lasztit

} }

v

-

FT

thisclient->sndCmd("(turn 40)\0"); std::cout << thisclient->bl.get_squad_number()<< "meccs van? ... ( dobas)" << std::endl;

If an agent can see the ball we will investigate its distance from the ball

1

v, v, v, v, v, v then the following situations will be investigated: 4

v

2

v

3

v

4

v

6

7

Is the ball close enough to kick it?

If yes, then, using the pass_to_farthes function, the agent will ask: whom should be passed to? If there are no suitable teammates, the thrower will kick the ball or turn 25 degrees to look for suitable teammates depending on whether this situation has already happened more than 10 times. Returning to the investigation of the distance of the ball, if the agent can see the ball under an angle smaller than 20 degrees, it will turn in order to try to correct the angle to 0.

D

5

5

A

3

R

2

v

6

v

7

v

8

5.2.1.1

In the same indentation level if the ball’s distance is less than 30 meters and the player is nearest to the ball, the player will sprint to take the throw-in. If none of the above conditions are met, the agent will move towards its tactical position (tx, ty). And finally, if the agent cannot see the ball, it will search the ball, to be more precise, it will make a 40 degrees turn.

Testing the throw-in

We have made a video on testing that can be seen at http://youtu.be/HiaPWqSzYxk. Using screenshots we emphasize some moments in order to better understand how the previous code snippet works. (These pictures are made independently from the video.) 92



FT

Figure 5.3 Testing the throw-in: player 11 kicks the ball across the touch line.

The next code snippet moves the player towards the ball .

} else if (thisclient->bl.get_ball_dist() < 40.0 && ((to=thisclient-> bl.nof_seen_teammates()) < 3)) { // 40-ról is jön bedobni, ha esetleg lát is társakat (mert az el ˝ oz˝ o ág nem teljesült) std::snprintf(buf, 64, "(dash %f)\0", 100.0/(to + 1.0)); thisclient->sndCmd(buf); std::cout << thisclient->bl.get_squad_number()<< " megyUNK dobni " << std::endl;

-

A

-

-

D R

Figure 5.4 Testing of the throw-in: player 4 starts to move towards the ball.

After some simulation cycles the player 4 will be closer to the ball than 30 meters. } else if (thisclient->bl.get_ball_dist() < 30.0 && thisclient->bl. pass_to_farthes(2)==-1) { // 30-ról is sprintel bedobni, ha nincs közelebbi társ thisclient->sndCmd("(dash 100)");

93

-



std::cout << thisclient->bl.get_squad_number()<< " megyek dobni 100" << std::endl;

-

D R A

FT

Figure 5.5 Testing the throw-in: player 4 is closer than 30 meters.

When the player agent reaches the ball, it will turn in order to see teammates who are available for receiving the ball. Figure 5.6 Testing of the throw-in: player 4 has just arrived to the ball.

The player 4 has found player 3 who is available for receiving the ball. if (thisclient->bl.get_ball_dist() < .8) { if ((to = thisclient->bl.pass_to_farthes(3)) != -1) { std::snprintf(buf, 64, "(kick %d %f)\0", thisclient->bl. tavhozEro(thisclient->bl.get_own_player(to).getDist()), thisclient->bl.get_own_player(to).getAng());

94



thisclient->sndCmd(buf); std::cout << time << " " << thisclient->bl.get_squad_number() << " passz (bedobas) " << to+1 << std::endl;

-

FT

Figure 5.7 Testing of the throw-in: player 4 passes the ball to player 3.

D R

A

Figure 5.8 Testing the throw-in: the ball is moving towards player 3.

5.2.2

The introduction of the tactical lineups

The Debrecen Great Forest FC++’s main new feature is the introduction of the tactical lineups into the agents. The lineups are embedded in the Coach class. class Coach { public: Coach(int formi = 0):formi(formi) { if (formi >= Formations::NOF || formi <0) formi = 0;

95



formations = new Formation[Formations::NOF] { // (a +--os megadásokkal már tisztára FerSML feeling) // 4_3_3 h {-51, 0, // att -4, 10, -1, 0, -3, -11, // mid -18, -16, -17, 2, -18, 17, // def -35, -19, -33, -10, -34, 12, -35, 24},

class Formations { public: static static static static

int int int int

const const const const

F_4_3_3_H F_4_3_3_F F_4_4_2_H F_4_4_2_F

= = = =

0; 1; 2; 3;

static int const F_CORNER_ATT = 4; static int const F_CORNER_DEF = 5;

FT

For illustrative purposes we use two lineups, these are the 4-4-2 and 4-3-3 soccer formations.

A

// number of all formations static int const NOF = F_CORNER_DEF+1;

R

};

D

Figure 5.9 The 4-4-2 formation.

The other two formations control the positioning of the players at corner kicks. 96



FT

Figure 5.10 Corner kick formations.

Example 5.1 Placing a player beside a goalpost Modify the defensive formation F_CORNER_DEF so that a player will stand beside a goalpost. 5.2.2.1

The implementation of the corner kick

A

Taking and defending a corner have been implemented in two different ways. The organization of the attackers’ source code is similar to what was used in the implementation of the throw-in. But in the case of the corner kicking there is a distinguished player who will be taking the corner kick. This player will be player 4 in default: static void cornerKickAtt(Client * thisclient) { // http://youtu.be/93F43ppEQ2g

D R

char buf[1024];

int time = thisclient->bl.get_time(); int squad_number = thisclient->bl.get_squad_number() -1; int lr = thisclient->bl.get_lr(); thisclient->coach.set_formation(Formations::F_CORNER_ATT); int tx = thisclient->coach.get_formation().get_formation_x(squad_number, lr); int ty = thisclient->coach.get_formation().get_formation_y(squad_number); SeenFlag & sf_opp_gt = (lr==’l’)?thisclient->bl.get_flag(Flag::GRT): thisclient->bl.get_flag(Flag::GLT); SeenFlag & sf_opp_gb = (lr==’l’)?thisclient->bl.get_flag(Flag::GRB): thisclient->bl.get_flag(Flag::GLB);

-

-

-

// ha látja a lasztit if (thisclient->bl.get_see_ball()) { if (thisclient->bl.get_ball_dist() < .8) { // ha már ott van a lasztinál, ha látja a kaput, elvégzi a szögletet: if (time - sf_opp_gt.get_time_stamp() < 2) { std::snprintf(buf, 64, "(kick %d %f)\0", 100, sf_opp_gt.getAng()); thisclient->sndCmd(buf); std::cout << time << " " << thisclient->bl.get_squad_number() << " berug (szoglet) " << std::endl;

97

-



} else if (time - sf_opp_gb.get_time_stamp() < 2) { std::snprintf(buf, 64, "(kick %d %f)\0", 100, sf_opp_gb.getAng()); thisclient->sndCmd(buf); std::cout << time << " " << thisclient->bl.get_squad_number() << " berug (szoglet) " << std::endl;

-

} else { // ha nem látja a kaput thisclient->sndCmd("(turn 25)\0"); std::cout << thisclient->bl.get_squad_number()<< " hol a kapu ? ..." << std::endl; }

-

FT

// megy a labdára innen } else if (std::abs(thisclient->bl.get_ball_ang()) > 20.0) { std::snprintf(buf, 64, "(turn %f)\0", thisclient->bl.get_ball_ang ()); thisclient->sndCmd(buf); std::cout << thisclient->bl.get_squad_number()<< "turn" << thisclient->bl.get_ball_ang() << std::endl; } else if (thisclient->bl.get_ball_dist() < 30.0 && thisclient->bl. pass_to_farthes(2)==-1) { // 30-ról is sprintel bedobni, ha nincs közelebbi társ thisclient->sndCmd("(dash 100)"); std::cout << thisclient->bl.get_squad_number()<< " megyek dobni 100" << std::endl;

-

-

D R A

} else if (squad_number == 3) { // a kijelölt játékos (ez tk. a 4-es player) megy elvégezni thisclient->sndCmd("(dash 100)"); std::cout << thisclient->bl.get_squad_number()<< " kijeloltkent megyek dobni 100" << std::endl;

-

} else { // többiek (akik nem mennek a labdára elvégezni) helyezkednek a szöglethez adott felállás szerint std::snprintf(buf, 64, "(pos %d %d 90)\0", tx, ty); thisclient->sndCmd(buf); }

} else { // ha nem látja a lasztit thisclient->sndCmd("(turn 40)\0"); std::cout << thisclient->bl.get_squad_number()<< "meccs van? ... ( szoglet)" << std::endl;

-

-

-

}

}

The defending is organized much more simply:

static void cornerKickDef(Client * thisclient) { // http://youtu.be/93F43ppEQ2g char buf[1024]; int time = thisclient->bl.get_time(); int squad_number = thisclient->bl.get_squad_number() -1; int lr = thisclient->bl.get_lr(); thisclient->coach.set_formation(Formations::F_CORNER_DEF); int tx = thisclient->coach.get_formation().get_formation_x(squad_number, lr); int ty = thisclient->coach.get_formation().get_formation_y(squad_number);

98

-


5.3. THE TEAM CALLED DEBRECEN DEEP . . .

// ha látja a lasztit if (thisclient->bl.get_see_ball()) { std::snprintf(buf, 64, "(pos %d %d 85)\0", tx, ty); thisclient->sndCmd(buf); } else { // ha nem látja a lasztit thisclient->sndCmd("(turn 40)\0"); std::cout << thisclient->bl.get_squad_number()<< "meccs van? ... ( szoglet)" << std::endl;

-

} }

We have made a video on testing that can be seen at http://youtu.be/-

A FT

5.2.2.1.1 Testing the corner kick 93F43ppEQ2g.

5.2.2.1.2 The evaluation of the team Debrecen Great Forest FC++ We cannot say that this team is able to play the soccer game itself. However the Debrecen Great Forest FC++ has already handled most of the play modes. The role of this team is merely to be used as an important step in developing the next team called Debrecen Deep Forest FC++ that will win agains Debrecen Great Forest FC++.

D OWNLOADING THE D EBRECEN G REAT F OREST rcssserver-15.1.0.light4.gf.tar.bz2.

D R

Example 5.2 Free kicks Following the implementations of the throw-in or the corner kick, develop your own implementation for the missing play modes like the free kick.

5.3

The team called Debrecen Deep Forest FC++

The team Debrecen Deep Forest FC++ is further developed from the team Debrecen Great Forest FC++. We focus on the implementation of the playOn function. We do not make major changes, but make fine-tuning adjustments in the code of Debrecen Great Forest FC++: • The goals scored by the Debrecen Great Forest FC++ are typically own goals or accidental goals due to the fact that this team cannon play organized attacking or defending football. The players should be positioned higher up on the pitch in order to improve the team’s play. Therefore we introduce that the players are able to pass only forward. • The main cause of the own goals is a slide tackle that is done in the wrong direction. Therefore we impove the angle for slide tackles. • We modify the method of gaining the ball. For example, as the following two figures show, player 3 and player 6 should go to the ball, but they do not do it because we use the method introduced above for the throw-in and the corner kick: the player agent will only go to the ball if it cannot see the teammates. 99



FT

Figure 5.11 Player 3 and player 6 should go to the ball.

Now an opposing player gains possession of the ball, therefore we will modify the agent: if the ball can be seen closer than the teammates, the agent will also go to the ball.

D R A

Figure 5.12 An opposing player gains possession of the ball.

• Like in the cases of the throw-in and the corner kick, the player possessing the ball will turn around in a circle to see where the teammates are. • We have also made further small improvements, for example the goalkeeper agent does not run out to a distance of 30 meters from its goal. The source code of the improvements are the following: static void playOn(Client * thisclient) { char buf[1024]; int time = thisclient->bl.get_time(); int squad_number = thisclient->bl.get_squad_number() -1; int lr = thisclient->bl.get_lr(); // egész pályás felállásba kapcsol (középkezdéskor még fél pályás volt, most átmegy "támadásba")

100

-



thisclient->coach.set_formation(Formations::F_4_3_3_F); // mint a FerSML-ben a (celx, cely) ennek felel meg most intuíciusan a t( arget)x, t(arget)x int tx = thisclient->coach.get_formation().get_formation_x(squad_number, lr); int ty = thisclient->coach.get_formation().get_formation_y(squad_number);

D R

A

FT

// ha látja a lasztit if (thisclient->bl.get_see_ball()) { int to = thisclient->bl.pass_to_nearest(2); int pd = (to!=-1)?thisclient->bl.get_own_player(to).getDist():0; // és olyan közel, hogy meg tudja rúgni if (squad_number == 0 && thisclient->bl.get_ball_dist() < 1.2) { std::snprintf(buf, 64, "(catch %f)\0", thisclient->bl. get_ball_ang()); thisclient->sndCmd(buf); // std::cout << " kapus bravur " << std::endl; } else if (thisclient->bl.get_ball_dist() < .8) { //std::cout << thisclient->bl.get_squad_number()<< " < .8 " << std::endl; // akkor // esetleg ide passzol majd int pass_to; // az ellen kapuját SeenFlag & sf_opp = (lr==’l’)?thisclient->bl.get_flag(Flag::GR): thisclient->bl.get_flag(Flag::GL); // a sajátját SeenFlag & sf_own = (lr==’l’)?thisclient->bl.get_flag(Flag::GL): thisclient->bl.get_flag(Flag::GR); // látta mostanság if (time - sf_opp.get_time_stamp() < 2 // és elég közel van (30m) && sf_opp.getDist() < 30.0) { // felé rúgja ha látja kick(thisclient, 100, sf_opp.getAng()); std::cout << thisclient->bl.get_squad_number()<< " kapura lo " << std::endl; // ha nincs elég közel, akkor próbál passzolni } else if ((pass_to = thisclient->bl.pass_to_farthest_fwd()) != -1 && (time - sf_own.get_time_stamp() > 3)) { kick(thisclient, thisclient->bl.tavhozEro(thisclient->bl.get_own_player( pass_to).getDist()), thisclient->bl.get_own_player(pass_to).getAng() ); // ha nem tud passzolni és közel a saját kapu, akkor (feltéve , hogy bal oldali a saját kapu) } else if (time - sf_own.get_time_stamp() < 1 // és elég közel van (25m) && sf_own.getDist() < 16.0) { // ha azt nem látja, akkor becsúszik kick(thisclient, 100, 180 + sf_own.getAng()); std::cout << thisclient->bl.get_squad_number()<< " becsuszik " << std::endl; } else { if (++thisclient->bl.nof_possessing_quantums < 7) { thisclient->sndCmd("(turn 30)\0"); std::cout << thisclient->bl.get_squad_number()<< " turn for finding targets " << std::endl; } else { kick(thisclient, 10, 20); std::cout << thisclient->bl.get_squad_number()<< " kis kick " << std::endl; }

101

-

-

-

-

-

-

-

-

-

-



D R A

FT

} } else if (std::abs(thisclient->bl.get_ball_ang()) > 20.0) { std::snprintf(buf, 64, "(turn %f)\0", thisclient->bl.get_ball_ang ()); thisclient->sndCmd(buf); // std::cout << thisclient->bl.get_squad_number()<< "turn" << thisclient->bl.get_ball_ang() << std::endl; } else if (squad_number != 0 && thisclient->bl.get_ball_dist() < 40.0 && to == -1) { // legyen agresszívabb a labdaszerzés: 40-r˝ ol is sprintel bedobni , ha nincs közelebbi társ dash_to_ball_100(thisclient, thisclient->bl.get_ball_dist()); //std::cout << thisclient->bl.get_squad_number()<< " egyedul megyek labdara 100" << std::endl; } else if (squad_number > 4 && thisclient->bl.get_ball_dist() < 30 && thisclient->bl.get_ball_dist() < pd && to != -1) { // legyen agresszívabb a labdaszerzés: 40-r˝ ol is sprintel bedobni , ha nincs közelebbi társ dash_to_ball_100(thisclient, thisclient->bl.get_ball_dist()); //std::cout << thisclient->bl.get_squad_number()<< " megyunk a labdara 100" << std::endl; } else if (squad_number != 0 && thisclient->bl.get_ball_dist() < 16.0 && (thisclient->bl.nof_seen_teammates()) < 1) { // 40-ról is jön bedobni, ha esetleg lát is társakat (mert az el ˝ oz˝ o ág nem teljesült) dash_to_ball_100(thisclient, thisclient->bl.get_ball_dist()); //std::cout << thisclient->bl.get_squad_number()<< " megyUNK a labdara " << std::endl; } else if (thisclient->bl.get_ball_dist() < 9.0) { dash_to_ball_100(thisclient, thisclient->bl.get_ball_dist()); //std::cout << thisclient->bl.get_squad_number()<< " megyUNK a labdara, aki csak latja " << std::endl; } else if (thisclient->bl.get_ball_dist() < 30.0) { std::snprintf(buf, 64, "(pos %d %d 50)\0", tx, ty); thisclient->sndCmd(buf); //std::cout << thisclient->bl.get_squad_number()<< " helyezkedik "<< "(" << tx << ", " << ty << ")" << std::endl; } else { std::snprintf(buf, 64, "(pos %d %d 30)\0", tx, ty); thisclient->sndCmd(buf); //std::cout << thisclient->bl.get_squad_number()<< " helyezkedik "<< "(" << tx << ", " << ty << ")" << std::endl; } } else { // ha nem látja a labdát // visszamegy "védekezésbe" thisclient->coach.set_formation(Formations::F_4_3_3_H); thisclient->sndCmd("(turn 40)\0"); //std::cout << thisclient->bl.get_squad_number()<< "meccs van? ..." << std::endl; }

-

-

-

-

-

-

-

-

-

-

}

5.3.1

The evaluation of the team Debrecen Deep Forest FC++

Unfortunately the above improvements do not reach the anticipated level, but the Debrecen Deep Forest FC++ can typically defeat the Debrecen Great Forest FC++ as it is shown by the next match results: 201208191102-DForestFC++_13-vs-GForestFC++_2.rcg 201208191116-GForestFC++_1-vs-DForestFC++_5.rcg 201208191128-DForestFC++_4-vs-GForestFC++_3.rcg 201208191200-DForestFC++_4-vs-GForestFC++_6.rcg 201208191212-GForestFC++_2-vs-DForestFC++_3.rcg 201208191223-DForestFC++_9-vs-GForestFC++_1.rcg

102



201208191235-DForestFC++_6-vs-GForestFC++_2.rcg 201208191247-GForestFC++_2-vs-DForestFC++_4.rcg 201208191301-DForestFC++_10-vs-GForestFC++_8.rcg 201208191318-DForestFC++_5-vs-GForestFC++_3.rcg

• But then a test match was played so well that we have recorded it to a video DForestFC++ GForestFC++ 13:2 that can be found at http://youtu.be/FOb8IQ0AF5w. • GForestFC++ - DForestFC++ 1:5 • DForestFC++ - GForestFC++ 4:3 • DForestFC++ - GForestFC++ 4:6 • GForestFC++ - DForestFC++ 2:3

• DForestFC++ - GForestFC++ 6:2 • GForestFC++ - DForestFC++ 2:4 • DForestFC++ - GForestFC++ 10:8 • DForestFC++ - GForestFC++ 5:3

FT

• DForestFC++ - GForestFC++ 9:1

A

The Debrecen Deep Forest FC++ also produces unintelligible errors. For example, the players pass backward in some given situation, due to the estimated position of the seen player is so wrong that it impairs the work of the function pass_to_farthest_fwd.

D R

D EBRECEN D EEP F OREST - HELIOS_ BASE , 0:

D EBRECEN D EEP F OREST - HELIOS2011, 0:

D OWNLOADING THE D EBRECEN D EEP F OREST FC++ rcssserver-15.1.0.light5.df.tar.bz2.

Example 5.3 Do not pass backward Improve the code so that the passing backward should occurs as rarely as possible. But for now do not use the advantages of the simplification. bool fwd(char lr, float fromx) const { if (lr == ’l’) { if (fromx < this->x) return true; else return false;

103



} else { if (fromx > this->x) return true; else return false; } }

Example 5.4 A good starting At kick off the positions of all players are well known. Therefore it is not too hard to program a good kick-off, do it now yourself.

T HE D EBRECEN D EEP F OREST FC++

FT

E XTENDING THE SIMPLIFICATION OF THE RCSS SERVER

RUNS WITH DEFAULTS

A

It may be noted that the Debrecen Deep Forest FC++ uses the pos command, but neither the client agent nor the server use the light response data. To be more precise, the client agent does not use and the server does not send the light response data, the latter case can be seen in the next screen snippet:

$ src/rcssserver rcssserver-15.1.0.light4.df

-

R

Copyright (C) 1995, 1996, 1997, 1998, 1999 Electrotechnical Laboratory. 2000 - 2012 RoboCup Soccer Simulator Maintenance Group.

D

Simulator Random Seed: 1345375129 CSVSaver: Ready STDOutSaver: Ready Using simulator’s random seed as Hetero Player Seed: 1345375129 wind factor: rand: 0.000000, vector: (0.000000, 0.000000) Hit CTRL-C to exit Light response: false Light response with angle: false Light response with angles: false

5.4

The team called Debrecen Round Forest FC++

Finally, to close the robot soccer examples, the Debrecen Deep Forest FC++ is further developed. The Debrecen Round Forest FC++ has already used the light response data from the simplified server. In addition, we improve the positioning of the players and introduce the usage of the online coach for this team to be developed. 104


5.4.1


The additional command line arguments of the simplified server

• server::light_response If it is switched on, the simplified server will send back the player agent’s own position. • server::light_response_with_angle If it is switched on, the simplified server will send back the player agent’s own position and its own body angle. • server::light_response_with_angles If it is switched on, the simplified server will send back the player agent’s own position and its own body and head angles. 5.4.1.1

The response of the simplified server

FT

To test the response give the commands turn_neck 20 and turn 30.

thisclient->bl.get_squad_number() thisclient->bl.get_time() << thisclient->bl.estx << thisclient->bl.esty << thisclient->bl.esta * (180.0 /

-

thisclient->bl.estn * (180.0 /

-

A

thisclient->sndCmd("(turn_neck 20)\0"); thisclient->sndCmd("(turn 30)\0"); ... std::cout << std::setw (6) << "squad " << std::setw (10) << " time " << std::setw (5) << " x " << std::setw (5) << " y " << std::setw (13) << " ang (body) " << 3.14159265359) << std::setw (13) << " ang (neck) " << 3.14159265359) << std::setw (13) << " ang (head) " << std::endl;

thisclient->bl.head_angle

<<

<<

then investigate the output: time 0

x -12

y -37

D R

squad 4 20 squad 4 20 squad 4 20 squad 4 20 squad 4 20

ang (body) 31.5529

ang (neck) 20

ang (head)

-

time 0

x -12

y -37

ang (body) 31.5529

ang (neck) 20

ang (head)

-

time 0

x -12

y -37

ang (body) 31.5529

ang (neck) 20

ang (head)

-

time 0

x -12

y -37

ang (body) 31.5529

ang (neck) 20

ang (head)

-

time 0

x -12

y -37

ang (body) 31.5529

ang (neck) 20

ang (head)

-

and finally compare it to the soccerwindow2’s debug information.

Figure 5.13 A portion of the soccerwindow2’s log file.

5.4.1.2

Receiving the response of the simplified server

The light response data and the estimated data are already handled separately in the lexer class: 105



// from light response float x; float y; float head_angle; // neck angle (rad) float body_angle; // (rad) // from classical estimations float estx; // x float esty; // y float esta; // body_angle (deg) float estn; // head_angle (deg) (from body_sense/head_angle)

5.4.2

Introducing the usage of the online coach

FT

The Debrecen Round Forest FC++ has already used the online coach. To enable this feature we need to connect the default 6002 port and communicate using the online coach’s protocol [RCSSMANUAL]. Now we are going to send the Debrecen Round Forest FC++’s XPM team logo as shown by the next code snippet: -

-

-

-

D

R

A

std::snprintf(buf, 512, "(team_graphic (%d %d %s))", 0, 0, " \"8 8 1 1\" \" c None\" \" \" \" \" \" \" \" \" \" \" \" \" \" \" \" \" "); thisclient->sndCmd(buf); std::snprintf(buf, 512, "(team_graphic (%d %d %s))", 1, 0, " \"8 8 5 1\" \" c None\" \". c #1F1F1A\" \"+ c #2A2A24\" \"@ c #36362F\" \"# c #434239\" \" \" \" \" \" \" \" \" \" \" \" @#\" \" @@@\" \" ++..\" "); thisclient->sndCmd(buf); std::snprintf(buf, 512, "(team_graphic (%d %d %s))", 2, 0, " \"8 8 8 1\" \" c None\" \". c #2A2A24\" \"+ c #36362F\" \"@ c #434239\" \"# c #504E44\" \"$ c #5C594E\" \"% c #666457\" \"& c #767365\" \" \" \" $\" \" $$$\" \" @##$%\" \"+@#$$%%$\" \"@#@@##$%\" \".@$###%&\" \"@%$$$$%&\" "); thisclient->sndCmd(buf); std::snprintf(buf, 512, "(team_graphic (%d %d %s))", 3, 0, " \"8 8 6 1\"\" c None\"\". c #5C594E\"\"+ c #666457\"\"@ c #767365\"\"# c #8B8778\"\"$ c #9F9B89\"\" +@@##\"\".++@@@@@\"\"..++++@@\"\"@@@@ ####\"\"..++@@@@\"\"++@@####\"\"@###$$$$\"\"@###$$$$\" "); thisclient->sndCmd(buf); std::snprintf(buf, 512, "(team_graphic (%d %d %s))", 4, 0, " \"8 8 12 1\" \" c None\" \". c #2A2A24\" \"+ c #36362F\" \"@ c #434239\" \"# c #504E44\" \"$ c #5C594E\" \"% c #666457\" \"& c #767365\" \"* c #8 B8778\" \"= c #9F9B89\" \"- c #B5B29E\" \"; c #C8C6B2\" \"$# * \" \"%$@%=-**\" \"&&&&****\" \"**======\" \"%%%%%&&*\" \"%$#.#&*=\" \"&%%+$&=;\" \"&%%+#%*;\" "); thisclient->sndCmd(buf); std::snprintf(buf, 512, "(team_graphic (%d %d %s))", 5, 0, " \"8 8 5 1\" \" c None\" \". c #8B8778\" \"+ c #9F9B89\" \"@ c #B5B29E\" \"# c #C8C6B2\" \" \" \". \" \"...+ \" \"+...++ \" \".++@ +++.\" \"+.....++\" \"@..++++.\" \"#+.+@@@@\" "); thisclient->sndCmd(buf); std::snprintf(buf, 512, "(team_graphic (%d %d %s))", 6, 0, " \"8 8 4 1\" \" c None\" \". c #8B8778\" \"+ c #9F9B89\" \"@ c #B5B29E\" \" \" \" \" \" \" \" \" \" \" \"+ \" \"+++ \" \"@+.+ \" "); thisclient->sndCmd(buf); std::snprintf(buf, 512, "(team_graphic (%d %d %s))", 7, 0, " \"8 8 1 1\" \" c None\" \" \" \" \" \" \" \" \" \" \" \" \" \" \" \" \" "); thisclient->sndCmd(buf);

-

-

-

-

-

The protocol supports only the png image format and can handle a maximum image size of 256x64. The team logo must be divided into tiles because the team_graphic command uses tiles of the size 8x8. 106



The first two parameters of the command gives the coordinates of the given tile in the range of (0-31)x(07) then the third parameter is followed that gives the rows of the tile. Example 5.5 Create the your own XPM team logo This exercise is fully solved in Java in the book [MIRC]. All you have to do is to rewrite it into C++.

GIMP, GIMP, GIMP Use the GIMP, it can save to XPM.

To connect the online coach we need to modify the starting script: #!/bin/bash

FT

host=${1-localhost} portp=${2-6000} portc=${3-6002} team=${4-RForestFC++}

A

for ((i=1;i<12;++i)) do src/rcsslightclient -host $host -port $portp -team $team -squad $i& sleep 1 done src/rcsslightclient -host $host -port $portc -team $team -squad 0& exit 0

In the window of the server we can see that the online coach has connected: $ src/rcssserver server::light_response_with_angles=true rcssserver-15.1.0.light5.rf

D R

Copyright (C) 1995, 1996, 1997, 1998, 1999 Electrotechnical Laboratory. 2000 - 2012 RoboCup Soccer Simulator Maintenance Group. Simulator Random Seed: 1345710410 CSVSaver: Ready STDOutSaver: Ready Using simulator’s random seed as Hetero Player Seed: 1345710410 wind factor: rand: 0.000000, vector: (0.000000, 0.000000) Hit CTRL-C to exit

Light response: false Light response with angle: false Light response with angles: true A A A A A A A A A A A A A

new new new new new new new new new new new new new

(v15) player (v15) player (v15) player (v15) player (v4) monitor (v15) player (v15) player (v15) player (v4) monitor (v15) player (v15) player (v15) player (v15) player

(RForestFC++ (RForestFC++ (RForestFC++ (RForestFC++ connected. (RForestFC++ (RForestFC++ (RForestFC++ connected. (RForestFC++ (RForestFC++ (RForestFC++ (RForestFC++

1) 2) 3) 4)

connected. connected. connected. connected.

5) connected. 6) connected. 7) connected. 8) connected. 9) connected. 10) connected. 11) connected.

107

-



A new (v15) online coach (RForestFC++) connected.

R

A

FT

Figure 5.14 The Debrecen Round Forest FC++’s team logo in the soccerwindow2 and the rcssmonitor.

D OWNLOADING THE D EBRECEN R OUND F OREST FC++

D

rcssserver-15.1.0.light5.rf.tar.bz2.

108

A FT Part III

D R

Java Case Studies

109

FT

A

R

D

Chapter 6

D R

A FT

Community consciousness net

111

FT

D

R

A

Abstract The „Community consciousness net” is only an exercise that is based on the mobile game called Hetedik Szem, in English „Seventh Eye”.

CHAPTER 6. COMMUNITY . . .

6.1. THE SEVENTH EYE MOBILE GAME

„A gépek ilyenformán szakadatlanul együttmuköd˝ ˝ o egységet alkotnak, s e nagy egységen belül a nyilvántartott adatok és ellentmondások folytonos változása szükségszeruen ˝ megy végbe.” —Wigner Jen˝o A tudomány növekedése - kedvez˝o kilátások és várható veszélyek [SZIRE]

6.1

The Seventh Eye mobile game

6.1.1

A FT

The Seventh Eye is a Java ME mobile game which was released as an open source subproject of Jávácska ONE. This game was introduced in detail in the environment of the lecture notes, in Mobil programozás, Nehogy már megint a mobilod nyomkodjon Téged! http://www.inf.unideb.hu/~nbatfai/konyvek/MOBP/mobp.book.xml.pdf, [MOBP]. We are only bringing forward the idea of „Community consciousness net”. The concept of this idea is based on the Java ME MIDP Hungarian language mobile game called Hetedik Szem, or in English Seventh Eye.

The Seventh Eye and the „Community consciousness net”

This exercise is introduced on the blog of the course by the following Hungarian language posts: • „Minket az Isten is egymásnak teremtett” http://progpater.blog.hu/2011/04/24/tudatmintak_rendezese, • „Közösségi háló reloaded” http://progpater.blog.hu/2011/03/11/kozossegi_halo_reloaded.

D R

The game Seventh Eye is „a free will probe”. The name and the idea of the game is rooted in our scientific reading experience, for example in [CSASZAR] book and the articles [VOLF] and [TCON]. The game works on a discrete time scale. It listens the player during 2048 equidistant time intervals of 100 ms. If the player pushes the fire button (it corresponds a situation where the player deflects his finger in line with the terminology of the above mentioned papers) the digit 1 will be assigned to the corresponding time interval and otherwise the digit 0. As a result, we get a sequence of 0’s and 1’s of length 2048. Such sequences are referred to as mental fingerprints in the game. These mental fingerprints are compared by Ziv-Lempel-Welch (LZW) algorithm. The idea of the comparison came from the book [SZSZTEK]. The standard deviations of the lengths of the branches of the LZW tree are compared. In the game we perform hypothesis testing to assess whether the two given standard deviations are from the same distribution or not. Example 6.1 Running the Seventh Eye on a real mobile phone The following photos show how the game runs on a Nokia 6212 classic. Figure 6.1 The starting icon of the Seventh Eye.

113



R

A

Figure 6.3 The main menu of the Seventh Eye.

FT

Figure 6.2 The splash screen of the Seventh Eye.

D

Example 6.2 The client side of the „Community consciousness net” Modify the Seventh Eye so that it will fulfil the following functions. • The user must be able to upload the gathered mental fibgerprints to the server. • The upload code must be run in a separated thread.

Example 6.3 The server side of the „Community consciousness net” Create a Java servlet that can receive and process the mental fingerprints. • First, develop a simple protocol for sending and receiving the mental fingerprints. • Then store the uploaded data in a database. Example 6.4 A community-based exercise In your acquaintance network, • record some fingerprints 114



• then try to draw the community structure using graphs, where the edges represent the nearest neighbours by comparing the mental fingerprints between your acquaintances.

D R

A FT

Example 6.5 A community portal based on the mental fingerprints If the previous exercise is successful, it would be interesting to think about to build a mental fingerprint based community portal.

115

FT

A

R

D

A FT Part IV

D R

Python Case Studies

117

FT

A

R

D

D R

A FT

This part shows the starting steps of building an AIML (Artificial Intelligence Markup Language) based knowledge base.

119

FT

A

R

D

Chapter 7

D R

A FT

A virtual librarian

121

FT

D

R

A

Abstract This exercise mainly helps students of the course called XML, HTML because the programming do not play an essential role in the building of an XML based knowledge base.

CHAPTER 7. A VIRTUAL LIBRARIAN

7.1. KÁLMÁN KÖNYVES

„Detective Del Spooner: Is there something you want tell me? Dr. Alfred Lanning: I’m sorry. My responses are limited. You must ask the right questions. ” —I, Robot [IROBOT]

7.1

Kálmán Könyves

import aiml import commands import re

D R

class TudatFa(object): agak = {}

A

#!/usr/bin/python # -*- coding: utf-8 -*-

FT

Kálmán Könyves (in English Coloman the Bookish) was a famous Hungarian king. But now, in our case here in this case studies he is a virtual librarian chat robot that is based on the Loebner prize-winning ALICE chatbot. Richard Wallace’s ALICE program uses his AIML [AIML] (Artificial Intelligence Markup Language) XML format. ALICE implementations are available in several languages. Now we use the Python implementation. This is called PyAIML or, in its other name, Program Y that can be downloaded from http://sourceforge.net/projects/pyaiml/ For this implementation we write a short front end Python program that is based on the PyAIML’s documentation. It is called KiralyiKonyvtaros.py. The following YouTube video shows its running: http://youtu.be/nVneMJt0UEo. The Kálmán Könyves chatbot is introduced in detail in the paper [KK] or in online form at http://tmt.omikk.bme.h show_news.html?id=5431&issue_id=522. As can be seen and heard in the above video, we also use the espeak program to say ALICE’s responses. A further function of the front end program is to build the LZW tree of words from the conversations. It is interested to note that in a given arbitrary level of the tree a node may include any number of client nodes. The TudatFa class controls the building of the tree of words. The AIMLChatterBot class is a wrapper class that hides the services of the PyAIML chatbot engine. Finally the infinite loop of the function tajekoztat of the class KiralyiKonyvtaros reads the user’s input from the console, then sends it to ALICE and receives back the response from ALICE. In addition the building of the word tree has been called from this loop, too.

# Ide jöhetnek majd olyan funkciók, mint a kapcsolat # az ILS-el, például kölcsönzéshez, hosszabbításhoz stb. class Konyvtaros: # most még ilyenek nincsenek pass

# A PyAIML (ProgramY) AIML cseveg˝ orobotot használjuk, # ebben az osztályban az ezzel kapcsolatos részek class AIMLChatterBot:

def __init__(self): self.konyvtaros = aiml.Kernel() self.konyvtaros.learn("../AIML/*.aiml.xml") self.konyvtaros.setBotPredicate("name", "Konyves Kalman") self.konyvtaros.setBotPredicate("master", "Batfai Norbert es Batfai Erika") self.konyvtaros.setBotPredicate("birthday", "2010. oktober 23.")

class KiralyiKonyvtaros(AIMLChatterBot, Konyvtaros): gyoker = fa = TudatFa()

123



def __init__(self): AIMLChatterBot.__init__(self) def tajekoztat(self): while 1: keres = raw_input(’olvasó> ’) if len(keres) == 0: self.kiir(self.gyoker) break valasz = self.konyvtaros.respond(keres) self.tudatfa(keres+" "+valasz) print valasz print commands.getoutput("espeak -v hu+f1 -p 40 -s 160 -k 8 \""+valasz+"\"" )

FT

def tudatfa(self, szoveg): szavak = re.compile("\s").split(unicode(szoveg, ’utf-8’)) print szavak for szo in szavak: if self.fa.agak.has_key(szo): self.fa = self.fa.agak[szo] print szo + u" - mar szerepelt, raleptem" else: self.fa.agak[szo] = TudatFa() self.fa.agak[szo].agak={} print szo + " - nem szerepelt, felvettem" self.fa = self.gyoker

R

A

melyseg = 0 def kiir(self, honnan): for szo in honnan.agak.keys(): m = (self.melyseg+1)*10 formatum=u"{0:" + str(m) + "d} {1:10s}" print formatum.format(self.melyseg, "<"+szo+">") self.melyseg +=1 self.kiir(honnan.agak[szo]) self.melyseg -=1

D

konyvesKalman = KiralyiKonyvtaros() konyvesKalman.tajekoztat()

124

-



P YTHON VS . C++ It is worth pointing out that the next Python code snippet

for szo in szavak: if self.fa.agak.has_key(szo): self.fa = self.fa.agak[szo] print szo + u" - mar szerepelt, raleptem" else: self.fa.agak[szo] = TudatFa() self.fa.agak[szo].agak={} print szo + " - nem szerepelt, felvettem" self.fa = self.gyoker do exactly the same function as the next C++ snippet

D R

A FT

// Mit kell betenni éppen, ’0’-t? if (b == ’0’) { /* Van ’0’-s gyermeke az aktuális csomópontnak? megkérdezzük T˝ ole, a "fa" mutató éppen reá mutat */ if (!fa->nullasGyermek ()) // ha nincs, hát akkor csinálunk { // elkészítjük, azaz páldányosítunk a ’0’ bet˝ u akt. parammal Csomopont *uj = new Csomopont (’0’); // az aktuális csomópontnak, ahol állunk azt üzenjük, hogy // jegyezze már be magának, hogy nullás gyereke mostantól van // küldjük is Neki a gyerek címét: fa->ujNullasGyermek (uj); // és visszaállunk a gyökérre (mert ezt diktálja az alg .) fa = &gyoker; } else // ha van, arra rálépünk { // azaz a "fa" pointer már majd a szóban forgó gyermekre mutat: fa = fa->nullasGyermek (); } } // Mit kell betenni éppen, vagy ’1’-et? else { if (!fa->egyesGyermek ()) { Csomopont *uj = new Csomopont (’1’); fa->ujEgyesGyermek (uj); fa = &gyoker; } else { fa = fa->egyesGyermek (); } }

-

-

from the http://www.inf.unideb.hu/~nbatfai/z3a7.cpp. But certainly the latter code only inserts letters into the tree.

Example 7.1 Kálmán Könyves on IRC using the Program W

125



Install Kálmán Könyves using the Program W. Example 7.2 Kálmán Könyves on the web using the Program D Install Kálmán Könyves using the Program D.

7.1.1

The structure of the AIML files

The next Hungarian language AIML file is a part of the work [KK], this and the other files can be download from the author’s page: http://www.inf.unideb.hu/~nbatfai/kk/.

FT

[norbert@matrica 0.0.2]$ python KiralyiKonyvtaros.py Loading ../AIML/konyvtar.aiml.xml... done (0.01 seconds) Loading ../AIML/tmt.aiml.xml... done (0.00 seconds) Loading ../AIML/udvariassag.aiml.xml... done (0.01 seconds) Loading ../AIML/jucs.aiml.xml... done (0.00 seconds) Loading ../AIML/robot.aiml.xml... done (0.00 seconds) Loading ../AIML/jcscs.aiml.xml... done (0.00 seconds) Loading ../AIML/kf.aiml.xml... done (0.01 seconds) olvasó> Hello, Alice! [u’Hello,’, u’Alice!’, u’Szervusz!’] Hello, - nem szerepelt, felvettem Alice! - nem szerepelt, felvettem Szervusz! - nem szerepelt, felvettem Szervusz!

D

R

A

olvasó> Ki vagy Te valójában? [u’Ki’, u’vagy’, u’Te’, u’val\xf3j\xe1ban?’, u’Virtu\xe1lis’, u’k\xf6nyvt\xe1ros ’, u’vagyok,’, u’egy’, u’cseveg\u0151’, u’robot.’, u’A’, u’nevem’, u’Konyves ’, u’Kalman.’, u’A’, u’Debreceni’, u’Egyetem’, u’Informatikai’, u’Kar\xe1n’, u’dolgozom.’] Ki - nem szerepelt, felvettem vagy - nem szerepelt, felvettem Te - nem szerepelt, felvettem valójában? - nem szerepelt, felvettem Virtuális - nem szerepelt, felvettem könyvtáros - nem szerepelt, felvettem vagyok, - nem szerepelt, felvettem egy - nem szerepelt, felvettem cseveg˝ o - nem szerepelt, felvettem robot. - nem szerepelt, felvettem A - nem szerepelt, felvettem nevem - nem szerepelt, felvettem Konyves - nem szerepelt, felvettem Kalman. - nem szerepelt, felvettem A - mar szerepelt, raleptem Debreceni - nem szerepelt, felvettem Egyetem - nem szerepelt, felvettem Informatikai - nem szerepelt, felvettem Karán - nem szerepelt, felvettem dolgozom. - nem szerepelt, felvettem Virtuális könyvtáros vagyok, egy cseveg˝ o robot. A nevem Konyves Kalman. A Debreceni Egyetem Informatikai Karán dolgozom. olvasó>

The input Hello, Alice! matches the pattern HELLO * defined by the category element: <pattern>HELLO *

126

-



The appropriate response is given in the contained template element. Now it is not a simple text element, but a recursive one. That means that the robot must response the same like in case of the pattern SZIA. That is the response will be one of the following possibilities: <pattern>SZIA

FT

Now the Szevasz! has been selected: Q: Hello, Alice! A: Szevasz!

D R

A

. # # Ez a program szabad szoftver; terjeszthet˝ o illetve módosítható a # Free Software Foundation által kiadott GNU General Public License # dokumentumában leírtak; akár a licenc 3-as, akár (tetsz˝ oleges) kés˝ obbi # változata szerint. # # Ez a program abban a reményben kerül közreadásra, hogy hasznos lesz, # de minden egyéb GARANCIA NÉLKÜL, az ELADHATÓSÁGRA vagy VALAMELY CÉLRA # VALÓ ALKALMAZHATÓSÁGRA való származtatott garanciát is beleértve. # További részleteket a GNU General Public License tartalmaz. # # A felhasználónak a programmal együtt meg kell kapnia a GNU General # Public License egy példányát; ha mégsem kapta meg, akkor # tekintse meg a oldalon. # # Version history: # # 0.0.1 Találkozás, búcsúzás és udvariassági formulák. Kerüljük a "kivezet˝ o" # mondatokat, például: # person1: Hogy vagy? # person2: Jól, tegnap olvastam egy jó könyvet. // mert erre a várható válasz, hgy mit... # illetve ahol kivezetünk jelezzük, hogy milyen lefed˝ o állomány kell majd. -->
127

-



xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://alicebot.org/2001/AIML-1.0.1 http://aitools.org/ aiml/schema/AIML.xsd">

<pattern>_ SZIA

D R A

<pattern>_ SZIA *

FT

<pattern>SZIA

<pattern>SZIA * <pattern>HELLO <pattern>SZEVA

<pattern>SZEVA * <pattern>SZEVASZ <pattern>SZEVASZ *

<pattern>SZIÓKA *

A

<pattern>ÜDV

FT

<pattern>SZIÓKA

D R

<pattern>ÜDV *

<pattern>ÜDVÖZÖLLEK <pattern>ÜDVÖZÖLLEK * <pattern>SZERVUSZ

<pattern>SZERVUSZ *

129



<pattern>HELLO *

<pattern>HELLÓ * <pattern>JÓNAPOT

D R A

<pattern>JÓNAPOT *

FT

<pattern>HELLÓ

<pattern>ÖRÜLÖK

<pattern>ÖRÜLÖK *

<pattern>VISZLÁT

130



<pattern>VISZLÁT *

A

FT

<pattern>KI VAGY

D R

<pattern>KI VAGY *

<pattern>KÖNYVTÁROS VAGY <pattern>* KÖNYVTÁROS VAGY <pattern>TE EMBER * <pattern>TE ROBOT * <pattern>TE EGY ROBOT * <pattern>ROBOT VAGY

-

D R A

FT

<pattern>MI A FELADATOD <pattern>MI A MUNKÁD

<pattern>MIVEL FOGLALKOZOL

<pattern>MI A FIGLALKOZÁSOD

<pattern>MIKOR SZÜLETTÉL <pattern>VAN SZÜLINAPOD

FT

<pattern>MIKOR VAN A SZÜLINAPOD

<pattern>MIKOR VAN A SZÜLETÉSNAPOD

A

<pattern>VAN SZÜLETÉSNAPOD

D R

<pattern>KI TANÍTOTT <pattern>KI TANÍTOTT *

<pattern>HOGY VAGY <pattern>JÓL

A

<pattern>ROSSZUL

FT

<pattern>NEM JÓL

R

<pattern>SEHOGY

D

<pattern>HOGY VAGY * <pattern>HOGY ÉRZED MAGAD <pattern>*

Example 7.3 Create your own chatterbot

134

-



D R

A FT

Choose your interest area and create the appropriate AIML XML files for your own chat bot.

135

FT

A

R

D

A FT Part V

D R

AspectJ Case Studies

137

FT

A

R

D

D R

A FT

In this part we introduce two AspectJ aspects. One is an analytic aspect the other a robot soccer aspect.

139

FT

A

R

D

Chapter 8

D R

A FT

What is the mother tongue of the object oriented programs?

141

FT

D

R

A

Abstract The aim of the analytic aspect to be developed is to analyse large object oriented software systems. Now we investigate the Program W that was already used in the previous case study. This theme is presented in detail in the paper [ASZ] or in online form at http://hiradastechnika.hu/data/upload/file/2012/HT2011_2_05.pdf

CHAPTER 8. WHAT IS THE MOTHER . . .

8.1. AN ANALYTICAL WEAVING

„NAGY TESTVÉR SZEMMEL TART” —1984 [ORWELL]

8.1

An analytical weaving

Like the previous case study, this one is also based on a publication, see [ASZ] . The related source codes and resources can be found at the author’s website http://www.inf.unideb.hu/~nbatfai/asz/. The idea is that we regard the logging of a running program as a corpus of an unknown language and the aspect to be developed simply listens to method calls. The form of the words of the unknown language is the following: the name of the caller class -> the name of the called class

and in another given case caller class.caller method -> called class.called method

FT

We are going to investigate the question: whether has this language the same word frequency distribution as can be observed in case of spoken languages? We use the next pointcut to capture all method calls pointcut fgvHivas() : call(* *(..)) && !cflow(adviceexecution());

then the advice

A

before() : fgvHivas() { ... String honnan = thisEnclosingJoinPointStaticPart.getSignature(). getDeclaringType().toString(); String hova = thisJoinPointStaticPart.getSignature().getDeclaringType() .toString(); ...

in

the

package

D R

logs the honnan -> hova-shaped, or in English from -> to words. Example 8.1 Weaving this aspect into ALICE Weave this aspect into ALICE, simply use the Ant script provided http://www.inf.unideb.hu/~nbatfai/asz/.

8.2

A robot soccer weaving

This is a regular exercise of the course Magas szint˝ u programozási nyelvek 2, in the robot soccer team called GoldenTeamFC-0.0.4sumkick-project.zip, where itself the Maven’s pom.xml file weaves the AspectJ aspect into the code of the team. In the case of GoldenTeam, we need the average of the powers of all performed passes and the average of the angles of the passes. In order to compute these quantities, we would need to process the all kick commands. It is a crosscutting concept and it can be implemented easily with AspectJ. public aspect NagytesoKick {

private long szamlalo = 1; private long eroSum = 0; private double szogSum = 0.0;

before(int ero, double szog): call(* kick(int, double)) && !cflow( adviceexecution()) && args(ero, szog) {

-

System.out.println("Nagyteso> " + thisJoinPointStaticPart. getSourceLocation()); System.out.println("Nagyteso> " + thisJoinPointStaticPart.getKind() ); System.out.println("Nagyteso> " + thisJoinPointStaticPart. getSignature());

143

-

CHAPTER 8. WHAT IS THE MOTHER . . .

8.2. A ROBOT SOCCER WEAVING

++szamlalo; eroSum += ero; szogSum += szog; System.out.println("Nagyteso> " + (szamlalo-1)); System.out.println("Nagyteso> " + (double)eroSum / szamlalo); System.out.println("Nagyteso> " + szogSum / szamlalo); } }

If the reader has any question about this aspect please comment on the blog post: http://progpater.blog.hu/2011/12/04/a_nagytestver_beleszott_egy_aspektust_a_csapatomba. Example 8.2 Try this AspectJ aspect yourself All you have to do is to download the GoldenTeam. Then let’s build it and run it, and see: - LATOM A MASIK

D

R

A

FT

2519280 [GoldenFC3 Player # 6] INFO hu.fersml.magyarfc.Jatekos KAPUT 6 tavolsaga = 21.5 iranya = 22.0 Nagyteso> Jatekos.java:512 Nagyteso> method-call Nagyteso> void atan.model.ActionsPlayer.kick(int, double) Nagyteso> 53 Nagyteso> 45.648148148148145 Nagyteso> -1.3333333333333333

144

-

A FT Part VI

D R

Bibliography

145

FT

A

R

D

BIBLIOGRAPHY

8.3

8.3. QUOTES

Quotes

[FBB]

David Kirkpatrick, The Facebook Effect: The Inside Story of the Company That Is Connecting the World , Virgin Publishing, 2011.

[IROBOT]

Alex Proyas, I, Robot, http://www.imdb.com/title/tt0343818/http://www.imdb.com/title/tt0343818/quotes , 2004.

[METAMATH] Gregory Chaitin, META MATH! The Quest for Omega, http://arxiv.org/PS_cache/math/pdf/0404/0404335v7.pdf , 2004. [ORWELL]

George Orwell, 1984, Európa mek.oszk.hu/00800/00896/00896.pdf , 1989.

[SZIRE]

Jen˝o Wigner, Szimmetriák és reflexiók/A tudomány növekedése - kedvez˝o kilátások és várható veszélyek (Ákos Károllyal, 1968), Gondolat, Budapest, 1972.

Operating systems

A FT

8.4

[KERNELDEV] Jonathan Corbet, Greg Kroah-Hartman, and Amanda McPherson, Linux Kernel Development: How Fast it is Going, Who is Doing It, What They are Doing, and Who is Sponsoring It, Linux Foundation http://go.linuxfoundation.org/who-writes-linux-2012 , 2012. [KMGUIDE]

Peter Jay Salzman, Michael Burian, and Ori Pomerantz, The Linux Kernel Module Programming Guide, Linux Documentation Project http://tldp.org/LDP/lkmpg/2.6/html/index.html , 2007.

[LDD]

Jonathan Corbet, Alessandro Rubini, and Greg Kroah-Hartman, Linux Device Drivers, O’Reilly Media, 3-rd http://lwn.net/Kernel/LDD3/ , 2005.

[MINIX]

Andrew S. Tanenbaum, A UNIX clone with source code for operating systems courses, ACM, SIGOPS Operating Systems Review http://dl.acm.org/citation.cfm?id=24596 , 21, 2029, 1987. SIGOPS Operation System Rev., Vol. 21, Issue 1, 20-29, 1987.

D R

[MINIX3_OS_BOOK] Andrew S. Tanenbaum and Albert S. Woodhull, Operating Systems Design and Implementation, Third Edition, Prentice Hall , 2006. [OS]

Andrew S. Tanenbaum and Albert S. Woodhull, Operációs rendszerek, PANEM , 1999.

[OS3]

Andrew S. Tanenbaum and Albert S. Woodhull, Operációs rendszerek: tervezés és implementáció, PANEM , 2007.

[ULK]

Daniel P. Bovet and Marco Cesati, Understanding the Linux Kernel, ISBN 0-596-00565-2, O’Reilly, 3rd edition , 2005.

8.5

Programming

[AUA2D]

Lei Tao and Runmei Zhang, AUA2D Soccer Simulation Team Description Paper for RoboCup 2011, http://mephisto.ist.tugraz.at/storage/104280b00fc97e0a88e79b36052499ea_AUA2D.pdf , 2011.

[COP]

Norbert Bátfai, Conscious Machines and Consciousness Oriented Programming, http://arxiv.org/abs/1108.2865 , 2011.

[EDINFERNO2D] Majd Hawasly and Subramanian Ramamoorthy, EdInferno.2D Team Description Paper for RoboCup 2011 2D Soccer Simulation League, http://wcms.inf.ed.ac.uk/ipab/robocup/research/TDP-Edinferno2D.pdf , 2011. [HELIOS]

Hidehisa Akiyama and Hiroki Shimora, HELIOS2010 Team Description, http://julia.ist.tugraz.at/robocup2010/tdps/2D_TDP_HELIOS.pdf , 2010. 147

BIBLIOGRAPHY

BIBLIOGRAPHY

[HELIOS2011] Hidehisa Akiyama, Hiroki Shimora, Tomoharu Nakashima, Yosuke Narimoto, and Tomohiko Okayama, HELIOS2011 Team Description, http://mephisto.ist.tugraz.at/storage/f10dc198b15f91ef023c354d90b1a993_helios2011_tdp.pdf , 2011. [JAVATTANITOK] Norbert Bátfai and István Juhász, Javát tanítok, Bevezetés a programozásba a Turing gépekt˝ol a CORBA technológiáig, Kempelen Farkas Digitális Fels˝ooktatási Tankönyvtár http://www.tankonyvtar.hu/site/upload/pdf/b10108.pdf http://www.tankonyvtar.hu/informatika/javat-tanitok-javat-080904 , 2007. [LINUXPROG] Bányász Gábor and Tihamér Levendovszky, LINUX programozás, Szak Kiadó , 2003. [LINUXPROG] Bányász Gábor and Tihamér Levendovszky, LINUX programozás, Szak Kiadó , 2003. Norbert Bátfai, Mesterséges intelligencia a gyakorlatban: bevezetés a robotfoci programozásba, Kempelen Farkas Digitális Fels˝ooktatási Tankönyvtár http://www.tankonyvtar.hu , A szerz˝o honlapján elérhet˝o a saját pdf, html és epub konverziója: http://www.inf.unideb.hu/~nbatfai/konyvek , 2011.

[MOBP]

Norbert Bátfai, Mobil programozás - Nehogy már megint a mobilod nyomkodjon Téged!, Kempelen Farkas Digitális Fels˝ooktatási Tankönyvtár http://www.tankonyvtar.hu , A szerz˝o honlapján elérhet˝o a saját pdf, html és epub konverziója: http://www.inf.unideb.hu/~nbatfai/konyvek , 2011.

[NADCO2D]

Mohammad Ali Sadeghi Marasht, NADCO-2D Soccer 2D Simulation Team Description Paper 2011, http://robolab.cse.unsw.edu.au/conferences/RoboCup-2011/TDPs/Soccer/Simulation/2d/S2D_NADCO-2D_TDP.pdf , 2011.

[NEHOGY]

Norbert Bátfai, Nehogy már a mobilod nyomkodjon Téged!, ISBN 978 963 473 094 1, Debrecen, DEENK http://www.eurosmobil.hu/NehogyMar , 2008.

A

FT

[MIRC]

[PARANOID] Vahid Khodabakhshi, Mojtaba Mesri, Navid KeyhaniRad, and Hosein Zolanvar, ParaNoid 2D Soccer Simulation Team Description Paper 2011, 2011. Norbert Bátfai, Párhuzamos programozás GNU/Linux környezetben: SysV IPC, P-szálak, OpenMP, Kempelen Farkas Digitális Fels˝ooktatási Tankönyvtár http://www.tankonyvtar.hu , A szerz˝o honlapján elérhet˝o a saját pdf, html és epub konverziója: http://www.inf.unideb.hu/~nbatfai/konyvek , 2011.

R

[PARP]

Morteza Barati, Zahra Hakimi, and Amir Homayoun Javadi, Photon 2D Soccer Simulation Team Description Paper, https://sites.google.com/site/ahjavadi/Attachments/Photon%2CTPD.pdf?attredirects=0 , 2011.

[POPR]

Norbert Bátfai, Paternoster of Programmers Reloaded: C, C++, Java, Python and AspectJ Case Studies, Kempelen Farkas Digitális Fels˝ooktatási Tankönyvtár http://www.tankonyvtar.hu , A szerz˝o honlapján elérhet˝o a saját pdf, html és epub konverziója: http://www.inf.unideb.hu/~nbatfai/konyvek , 2011.

D

[PHOTON]

[PP]

Norbert Bátfai, Programozó Páternoszter, ProgramozoPaternoszter.pdf , 2007.

http://www.inf.unideb.hu/~nbatfai/-

[RCSSMANUAL] Mao Chen, Klaus Dorer, Ehsan Foroughi, Fredrik Heintz, ZhanXiang Huang, Spiros Kapetanakis, Kostas Kostiadis, Johan Kummeneje, Jan Murray, Itsuki Noda, Oliver Obst, Pat Riley, Timo Steffens, Yi Wang, and Xiang Yin, Users Manual RoboCup Soccer Server for Soccer Server Version 7.07 and later, https://sourceforge.net/projects/sserver/files/rcssmanual/ , 2003. [UDPROG]

Norbert Bátfai, The Yearbook of the Programmers of University of Debrecen, Kempelen Farkas Digitális Fels˝ooktatási Tankönyvtár http://sourceforge.net/projects/udprog/, 2014.

[UNP]

W. Richard Stevens, UNIX Network Programming., Prentice Hall PTR , 1998. 148

BIBLIOGRAPHY

8.6

8.6. FOOTBALL

Football

[DEIKFOCI]

Norbert Bátfai, Márton Ispány, Péter Jeszenszky, Sándor Széll, and Gábor Vaskó, A Debreceni Egyetem labdarúgást szimuláló szemináriuma, Híradástechnika http://www.hiradastechnika.hu/data/upload/file/2011/2011_01_01magyar/batfain.pdf , 2011. Híradástechnika, 66/1, 32-36, 2011.

[FERSML]

Norbert Bátfai, Footballer and Football Simulation Markup Language and related Simulation Software Development, Journal of Computer Science and Control Systems http://electroinf.uoradea.ro/reviste%20CSCS/volumes/JCSCS_Nr_1_integral.pdf , 2010. Journal of Computer Science and Control Systems, III/1, 13-18, 2010.

[SRCSS]

N. Bátfai, R. Dóczi, J. Komzsik, A. Mamenyák, Cs. Székelyhídi, J. Zákány, M. Ispány, and Gy. Terdik, Applications of a simplified protocol of RoboCup 2D Soccer Simulation, 2013.

8.7

Math

A FT

Infocommunications Journal, 5/1, 15-20, 2013.

[BRILLPOT]

D. R. Brillinger, A potential function approach to the flow of play in soccer, Journal of Quantitative Analysis in Sports http://www.stat.berkeley.edu/~brill/Papers/jqas.pdf , 3, , 2007.

[SZSZTEK]

Gábor Tusnády, Sztochasztikus számítástechnika, KLTE http://www.math-inst.hu/~tusnady/mind.pdf , 1996.

8.8

For children

[JAVACSKA]

Background

D R

8.9

Erika Bátfai and Norbert Bátfai, Fantasztikus programozás, Debreceni Egyetem Egyetemi és Nemzeti Könyvtár http://javacska.lib.unideb.hu/konyv/bv-naplojakezirat-I-5_0_0.pdf , 2004.

[AIML]

R. S. Wallace, The Elements of AIML Style, http://www.alicebot.org/style.pdf , 2003.

[ASZ]

Norbert Bátfai, Van-e az objektum orientált programoknak anyanyelve: avagy egy analitikai szövés bevezetése, Híradástechnika http://hiradastechnika.hu/data/upload/file/2012/HT2011_2_05.pdf , 2011. Híradástechnika, 66/2, 27-32, 2011.

[CSASZAR]

Roger Penrose, A császár új elméje, Akadémiai, 1993.

[KATEDRALIS] Eric S. Raymond, The Cathedral and the Bazaar, O’Reilly Media http://magyarirodalom.elte.hu/robert/szovegek/bazar/ magyar fordítás: http://magyarirodalom.elte.hu/robert/szovegek/bazar/ , 1999.

[KK]

Norbert Bátfai and Erika Bátfai, Virtuális könyvtáros segítheti majd a kutatókat kézirataik beküldésében a Debreceni Egyetemen, Tudományos és Muszaki ˝ Tájékoztatás , 2010. Tudományos és Muszaki ˝ Tájékoztatás, 58/1, , 2011.

[RUSSELLNORVIG] S. J. Russel and P. Norvig, Artificial Intelligence: a Modern Approach, ISBN 0 13 103805 2, New Jersey, Prentice-Hall, Inc., 1995. [TCON]

B. Libet, E. Wright, B. Feinstein, and D. K. Pearl, Subjective referral of the timing for a conscious sensory experience, Brain , 102, 193-224, 1979.

[VOLF]

H. H. Kornhuber, L. Deecke, and P. Scheid, Voluntary finger movement in man: Cerebral potentials and theory, Biological Cybernetics , 23, 99-119, 1976.

149

FT

A

R

D

Index FD_SET, 57 FD_ZERO, 57 FerSML, 83 fork, 57 fs/proc/array.c, 37 funktor, 111

_ .config, 37 .ko, 37 /boot, 37 /boot/vmlinuz, 37 /proc, 37 /var/log/messages, 37 Éric Lévénez, 1 2D RCSS, 83

B Berkeley socket API, 57 BSD, 11, 57

D R

C caller_ptr, 11 Cantor, 1 chat robot, 121 chatbot, 121 create_proc_entry, 37 crosscutting concept, 141 ctime_r, 57 current, 37 current_thread_info(), 37

D dash, 83 Debrecen Deep Forest FC++, 83 Debrecen Great Forest FC++, 83 Debrecen Murmurs FC++, 83 Debrecen Round Forest FC++, 83 Debrecen Woodland FC++, 83 Debreceni Hivatásos FC++, 83 dmesg, 37 do_getinfo, 11 dst_ptr, 11 E Einstein, 1 EINTR, 57 Eric Steven Raymond, 11 esr, 11 F F_GETFL, 57 Facebook, 1 fcntl, 57 FD_ISSET, 57

H Hetedik Szem, 111

A FT

A accept, 57 AIML, 121 algorithm, 1 ALICE, 121 Artificial Intelligence Markup Language, 121 asm/thread_info.h, 37 aspect, 141 AspectJ, 141

G gcc, 57 GIMP, 83 GNU GPL, 11 GNU/Linux, 37 GoldenTeam FC, 141

I include/linux/list.h, 37 include/linux/sched.h, 37 include/minix/com.h, 11 include/minix/sys_config.h, 11 include/minix/syslib.h, 11 infinity, 1 insmod, 37 IO multipexing, 57 IPC, 11 ipcs, 57 IPv4, 57 IRC, 121 J Jávácska ONE, 111 JAD, 111 JAR, 111 Java EE, 111 Java ME, 111 JDK, 111 Jesus, 1

K Kálmán Könyves, 121 Kernel .config support, 37 kernel modul, 37 kernel/main.c, 11, 37 kernel/proc.c, 11, 37 kernel/proc.h, 11 kernel/sched/core.c, 37 Knuth, 1 Kolmogorov, 1 L LHC, 37 light client, 83 Light FC++, 83 Linus Torvalds, 1, 37 Linus-Tanenbaum debate, 37 Linux, 11, 37 151

INDEX

INDEX

Q quantum informatics, 1 R random, 1 RCSS, 83 Richard Stallman, 1 Richard Wallace, 121 rmmod, 37 runmidlet, 111

S S_IRUGO, 37 select, 57 select(), 57 semaphore arrays, 57 semget, 57 semop, 57 server::light_response, 83 server::light_response_with_angle, 83 server::light_response_with_angles, 83 servers/is/dmp.c, 11 servers/is/dmp_kernel.c, 11 servers/is/proto.h, 11 Servlet, 111 SETVAL, 57 shared memory, 57 shmat, 57 shmget, 57 SIGCHLD, 57 soccerwindow2, 83 spece, 1 STL, 111 struct list_head, 37 struct proc, 11 struct sembuf, 57 struct seq_file, 37 struct sigaction, 57 struct sockaddr_in, 57 struct task_struct, 37 struct timeval, 57 Sun Java Wireless Toolkit for CLDC 2.5.2 ML, 111 Sys V IPC, 57 sys/types.h, 57 sys_getmatrix, 11 sys_getproctab, 11 számítás, 1

R

A

M major.minor.revision.patchlevel, 37 make, 37 make install, 37 make menuconfig, 37 make modeules_install install, 37 make modules_install install, 37 man 2 bind, 57 man 2 listen, 57 man 2 socket, 57 man 3 ftok, 57 man 3 htons, 57 man 7 ip, 57 Mark Zuckerberg, 1 microkernel, 11, 37 MIDlet, 111 MINIX, 11, 37 MINIX 3, 11 MINIX 3.2, 11 MINIX 3.2.1, 11 model of consciousness, 1 monolitic kernel, 37 msgget, 57 mutual exclusion, 57

POSIX, 57 printk, 37 proc_mkdir, 37 process, 11 Process Control Block, 11 process table, 11 Program D, 121 Program W, 121 Program Y, 121 PyAIML, 121

FT

Linux 3.5, 37 Linux PCB, 37 Linux Programmer’s Manual, 57 Linux User’s Manual, 57 linux/list.h, 37 linux/proc_fs.h, 37 linux/sched.h, 37 linux/seq_file.h, 37 list_entry, 37 list_for_each, 37 Loenber award, 121 Lord’s Prayer, 1 LZW, 111

D

N Nokia 6212 classic, 111 NR_PROCS, 11 NR_TASKS, 11 O O=output/dir, 37 O_NONBLOCK, 57 online coach, 83 open source, 11 OrchOR, 1 OTA, 111

P p_cpu_time_left, 11 p_nr, 11 p_quantum_size_ms, 11 Pater noster, 1 PCB, 11 pos, 83

T 152

INDEX

INDEX

Tanenbaum, 11 TASK_STATE_TO_CHAR_STR, 37 TCP, 57 TCP/IP, 57 team_graphic, 83 telnet, 57 THREAD_SIZE, 37 time, 1 Turing, 1 turn, 83 turn_neck, 83

V virtual file system, 37 vmlinuz, 37 W wait, 57 weaving, 141 wildcard, 57 X XPM, 83

D R

Z Ziv-Lempel-Welch, 111 zombi, 57

A FT

U union thread_unio, 37 UNIX, 11

153

FT

A

R

D

Colophon

D R

A FT

This book is written in the framework of the project TÁMOP-4.1.2.A/1-11/1-2011-0063.

155

DRAFT. Paternoster of Programmers Reloaded. Dr. Norbert Bátfai. March 9, C, C++, Java, Python and AspectJ Case Studies

Recommend Documents