Άσκηση C

[gio@]

Μπορείτε να ρίξετε τα φώτα σας παρακαλώ γιατί από ότι κατάλαβα είναι πολύ παλούκι θα θέλαμε λίγο βοήθειά για να τη λύσουμε..

 

 

Να γραφεί πρόγραμμα σε C το οποίο θα έχει ως σκοπό την παραγωγή ενός πηγαίου κώδικα χωρίς σχόλια.

Το πρόγραμμα θα πρέπει να παίρνει σαν παράμετρο ένα όνομα αρχείου πηγαίου κώδικα σε C (έστω ask.c) και θα μετράει το συνολικό του μέγεθος (init_size). Έπειτα θα δημιουργεί (init_size/50 + 1) διεργασίες (όπου "/" είναι ακέραια διαίρεση) δηλαδή αν το μέγεθος του αρχείου είναι 134 χαρακτήρες, θα δημιουργεί (134/50 + 1 = 2 + 1 = 3 διεργασίες). Κάθε διεργασία θα επεξεργάζεται και διαφορετικό κομμάτι του κώδικα, το οποίο θα έχει μέγεθος το πολύ 50 χαρακτήρων. Δηλαδή στο συγκεκριμένο παράδειγμα, η πρώτη διεργασία θα επεξεργαστεί το κομμάτι του αρχείου στο διάστημα [0...49] (δηλαδή από την θέση 0 έως και την θέση 49), η δεύτερη το κομμάτι [50...99] και η τρίτη το [100...133].

 

Από την αρχική επεξεργασία θα παράγεται ένα αρχείο (έστω ask.c.tmp) το οποίο θα έχει ίδιο μέγεθος με το αρχικό (ask.c) αλλά στη θέση των σχολίων θα υπάρχουν κάποιοι ειδικοί χαρακτήρες. Τα σχόλια στη C συμβολίζονται ως "/* ..... */" ή "// .... \\n" (όπου "\\n" είναι το τέλος της γραμμής). Οι ειδικοί χαρακτήρες αντικατάστασης των σχολίων, μπορούν να είναι είτε σταθεροί χαρακτήρες (π.χ. "@") είτε δυναμικοί στους οποίους να υπάρχει και η πληροφορία του μήκους του σχολίου (π.χ. _C8, ^8 (σχόλιο μήκους 8 χαρακτήρων)). Όλες οι διεργασίες εκτελούνται "ταυτόχρονα" (εναλλαγή των διεργασιών πριν ολοκληρώσουν την επεξεργασία τους) αλλά το διάβασμα από το αρχικό αρχείο και το γράψιμο στο τελικό θα πρέπει να "προστατεύεται" από δύο σημαφόρους, έναν για το διάβασμα και έναν για το γράψιμο. Κάθε διεργασία θα προσπαθεί αρχικά να κάνει down() το σημαφόρο του διαβάσματος, θα πηγαίνει τον κέρσορα στο επόμενο χαρακτήρα από αυτόν που είχε διαβάσει (στο αρχικό αρχείο), θα τον διαβάζει, θα κάνει up() τον σημαφόρο του διαβάσματος και έπειτα θα κάνει down() το σημαφόρο του γραψίματος, θα πηγαίνει τον κέρσορα στην ίδια θέση με αυτή από την οποία διάβασε τον χαρακτήρα (στο αρχείο tmp), θα γράφει το γράμμα (ή τον ειδικό χαρακτήρα αν αυτό που διάβασε είναι σχόλιο) και τέλος θα κάνει up() το σημαφόρο γραψίματος.

 

