ホーム » 2019 » 1月 » 09

日別アーカイブ: 2019年1月9日

2019年1月
 12345
6789101112
13141516171819
20212223242526
2728293031  

検索・リンク

参照カウンタ法とガベージコレクタ

共有のあるデータの取扱の問題

リスト構造で集合計算おこなう場合の和集合を求める処理を考える。

struct List* join( struct List* a , struct List* b )
{  struct List* ans = b ;
   for( ; a != NULL ; a = a->next )
      if ( !find( ans , a->data ) )
         ans = cons( a->data , ans ) ;
   return ans ;
}
void list_del( struct List* p )
{                            // ダメなプログラムの例
   while( p != NULL ) {      // for( ; p != NULL ; p = p->next )
      struct List* d = p ;   //    free( p ) ;
      p = p->next ;
      free( d ) ;
   }    
}
void main() {
   // リストの生成
   struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
   struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
   struct List* c = join( a , b ) ; // c = { 1, 1, 2, 3 }
                                     //          ~~~~~~~ ここは b
   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( c ) ;
   list_del( b ) ;
   list_del( a ) ; // list_del(c)ですでに消えている
}                  // このためメモリー参照エラー発生

このようなプログラムでは、下の図のようなデータ構造が生成されるが、処理が終わってリスト廃棄を行おうとすると、bの先のデータは廃棄済みなのに、list_del(c)の実行時に、その領域を触ろうとして異常が発生する。

参照カウンタ法

上記の問題は、b の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。

参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。

  • データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に1とする。
  • 処理の中で共有が発生すると、参照カウンタをカウントアップする。
  • データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。
struct List {
   int          refc ; // 参照カウンタ
   int          data ; // データ
   struct List* next ; // 次のポインタ
} ;

void list_del( strcut List* p ) {  // 再帰で全廃棄
   if ( p != NULL
        && --(p->refc) <= 0 ) {    // 参照カウンタを減らし
      list_del( p->next ) ;        // 0ならば本当に消す
      free( p ) ;
   }
}

ただし、参照カウンタ法は、循環リストではカウンタが0にならないので、取扱いが苦手。

参照カウンタ法が用いられている事例をあげよ。

ガベージコレクタ

では、循環リストの発生するようなデータで、共有が発生するような場合には、どのようにデータを管理すれば良いだろうか?
最も簡単な方法は、処理が終わっても、使い終わったメモリを返却しない、方法である。ただし、このままでは、メモリを使い切ってしまう。

そこで、廃棄処理をしないまま、ゴミだらけになってしまったメモリ空間を再利用するのが、ガベージコレクタである。
ガベージコレクタは、貸し出すメモリ空間が無くなった時に起動され、

  1. すべてのメモリ空間に、「不要」の目印をつける。(mark処理)
  2. 変数に代入されているデータが参照している先のデータは「使用中」の目印をつける。(mark処理)
  3. その後、「不要」の目印がついている領域は、だれも使っていないので回収する。(sweep処理)


この方式は、マークアンドスイープ法と呼ばれる。ただし、このようなガベージコレクタが動く場合は、他の処理ができず処理が中断されるので、コンピュータの操作性という点では問題となる。

最近のプログラミング言語では、参照カウンタとガベージコレクタを取り混ぜた方式でメモリ管理をする機能が組み込まれている。このようなシステムでは、局所変数のような生成され関数終了といったすぐに不要となる領域は、ガベージコレクタで管理し、大域変数のような長期間保管するデータはガベージコレクタで管理される。

 

メールヘッダとspam

メールヘッダ

メールを出すときには、宛先やタイトルや本文などの情報がついている。

From: foo@bar.jp      送信元のメールアドレス
To:   hoge@piyo.jp    送り先のメールアドレス
Cc:   hogehoge@bar.jp 送信内容を確認してもらうためのコピーの送り先
Bcc:  hogefuga@bar.jp 送信相手にコピーしたことが見えないように送る時
Subject: 会議の議事録  メールのタイトル
Date: 2019年 1月 9日 12:34:56 メールを送った時間
本文
-- 
署名

送信相手に届くメールでは、上記以外にも様々な情報がつけられる。これらの情報を見ると、迷惑メールか確認することもある程度可能となる。

Received: from 送信元 by 受信サーバ
Reply-To: 返信する際の送り先
Return-Path: 送信に失敗した時に送り返す先
DKIM-Signature: メールサーバの公開鍵署名
Received-SPF: 送信元のDNS情報など

spam

メールでは、送信時に送信者の認証をしないので、送信元の名前を偽ってメールを送ることが簡単にできる。このため、広告目的、ウィルス感染目的にメールがよく使われる。こういったメールは、一般的に spam と呼ばれる。

イギリスのコメディグループ・モンティパイソンが、コントの中で、しつこくspam,spam,spam,spam….と、騒ぐ様からspamと呼ばれるようになった。大文字のSPAMと書かないこと。(ランチョンミートの缶詰)

なぜspamが届くのか?

たぶん、メールを利用していると、誰でも spam が送られてきた体験があるはず。でも、自分のメールアドレスがどうやって、送信元に知られてしまったのだろうか?

インターネットで企業などでメールアドレスを記入して、そこから情報が漏れたのだろうか?実際、企業がクラッキングに会い、情報漏えいの場合もあるが、一般的には、“aaa”さん、”aab”さん、”aac”さんといったように、文字列の組み合わせを順次組み合わせてユーザ名を作って送っているだけである。当然、このような方法では、宛先不明のメールが発生するが、迷惑メールの送信業者はそんなことは気にしない。ただし、大量の迷惑メールを送ると、インターネットの接続業者に目をつけられてアカウント停止となるため、ウィルスに感染させたパソコンを遠隔操作してspamメールを送るのが一般的である。このため、以下のことはしないこと。

  • 迷惑メールの送信元に抗議メールを送らない。(From欄にメールアドレスを勝手に使われる場合がある)
  • “I Love You”とか”くじに当選しました”といったメールはその時点で怪しい。
  • 怪しいメールを開封しない。(ウィルスなどが添付されている場合がある。)
  • メールの中のリンクをクリックするのは危険。(有名企業名を偽って怪しいサイトに誘導される可能性)

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー