Notes: Operative Systems – Part 6

< Previous (Operative Systems – Part 5) | (Operative Systems – Part 7) Next >

NOTIFICATION: These notes are published for educational purposes. Using these notes is under your own responsibility and risk. These notes are given ‘as is’. I do not take responsibilities for how you use them.

PDF Content:

  • Least recently used  (LRU) page replacement algorithm
  • Not frequenty used (NFU) algorithm
  • Aging (approximation of LRU) algorithm
  • Working set
  • Current virtual time
  • Page replacement algorithm
  • Clock page replacement algorithm
  • WSClock page replacement algorithm
  • Local vs. Global replacement policies
  • Internal vs. External fragmentation
  • Page size
  • Periodic cleaning policy
  • Thrashing
  • Separation of policy and mechanism
  • Concurrency vs. parallelism
  • Critical sections

Operative_Systems_6

 

< Previous (Operative Systems – Part 5) | (Operative Systems – Part 7) Next >

Share

Prolog using Examples – Part 5

The follow is a continuation of the previous posting “Prolog using Examples – Part 4”

Example 1: Check the prefix of a list.

/* Base case */
/* When the list of prefix checked is empty means that we stop checking */
prefix([],_).

/* Recursive case */
/* Both head of the list must be the same */
prefix([Head|Tail_A], [Head|Tail_B]):-
    prefix(Tail_A, Tail_B).

?- prefix([1,b], [1,b,c,4]).
true.

?- prefix([1,b], [1,d,c,4]).
false.


/* prefix will search for each prefix everytime OR ';' is used */
?- prefix(Lst, [1,2,3,4]).
Lst = [] ;
Lst = [1] ;
Lst = [1, 2] ;
Lst = [1, 2, 3] ;
Lst = [1, 2, 3, 4] ;
false.

/* Generate a list where list [1,2,3,4] is the prefix and the tail is a dynamic variable */
?- prefix([1,2,3,4],Lst).
Lst = [1, 2, 3, 4|_G3713]. 

Example 2: Check the suffix of a list.

/* Base case */
/* When both list are the same, we found the suffix */
suffix(Lst_tail, Lst_tail).

/* Recursive case */
/* We want to check always the tail of the list, so the base case can check if they are the same */
suffix([_|Tail], Lst) :-
    suffix(Tail, Lst).

?- suffix([a,2,c,4],[c,4]).
true.

?- suffix([a,2,c,d],[c,4]).
false.

/* Obtain the next tail everytime OR ';' is used */
?- suffix([1,2,3,4], Lst).
Lst = [1, 2, 3, 4] ;
Lst = [2, 3, 4] ;
Lst = [3, 4] ;
Lst = [4] ;
Lst = [].

/* Be careful, in this kind of cases prolog keep generating dynamic variables in from of the list */
?- suffix(Lst, [1,2,3,4]).
Lst = [1, 2, 3, 4] ;
Lst = [_G3704, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, _G3713, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, _G3713, _G3716, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, _G3713, _G3716, _G3719, 1, 2, 3|...] ;
... /* Keep generating dynamic variables */

 

Example 3: In this example, we are introducing append. append is the unification of two lists, List_A, List_B, into one list that we are going to call list AB, List_AB.

The code of append is the follow:

/* Base case */
/* Will stop recursion when List_A is empty indicating that all the elements are in List_AB */
append([], Lst, Lst).

/* Recursive case */
append([Head|Tail_A], List_B, [Head|Tail_AB]):-
    append(Tail_A, List_B, Tail_AB).

First append will move 1, 2,  and 3 atoms from List_A to List_AB using recursion:

/* Recursive case */
append([Head|Tail_A], List_B, [Head|Tail_AB]):-
    append(Tail_A, List_B, Tail_AB).

append([1,2,3], [4,5,6], []) → append([2,3], [4,5,6], [1])  → append([3], [4,5,6], [1,2])  → append([], [4,5,6], [1,2,3])

When List_A is empty, then it will append List_B to List_AB as a tail of List_AB using the base case:

/* Base case */
/* Will stop recursion when List_A is empty indicating that all the elements are in List_AB */
append([], Lst, Lst).


append([], [4,5,6], [1,2,3]) → append([], [], [1,2,3,4,5,6])  → List_AB = [1,2,3,4,5,6]

Example 4: Even do append seems to create a list by appending List_A with List_B, append can behave in a different ways depending of how it is used:

Let see the code for append:

append([], Lst, Lst). /* ← Base case */
append([Head|Tail_A], List_B, [Head|Tail_AB]):-  /* ← Recursive case */
    append(Tail_A, List_B, Tail_AB).

 