Εφόσον ολοκληρωθούν όλες οι διεργασίες, η αρχική διεργασία θα δημιουργεί σε δεύτερο στάδιο επεξεργασίας το τελικό αρχείο (έστω ask_bare.c) το οποίο θα δημιουργείται με βάση το ask.c.tmp αλλά χωρίς να περιέχει τους ειδικούς χαρακτήρες με τους οποίους είχαν αντικατασταθεί τα σχόλια. Προφανώς το μέγεθος αυτού του αρχείου (final_size) θα είναι ίσο ή μικρότερο από το αρχικό. Οπότε μετά το τέλος της δημιουργίας αυτού του αρχείου, θα εκτυπώνεται το ποσοστό συμπίεσης σε σχέση με το αρχικό αρχείο ((final_size-init_size)/init_size).

 

Παρακάτω υπάρχουν παραδείγματα κατανόησης.

 

 

>*** ask.c ***

#include <stdio.h>

/* to prwto mou programma */
main(){
printf("Hello world!!!\\n"); // ektypwsi
}


*** ask.c.tmp (σταθερός χαρακτήρας) ***

#include <stdio.h>

@@@@@@@@@@@@@@@@@@@@@@@@@@@@
main(){
printf("Hello world!!!\\n"); @@@@@@@@@@@
}

ή


*** ask.c.tmp (δυναμική αναπαράσταση) ***

#include <stdio.h>

_C28
main(){
printf("Hello world!!!\\n"); _C11
}

(όπου η αλληλουχία "_C" δεν υπάρχει μέσα στον κώδικα)

ή


*** ask.c.tmp (δυναμική αναπαράσταση) ***

#include <stdio.h>

^28
main(){
printf("Hello world!!!\\n"); ^11
}

(όπου "^" ειδικός χαρακτήρας ο οποίος δεν υπάρχει μέσα στον κώδικα)


*** ask_bare.c ***

#include <stdio.h>

main(){
printf("Hello world!!!\\n");
}

 

[bookysmell2004]

Μια καλή αρχή είναι να μας ενημερώσετε σχετικά με το λειτουργικό που θα δουλέψετε. Η υλοποίηση είναι πολύ OS-specific.

 

Πέρα από αυτό πρέπει να ξεκινήσετε δουλεύοντας λίγο τις παραμέτρους εκκίνησης. Παρόλο που η άσκηση δηλώνει μία παράμετρο (το όνομα του αρχείου προς επεξεργασία), προτείνω να μπουν και δύο ακόμη που θα είναι το offset της εκκίνησης και το μήκος της επεξεργασίας. Έτσι μία κλήση με παραμέτρους "test.c 50 99" θα ξεκινάει ένα process που θα επεξεργάζεται το αρχείο test.c ξεκινώντας από τη θέση 50 μέχρι και τη θέση 99. Όταν το πρόγραμμα ξεκινάει με μία παράμετρο, θα μετρά το μέγεθος του αρχείου (GetFileSizeEx σε Win32 - υπάρχει και ο ANSI τρόπος βέβαια με fseek), θα υπολογίζει τον αριθμό των processes, θα τις ξεκινά με τις ανάλογες παραμέτρους (CreateProcess σε Win32) και θα "κάνει κάτι" (πολύ φοβάμαι ότι θα πρέπει να χρησιμοποιηθεί mutex για την αναμονή, είναι κάπως θολή η εκφώνηση στο τι πρέπει να χρησιμοποιηθεί) μέχρι να τερματίσουν τα 3 processes. Θα πρέπει επίσης να δημιουργήσει τους σημαφόρους (με ονόματα γνωστά σε όλα τα processes) για να μπορούν να τους ανεβοκατεβάζουν τα υπόλοιπα.

 

Όταν το πρόγραμμα κληθεί με 3 παραμέτρους, ξέρει ότι είναι ένα από τα processes που θα κάνει την επεξεργασία του αρχείου και θα ξεκινάει ένα loop.

 

>
bool inComment
Πήγαινε στη θέση {δεύτερη παράμετρος}
Κάνε αυτά μέχρι να φτάσουμε στη θέση {τρίτη παράμετρος}
    Προσπάθησε να πάρεις τον σημαφόρο διαβάσματος (OpenSemaphore/WaitForSingleObject)
    Διάβασε έναν χαρακτήρα από το αρχικό αρχείο
    Ελευθέρωσε τον σημαφόρο διαβάσματος (ReleaseSemaphore)
    Αν συναντήσαμε χαρακτήρα τερματισμού σχολίου: inComment=false
    Προσπάθησε να πάρεις τον σημαφόρο γραψίματος.
    Αν inComment γράψε '@' στο αρχείο εξόδου αλλιώς γράψε το χαρακτήρα που διαβάσαμε. (διάβαζε σκέψη 3/4)
    Ελευθέρωσε το σημαφόρο γραψίματος.

(*πολύ* χοντρικό πρόγραμμα)

 

Για την ειδοποίηση του αρχικού process για το τέλος των απογόνων-process θα μπορούσαν να χρησιμοποιηθούν 3 mutexes και η WaitForMultipleObjectsEx.

 

Και για το τελικό στάδιο της καταμέτρησης συμπίεσης, πιστεύω είναι ανέκδοτο αν έχετε κάνει όλα τα άλλα ;p

 

Κάποιες σκέψεις:

1. Αν το μέγεθος είναι 100 θα πρέπει να δημιουργηθούν 100/50+1=3 processes; Το τρίτο τι θα κάνει; Εποπτεία;

2. Όταν ανοίγεται ένα συγκεκριμένο αρχείο από πολλαπλά processes θα πρέπει το λειτουργικό να το επιτρέψει (Windows 7 32-bit VS2008 εδώ φαίνεται να μην υπάρχει πρόβλημα).

3. 3 processes πρόκειται να προσθέτουν χαρακτήρες στο temp αρχείο ταυτόχρονα και αυτό δεν είναι καθόλου εύκολο όσο ακούγεται επειδή κανείς δεν μπορεί να εγγυηθεί ότι τα processes θα παίρνουν γραμμή προτεραιότητας σειριακά ώστε να κάνεις μια απλή πρόβλεψη για το ποιο σημείο του αρχείου θα πρέπει να γράψεις. Οι σημαφόροι έχουν μεταβλητή που σου λέει πόσες φορές έχει γίνει συνολικά release. Αυτό όμως πάλι δε βοηθάει σε περιπτώσεις περισσότερων των 2 processes (είναι προφανές γιατί, αν είστε μόνο δύο και ξέρεις πόσα release έχεις κάνει, αυτόματα ξέρεις πόσα έχει κάνει το άλλο process, άρα ξέρεις και πόσους χαρακτήρες έχει γράψει και οπότε ξέρεις που θα ξεκινήσεις το γράψιμο στο αρχείο).

4. "θα πηγαίνει τον κέρσορα στην ίδια θέση με αυτή από την οποία διάβασε τον χαρακτήρα (στο αρχείο tmp)". Η παρένθεση κολλάει στο "διάβασε" ή στο "πηγαίνει"; Σε όποιο από τα δύο και να κολλάει έχει λογικό κενό. Δε γίνεται να πάει στην ίδια θέση με το αρχικό αρχείο (πχ. το δεύτερο process που θα γράψει τον 50οστό χαρακτήρα αν το tmp αρχείο είναι ακόμη άδειο; ).

5. Οι συναρτήσεις που έγραψα είναι όλες για Windows αλλά φαντάζομαι υπάρχουν αντίστοιχες και για όλα τα άλλα λειτουργικά.

Επεξ/σία 21 Μαΐου 2010 από bookysmell2004

[pinball_elf]

Μία επιπρόσθετη σκέψη/απορία στις παρατηρήσεις του bookysmell2004, έιναι πως θα χειρίζονται οι διάφορες διεργασίες το γεγονός ότι ένα σχόλιο του κώδικα μπορεί να μην είναι ολοκληρωμένο στο κομμάτι (50 bytes) του αρχείου που έχει αναλάβει να χειριστεί η εκάστοτε διεργασία?

 

