Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Mala pitalica oko "UNIX" c-a

[es] :: C/C++ programiranje :: Mala pitalica oko "UNIX" c-a

[ Pregleda: 4156 | Odgovora: 19 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

chupcko
Negde
Beograd

Član broj: 5560
Poruke: 1141

Sajt: www.google.com


+63 Profil

icon Mala pitalica oko "UNIX" c-a04.10.2004. u 09:16 - pre 237 meseci
U ovoj temi ce biti jedna mala mala pitalica, cisto da se razmrda mozak :).

Mozda vise odgovara nekoj drugoj temi, ali meni se za sada svidja ovde.

Dakle potrebno je odgovoriti na sledece pitanje, u zavisnosti od n, koliko puta ce sledeci "kodovi" da ispisu slova m.

a)
Code:

for(i=0;i<n;i++)
  fork();
printf("m");


b)
Code:

printf("m");
for(i=0;i<n;i++)
  fork();


Savetujem da prvo resite a), kao i da ne startujete taj kod.

Naravno sama funkcija je lep odgovor, ali ako moze i objasnjenje, to bi bilo lepo :).

P.S. Kod koji je naveden, moze biti veoma opsasan, ne savetujem da ga ispobavate :).
CHUPCKO
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 11:46 - pre 237 meseci
Pa ovo bas i nije u vezi sa C++-om vec sa matematikom. Na prvi pogled bez papira i olovke bih rekao da je resenje pod a) 2^n a resenje pod b) 1.
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 12:06 - pre 237 meseci
Evo da probam.

Mada moram da priznam da sam varao na kartama, pošto sam neverovatnom igrom slučaja juče dobio skoro isto takvo pitanje. I upecao se kao šaran na „očigledan“ odgovor, ali sam probao da zatim razmislim o čemu je reč. U svakom slučaju evo nekakvog objašnjenja, možda sam čak i nabo pravu stvar.

Kao što svi znaju (a ko ne zna može da iskoristi man fork pa da vidi), fork() pravi kopiju trenutnog procesa, ako sve prođe kako treba, ili vraća grešku ako bude problema.

Zbog toga nema sumnje je da petlja i poziv fork() naprave najviše kopija trenutnog procesa za , odnosno ostavi jednu jedinu kopiju programa za .

Ako gledate kao što sam ja gledao isprva, pomislićete da u prvom slučaju svi procesi ispisuju po jedan m, a da u drugom samo prvi proces ispisuje m. Ovog pitanja naravno ne bi bilo kada bi sve bilo tako pravolininjski. Na mom računaru, oba programa ispisuju m-ove puta! Da stvar bude zanimljivija, ako se "m" zameni sa "m\n", stvari bivaju drugačije; prvi program ima manje-više isti izlaz, dok drugi da samo jedno slovo m .

Međutim, upis u stdout je linijski baferisan. To što smo upisali slovo u stdout pomoću printfa ne znači da će ono automatski da se pojavi na terminalu. Jednostavno je ostalo u izlaznom baferu i čeka ili znak za novi red ili da bafer bude popunjen ili fflush() kako bi bilo prosleđeno dalje. (možda postoje još neke mogućnosti, ja ih više ne znam; sećam se jedino da na je DOS-u to radilo malko drugačije, negde u C-FAQ-u postoji pitanjce na ovu temu, možda ga kasnije nađem).

Posmatramo program b). Dakle najpre upišemo u bafer slovo m. Zatim pozovemo fork() odgovarajući broj puta. Ali pošto fork() kopira „sve“ podatke o procesu (ne znam šta tačno znači sve, to je verovatno negde definisano al to ne znači da moram da takve podatke držim u glavi:) posle nekoliko fork()-ova dobili smo procese koji svi „misle“ da imaju po jedno m u izlaznom baferu. (šta se tačno kopira i da li je sam bafer deljen između procesa ili se pak naprave nezavisne kopije za svaki proces, to ne znam; međutim to ima uticaj na ono što se zatim dešava s programom ali o tom potom, već je dosta pretpostavki ispucano).

Na kraju svih procesa, svi odrade fflush() (ovo bi trebalo da je deo runtime biblioteke, pretpostavljam) i svi ispišu po jedno m. Redosled događaja ovde zavisi verovatno i od toga da li je korisnik promenio način baferisanja, veličinu bafera i šta znam šta još, ali to je opet još jedan set pretpostavki.