Lets say we do  append(List_A, [5,6], [1,2,3,4,5,6]). What would be the result?

As you can see List_AB have 1,2,3,4,5, and 6 while List_B have 5 and 6, Prolog will unify List_A with 1,2,3, and 4.

?- append(List_A, [5,6], [1,2,3,4,5,6]).
List_A = [1, 2, 3, 4] .

Share

Prolog using examples – Part 4

In this part of this practical tutorial, we are going to do some coding involving facts, rules, recursion, and lists.

Example 1: Obtain the head of the list, obtain the tail of the list.

/* Get the head of the list */
get_head(Head, [Head|_]).

/* Get the tail of the list */
get_tail(Tail, [_|Tail]).

?- get_head(Head_is, [a,b,c,d]).
Head_is = a.

?- get_tail(Tail_is, [a,b,c,d]).
Tail_is = [b, c, d].

Example 2: Find out if an element is a member of a list.

/* Base case - We find the element inside the list */
/* The element is found if the head of the list can be unified with the element we are searching */
member(Element, [Element|_]).

/* Recursive function that call member with the tail without taking care of the head of the list */
/* The idea is that the base case will be called and check if the element is found */
member(Element, [_|Tail]) :-
    member(Element, Tail).    

?- member(a, [a,1,3,b,c]).
true .

/* Using OR ';', we ask Prolog to search for another element in the list */
?- member(a, [a,1,a,b,c]).
true ;
true ;
false.

/* Element is not found in the list */
?- member(a, [c,1,3,b,c]).
false.

Example 3: Find an specific element member inside a list in a determined position.

/* Base case */
/* The element was found in the list was found, set Position to 1 to stop recursion */
get_member_at(1, [Head|_], Head).

/* Recursive case */
/* Go thought the list until position is less than 1 indicating that member was found */
get_member_at(Position, [_|Tail], Element):-
    Position > 1,
    Temp_Position is Position - 1,
    get_member_at(Temp_Position, Tail,  Element).

/* Get the member at position 3 of the list */
?- get_member_at(3, [1,3,5,7], Lst).
Lst = 5. 

/* This fails when trying to get an element out or bounds of the list */
?- get_member_at(5, [1,3,5,7], Lst).
false. 

/* BE CAREFUL, Sometimes prolog can behave weird base on how you use your functors eg.*/

/* The follow is when prolog create dynamic variables because doesn't now the limit of the list */
?- get_member_at(5, Lst, Lst).
Lst = [_G455, _G458, _G461, _G464, **|_G468].

/* In this case, not only produce dynamic variables to be instanciated, but also add
the list [1,a,b] as the fifth head element of the list */
?- get_member_at(5, Lst, [1,a,b]).
Lst = [_G473, _G476, _G479, _G482, [1, a, b]|_G486] ;

Example 4: Lets obtain the numbers of elements that belong to a simple list.

/* Base case - When the list is empty, unify with zero */
number_of_elements([], 0).

/* Recursive case */
number_of_elements([_|Tail], Number_counted) :-
    number_of_elements(Tail, counter),
    Number_counted is counter + 1.

In the recursive case, Prolog will call number_of_elements passing the tail of the list until the list is empty. Then, for every time number_of_elements was call it would return the counter + 1 to the previous call. At the end, we will obtain the total number of elements in the list.

?- number_of_elements([a,1,b,2,^, &], Counted).
Counted = 6.

/* In this case the sublist [1,2,3] inside the list is considerate an element as a whole */
?- number_of_elements([a,b,c,[1,2,3]], Counted).
Counted = 4.

?- number_of_elements([[a,b,c,1,2,3]], Counted).
Counted = 1.

If inside the code we would had the unification symbol instead of the word ‘is’, we would have a different result:

/* Base case - When the list is empty, unify with zero */
number_of_elements([], 0).

/* Recursive case */
number_of_elements([_|Tail], Number_counted) :-
    number_of_elements(Tail, counter),
    Number_counted is counter + 1.

?- number_of_elements([a,1,b,2,^, &], Counted).
Counted = 0+1+1+1+1+1+1.

Example 5: Lets sort a list of elements

/* Base case - Empty list */
sort_list([]).

/* Base case - [_] indicate we don't case about the element, there is only one, the list is sorted */
sort_list([_]).

/* Recursion case */
sort_list([First_element, Second_element|Tail]):-
    First_element =< Second_element,
    sorted([Second_element|Tail]).

?- is_list_sorted([1,2,3,4]).
true .

?- is_list_sorted([1,2,3,4]).
true ;
false.