Για να αποφθεχθεί το παραπάνω και οι παρατηρήσεις του bookysmell2004, έιναι θεμιτό απο την λύση του προβλήματος αντί να χειρίζεται κάθε διεργασία ένα κομάτι του αρχείου των 50 χαρακτήρων, να χειρίζεται το πολύ 50 χαρακτήρες του αρχείου(και ανάλογα με το που βρίσκεται ο κέρσορας), ή ξεφέυγει εντελώς απο την έννοια της άσκησης?

Επεξ/σία 21 Μαΐου 2010 από pinball_elf

[bookysmell2004]

Όντως, πολύ σωστή παρατήρηση! Αν το μέγεθος επεξεργασίας είναι αυστηρά 50 χαρακτήρες, πολύ φοβάμαι ότι το πρόβλημα δε λύνεται με ένα pass.

 

Με δύο pass θα μπορούσαν να καταγράφονται δύο (θεωρητικά) μεταβλητές για κάθε 50-byte block στο πρώτο pass (μία μεταβλητή για το αν ολοκληρώθηκε το block με σχόλιο και μία με το τι τύπου σχόλιο προηγήθηκε, // ή /*) έτσι ώστε στο δεύτερο pass να ξέρει το process αν ξεκινάμε μέσα σε σχόλιο ή όχι.

 

Να συμπληρώσω ότι το πρώτο pass μπορεί να ενσωματωθεί στο αρχικό process, το οποίο θα περνά τις παραπάνω μεταβλητές σαν παραμέτρους στους απογόνους, έτσι ώστε να μην καταπατήσουμε την αυστηρότητα της εκφώνησης. Έτσι, στα παραπάνω που έγραψα αντί για 3 παραμέτρους το κάθε process μπορεί να δέχεται 4 με την τέταρτη έναν int με τιμές 0 (η επεξεργασία ξεκινάει θεωρώντας τον πρώτο χαρακτήρα χρήσιμο/μη σχολιασμένο), 1 (ξεκινάμε με σχόλιο τύπου //) ή 2 (ξεκινάμε με σχόλιο τύπου /*).

 

EDIT: Ήμουν λιγάκι βιαστικός. Χρειάζεται κι άλλη μία παράμετρος, ο τελευταίος χαρακτήρας του προηγούμενου block (μπορεί να είναι και int). Κι αυτό για να καλύψουμε περιπτώσεις που το προηγούμενο block τελειώνει με τον χαρακτήρα / και το νέο block ξεκινάει με τον χαρακτήρα / ή *.

 

Συνοψίζοντας, ένα πρόγραμμα

 

>/* add.c
* a simple C program
*/

#include <stdio.[color="red"]%[/color]h>
#define LAST 10

int main()
{
int i, sum = 0;
[color="red"]%[/color]	for ( i = 1; i <= LAST; i++ ) {
	sum += i;
} /*[color="Red"]%[/color]-for-*/
printf("sum = %d\n", sum);
// return
re[color="red"]%[/color]turn 0;
}

 

είναι 209 χαρακτήρες θεωρώντας τα line endings 1 byte (οι κόκκινοι δεν συμπεριλαμβάνονται στο αρχείο, είναι για τη σηματοδότηση του 50-byte block). Έτσι το αρχικό process θα καλεστεί ως εξής:

>app add.c

και με τη σειρά του αυτό θα καλέσει τον εαυτό του 209/50+1=5 φορές

>
app add.c 0 49 0
app add.c 50 99 0
app add.c 100 149 0
app add.c 150 199 2 //ξεκινάμε με σχόλιο τύπου /*
app add.c 200 208 0

 

Στο παραπάνω παράδειγμα δε χρειάστηκε η τελευταία παράμετρος που ανέφερα στο edit αλλά ελπίζω να έγινε κατανοητή.

Επεξ/σία 22 Μαΐου 2010 από bookysmell2004

[nan]

τελικα η λυση ποια ειναι ρε παιδια?

[παπι]

Τι εγινε με τις ανασκαφες;