f
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 12:24 - pre 237 meseci
Malo mi je cudno da svako ima poseban bafer za stdout. Mozda se dobija razlicito resenje u zavisnosti od unixa?
 
Odgovor na temu

chupcko
Negde
Beograd

Član broj: 5560
Poruke: 1141

Sajt: www.google.com


+63 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 12:43 - pre 237 meseci
Pa ovo je defintino c, kao i pokazivanje razumevanja c-a, a sada, ja ionako mislim da sve ima veze sa matematikom.

Lepo je to sto je broj ispisanih slova m 2^n, i lepo ono sa bafferom, ali da li moze neko da mi obrazlozi lepo natenane, sto bas 2^n :). (mislim ja znam odgovor, ali da malo i drugi razmisljaju na pravi nacin :) ).

Sto se tice raznih verzija "unix"-a, sve zavisi od implementacije baffer-a.
CHUPCKO
 
Odgovor na temu

salec

Član broj: 6527
Poruke: 1738
*.rcub.bg.ac.yu



+25 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 13:39 - pre 237 meseci
Pa, svaki od trenutno postojecih procesa ce u sledecoj iteraciji petlje da opet forkuje, tj. da se udvoji... nesto kao sirenje bakterija deobom ;-).
 
Odgovor na temu

caboom
Igor Bogicevic
bgd

Član broj: 255
Poruke: 1503
80.93.230.*

ICQ: 60630914


+1 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 14:36 - pre 237 meseci
Citat:
chupcko:
Sto se tice raznih verzija "unix"-a, sve zavisi od implementacije baffer-a.


jep definitivno... ja sam se upecao na ovo. npr. implementacija kod cygwin-a nije ista kao kod slonvarisa.
 
Odgovor na temu

chupcko
Negde
Beograd

Član broj: 5560
Poruke: 1141

Sajt: www.google.com


+63 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 14:51 - pre 237 meseci
To je odlicno, ali nedovoljno, zasto bas 2^n, sto ne 2*n ?

Jel moze neki malo jaci dokaz ?

CHUPCKO
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 19:09 - pre 237 meseci
Citat:
chupcko:Jel moze neki malo jaci dokaz ?

Zar zaista mislis da ce neko za ociglednu stvar da ti pise tu rekurentne jednacine i precizan matematicki dokaz? U stvari i ne shvatam za sta hoces dokaz? Posto je vec receno da se kod svakog i broj procesa udvoji da li ti onda treba dokaz da je 2*2*2 (i puta) = 2^n a ne 2*n ?
 
Odgovor na temu

chupcko
Negde
Beograd

Član broj: 5560
Poruke: 1141

Sajt: www.google.com


+63 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 21:32 - pre 237 meseci
Pa ako je ocigledno utoliko ces mi lakse objasniti zasto je 2^n :).

Ovo nije u cilju jer ja ne znam, nego da malo aktiviram mozgove, ali sada kada malo bolje razmislim sto bi to radio :).

Dakle ako zabranimo sintagme tipa : ocigledno je, elemetarno sledi i slicno ...
kako bi neku nevernu tomu ubedio da to bas se toliko puta izvrsava :).
CHUPCKO
 
Odgovor na temu

vladab
Vladimir Bašanović
Beograd

Član broj: 9512
Poruke: 498
*.vdial.verat.net



Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 21:49 - pre 237 meseci
Iskompajlirao mu kod i pustio da odradi posao za mene. :O)
DESCRIPTION
fork creates a child process that differs from the parent process only
in its PID and PPID, and in the fact that resource utilizations are set
to 0. File locks and pending signals are not inherited.

Under Linux, fork is implemented using copy-on-write pages, so the only
penalty incurred by fork is the time and memory required to duplicate
the parent's page tables, and to create a unique task structure for the
child.


man fork
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
..-chandran.sbs.auckland.ac.nz



+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 22:21 - pre 237 meseci
Citat:
chupcko: Pa ako je ocigledno utoliko ces mi lakse objasniti zasto je 2^n :).

Pa objasnjeno ti je. Za svako i broj procesa se udvoji. Na kraju onda imamo 2^n procesa.

Citat:
Ovo nije u cilju jer ja ne znam, nego da malo aktiviram mozgove