?- is_list_sorted([1,3,3,4]).
true.

?- is_list_sorted([1,3,5,4]).
false.

This topic will continue in the next posting.

Share

Prolog using Examples – Part 3

Prolog have a powerful way to work data by the use of lists. A list is normally a group of elements in each elements would have to pointers, one to the value and another to the next element or rest of the of the list. Just to clarify, we don’t see these pointers.

A list is represented in this way: T = [1, 2, 3, 4, 5] in which T is unified with this list and each number is an element of the list.

You can have also a list inside the list: T = [1, [a, b], 3, 4, 5].

The follows are some examples of how to work with list in Prolog:

Example 1: Lets have two variables, Head and Tail, we want the first element of the list to be unified with the Head variable and the rest of the list to be unified with the tail.

?- [Head|Tail] = [1,2,3,4,5].
H = 1,
T = [2, 3, 4, 5].

Example 2: Let say we wish to obtain the first two elements of the list, First_element and Second_element, and the rest of the list to the variable Tail.

?- [First_element, Second_element|Tail] = [1,2,3,4,5].
First_element = 1,
Second_element = 2,
Tail = [3, 4, 5].

If there are just two elements in the list, the Tail will be pointing to an empty list. An empty list is represented by []

?- [First_element, Second_element|Tail] = [1,2].
First_element = 1,
Second_element = 2,
Tail = [].

A list with less elements that needed, Prolog will indicate us cannot be done.

?- [First_element, Second_element|Tail] = [1].
False

/* Here [A] = [1] means that A is unified with 1, while B is unified with 2,3,4,5 */
?- [[A]|B] = [[1],2,3,4,5].
A = 1,
B = [2, 3, 4, 5].

/* [A|B] = [1,2], C = [3,4,5] → A = 1, B = [2], C = [3,4,5] */
?- [[A|B]|C] = [[1,2],3,4,5].
A = 1,
B = [2],
C = [3, 4, 5].

?- [[A|B]|C] = [[1,2,3],4,5,6].
A = 1,
B = [2, 3],
C = [4, 5, 6].

?- [[A|B]|[C|D]] = [[1,2,3],4,5,6].
A = 1,
B = [2, 3],
C = 4,
D = [5, 6].

There are cases in which we can use the feature that Prolog provide of unification.

/* This case, we have the same Head. Notice we have two 3's,
one inside the sublist and one of the list */
?- [[Head|Tail_A]|[Head|Tail_B]] = [[3,4,5],3,6,7].
Head = 3,
Tail_A = [4, 5],
Tail_B = [6, 7].

The following case would fails because the first list [Head|Tail_A] would unify with [3, 4, 5] and the second [Head|Tail_B] list would unify with [2,6,7], since the atom 3 is not the same as the atom 2 then it false.

?- [[Head|Tail_A]|[Head|Tail_B]] = [[3,4,5],2,6,7].
false.

The follow is the same example but using different atoms:

?- [[A|B]|[A|D]] = [[a,b,c],a,e,f].
A = a,
B = [b, c],
D = [e, f].

?- [[A|B]|[A|D]] = [[a,b,c],d,e,f].
false.

?- [[A|B]|[_|D]] = [[a,b,c],a,e,f].
A = a,
B = [b, c],
D = [e, f].

?- [[_|B]|[_|D]] = [[a,b,c],a,e,f].
B = [b, c],
D = [e, f].

?- [[A|T]|[B|T]] = [[a,b,c],d,b,c].
A = a,
T = [b, c],
B = d.

This proves that Prolog consider  numbers as atoms (constants) in the same way as lower case characters/names and strings such as ‘abc’.

Using an underscore inside the brackets indicate that we don’t care about that element or elements:

?- [_|Tail] = [1,2,3,4,5].
Tail = [2, 3, 4, 5].

?- [_|Tail] = [1,2,3,4,5].
Tail = [2, 3, 4, 5].

?- [_|_] = [1,2,3,4,5].
True

In following posting, we will see how to work with lists using facts, rules, and recursion.

Share

Prolog using Examples – Part 2

Lets begin with cases related with recursion:

In an imperative style,  you would use a loop to produce a result, while in an functional style, it is common to use recursion to produce the same result.

The most common example related with recursion is the factorial recursion, in which for example the factorial of 6 (6! = 5 * 4 * 3 * 2 * 1) would give us

/* Base case of the factorial, when N is 0 then return 1 */
factorial(0, 1).

factorial(N, M) :-
    N1 is N - 1,
    factorial(N1, M1),
    M is N * M1.
