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