To nije aktiviranje mozgova nego smaranje oko ociglednih stvari. Kao kada te u osnovnoj skoli teraju da postupno recis jednacinu 8-x=5 pa onda da sabiras sve sa x pa da oduzimas 5 itd...

Citat:
kako bi neku nevernu tomu ubedio da to bas se toliko puta izvrsava :).

Pa ako neko ne moze da shvati ono gore onda mu ne bi pomogao ni matematicki precizan dokaz. Lepo bih mu pustio program, pokazao za par primera da je formula tacna i to bi bilo to.

Mada zaista ne znam koliko precizan dokaz trazis.
1. f(0)=1
2. f(n)=f(n-1)+f(n-2)+...+f(0)
2. => f(n-1)=f(n-2)+...+f(0)
=> f(n)=f(n-1)+f(n-1)
=> f(n)=2*f(n-1)
=> f(n)=2^n*f(0)

Mada opet ovo nije precizan dokaz. Izmedju drugog i treceg reda mi fale neki koraci. Valjda bi trebalo prvo da napisem kada umesto n stavim n-1 da dobijem f(n-1)=f(n-1-1)+f(n-1-2)....+f(0). I trebalo bi da koristim oznake sigma itd... Dalje fale mi koraci izmedju poslednjeg i pretposlednjeg reda.
Izvini, chupko, ali ne idemo svi na pmf da znamo do detalja sve matematicke aksiome. I dalje mislim da to sto ti trazis nema nikakve veze sa mozganjem nego sa poznavanjem matematickih aksioma. Meni ovo sto sam napisao nije nista ociglednije od prve recenice u mom postu. Predajem se, ajde da vidimo matematicki precizan dokaz.

[Ovu poruku je menjao srki dana 05.10.2004. u 00:59 GMT+1]
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 22:40 - pre 237 meseci
Rekao bih da chupcko misli na Hoareov formalizam (inicijali su C.A.R. Hoare jer on to jeste:): preduslov, invarijanta, postuslov. Koliko se sećam i na ETF-u je o tome bilo reči (upisujte, deco, ETF:), a pošto ne želim da kvarim zabavu ostaviću samo ovu usputnu primedbu.

Formalizam (IMHO) ne koristi puno bez dobre knjige koja ga objašnjava. Jako dobra stvarčica koja lepo govori kako algoritme dokazivati indukcijom je ova knjiga Udija Manbera (Introduction to Algorithms, a creative approach). Dobra strana knjige nije u insistiranju na induktivnim dokazima, već što pokazuje kako se upotrebom indukcije jedan (veliki) problem polako „oljušti“ i elegantno reši. Biblioteka PMF bi trebala da je ima. Na Amazonu je malko skupa.

f
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
..-chandran.sbs.auckland.ac.nz



+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a04.10.2004. u 23:50 - pre 237 meseci
Iz kog predmeta se to radi? Mozda iz matematike 4 jer sam to onako otaljao i polovicno ucio samo da prodjem ispit a na predavanja nisam isao.
 
Odgovor na temu

chupcko
Negde
Beograd

Član broj: 5560
Poruke: 1141

Sajt: www.google.com


+63 Profil

icon Re: Mala pitalica oko "UNIX" c-a05.10.2004. u 07:56 - pre 237 meseci
Pa recimo, da nije samo to matematika, cini mi se da se do rezultata doslo eksperimentalnim putem :).

Slaze, se da se u svakom pozivu forka, proces duplira, ali koliko puta pozivamo fork ?

Kada je i=0, pozivamo fork i u oba nastala procesa nastavljamo odatle, zar ne.
Znaci imacemo dva procesa u kojem je i=1, pa zatim 4 procesa u kojem je i=2, i tako do n.

Slazem se da je to to, ali ono, postoje vizelizacije i jos po koji mehanizmi :).

Uzgred razlika izmedju majsora i segrta je bas u tome sto se majstor smara oko svega :).

Svaki moj pokusaj da se es ne pretvori u forum resavaca domacih i drugih problema se svodi na to, da ljudima odgovara da es bude bas to, forum gde ce slabi djaci a pak upuceni na net, naci resenja :).

C.A.R. Hoare i Dijkstra su se bavili dokazivanjem korektnosti rada programa, i ako bas zelis da vidis sta je smaranje, probaj da procitas neki njihov rad :). (ali bas korisno smaranje).
A mozda i nadjes knjigu Suada Alajgica (nesto kao osnovi programiranja, pascal), tu imas lepu osnovu za sve to.