?- factorial(6, T).
T = 720;
ERROR: Out of local stack

Note: As you can see, when we added the OR ‘;’, prolog tried to find another  answer and went out of bound.
To prevent this we can do an small modification as follows:

/* Base case of the factorial, when N is 0 then return 1 */
factorial(0, 1).

factorial(N, M) :-
    N > 0
    N1 is N - 1,
    factorial(N1, M1),
    M is N * M1.
?- factorial(6, T).
T = 720;
False

In this case, when we tell Prolog that we wish to find another possible answer, Prolog would indicate false since it cannot find any other possible solution.

Lets go over some examples:

Example 1: We have a family and we wish to know the descendent of some individual.

/* Maria is_mother_of Pedro */
is_mother_of(Maria, Pedro).

/* Susana is_mother_of Maria */
is_mother_of(Susana, Maria).

/* Pepe is_father_of Pedro */
is_father_of(Pepe, Pedro).

/* Diego is_father_of Pepe */
is_father_of(Diego, Pepe).

/* Person is_parent_of Child if Person is_mother_of Child */
is_parent_of(Person, Child):- is_mother_of(Person, Child).

/* OR */

/* Person is_parent_of Child if Person is_father_of_Child */
is_parent_of(Person, Child):- is_father_of(Person, Child) */

/* Begin RECURSION */

/* Recursion Base */

/* Person is_decendent_of Adult if Adult is_parent_of Person */
is_decendent_of(Person, Adult) :- is_parent_of(Adult, Person).

/* Recursion */
/* Person is_decendent_of Adult if Older(person) is_parent_of Person AND Older is_decendent_of Adult */
 is_decendent_of(Person, Adult) :- is_parent_of(Older, Person), is_decendent_of(Older, Adult).

Example 2: Fibonacci (http://en.wikipedia.org/wiki/Fibonacci_number) is an integer sequence such as 0, 1, 1, 2, 3, 5, 8… As you may notice, the first two numbers are 0 and 1, an the subsequence is form by a number created from the sum of the two previous numbers: 0 + 1 = 1 (0,1,1) , 1 + 1 = 2 (1,1,2), 1 + 2 = 3 (1,2,3), 2 + 3 = 5 (2,3,5) …

/* Recursion base case */
fibonacci(0, 0).

/* Recursion base case */
fibonacci(1, 1).

/* Recursion */
fibonacci(N, F) :-
    N1 is N - 1,
    N2 is N - 2,
    fibonacci(N1, F1),
    fibonacci(N2, F2),
    F is F1 + F2.

?- fibonacci(8, T).
T = 21;
ERROR: Out of local stack

Again in this case, when asking prolog to find another answer, it would go out of bounds because there is no case that stop it to keep calling itself. We need to modify this program:

/* Recursion base cases */
fibonacci(0, 0).
fibonacci(1, 1).

/* Recursion */
fibonacci(N, F) :-
    N > 0,
    N1 is N - 1,
    N2 is N - 2,
    fibonacci(N1, F1),
    fibonacci(N2, F2),
    F is F1 + F2. ?- fibonacci(8, T).
T = 21;
False

Again, Prolog couldn’t find a different answer when we ask it to search for it and let it know by returning false after the OR ‘;’.

Example 3: The following code is the Ackermann’s predicate (http://en.wikipedia.org/wiki/Ackermann_function).
One of the purposes to doing this kind of function could be to test the limits of the compiler.
The Ackermann’s functions is defined as follows:
ackermann( m,n ) =    n + 1                                                             if m = 0
ackermann( m,n ) =    ackermann(m – 1, 1)                                if n = 0 and m > 0
ackermann( m,n ) =    ack( m-1, ackermann( m, n-1 ) )          if n >0 and m > 0

/* ackermann(m, n) = n + 1 if m = 0 */
ackermann(Mi, Ni, No):- Mi = 0, No is Ni + 1.

/* ackermann(m, n) = ackermann(m - 1, ackermann(m, n - 1)) if n > 0 and m > 0 */
ackermann(Mi, Ni, No):-
    Mi > 0, Ni > 0,
    Mi2 is Mi - 1, Ni2 is Ni - 1,
    ackermann(Mi, Ni2, No2),
    ackermann(Mi2, No2, No).

/* ackermann(m, n) = ackermann(m - 1, 1) if n = 0 and m > 0 */
ackermann(Mi, Ni, No):-
    Mi > 0, Ni = 0,
    Mi2 is Mi - 1, Ni2 is 1,
    ackermann(Mi2, Ni2, No).

In the next blog posting, we are going to see Lists in Prolog.

Share