Inace ovo sto sam ja "zadao" je tipican problem racunjanja slozenosti algoritma, ako zelis da progrmiras, jednom ces morati da izarcaunas koliko ti je "slozen" algoritam, cisto da ne radis posle sortiranje u n^2 koraka :).

CHUPCKO
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a05.10.2004. u 08:58 - pre 237 meseci
Citat:
chupcko: Pa recimo, da nije samo to matematika, cini mi se da se do rezultata doslo eksperimentalnim putem :).

Pa da se do rezultata doslo eksperimentalnim putem onda ne bih pogresio pod b).

Citat:
Inace ovo sto sam ja "zadao" je tipican problem racunjanja slozenosti algoritma

Naravno da to znam, ali jos uvek ne znam na koji nacin moze matematicki precizno da se pokaze da je rezultat 2^n? Koje su osnovne aksiome od kojih polazimo?
Ti si u stvari samo ponovio ono da se kod svakog "i" broj procesa duplira. Ne vidim neki dokaz za neverne tome. Ako bismo jos pominjali Hoare-a, pa tek onda im ne bismo pomogli.
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a05.10.2004. u 09:04 - pre 237 meseci
Citat:
Iz kog predmeta se to radi?
Iz Programiranja i programskih jezika. Udžbenik za taj predmet je stvarno kompletan uvod u programiranje. Šteta što ga je izgleda malo ko čitao. Nisam video dotičnu knjigu Suada Alajgića (jer, jelda, svaki ciga svoga konja hvali:) ali mogu da posvedočim da je i prof. Jozo Dujmović uradio odličan posao.

f
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a05.10.2004. u 09:37 - pre 237 meseci
Citat:
Svaki moj pokusaj da se es ne pretvori u forum resavaca domacih i drugih problema se svodi na to, da ljudima odgovara da es bude bas to, forum gde ce slabi djaci a pak upuceni na net, naci resenja :).
Hm — ne bih rekao da ljudima odgovara (kojim?). S druge strane činjenica je da je mnogo više njih zainteresovano za tehnička pitanja (kako u Windowsu da uradim...), ali IMHO je i u „velikom“ svetu raspodela je nekako slična, nekako treba očekivati da i ovde bude otprilike tako.
Citat:
Inace ovo sto sam ja "zadao" je tipican problem racunjanja slozenosti algoritma, ako zelis da progrmiras, jednom ces
Meni se učinilo da te je zanimalo (ili bar: da si hteo da čuješ) zašto se rezultati izvršavanja a) i b) ne razlikuju (ili bar: zašto b) ispisuje tu i tamo više od jednog slova), s obzirom da je deo sa forkovanjem isti u oba slučaja. Međutim može se desiti da nisam ispravno pročitao ili da sam implicitno razmišljao o sličnom pitanju od prethodnog dana. (tj. ako sam pogrešio, ovaj pasus zanemariti :)

f
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Mala pitalica oko "UNIX" c-a05.10.2004. u 09:47 - pre 237 meseci
Citat:
filmil: Iz Programiranja i programskih jezika.
Udžbenik za taj predmet je stvarno kompletan uvod u programiranje. Šteta što ga je izgleda malo ko čitao.

Mislim da si ti prva osoba koju znam da je uopste otvorila tu knjigu. Ako se na predavanjima radilo to sam sigurno propustio jer nisam isao na predavanja. Mada ne verujem da se te godine to radilo jer su tada bili neki strajkovi (ili nesto drugo) pa ionako nisu stigli sve da ispredaju (znam da tada nismo morali da znamo Fortran za ispit).
 
Odgovor na temu

chupcko
Negde
Beograd

Član broj: 5560
Poruke: 1141

Sajt: www.google.com


+63 Profil

icon Re: Mala pitalica oko "UNIX" c-a05.10.2004. u 10:36 - pre 237 meseci
Uf, ja znam dosta toga oko c-a, naravno da sam znao resenje pre nego sto sam postovao ovde.

Ideja je da se malo ubaci nauka u sve to :).
Ali ajde, najbolje da dignem ruke.

P.S. main(){main(fork());}

CHUPCKO
 
Odgovor na temu

[es] :: C/C++ programiranje :: Mala pitalica oko "UNIX" c-a

[ Pregleda: 4156 | Odgovora: 19 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.